HashMap - Hybrid approach

[Alex Yakovlev]

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.