Faster HashMap implementation

[Joe Kearney]

Alex,
Might I suggest you look at the test framework in Google
Collections<http://code.google.com/p/google-collections/>?
Extremely good coverage and only a couple of lines to set up.
Tests for maps in java.util:
http://www.google.com/codesearch/p?hl=en#YXcrkXezIpQ/trunk/testfw/com/google/common/collect/testing/TestsForMapsInJavaUtil.java
<http://www.google.com/codesearch/p?hl=en#YXcrkXezIpQ/trunk/testfw/com/google/common/collect/testing/TestsForMapsInJavaUtil.java>See
for example line 118.

Thanks,
Joe

2009/6/6 Alex Yakovlev <alex14n at gmail.com>

> 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 cs.oswego.edu> 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: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090606/b00c941f/attachment.html>