4 ms·
To 1, they answer this in the paper; one knows it because The xor operation in Eq. (1) ensures an important property: h1(x) can also be calculated from h2(x) a
by thenewwazoo 10y ago
To 1, they answer this in the paper; one knows it because
The xor operation in Eq. (1) ensures an important property: h1(x) can also be calculated from h2(x) and the fingerprint using the same formula. In other words, to displace a key originally in bucket i (no matter if i is h1(x) or h2(x)), we directly calculate its alternate bucket j from the current bucket index i and the fingerprint stored in this bucket by
j = i ⊕ hash(fingerprint).
- blauditore 10y agoThanks. That's quite nice, but also reduces available hashing functions to pairs with that property. But I guess that's not really a problem.
- dgacmu 10y agoIf I'm understanding your comment right, you mean that the underlying cuckoo hash table can only use 2 buckets per item, right? We actually generalized this, but only in Bin's thesis: https://www.cs.cmu.edu/~binfan/thesis/thesis_ss.pdf https://www.cs.cmu.edu/~binfan/thesis/thesis_ss.pdf See section 4.5. It was a bit more computationally expensive, so we didn't push forward with it in our implementation, as "2,4" cuckoo hash tables (2 hash functions to identify buckets, 4 associative elements) performed so well already.