Faster HashMap implementation

Rémi Forax forax at
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

More information about the core-libs-dev mailing list