Faster HashMap implementation

[Doug Lea]

Sorry for the delay; I've been side-tracked exploring
concurrent trie/hash algorithms

But I did want to point out a problem shared with
all purely table-based approaches, including yours.
Assuming power of 2 capacities, you can only hold up to 1 << 29
entries, because max power of 2 array length is 1 << 30.
This holds even in -d64 mode.
Current HashMap works up through size == Integer.MAX_VALUE.
(And even "works" if size overflows so long as you don't
call size().) I know that there are some extremely
large hash maps out there. Maybe some would newly
encounters failures.

There are ways out of this, using some sort
of dynamic structures for overflow.

You might think that it is unfair that IdentityHashMap
has always had a similar limitation and gotten away with it,
but the ground rules here are that you cannot cause programs
that used to work, to fail in JDK updates. And worse,
we must conservatively assume that any legitimate usage
that is possible actually exists.


-Doug