IdentityHashMap & natStackTrace

Ranjit Mathew
Fri Nov 26 06:53:00 GMT 2004

Rutger Ovidius wrote:

> public Object put(Object key, Object value)
>        ...
>        if (size > threshold) {
>           table = new Object[old.length << 1 + 2];
> These two issues seem to be a burden on the heap.  I can drop ~400k of
> ram by doubling the size of this instead of using "old.length << 1 +
> 2" during each table expansion.

Good catch!

As Chris points, due to operator precedence weirdness this
becomes a left shift by 3 or multiplication by 2^3, in line
with what you observed.

This was introduced almost two years ago in a merge from

Relevant change:

  // This isn't necessarily prime, but it is an odd number of key/value
  // slots, which has a higher probability of fewer collisions.
- table = new Object[old.length * 2 + 2];
+ table = new Object[old.length << 1 + 2];

I think this is surely a bug - the comment above this line
didn't hold earlier and doesn't hold now - we still have
an even number of slots.  (I don't have my Knuth handy right
now, but surely there must be a simple method of calculating
the nearest prime to (old.length * 2)...)

You should either file a bug or submit a patch fixing
this issue.

> This implementation fills the array with emptyslot (Arrays.fill),
> which uses a whole bunch of memory. Can't a guard be used on lookups
> instead of actually filling this in (checking equality with
> emptyslot)?

Can you elaborate on that?  Note that a NULL can't be used and
"emptyslot" is a reference to the same sentinel Object.


Ranjit Mathew          Email: rmathew AT gmail DOT com

Bangalore, INDIA.      Web:

More information about the Java mailing list