Cuckoo hashing is not so new method of implementing hash tables. It has some very nice properties providing the load factor is not too high. Since objects are by reference, the load factor of the array is not a memory issue directly. As such its well suited to java.
In particular is has worst case O(1) performance as opposed to O(n) for chaining and other hash table implementations. Anyway i have been asked to make my updated versions available (I have already made previous versions available). This has been used in production code for some time now. So it should be pretty stable.
Its also always faster than a HashMap for all my test cases.
However comments are for wimps and communists
I do break the collections contract also. All methods that return a collection, are not backed by the original collection. That is they are copies.
This is no longer true. They now conform completely to the Map contract.
the attachment has all the source for the package…and perhaps a little extra just to make sure that I didn’t miss anything. This is used in this project: http://www.mabs.at/ewing/msms/index.shtml
Note that for these classes you can choose between BSD, Apache or LGPL with classpath exception for a license.
Comments and suggestions are always welcome. Note i lurk in #lwjgl on IRC a lot too.
Ok so I found out that some of the hashing code was pretty brain dead. This is now fixed. Also added is a junit test for almost everything in cuckoo.*. Not that i found any bugs other than poor performance from bad hashing.
For some reason the attachment is not working. I a, re-attaching. If that does not work, try this:
Well i fixed the brain dead hashing with brain dead bugs. BIG bugs that totally ruined all performance. Its now fixed. Sorry. Attachment now also fixed properly.
Just synced the comments with the code. :persecutioncomplex: