User:JessRyanA/2-left hashing

2-left hashing is a method of implementing a dictionary that uses two seperate hash functions. Two equally-sized hash tables are created. When adding a key, it is added to the table with the least collisions. If the each table has the same number of collisions for the key, the key is added preferentially to one table (the "left" table).

The maximum number of collisions is $.69...\log _{2}\ln n+O(1)$ with high probability. Using two hash functions exponentially reduces the number of collisions compared to a single hash table, but adding additional hash functions will only reduce it by a constant factor. The lookup time is similar to a single hash table, and the two lookups can be conducted in parallel.

See Also

• 2-choice hashing
• Cuckoo hashing

References

 This article incorporates public domain material from the National Institute of Standards and Technology