Faster HashMap implementation (original) (raw)

Doug Lea dl at cs.oswego.edu
Sat Jul 4 07:00:39 UTC 2009

somehow 10 days for you is the same as 2 days for the rest of us. :)

(Well, I was unexpectedly stranded at JFK for 20 hrs, but now really am in sporadic e-mail mode for 9 days.)

More seriously, it would be great to have a HashMap that takes less memory and performs as well or better so I am following this with interest. If things work out, I'd be interested in borrowing the ideas for Scala's mutable HashMap (an additional thing to take into account there is the ongoing specialization work).

Specialization should help common cases. the three of : Strings, Integer/Long, and identity-based (no equals/hashCode override) not only seem to together account for up to 80% of usages, but all three would allow more space-conserving and faster solutions in part because there is no reason to store hash codes for them.

Maybe it is worth introducing java.util.CheckedHashMap (as in my previous note) as a relatively simple way for people to get this better performance in Java at the expense of having to consciously change existing constructions of HashMap. This would at least avoid the need for people to use non-JDK alterantives in these cases. On the other hand, the very low relative occurrence of programs using IdentiyHashMap in the many cases it applies suggests that people won't often enough use these when they should?

-Doug

More information about the core-libs-dev mailing list