Faster HashMap implementation

[Alex Yakovlev]

Doug,

Checking key reference equality before hashcode looks like a big win.

Have you considered using balancing tree instead of bit trie?
This could decrease look depth from number of hash bits to log2(tree size).

Also, there could be a sence in using adjacent table cell for key/value if it's
not used. Maybe also without a hashcode check for less cache misses.
In practice this gives ~4-5% performance for get(). In theory, when
70% of gets are resolved at first try, 23% on second, assuming that
adjacent cell is empty in 50% cases, and in best case (referential equality)
we'll have 1 cache miss instead of 3, thus .23*.5*(2/3) = 7.67%
in worst case (2 cache misses instead of 4 with hashcode check) +5.75%

On Wed, Jul 1, 2009 at 2:09 AM, Doug Lea<dl at cs.oswego.edu> wrote:
>
> Inspired by the combination of Alex's efforts and ongoing
> work on concurrent caches, I put together a version
> of HashMap (called HashMapV2 for now) with a snapshot at
>  http://gee.cs.oswego.edu/dl/wwwtmp/HashMapV2.java
> (This retains the openjdk GPL header etc.)