3
$\begingroup$

In cuckoo hashing, an insertion failure occurs when there is an infinite loop of displacements. This is detected by a “max iterations” count on the insert function.

When the insert fails, the table is rehashed using two new hash functions. These are selected from a given hash family.

My question - how are these hash functions chosen in practice?

I know there are common black-box hash functions like Murmur, Jenkins32, FNV, etc. I guess they could be used in sequence, but they’re optimised for different things. And rehashing the table can also fail, so such a “sequence” couldn’t be short, otherwise it’d risk another possible infinite loop.

I know that we can create arbitrary hash functions with various bitwise manipulations and arbitrary constant multiplications, but levels of dispersion and avalanching changes depending on the constants picked.

Further, I know that certain hashes allow us to seed their outputs, but my understand is that the choice of hash constants is significant to how well it performs, and the seed determines this.

I feel like I’m missing a fundamental understanding of how we can pick an arbitrary set of “good” hash functions from a given hash family.

$\endgroup$
1

3 Answers 3

1
$\begingroup$

Great question, well, actually a family of questions :)

Let's start with Cyckoo hashing. I checked the Wikipedia article to be sure, and indeed it doesn't mention any families. So, the answer is simple - you just use 2 hash functions, whose avalanche and other properties are good enough for you.

These 2 functions are fixed for each cuckoo hashtable, providing 2 allowed positions for each key. Just think about it - if you use NEW hash functions for each rehashing operation, then you can't find a key with 2 lookups, since this key can end up in ANY position of the hashtable!

$\endgroup$
0
$\begingroup$

If you only have one hash function $h$, you can turn it into two as follows:

$$\begin{align*} h_0(x) &= h(0 || x)\\ h_1(x) &= h(1 || x) \end{align*}$$

where $||$ denotes concatenation. In other words, you prefix the value being hashed with an identifier of which hash function you are using.

$\endgroup$
0
$\begingroup$

So apparently the right answer here is Tabulation hashing which guarantees the behavior for Cuckoo hashing. The linked paper provides the rather technical details and proofs.

$\endgroup$

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.