Faster HashMap implementation

Alex Yakovlev alex14n at gmail.com
Sat Jun 6 17:20:33 UTC 2009


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/e3b7a9ce/attachment.html>


More information about the core-libs-dev mailing list