Linear hashing: Difference between revisions

Revision as of 01:33, 4 February 2010

Revision as of 01:49, 4 February 2010

Line 25:

Thus the hash buckets are expanded round robin, and seem unrelated to where buckets overflow at the time of expansion.

Overflow buckets are used at the sites of bucket overflow, but( thesethe arenormal eventuallybucket reabsorbedhas whena pointer to the roundoverflow robinbucket),

but these are eventually reabsorbed when the round robin comes to the bucket with the overflow bucket,
and the contents of that bucket and the overflow bucket are redistributed by

by the future hash function ( hash(key) mod N * (2^{level'''+1'''} ).
The degenerate case, which is unlikely with a randomized hash function,

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

before being absorbed when that bucket's turn to split comes in the round robin.

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,

and overflow buckets are eventually reabsorbed during a later split, which must eventually happen because splitting occurs round robin.