Faster HashMap implementation

[Doug Lea]

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