Faster HashMap implementation (original) (raw)

Doug Lea dl at cs.oswego.edu
Sat Jun 13 12:30:55 UTC 2009


Ismael Juma wrote:

Out of curiosity, do you know if any tests have been done with an open addressing scheme similar to Python dictionaries[1] in Java? Near the top, there's a comment explaining how it works and the motivation.

More or less. This is roughly similar to the schemes I mentioned a few days ago, of first direct-addressing. The python approach (as noted in its comments) has most trouble with cases that occur too often in Java to ignore: Poor entropy in low bits (the hashCodes for commonly used Floats and Doubles are especially problematic (Aside: you wouldn't think these would ever be used keys, but they are)) and much-greater-than-expected duplicate codes (mainly the particular value zero). However, these do seem amenable to one of the hybrid approaches I mentioned; I'll try to get a full version together soon.

-Doug



More information about the core-libs-dev mailing list