Faster HashMap implementation

[Alex Yakovlev]

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>