Package cern.colt.map

Class PrimeFinder

java.lang.Object
cern.colt.map.PrimeFinder

public class PrimeFinder extends Object
Not of interest for users; only for implementors of hashtables. Used to keep hash table capacities prime numbers.

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 int's). Memory requirements: 1 KB static memory.

Version:
1.0, 09/24/99
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    The largest prime this class can generate; currently equal to Integer.MAX_VALUE.
    private static final int[]
    The prime number list consists of 11 chunks.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Makes this class non instantiable, but still let's others inherit from it.
  • Method Summary

    Modifier and Type
    Method
    Description
    protected static void
    main(String[] args)
    Tests correctness.
    static int
    nextPrime(int desiredCapacity)
    Returns a prime number which is >= desiredCapacity and very close to desiredCapacity (within 11% if desiredCapacity >= 1000).
    protected static void
    statistics(int from, int to)
    Tests correctness.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • largestPrime

      public static final int largestPrime
      The largest prime this class can generate; currently equal to Integer.MAX_VALUE.
      See Also:
    • primeCapacities

      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 invalid input: '<'= desired capacity * 1.11 (11%). For any desired capacity >= 200 the list includes a prime number invalid input: '<'= desired capacity * 1.16 (16%). For any desired capacity >= 16 the list includes a prime number invalid input: '<'= desired capacity * 1.21 (21%). 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 invalid input: '<'= 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.
  • Constructor Details

    • PrimeFinder

      protected PrimeFinder()
      Makes this class non instantiable, but still let's others inherit from it.
  • Method Details

    • main

      protected static void main(String[] args)
      Tests correctness. Try from=1000, to=10000 from=200, to=1000 from=16, to=1000 from=1000, to=Integer.MAX_VALUE
    • nextPrime

      public static 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.
    • statistics

      protected static void statistics(int from, int to)
      Tests correctness.