gnu.trove
Class PrimeFinder
public final
class
PrimeFinder
extends Object
Used to keep hash table capacities prime numbers.
Not of interest for users; only for implementors of hashtables.
Choosing prime numbers as hash table capacities is a good idea
to keep them working fast, particularly under hash table
expansions.
However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to
keep capacities prime. This class provides efficient means to
choose prime capacities.
Choosing a prime is O(log 300) (binary search in a list
of 300 ints). Memory requirements: 1 KB static memory.
Version: 1.0, 09/24/99
Author: wolfgang.hoschek@cern.ch
Method Summary |
static int | nextPrime(int desiredCapacity)
Returns a prime number which is >= desiredCapacity
and very close to desiredCapacity (within 11% if
desiredCapacity >= 1000 ).
|
public static final int largestPrime
The largest prime this class can generate; currently equal to
Integer.MAX_VALUE.
private static final int[] primeCapacities
The prime number list consists of 11 chunks.
Each chunk contains prime numbers.
A chunk starts with a prime P1. The next element is a prime
P2. P2 is the smallest prime for which holds: P2 >= 2*P1.
The next element is P3, for which the same holds with respect
to P2, and so on.
Chunks are chosen such that for any desired capacity >= 1000
the list includes a prime number <= desired capacity * 1.11.
Therefore, primes can be retrieved which are quite close to any
desired capacity, which in turn avoids wasting memory.
For example, the list includes
1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
So if you need a prime >= 1040, you will find a prime <=
1040*1.11=1154.
Chunks are chosen such that they are optimized for a hashtable
growthfactor of 2.0;
If your hashtable has such a growthfactor then, after initially
"rounding to a prime" upon hashtable construction, it will
later expand to prime capacities such that there exist no
better primes.
In total these are about 32*10=320 numbers -> 1 KB of static
memory needed.
If you are stingy, then delete every second or fourth chunk.
public static final int nextPrime(int desiredCapacity)
Returns a prime number which is
>= desiredCapacity
and very close to
desiredCapacity
(within 11% if
desiredCapacity >= 1000
).
Parameters: desiredCapacity the capacity desired by the user.
Returns: the capacity which should be used for a hashtable.