Extendible hashing

Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup. Because of the hierarchical nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes. Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup. Because of the hierarchical nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes. Extendible hashing was described by Ronald Fagin in 1979.Practically all modern filesystems use either extendible hashing or B-trees.In particular, the Global File System, ZFS, and the SpadFS filesystem use extendible hashing. Assume that the hash function h ( k ) {displaystyle h(k)} returns a string of bits. The first i bits of each string will be used as indices to figure out where they will go in the 'directory' (hash table). Additionally, i is the smallest number such that the index of every item in the table is unique.