| 4.2.1 Extendible hashing
Traditional hash methods are burdened with 2 disadvantages:
-
Sequential processing of a file according to the natural order on the keys is not supported.
-
They are not extendible.
Hash table size is pre-determined
Hash table size heavily relies on hash function
Overestimation of the number of records results in wasted space.
Underestimation of the number of records results in rehashing
Extendible hashing method allows hashing to adapt to dynamic files. Hash tables are naturally balanced. By extending the hash address space from the directory address space, hash tables can be made extendible.
| 