Cuckoo Hash
From Wikipedia:
Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table
Very basically, a Cuckoo hash is a table, where the position of an element can be one of two places. On insertion, if there is another element (call it ‘y’) in the candidate spot, it is replaced by the item you are inserting. Then you re-add the ‘y’ element to the hash, using the second hash method. Doing this could cause another element (call it ‘z’) to be displaced, in which case the cycle repeats until all elements are in their new spots.
To look up if an element is in the table, you need to check both possible spots.
You can run into a problem with cycles when inserting values if, for example, h1(x) = h2(y) and h2(x) = h1(y), but you can limit the number of re-insertions to avoid this. If you reach this limit, you can change your hashing methods and re-insert everything again. This problem happens even more frequently if the load factor on your table is too high, so you can put checks in place to increase the size of the table if you detect that the load is getting high. In my example, I set the top table load factor to 60%, at which point I double the size of the table and re-insert the elements.
The main problem I’m running into is that the insert method can call the rehash method if it loops too many times trying to place everything…but rehash calls insert to rebuild the table with new hashing methods. This seems to lead to deeply recursive problems, even with a load set to 50%. I’m not sure how to fix this right now, but I’ll keep working at it and take any suggestions. One method might be to find better hashing algorithms, but I thought the one I was using was descent.
Anyway, since I’m still learning about it, here’s a few links to read:
- Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006. (PDF)
- Some String hashing algorithms
- Cuckoo Hash Attempt 1 – My first attempt at implementing a Cuckoo Hash in Ruby
This entry was posted on Tuesday, May 12th, 2009 at 12:44 pm and is filed under Data and Algorithms, Learning, Programming Problems. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
