1
$\begingroup$

If we come to the situation when we have to insert again the original key into the original table, I believe we have found a cycle. Is there a way to prove this?

$\endgroup$
1
$\begingroup$

Yes there is, using algorithms such as Brent's cycle finding algorithm.

However, this is quite expensive and has fairly complicated code. What most implementations do is define some constant cycle/chain length, for example $\log n$ where $n$ is the number of elements in the hash table. If you find a chain (or cycle, but we never investigate whether it's actually a long chain or a cycle) larger than that constant we rehash or increase the hash table size.

But if your goal is merely the prove that you have a cycle, and you do not care about efficiency, the simplest method is to invoke the pigeonhole principle, and just loop $n + 1$ times where $n$ is the number of possible slots in the hash table. If you never find an empty slot you must have a cycle.

$\endgroup$
  • $\begingroup$ Therefore just to be sure, if we insert key A into table 1 of Cuckoo table H at time t1. If we come again to the state of having to insert key A again into table 1 of Cuckoo table H, the position of Cuckoo table H now is the same as it was at time t1. $\endgroup$ – matt May 11 '17 at 10:30
  • $\begingroup$ Actually, returning to the same key is not sufficient to demonstrate a cycle. It's a cycle the third time you see the key. $\endgroup$ – rici Jun 8 '17 at 20:54
0
$\begingroup$

No, a repetition is not sufficient to demonstrate that there is a cycle.

If a key needs to be inserted into a cuckoo hash table, and it cannot be directly inserted (i.e. neither of the two hashes produces an empty nest), then there are two possible elements which could be evicted. The algorithm selects one of these two elements, and proceeds to do the eviction chain. After the first eviction, at each step there is only one possible choice, which is the "other hash". It's possible that this will lead back to the original element leading it to be evicted; this time, the other hash will be selected, so the next steps will not be the same as the cycle.

So a cycle results only if the same element is encountered twice during the eviction.

One useful way of looking at this is to consider the "cuckoo graph": a graph whose nodes are hash table positions (hash values) and whose edges are keys in the hash table. Each edge connects the two possible hash values for the key. A new key can be added provided that the SCC containing the new edge contains at most one cycle.

There is a good explanation of the cuckoo graph with a great animated graphic on Adrian Neumann's page on cuckoo hashing.

In fact, it is quite common for a key to repeat once during the cuckoo algorithm, so the using an unmodified cycle detection algorithm will result in too many rehashes, making the expected insertion time larger than $O(1)$. Instead of using a more complicated cycle detector, the usual approach is to simply cut off the eviction chain after it gets to some length. Since the probability that a chain reaches length $k$ is exponential in $k$, there is a threshold in $O(log N)$ (where $N$ is the size of the table) where the probability of a false positive is sufficiently low that the insertion time is still $O(1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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