Faster HashMap implementation (original) (raw)

Doug Lea dl at cs.oswego.edu
Mon Jun 8 16:34:22 UTC 2009

Florian Weimer wrote:

Or don't use the hash structure at all and just do a sequential search. Then the index array isn't needed at all.

It is possible to use a look-aside strategy for tiny HashMaps. I think one of the Apache commons maps does this. But the idea of using open-address tables to cover this case more nicely doesn't work out very well. While open-addressing is used in IdentityHashMap (and in a very specialized form in ThreadLocal), you cannot live with linear-probed versions otherwise: Many user-defined hashCodes (and some JDK-defined ones too!) are not very good. While we can use bit-spreading corrections to help with this, we cannot do anything about the fact that duplicated hash codes (that is, two different objects with the same hash code) are vastly more common than you'd hope. This causes big pile-ups under linear probing but is only a localized problem with binned maps like current HashMap. Which is one reason to consider the hybrid scheme I mentioned.

-Doug

More information about the core-libs-dev mailing list