While spending some time with Bloom Filters, I came across an interesting hashing technique called Cuckoo Hashing. In short, Cuckoo Hashing is a technique for building a hashtable with guaranteed O(1) access time. Very useful. Unfortunately, after poking around the net a bit, I wasn’t able to find any standalone implementations in Java. So I wrote one. If you find it useful, please drop me a line.
Standalone, Java implementation of Cuckoo Hashing
Previous post: Scrum Master
{ 6 comments… read them below or add one }
link http://lmonson.com/blog/?page_id=99 is dead
I’m not sure why the link wasn’t working for you — the page is very much alive and active. Could you try to access it again? If it still isn’t working, give me a shout and I’ll get the pages to you another way….
Link does not work for me either.
I republished the page from WordPress…. I apologize for the inconvenience.
It was a interesting idee to use pseudo-random in stead of the universal hash function. But after running a performance test against my implementation that respects de dessign of the original paper on cuckoo hashing, pseudo-random just did not make it :p.
Your implementation causse also a big memory over-use, becaus it only can rehash when augmenting the table.
Why dont you publish your “better” implementation then Thim – I am sure many people would appreciate it!?