What is extendible hashing What is extendible hashingSolutio

Solution

Extendible hashing is a special hashing system in which a bit string is used as hash. hash function returns a bit string and the leftmost bit or bits are used to decides where the key will be in the hash table.

For example

let h(k1) = 10101, h(k2)= 01101

For k1 the the leftmost bit is 1 and for k2 its 0 so k1 will go to bucket 1 and k2 to bucket 0.

Now suppose we have another key k3 as h(k3)= 10110, here all three keys cannot be distinguished by 1 bit, so two bits will be used as

for k1, k2 and k3 leftmost bits are 10 , 01 and 11 resp.

The number of leftmost bits to be used is the number which can uniquely represent every item in the table.