0

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?

shiv shah
  • 77
  • 8
  • Possible duplicate of [Advantages of Binary Search Trees over Hash Tables](https://stackoverflow.com/questions/4128546/advantages-of-binary-search-trees-over-hash-tables) – President James K. Polk Nov 08 '18 at 00:29
  • Are you asking why tree maps are more common than hash maps? If so, I'd say that's a false premise - hash maps are easily more commonly used in most languages / library ecosystems. Or are you asking why other resolution strategies are more common for hash maps than Cuckoo Hashing? If so, the "Practice" section of the Wikipedia article on Cuckoo Hashing might give one reason. – sepp2k Nov 08 '18 at 00:32

1 Answers1

1

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87