Jump to content

User:JessRyanA/2-left hashing

From Wikipedia, the free encyclopedia

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).[1]

The maximum number of collisions is 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

[edit]

References

[edit]

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

  1. ^ Public Domain This article incorporates public domain material from Paul E. Black. "2-left hashing". Dictionary of Algorithms and Data Structures. NIST.