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

)

{\displaystyle O(2+(m-1)/n)}

, where

m

{\displaystyle m}

is the number of keys and

n

{\displaystyle n}

is the size of the array. The most collisions is

log

2

⁡

ln

⁡

n

+

θ

(

m

/

n

)

{\displaystyle \log _{2}\ln n+\theta (m/n)}

with high probability."

How it works

2-choice hashing utilizes two hash functions h1(x) and h2(x). The two hash functions should be independent and have no correlation to each other. Having two hash functions allows any key x to have up to two potential locations to be stored based on the values of the respective outputs, h1(x) and h2(x). Although there are two hash functions, there is only one table; both hash functions map to locations on that table.

Implementation

The most important functions of the hashing implementation in this case are insertion and search.

Insertion: When inserting the values of both hash functions are computed for the to-be-inserted object.