Re: Overflowing HashMap
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.
--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg