5

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?

1 Answer 1

Reset to default
3

Lookup would implemented in a procedural language as

lookup(key){

    int h1 = hash1(key);
    if(table[h1%table.length].key == key){
        return table[h1%table.length].value;

    int h2 = hash2(key);
    if(table[h2%table.length].key == key){
        return table[h2%table.length].value;

    return null;

}

No loops, no complexity, nothing that would make lookup take more than a constant worst case time.

The magic that makes this work is in the insert and rehash logic and requires that no 3 elements map to the same pair of hashes or more generally for every set of n elements there must be at least n unique hashes.

Some implementations would require that the hash function is tunable with a parameter so it can select 2 arbitrary parameters for the hash. Then when the above precondition is violated then it'll pick 2 new parameters and rehash.

5
  • Yes, but in the example where there are 3 or more items that always hash to the same index (which is always a possibility, however unlikely, for large enough data, and which is simulated by the code I linked by creating multiple objects that provide the same predefined equal hash code but which do not test as equal), how is this handled?
    – Jules
    Commented Apr 1, 2016 at 12:49
  • For example, say we had a rather bad implementation of strings where the tunable hash function was hash(salt) { return salt + c[0] +c[1] + c[2]; }, and I insert items with keys "hello", "help" and "hell". Then, no matter how many times the table is rehashed, those three will always collide, and there will only be two spaces available to store them. How is this resolved?
    – Jules
    Commented Apr 1, 2016 at 12:59
  • 1
    @Jules it can't. The best way to guarantee the diversity is to let the salt affect the hash in a non linear way like hash(salt) { return salt*(c[0] +salt*(c[1] + *salt*c[2])); }
    – ratchet freak
    Commented Apr 1, 2016 at 13:04
  • That's what I thought. But the implementation I'm testing seems to cope with it somehow, and I can't figure out how. The time taken for performing 1000 lookups is to within a handful of percent identical for 1, 10, or 50 items added to the table, all of which collide for all possible hash functions. I think the memory usage is growing exponentially (it's certainly increasing quite quickly), which is probably part of the trick, but I have no idea what it's doing with the extra memory that helps.
    – Jules
    Commented Apr 1, 2016 at 13:09
  • @Jules You need to be able to monitor the size of the arrays within the hash table to see what is going on in terms of memory use. Cuckoo hashing does not simply try twice to insert and quit. The O(1) cost is the amortized cost. It is called "cuckoo" because elements are "bounced" from one hash table to another, until it stabilizes. If a cycle is detected, or you run out of space, the whole thing must be rehashed.
    – Frank Hileman
    Commented Apr 1, 2016 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.