Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

BigDecimal nextProbablePrime(). HashMap initial capacity  RSS feed

 
Chris Brat
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

Where can I find information about the performance of the
nextProbablePrime() method in the java.math.BigInteger class? The
relates to the initial capacity of a HashMap.

The HashMap that can hold data of at least size X and at most Y,
and I want to set the initial capacity to the next possible prime
between X and Y.

By the way Y = X * 2.

At the moment I am setting the capacity to X but I've read that
HashMaps perform better if the initial capacity is a prime number - I
want to test this.

Will setting the initial capacity to the value returned by nextProbablyPrime() - starting from position X - have a significant improvement or is it going to waste memory?

Thanks,
Chris
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you investigate the source code for HashMap, you will find that internally it always uses a capacity which is a power of two. Whatever capacity you request, the code will find the smallest power of two which is >= the number you requested, and use that instead:

So there's really no point to trying to find a prime capacity; it won't be used.
 
Chris Brat
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

Thanks for the reply.

Is that true for all versions?

C
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No. The power-of-two HashMap implementation showed up in JDK 1.4 and was refined a bit in JDK 1.5/5. Seems to still be used in JDK 6. It's not guaranteed to be there in the future. But unless you're targeting a specific JDK which is known to allow precise setting of the capacity, I wouldn't bother trying to optimize this.

If you were using a JDK for which prime capacities were optimal, I think it might make sense to simply precalculate an array of prime sizes to choose from. You could never have more than Integer.MAX_INTEGER capacity anyway, right? A list of thirty or so prime numbers ought to do the trick, with each one roughly double the size of the previous one. So rather than call BigInteger.nextProbablePrime(), you'd just look up the next size in your list. Ought to be much quicker, I'd think.
 
Chris Brat
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Jim.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If a HashMap needs to hold X objects, doesn't the capacity need to be set to at least X / loadfactor?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes. Well, "need" may be arguable in some contexts, but (a) it's a good idea since performace will probably decrease otherwise, and (b) it's sorta required by the API for HashMap. Which is to say that HashMap will take care of this for us anyway, if we are indeed using a plain vanilla HashMap from the JDK.. But I understood that the question we were addressing was, is it worthwhile to pre-emptively set the capacity? (To something greater than the minimum allowed by the load factor.) And if we do so, is it worthwhile to set it to a prime number? My answer being no, unless we're talking about some particular hashtable implementation other than the ones Sun privides in JDK 1.4+.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!