Cuckoo Hash – Part 2
Small update, the recursion was killing me, so I introduced some attempts to control how deeply the code recurses. My approach was basically to introduce a depth count, and if the depth count reaches 0, I force a storage growth on the next rehash, thus reducing the number of collisions by increasing the storage size.
This approach is working pretty well, especially if the size of the storage is set to a larger size to start with. The insertions and hashing and lookups are fast, it’s the rehashing and collisions that cause lots of problems.
Cuckoo Hash Part 2 – Second ‘version’ of my cuckoo hash implementation, including the changes above. It now uses a list of 499 commonly used english words, and inserts 6 permutations of the list (pattern: “word-i“, where i is 1-6), for a total insertion count of 2994.
This entry was posted on Wednesday, May 13th, 2009 at 2:26 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.
