Faster HashMap implementation

Alex Yakovlev alex14n at
Wed Jul 1 12:50:49 UTC 2009


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> 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
> (This retains the openjdk GPL header etc.)

More information about the core-libs-dev mailing list