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