Faster HashMap implementation

Doug Lea dl at
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?


More information about the core-libs-dev mailing list