Extendible Hashing

Extendible Hashing uses a hash function that computes the binary representation of an arbitrary key and an array, serving as a directory, where each entry maps to exactly one bucket. The computed hash maps to exactly one entry in the array, whereby the bucket is determined.

The hash function also uses a bitmask to blend out unnecessary bits. This however depends entirely on the size of the array, which is defined as 2d, with d being the global depth. So the hash consists only of d bits. This implementation uses the least-significant bits.

If, however, a bucket reaches the limit of its capacity b, then the bucket is split and its values are rehashed. Since every entry in the array can only reference one bucket at any given time, it also becomes necessary to expand the array from time to time, which is accomplished by incrementing d by 1.

In order to split and expand in a controlled manner another variable k, the local depth, is saved in every bucket, that helps to keep track of the entries referencing the bucket. 2d-k gives the number of entries mapping to this block.

In case of a bucket overflow, these are core steps to resolve the issue:

If k < d : split the bucket

If k = d : double the array size

Legend

b: bucket size d: global depth k: local depth