Hashtable with two tables (Cuckoo Hashing)
-
Hello, I havent found much information about cuckoo hashing apart from the official papers.. I have some questions about it, 1. What would be two good random functions for this type of hashing? 2. What about the rehashing algorithm? Because i'm having troubles with the official specification of it.. which kinda loops between inserting and rehashing infinitely
-
Hello, I havent found much information about cuckoo hashing apart from the official papers.. I have some questions about it, 1. What would be two good random functions for this type of hashing? 2. What about the rehashing algorithm? Because i'm having troubles with the official specification of it.. which kinda loops between inserting and rehashing infinitely
I have no experience with cuckoo hashing, so I can't help you there. If you need to manage hash collisions and have problems with cuckoo or are worried about infinite loops and rehashing, you may consider using chaining[^]. While it's not as performing as cuckoo, it's very simple to implement, scalable, and works like a charm. :)
2+2=5 for very large amounts of 2 (always loved that one hehe!)
-
Hello, I havent found much information about cuckoo hashing apart from the official papers.. I have some questions about it, 1. What would be two good random functions for this type of hashing? 2. What about the rehashing algorithm? Because i'm having troubles with the official specification of it.. which kinda loops between inserting and rehashing infinitely
How about using a modified Jenkins One a at a Time[^] Instead of starting the hash from zero, I tried getting the first hash using root 0 and the second using the first as a root. The two resulting hash's are pretty well distributed.
Panic, Chaos, Destruction. My work here is done.
-
Hello, I havent found much information about cuckoo hashing apart from the official papers.. I have some questions about it, 1. What would be two good random functions for this type of hashing? 2. What about the rehashing algorithm? Because i'm having troubles with the official specification of it.. which kinda loops between inserting and rehashing infinitely
I'd never heard of cuckoo hashing before; it seems like an interesting concept, though I would be paranoid about worst-case behavior if hash functions are poorly chosen (most hash table algorithms will run in bounded time even with the worst possible hash functions; the worst-case time to add an item to a cuckoo-hash table would seem to be unbounded). At the expense of some extra book-keeping (probably O(1) in typical cases, but bounded even in the worst case), I would think one could implement a variation of cuckoo hash in which every item was stored at location (H1+k*H2) mod N (as with double hashing), but which provided that if the cell targeted by an item with a certain 'k' contained an item with a sufficiently smaller 'k', the latter item would be displaced. That would tend to balance out the number of search steps required to find any particular item. Provided that H2 is always relatively prime to N, the algorithm should always terminate. If there are never any deletions, the extra book-keeping would be minimal; deletions could complicate things, though.