Why we don't use Cuckoo Hashing

My question is from what i understand Cuckoo Hashing takes usually 0(1) time for insert delete and find. The worst case scenario is O(1) (amortized). My question is why isn't this algorithm used more often. Why would we use a different algorithm to look things up inserting or deleting rather then something like Cuckoo Hashing?

1 answer

  • answered 2018-11-08 01:48 Matt Timmermans

    Cuckoo hashing requires an unbounded number of different independent hash functions, which is not compatible with the way we usually implement a generic hash table, since that only requires one hash function to be specified.

    If you are writing a hash table implementation for a specific data type, then the hash function(s) can be built into the table implementation and cuckoo hashing may be reasonable.

    Even in that case, however, you probably won't be able to prove that you can support any set of elements, since your hash functions won't really be random and independent, so a cuckoo hashing implementation has O(1) expected time for insert, but in a real implementation there may be a case or two in which it will go into an infinite loop or fail.

    You could engineer a fallback for cases like that, but then is cuckoo hashing worth the extra complexity?

    Cuckoo hashing may be a good alternative to perfect hashing, when the hash table is computed in advance... but if you're doing it in advance then insertions don't usually have to be that fast so you can use perfect hashing instead.