Method for Extendible Hashing
Original Publication Date: 1978-Jul-01
Included in the Prior Art Database: 2005-Feb-21
This article describes a method for expanding the content of hash tables dynamically as the size of the underlying data base increases. The method starts with the use of a key (or unique identifier) K, either of fixed or variable length. In this method, it is necessary to locate the data associated with K for the purpose of insertion, deletion, or update. Let there exist a fixed hash f, selected from a class of "universal hash functions." There is defined a pseudokey K' associated with K by the expression K'=f(K). The function f should be selected such that the pseudokeys are of fixed length and distributed nearly uniformly. As an example, one half of the pseudokeys have a final bit of zero, while one quarter of the pseudokeys end with bits 01, etc.