How to create empty buckets in extendible hashing

Question

I know how to do extendible hashing on paper, but I don't know how it's possible for empty buckets to be created.

What would cause empty buckets to be created in extendible hashing? Can you show a simple example?

Answer 1

Assume the hash function h(x) is h(x) = x and each bucket can hold two things in it.

I will also use the least significant bits of the hash code as in index into the hash directory, as opposed to the most significant bits.

Basically, to get an empty bucket, we want to induce a doubling of the hash table by trying to place something into a bucket that has no space but we want that doubling to fail.

So, let's start inserting stuff.

First, insert 0. This should go in the first bucket, since h(0) = 0 and 0 % 2 = 0.

Then, insert 4. This should also go in the first bucket, since h(4) = 4 and 4 % 2 = 0.

Now, inserting 8 fails since the bucket can only hold two things, so the table must be doubled in size. Therefore, the global hash level increases from 1 to 2. Other changes include a new third bucket and the fourth hash index pointing to the second bucket.

Unfortunately, since the rehashing process takes h(x) % 4 and all of our numbers are (deliberately) multiples of 4, the first bucket remains too full and the third bucket is empty. This resolves itself with yet another doubling of the hash table.