Faster HashMap implementation (original) (raw)

Rémi Forax forax at univ-mlv.fr
Sat Jul 4 14:47:17 UTC 2009

Doug Lea a écrit :

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.

The other solution is to teach the VM. We can image something that based on type profiling select the optimized Map implementation. I know that there is already something like that in the hotspot sources but I haven't take a look to this part of the VM so I don't know exactly what is done.

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 Rémi

More information about the core-libs-dev mailing list