Linear hashing: Difference between revisions

Revision as of 01:24, 4 February 2010

Revision as of 01:29, 4 February 2010

Line 30:

with a randomized hash function, is that enough entries are hashed to the same bucket so that there is enough entries

to overflow more than one overflow bucket ( assuming overflow bucket size = normal bucket size), before being absorbed by

a delayed round robin split.

The point of the algorithm seems to be that overflow is preempted by gradually increasing the number of available buckets,

Line 40:

Therefore the new hash function will only hash to buckets created by previous splits.

and having the hash function conditional on the split variable, so any hash value greater than '''split''' is still used ( where hash is h(k) mod N * 2^level , as above ), but

any hash value <= split will be recalculated as h(k) mod N * 2^{level '''+ 1'''}

There is some flexibility in choosing how often the expansion operations are performed.

One obvious choice is to perform the expansion operation each time no more slots are available at the target slot ___location. Another choice