HashMap - Hybrid approach (original) (raw)

Alex Yakovlev alex14n at gmail.com
Tue Jun 9 21:02:23 UTC 2009

Doug,

To have single-indirect access we need to read key/value objects with the first array read. This is because we cannot store int and object in one array - there's no structures in java.

But this approach have a negative side: we don't have stored hashcode to compare, hence we need to directly call equals method (or have reference equality on keys).

And in the same array we can store other pointers - it will be prefetched into CPU cache. Thus we can store 3 pointers in each hashtable entry: our key, value, and HashEntry structure with collisions. Thus in many situations we'll have "at most a single cache miss".

I've tested this approach on Objects - and it is 20-30% faster in all tests compared to HashMap, but my map still has faster puts.

But when equals is expensive this approach is slower in some tests. And if we read stored hashcode before comparing real keys - it's 2 cache misses on existing mapping read, same as in HashMap (pointer to Entry and Entry contents) and my map (int index, object key).

So this approach is questionable, but can give significant performance boots in some situations (fast equals and reference equality of looked up and stored keys).

And we cannot store collisons in pre-allocated arrays - to read it from the same array with keys/values it needs to be an object. Thus writing speed on my original map will always be faster.

On Mon, Jun 8, 2009 at 8:07 PM, Doug Lea <dl at cs.oswego.edu> wrote:

It strikes me that there might be a bigger win available here by using some hybrid strategy based on IdentityHashMap-like single-indirect (i.e., usually at most a single cache miss) for collision-free accesses but using a variant of your clever packed-indices under collisions. I might try this out someday.

More information about the core-libs-dev mailing list