Most hash table implementations guarantee O(1) average case but O(n) maximum case for lookup (where 'n' is the number of keys in the table). But Cuckoo Hashing is described as O(1) maximum. Apparently it achieves this by using two hash functions, and if it gets a collision with one, it uses the alternative one. If it gets collisions with both, it first tries to shuffle items around to make space, but if there are three keys that all hash to the same value with both hash functions, this will fail.
As I understand it, the next approach is to change the hash functions.
In a type-generic implementation (e.g. this Haskell implementation) the obvious way to do this is to provide an interface that allows a family of hash functions to provided, in this case the
Hashable typeclass, which contains a function
hashWithSalt :: Int -> a -> Int (where
a is the type being hashed). However, this only provides a single
Int parameter and a single
Int output, which is 32-bits * 2 = 64 bits of possible hash and salt, therefore with any values containing more data than 65 bits there will still be potential items which always collide. In a theoretical worst case (e.g. as generated using this code which certainly seems to show O(1) lookup times at least for n <= 50 -- above that, insertion time becomes problematically large for some reason) there could be 'n' items that all collide with all potential hashing functions.
How, therefore, is it possible that the maximum complexity of lookup is O(1)? Is there some implementation trick I haven't grasped that avoids this problem?