Faster HashMap implementation (original) (raw)

Alex Yakovlev alex14n at gmail.com
Fri Jun 5 05:05:56 UTC 2009

Doug,

On Thu, Jun 4, 2009 at 4:32 PM, Doug Lea <dl at cs.oswego.edu> wrote:

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.

Well, it can be done by adding another index array, I've commited it to http://github.com/alex14n/CompactHashMap have a look. It is not tested, sorry, so there might be some bugs, code is not optimized and even basic HashMap performance can degrade because of couple of extra virtual calls.

Also, now it has to create a new Entry on each removeEldestEntry check - maybe it could be cached, but I am not sure if my approach would be better than just using original version.

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.)

Now I just force load factor to 1 if argument is greater than 1.

I've also added some modCount/ConcurrentModificationException checks for better compatibility with original version, again I am not sure if it is enough.

Also, the time/space impact of per-node Entry allocation in

entrySet iterators will be noticeable to some applications. This is likely not a big concern though.

Hope so.

Across such issues, it would take some further work to

make a strong case for actually replacing HashMap.

I hope my recent modifications will help.

If we had reified generics, we might be able to do something

about this but otherwise there seems to be no good way to adapt internal algorithms to key types. Similarly for values.

Scala language announce type specializations that will help this greatly: http://lamp.epfl.ch/~dragos/files/scala-spec.pdf

For java there already are good implementations like fastutil: http://fastutil.dsi.unimi.it/

Alex -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090605/b363c96f/attachment.html>

More information about the core-libs-dev mailing list