Visualiation of Cuckoo Hashing

The Cuckoo Hashing scheme consists of two tables. Every key has exactly two possible locations: one in the first and one in the second table, and it has to be stored in one of these two locations. When inserting a key, it can happen that other keys already reside in the two possible locations for a key. In this case, the key that resides in the first table cell is evicted and moved to its second possible residence. This could kick out another key and so on, until a free table cell is found, or we run into a situation where the keys cannot be stored according to the cuckoo hashing rules. (Can you think of an example with 3 keys that cannot be stored?)

The visualization on the right shows the insertion of six keys a,b,c,d,e,f. Each key has a color and when the key is inserted, we add a line connecting a table cell in the first table with a cell in the second table, which shows the two possible locations for the key. You can start the insertion of a key by pressing a mouse button.

The examples shows the essential three different cases that may happen when we insert a key:

1. The insertion procedure inserts the key in the first table and may kick out a key there, but a key is never kicked out twice.
2. The insertion procedure inserts a key and there exists a key that is kicked out for the second time (key e in our example). Then the inserted key is moved to the second table. This succeeds if there does not exist another key that is place into a previously visited cell.
3. The situation in 2. occurs, but there exists a key that visits a previously visited cell again after the inserted key is moved to the second table. In this case the insertion yields a loop, because there are not enough table cells to store the keys (That happens when key f is inserted in the example).

Interact with the keys!

Martin Aumüller, 2009.