• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

BigDecimal nextProbablePrime(). HashMap initial capacity

 
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Thanks for the reply.

Is that true for all versions?

C
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Jim.
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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+.
 
I’m tired of walking, and will rest for a minute and grow some wheels. This is the promise of this tiny ad:
New web page for Paul's Rocket Mass Heaters movies
https://coderanch.com/t/785239/web-page-Paul-Rocket-Mass
reply
    Bookmark Topic Watch Topic
  • New Topic