Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.help > #1812

Re: Overflowing HashMap

Show all headers | View raw

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

Back to comp.lang.java.help | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Overflowing HashMap Roedy Green <see_website@mindprod.com.invalid> - 2012-06-03 07:39 -0700
  Re: Overflowing HashMap Patricia Shanahan <pats@acm.org> - 2012-06-03 08:08 -0700
    Re: Overflowing HashMap Roedy Green <see_website@mindprod.com.invalid> - 2012-06-03 19:59 -0700
      Re: Overflowing HashMap Gene Wirchenko <genew@ocis.net> - 2012-06-04 10:25 -0700
  Re: Overflowing HashMap Knute Johnson <nospam@knutejohnson.com> - 2012-06-03 08:40 -0700
    Re: Overflowing HashMap David Lamb <dalamb@cs.queensu.ca> - 2012-06-03 12:55 -0400
      Re: Overflowing HashMap Lew <noone@lewscanon.com> - 2012-06-03 12:06 -0700
        Re: Overflowing HashMap Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-06-03 13:30 -0700
          Re: Overflowing HashMap Lew <noone@lewscanon.com> - 2012-06-03 13:52 -0700
    Re: Overflowing HashMap Roedy Green <see_website@mindprod.com.invalid> - 2012-06-03 20:51 -0700
      Re: Overflowing HashMap Patricia Shanahan <pats@acm.org> - 2012-06-03 20:59 -0700
        Re: Overflowing HashMap Roedy Green <see_website@mindprod.com.invalid> - 2012-06-03 21:13 -0700

csiph-web