David Lamb wrote:
Knute Johnson wrote:
Roedy Green wrote:
One of the problems is HashMaps, even in 64-bit JVMs, can still only
hold 1<< 30 elements.
What does that mean?
Maybe hashmaps use only (most of) an int for indices?
Maps don't have indices.
But whether they're limited to 'int' range capacity is very easy to check.
Sure enough, right there in the source for 'HashMap', is
transient Entry[] table;
But all of that is unnecessary effort. I can't believe I bothered, lazy
as I am, given that the Javadocs guarantee that a 'Map' can hold at most
'Integer.MAX_VALUE' elements usefully. (In principle there's no reason a
'TreeMap' couldn't hold more than that, but it would likely become
unuseful at that point. For example, 'putAll(sortedMapOverSized)' might
surprise you.)
<http://docs.oracle.com/javase/7/docs/api/java/util/Map.html#size()>
<http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/HashMap.java>
<http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/TreeMap.java>
P.S., 'TreeMap' has an interesting expression to handle the infamous
overflow bug for tree sorting/searching of which Josh Bloch has
red-facedly written:
int mid = (lo + hi) >>> 1;
P.P.S, Yes, I know that source comes from a pretty old Java version
(b147), but that shouldn't matter here. That site didn't have newer and
it's too well organized to ignore.
= hi = Integer.MAX_VALUE. The ">>>" handles it, since that is an
"unsigned" operation. While lo+hi might be out of range for signed