I was reading this very good summary of Cuckoo hashing.

It includes a result (page 5) that:

A stash of constant sizes reduces the probability of any failure to fall from $\Theta(1/n)$ to $\Theta(1/n^{s+1})$ for the case of $d= 2$ choices

It references the paper KMW08. But KMW08 only has the result (Theorem 2.1) that:

For every constant integer $s \geq 1$, for a sufficiently large constant $\alpha$, the size $S$ of the stash after all items have been inserted satisfies $Pr(S \geq s) =O(n^{-s})$.

Note that the $s$ in the different theorems is slightly different, in the first if the stash is of size $s$, it is not a failure, in the second, if the stash is of size $s$ it is a failure. This is why the first has $s+1$ and the second has $s$.

The difference between the two is then that the first uses theta-notation, whereas the second uses big-O notation. So my questions:

  • Do we know that the failure probability is $\Omega(n^{-(s+1)})$?
  • If so, do we know the constants in the $\Theta(n^{-(s+1)})$ expression?

And if so, which papers presented these results?


Your Answer

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

Browse other questions tagged or ask your own question.