001: package com.jofti.util;
002:
003: /**
004:
005: * An amended version of the PrimeFinder implementation from CERN's COLT project.
006: *
007: * Not of interest for users; only for implementors of hashtables.
008:
009: * Used to keep hash table capacities prime numbers.
010:
011: *
012:
013: * <p>Choosing prime numbers as hash table capacities is a good idea to keep them working fast,
014:
015: * particularly under hash table expansions.
016:
017: *
018:
019: * <p>However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to keep capacities prime.
020:
021: * This class provides efficient means to choose prime capacities.
022:
023: *
024:
025: * <p>Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of 300 int's).
026:
027: * Memory requirements: 1 KB static memory.
028:
029: *
030:
031: * @author steve@jofti.com
032: * @author wolfgang.hoschek@cern.ch
033:
034: * @version 1.1 03/01/06
035: * @version 1.0, 09/24/99
036:
037: */
038: public class PrimeFinder {
039:
040: /**
041:
042: * The largest prime this class can generate; currently equal to <tt>Integer.MAX_VALUE</tt>.
043:
044: */
045:
046: public static final int largestPrime = Integer.MAX_VALUE; //yes, it is prime.
047:
048: /**
049:
050: * The prime number list consists of 11 chunks.
051:
052: * Each chunk contains prime numbers.
053:
054: * 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.
055:
056: * The next element is P3, for which the same holds with respect to P2, and so on.
057:
058: *
059:
060: * Chunks are chosen such that for any desired capacity >= 1000
061:
062: * the list includes a prime number <= desired capacity * 1.11 (11%).
063:
064: * For any desired capacity >= 200
065:
066: * the list includes a prime number <= desired capacity * 1.16 (16%).
067:
068: * For any desired capacity >= 16
069:
070: * the list includes a prime number <= desired capacity * 1.21 (21%).
071:
072: *
073:
074: * Therefore, primes can be retrieved which are quite close to any desired capacity,
075:
076: * which in turn avoids wasting memory.
077:
078: * For example, the list includes 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
079:
080: * So if you need a prime >= 1040, you will find a prime <= 1040*1.11=1154.
081:
082: *
083:
084: * Chunks are chosen such that they are optimized for a hashtable growthfactor of 2.0;
085:
086: * If your hashtable has such a growthfactor then,
087:
088: * after initially "rounding to a prime" upon hashtable construction,
089:
090: * it will later expand to prime capacities such that there exist no better primes.
091:
092: *
093:
094: * In total these are about 32*10=320 numbers -> 1 KB of static memory needed.
095:
096: * If you are stingy, then delete every second or fourth chunk.
097:
098: */
099:
100: private static final int[] primeCapacities = {
101:
102: //chunk #0
103:
104: largestPrime,
105:
106: //chunk #1
107:
108: 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203,
109: 6421,
110: 12853,
111: 25717,
112: 51437,
113: 102877,
114: 205759,
115:
116: 411527,
117: 823117,
118: 1646237,
119: 3292489,
120: 6584983,
121: 13169977,
122: 26339969,
123: 52679969,
124: 105359939,
125:
126: 210719881,
127: 421439783,
128: 842879579,
129: 1685759167,
130:
131: //chunk #2
132:
133: 433, 877, 1759, 3527, 7057, 14143,
134: 28289,
135: 56591,
136: 113189,
137: 226379,
138: 452759,
139: 905551,
140: 1811107,
141:
142: 3622219,
143: 7244441,
144: 14488931,
145: 28977863,
146: 57955739,
147: 115911563,
148: 231823147,
149: 463646329,
150: 927292699,
151:
152: 1854585413,
153:
154: //chunk #3
155:
156: 953, 1907, 3821, 7643, 15287, 30577, 61169,
157: 122347,
158: 244703,
159: 489407,
160: 978821,
161: 1957651,
162: 3915341,
163:
164: 7830701,
165: 15661423,
166: 31322867,
167: 62645741,
168: 125291483,
169: 250582987,
170: 501165979,
171: 1002331963,
172:
173: 2004663929,
174:
175: //chunk #4
176:
177: 1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853,
178: 267713,
179: 535481,
180: 1070981,
181: 2141977,
182: 4283963,
183:
184: 8567929,
185: 17135863,
186: 34271747,
187: 68543509,
188: 137087021,
189: 274174111,
190: 548348231,
191: 1096696463,
192:
193: //chunk #5
194:
195: 31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929,
196: 35863, 71741, 143483, 286973, 573953,
197:
198: 1147921,
199: 2295859,
200: 4591721,
201: 9183457,
202: 18366923,
203: 36733847,
204: 73467739,
205: 146935499,
206: 293871013,
207:
208: 587742049,
209: 1175484103,
210:
211: //chunk #6
212:
213: 599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027,
214: 310081, 620171, 1240361, 2480729,
215:
216: 4961459,
217: 9922933,
218: 19845871,
219: 39691759,
220: 79383533,
221: 158767069,
222: 317534141,
223: 635068283,
224: 1270136683,
225:
226: //chunk #7
227:
228: 311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037,
229: 164089, 328213, 656429, 1312867,
230:
231: 2625761, 5251529, 10503061, 21006137,
232: 42012281,
233: 84024581,
234: 168049163,
235: 336098327,
236: 672196673,
237:
238: 1344393353,
239:
240: //chunk #8
241:
242: 3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949,
243: 21911, 43853, 87719, 175447, 350899,
244:
245: 701819, 1403641, 2807303, 5614657, 11229331, 22458671,
246: 44917381, 89834777, 179669557,
247:
248: 359339171,
249: 718678369,
250: 1437356741,
251:
252: //chunk #9
253:
254: 43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159,
255: 46327, 92657, 185323, 370661, 741337,
256:
257: 1482707, 2965421, 5930887, 11861791, 23723597, 47447201,
258: 94894427, 189788857, 379577741,
259:
260: 759155483,
261: 1518310967,
262:
263: //chunk #10
264:
265: 379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649,
266: 195311, 390647, 781301, 1562611,
267:
268: 3125257, 6250537, 12501169, 25002389, 50004791, 100009607,
269: 200019221, 400038451, 800076929,
270:
271: 1600153859
272:
273: };
274:
275: static { //initializer
276:
277: // The above prime numbers are formatted for human readability.
278:
279: // To find numbers fast, we sort them once and for all.
280:
281: java.util.Arrays.sort(primeCapacities);
282:
283: }
284:
285: /**
286:
287: * Makes this class non instantiable, but still let's others inherit from it.
288:
289: */
290:
291: protected PrimeFinder() {
292: }
293:
294: /**
295:
296:
297:
298:
299: /**
300:
301: * Returns a prime number which is <code>>= desiredCapacity</code> and very close to <code>desiredCapacity</code> (within 11% if <code>desiredCapacity >= 1000</code>).
302:
303: * @param desiredCapacity the capacity desired by the user.
304:
305: * @return the capacity which should be used for a hashtable.
306:
307: */
308:
309: public static int nextPrime(int desiredCapacity) {
310:
311: int i = java.util.Arrays.binarySearch(primeCapacities,
312: desiredCapacity);
313:
314: if (i < 0) {
315:
316: // desired capacity not found, choose next prime greater than desired capacity
317:
318: i = -i - 1; // remember the semantics of binarySearch...
319:
320: }
321:
322: return primeCapacities[i];
323:
324: }
325:
326: }
|