User:JessRyanA/2-left hashing

{{Userspace draft|source=ArticleWizard|date=August 2013}}

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).{{DADS|2-left hashing|twoLeftHashing}}

The maximum number of collisions is $.69...\; \backslash log\_2\; \backslash 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.