2-Left Hashing
2-left hashing is (just as 2-Choice Hashing) more of a variation that can be applied to other hash table implementations, rather than a full implementation itself.
It's commonly used with separate chaining, but can technically be used with any resolution strategy.
Representation
In 2-left hashing two hash tables are used (two hash functions and two arrays).
Example: State of a hash table using 2-left hashing and separate chaining.
Insertion
The key is inserted in the left hash table if the bucket it hashes to in the left table has a lower or equal load than the bucket it hashes to in the right hash table.
Example: Insertions using 2-Left Hashing.
Lookup
Lookup is performed in both tables. This can be done in parallel.
Removal
Similar to how lookup works.
D-Left Hashing
The approach can be generalized to an arbitrary number of hash tables. This is called d-left hashing.
The performance gained when going from two tables to three (and beyond) is however far smaller than when going from one to two.
Comparison to 2-Choice Hashing
2-Choice Hashing also uses two hash functions and inserts the key in the bucket with least load. Only a single table is used however, and ties are resolved randomly.
Why would splitting the table up in two, and resolve ties assymetrically to the left be any better?
For the maximum load to increase, two buckets with the same load must be chosen. If ties are resolved asymmetrically to the left, the left part will always be slightly ahead of the right part, and ties will be less frequent.