Faster HashMap implementation

Joe Kearney Joe.Kearney at
Sat Jun 6 17:47:16 UTC 2009

Might I suggest you look at the test framework in Google
Extremely good coverage and only a couple of lines to set up.
Tests for maps in java.util:
for example line 118.


2009/6/6 Alex Yakovlev <alex14n at>

> Doug,
> I've finished HashMap, HashSet, LinkedHashMap, and LinkedHashSet
> porting to my approach. I run several tests I've found in
> jdk/test/java/util/*
> that are directly related to these classes, not sure I've found all of
> them.
> I have not compiled the whole jdk classes - only these 4 (removed 'Fast'
> prefix from names and put them into java.util package) and replaced
> those in my rt.jar of binary jdk7b59. Applications like Eclipse and Tomcat
> are running fine.
> Are there any thorough regression/compliance tests for java collections?
> On Thu, Jun 4, 2009 at 4:32 PM, Doug Lea <dl at> wrote:
>> Alex Yakovlev wrote:
>>> While playing with scala programming language I've come toa HashMap
>>> implementation
>>> that appears to be faster than current java.util.HashMap, also with a
>>> lower memory footprint.
>> This is a promising approach. The indirection using the
>> index array makes for a better time/space tradeoff than
>> current HashMap for many usages.
>> There are however a couple of constraints on HashMap
>> that have made it difficult to replace it with
>> overhauled internals, despite a few explorations in
>> doing so.
>> The main one is that LinkedHashMap is declared as a
>> subclass of HashMap. There's not
>> an obvious way to add insertion- or access- ordered links
>> to your version. This still might not be a huge obstacle,
>> since with some care, and some wastage, LinkedHashMap
>> could ignore its superclass implementation and re-establish
>> current approach.
>> Also, the meaning/impact of load-factor parameters differs
>> in your version. It seems possible to reinterpret these internally
>> to provide approximately equivalent statistical properties.
>> (For example a loadFactor argument of 2.0 might translate into
>> internal one of around 0.9.)
>> Across such issues, it would take some further work to
>> make a strong case for actually replacing HashMap.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the core-libs-dev mailing list