2-choice hashing

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 _{2}\ln n+\theta (m/n)$ with high probability.

See also

• 2-left hashing

 This article incorporates public domain material from Paul E. Black. "2-choice hashing". Dictionary of Algorithms and Data Structures. NIST.