Hash Tables with Worst-Case O(1) Access -- Cuckoo Hashing | Lei Jiang Coding

Hash Tables with Worst-Case O(1) Access — Cuckoo Hashing | Lei Jiang Coding

Power of two choices

If N items are randomly tossed into N bins, the size of the largest bin is expected to be Θ(loglogN) a significantly lower number

 Cuckoo Hashing

In cuckoo hashing, suppose  N items and maintain two tables, each more than half empty, two independent hash functions that can assign each item to a position in each table. Based on the randomly chosen hash functions, one item can either position i in table 1 or position j in table 2. Immediately, this implies that a search in a cuckoo hash table requires at most two table accesses, and a remove is trivial, once the item is located (lazy deletion is not needed now!).

The cuckoo hashing algorithm is simple: To insert a new item,x, first make sure it is not already there.use the first hash function, and if the (first) table location is empty, the item can be placed.

The probability that a single insertion would require a new set of hash functions can be made to be O(1/N^2); the new hash functions themselves generate N more insertions to rebuild the table,but even so,this means the rebuilding cost is minimal.

Instead of two tables, we can use a higher number of tables, such as 3 or 4. While this increases the cost of a lookup, it also drastically increases the theoretical space utilization.

Read full article from Hash Tables with Worst-Case O(1) Access — Cuckoo Hashing | Lei Jiang Coding