Home › Multilingual Archive Index › 2-choice hashing

2-choice hashing

2-choice hashing, also known as 2-choice chaining, is a variant of a hash table in which keys are added by hashing with two hash functions. The key is put in the array position with the fewer (colliding) keys. Some collision resolution scheme is needed, unless keys are kept in buckets. The average-case cost of a successful search is O(2 + (m-1)/n), where m is the number of keys and n is the size of the array. The most collisions is log₂lnn + θ(m / n) with high probability.

See also

• 2-left hashing

Paul E. Black, 2-choice hashing at the NIST Dictionary of Algorithms and Data Structures.