I coded a cuckoo hashed hashtable for a class once, and recently had a lecture on cuckoo hashing given to my class by Rasmus Pagh himself (inventor of cuckoo ha

I coded a cuckoo hashed hashtable for a class once, and recently had a lecture on cuckoo hashing given to my class by Rasmus Pagh himself (inventor of cuckoo hashing). Its really surprising actually how complex the probability behind cuckoo hashing really is (and how tied to graph theory/bipartite matchings it is). The amazing part is, not only is access O(1), the expected insertion time whenever there is no rehashing is also O(1) and rehashing occurs infrequently.