Cuckoo Hashing Visualization
Cuckoo hashing is an elegant method for resolving collisions in hash tables. It was invented in 2001 by Rasmus Pagh and Flemming Friche Rodler. It has the rare distinction of being easy to implement and efficient both in theory and practice.
In the basic variant of Cuckoo hashing we use two hash tables T1 and T2 of equal size, and we index them with the hash functions h1, respectively h2. Here are the main operations:
- Search couldn't be easier: an element x can exist in one of two locations: in T1 at position h1(x) or in T2 at position h2(x). We can check both locations in constant time.
- Delete is similarly easy: we look at the two possible locations, and if the element is there, we delete it.
- Insert is a bit trickier: we put x in T1[h1(x)]. If there was some element y stored in that location, y must be evicted (thus the name "cuckoo" hashing). We put y in its other valid location T2[h2(y)]. If that location is occupied by some element z, we have to evict z and insert it in its other valid location T1[h1(z)]. We continue like this until we find an empty place and the process finishes, or until we give up because it starts to take too long (perhaps because we ran into a loop). If the latter happens, we conclude that insert failed, we stop and we rehash everything with new hash functions (increasing the table sizes if the tables are getting too full). It can be shown that insert takes constant time (on average), even if we account for the possible rehashing - assuming that the hash functions are sufficiently good.
For more details and variations on the theme read the original article, or the wikipedia page and references therein.
Here is a visualization of Cuckoo hashing. You can search, insert, or delete arbitrary elements via the text box in the middle.