Faster HashMap implementation (original) (raw)

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

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>

More information about the core-libs-dev mailing list