hash two keys to one index

[Chris Uppal]

Newly allocated objects are usually adjacent in memory regardless of
their type. Depending on the garbage collector, objects with links to
each other may well be copied to nearby locations in the main heap.

[I'm mostly repeating myself, but just to bring some closure to this]

Sure, but hash-tables don't tend to place sequentially-allocated objects in
sequential slots. The GC will probably group the chain-links together, but
probably not the objects refered to by the links. In the end open chaining adds
another layer of indirection, double-hashing adds an extra "bounce" to the
memory access patterns. It's up to the developer to choose (with or without
measurement) a design which appeals; my point is only that considerations of
the /number/ of probes doesn't exhaust the influences on performance.

-- chris

 

[Mark Thornton]

Mark Thornton wrote:

Newly allocated objects are usually adjacent in memory regardless of
their type. Depending on the garbage collector, objects with links to
each other may well be copied to nearby locations in the main heap.

[I'm mostly repeating myself, but just to bring some closure to this]

Sure, but hash-tables don't tend to place sequentially-allocated objects in
sequential slots. The GC will probably group the chain-links together, but
probably not the objects refered to by the links.

Allegedly the train collector is likely to do exactly that depending on
what other links exist and whether the objects are of similar 'age' to
the hash table.

measurement) a design which appeals; my point is only that considerations of
the /number/ of probes doesn't exhaust the influences on performance.

Indeed not. Which is why it is good to have many different
implementations of Map.

Mark Thornton

 

[Mark]

When considering the efficiency of data-structures in the modern world, it's
always worth thinking a bit about cache effects. Both open chaining, and any
form of double hashing, have poor effects on locality-of-reference, with memory
accesses jumping all over the shop rather than sequential.

May not make much difference in Java (which tends to be cache-unfriendly anyway
for objects), but worth thinking about. Especially if you end up considering
on-disk structures (I realise that isn't relevant to your immediate task).

-- chris

What about with LRU associative mapping? Then it doesn't really matter
where it's stored in memory -- although you might only have one useful
value in each cache block rather than the multiple you might get by not
using a sparse array.