2-choice hashing

From Wikipedia, the free encyclopedia

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 2 ln n + θ(m / n)$ with high probability.