## 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:

- 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.
- 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.
- 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.