Q: How does cuckoo hashing guarantee O(1) lookups in presence of persistent hash collisions 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?

A: 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.
