KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > util > collections > IntObjectHashMap


1 /*
2  Copyright 1999 CERN - European Organization for Nuclear Research.
3  Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
4  is hereby granted without fee, provided that the above copyright notice appear in all copies and
5  that both that copyright notice and this permission notice appear in supporting documentation.
6  CERN makes no representations about the suitability of this software for any purpose.
7  It is provided "as is" without expressed or implied warranty.
8  */

9 package prefuse.util.collections;
10
11 import java.util.ArrayList JavaDoc;
12 import java.util.Arrays JavaDoc;
13
14 /**
15  * Hash map holding (key,value) associations of type <tt>(int-->Object)</tt>;
16  * Automatically grows and shrinks as needed; Implemented using open addressing
17  * with double hashing. First see the <a HREF="package-summary.html">package
18  * summary</a> and javadoc <a HREF="package-tree.html">tree view</a> to get
19  * the broad picture.
20  *
21  * This class has been adapted from the corresponding class in the COLT
22  * library for scientfic computing.
23  *
24  * @author wolfgang.hoschek@cern.ch
25  * @version 1.0, 09/24/99
26  * @see java.util.HashMap
27  */

28 public class IntObjectHashMap extends AbstractHashMap implements Cloneable JavaDoc {
29     
30     protected static final int defaultCapacity = 277;
31     protected static final double defaultMinLoadFactor = 0.2;
32     protected static final double defaultMaxLoadFactor = 0.5;
33     
34     protected static final byte FREE = 0;
35     protected static final byte FULL = 1;
36     protected static final byte REMOVED = 2;
37     
38     /**
39      * The hash table keys.
40      */

41     protected int table[];
42
43     /**
44      * The hash table values.
45      */

46     protected Object JavaDoc values[];
47
48     /**
49      * The state of each hash table entry (FREE, FULL, REMOVED).
50      */

51     protected byte state[];
52
53     /**
54      * The number of table entries in state==FREE.
55      */

56     protected int freeEntries;
57     
58     /**
59      * Constructs an empty map with default capacity and default load factors.
60      */

61     public IntObjectHashMap() {
62         this(defaultCapacity);
63     }
64
65     /**
66      * Constructs an empty map with the specified initial capacity and default
67      * load factors.
68      *
69      * @param initialCapacity
70      * the initial capacity of the map.
71      * @throws IllegalArgumentException
72      * if the initial capacity is less than zero.
73      */

74     public IntObjectHashMap(int initialCapacity) {
75         this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor);
76     }
77
78     /**
79      * Constructs an empty map with the specified initial capacity and the
80      * specified minimum and maximum load factor.
81      *
82      * @param initialCapacity
83      * the initial capacity.
84      * @param minLoadFactor
85      * the minimum load factor.
86      * @param maxLoadFactor
87      * the maximum load factor.
88      * @throws IllegalArgumentException
89      * if
90      * <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
91      */

92     public IntObjectHashMap(int initialCapacity, double minLoadFactor,
93             double maxLoadFactor) {
94         setUp(initialCapacity, minLoadFactor, maxLoadFactor);
95     }
96
97     /**
98      * Removes all (key,value) associations from the receiver. Implicitly calls
99      * <tt>trimToSize()</tt>.
100      */

101     public void clear() {
102         Arrays.fill(state, FREE);
103         Arrays.fill(values, null);
104         
105         this.distinct = 0;
106         this.freeEntries = table.length; // delta
107
trimToSize();
108     }
109
110     /**
111      * Returns a deep copy of the receiver.
112      * @return a deep copy of the receiver.
113      */

114     public Object JavaDoc clone() {
115         try {
116             IntObjectHashMap copy = (IntObjectHashMap) super.clone();
117             copy.table = (int[]) copy.table.clone();
118             copy.values = (Object JavaDoc[]) copy.values.clone();
119             copy.state = (byte[]) copy.state.clone();
120             return copy;
121         } catch (CloneNotSupportedException JavaDoc e) {
122             // won't happen
123
return null;
124         }
125     }
126
127     /**
128      * Returns <tt>true</tt> if the receiver contains the specified key.
129      * @return <tt>true</tt> if the receiver contains the specified key.
130      */

131     public boolean containsKey(int key) {
132         return indexOfKey(key) >= 0;
133     }
134
135     /**
136      * Returns <tt>true</tt> if the receiver contains the specified value.
137      * @return <tt>true</tt> if the receiver contains the specified value.
138      */

139     public boolean containsValue(Object JavaDoc value) {
140         return indexOfValue(value) >= 0;
141     }
142
143     /**
144      * Ensures that the receiver can hold at least the specified number of
145      * associations without needing to allocate new internal memory. If
146      * necessary, allocates new internal memory and increases the capacity of
147      * the receiver.
148      * <p>
149      * This method never need be called; it is for performance tuning only.
150      * Calling this method before <tt>put()</tt>ing a large number of
151      * associations boosts performance, because the receiver will grow only once
152      * instead of potentially many times and hash collisions get less probable.
153      *
154      * @param minCapacity
155      * the desired minimum capacity.
156      */

157     public void ensureCapacity(int minCapacity) {
158         if (table.length < minCapacity) {
159             int newCapacity = nextPrime(minCapacity);
160             rehash(newCapacity);
161         }
162     }
163
164     /**
165      * Returns the value associated with the specified key. It is often a good
166      * idea to first check with {@link #containsKey(int)} whether the given key
167      * has a value associated or not, i.e. whether there exists an association
168      * for the given key or not.
169      *
170      * @param key
171      * the key to be searched for.
172      * @return the value associated with the specified key; <tt>null</tt> if
173      * no such key is present.
174      */

175     public Object JavaDoc get(int key) {
176         int i = indexOfKey(key);
177         if (i < 0)
178             return null; // not contained
179
return values[i];
180     }
181
182     /**
183      * @param key
184      * the key to be added to the receiver.
185      * @return the index where the key would need to be inserted, if it is not
186      * already contained. Returns -index-1 if the key is already
187      * contained at slot index. Therefore, if the returned index < 0,
188      * then it is already contained at slot -index-1. If the returned
189      * index >= 0, then it is NOT already contained and should be
190      * inserted at slot index.
191      */

192     protected int indexOfInsertion(int key) {
193         final int tab[] = table;
194         final byte stat[] = state;
195         final int length = tab.length;
196
197         final int hash = key & 0x7FFFFFFF;
198         int i = hash % length;
199         // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
200
int decrement = hash % (length - 2);
201         // int decrement = (hash / length) % length;
202
if (decrement == 0)
203             decrement = 1;
204
205         // stop if we find a removed or free slot, or if we find the key itself
206
// do NOT skip over removed slots (yes, open addressing is like that...)
207
while (stat[i] == FULL && tab[i] != key) {
208             i -= decrement;
209             // hashCollisions++;
210
if (i < 0)
211                 i += length;
212         }
213
214         if (stat[i] == REMOVED) {
215             // stop if we find a free slot, or if we find the key itself.
216
// do skip over removed slots (yes, open addressing is like that...)
217
// assertion: there is at least one FREE slot.
218
int j = i;
219             while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
220                 i -= decrement;
221                 // hashCollisions++;
222
if (i < 0)
223                     i += length;
224             }
225             if (stat[i] == FREE)
226                 i = j;
227         }
228
229         if (stat[i] == FULL) {
230             // key already contained at slot i.
231
// return a negative number identifying the slot.
232
return -i - 1;
233         }
234         // not already contained, should be inserted at slot i.
235
// return a number >= 0 identifying the slot.
236
return i;
237     }
238
239     /**
240      * @param key
241      * the key to be searched in the receiver.
242      * @return the index where the key is contained in the receiver, returns -1
243      * if the key was not found.
244      */

245     protected int indexOfKey(int key) {
246         final int tab[] = table;
247         final byte stat[] = state;
248         final int length = tab.length;
249
250         final int hash = key & 0x7FFFFFFF;
251         int i = hash % length;
252         // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
253
int decrement = hash % (length - 2);
254         // int decrement = (hash / length) % length;
255
if (decrement == 0)
256             decrement = 1;
257
258         // stop if we find a free slot, or if we find the key itself.
259
// do skip over removed slots (yes, open addressing is like that...)
260
while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
261             i -= decrement;
262             // hashCollisions++;
263
if (i < 0)
264                 i += length;
265         }
266
267         if (stat[i] == FREE)
268             return -1; // not found
269
return i; // found, return index where key is contained
270
}
271
272     /**
273      * @param value
274      * the value to be searched in the receiver.
275      * @return the index where the value is contained in the receiver, returns
276      * -1 if the value was not found.
277      */

278     protected int indexOfValue(Object JavaDoc value) {
279         final Object JavaDoc val[] = values;
280         final byte stat[] = state;
281
282         for (int i = stat.length; --i >= 0;) {
283             if (stat[i] == FULL && val[i] == value)
284                 return i;
285         }
286
287         return -1; // not found
288
}
289
290     /**
291      * Returns the first key the given value is associated with. It is often a
292      * good idea to first check with {@link #containsValue(Object)} whether
293      * there exists an association from a key to this value.
294      *
295      * @param value the value to search for.
296      * @return the first key for which holds <tt>get(key) == value</tt>;
297      * returns <tt>Integer.MIN_VALUE</tt> if no such key exists.
298      */

299     public int keyOf(Object JavaDoc value) {
300         // returns the first key found; there may be more matching keys,
301
// however.
302
int i = indexOfValue(value);
303         if (i < 0)
304             return Integer.MIN_VALUE;
305         return table[i];
306     }
307
308     /**
309      * Fills all keys contained in the receiver into the specified list. Fills
310      * the list, starting at index 0. After this call returns the specified list
311      * has a new size that equals <tt>this.size()</tt>.
312      * <p>
313      * This method can be used to iterate over the keys of the receiver.
314      *
315      * @param list
316      * the list to be filled
317      */

318     public int keys(int[] list) {
319         int[] tab = table;
320         byte[] stat = state;
321
322         if ( list.length < distinct )
323             return -1;
324         
325         int j = 0;
326         for (int i = tab.length; i-- > 0;) {
327             if (stat[i] == FULL)
328                 list[j++] = tab[i];
329         }
330         return distinct;
331     }
332
333     /**
334      * Associates the given key with the given value. Replaces any old
335      * <tt>(key,someOtherValue)</tt> association, if existing.
336      *
337      * @param key
338      * the key the value shall be associated with.
339      * @param value
340      * the value to be associated.
341      * @return <tt>true</tt> if the receiver did not already contain such a
342      * key; <tt>false</tt> if the receiver did already contain such a
343      * key - the new value has now replaced the formerly associated
344      * value.
345      */

346     public boolean put(int key, Object JavaDoc value) {
347         int i = indexOfInsertion(key);
348         if (i < 0) { // already contained
349
i = -i - 1;
350             this.values[i] = value;
351             return false;
352         }
353
354         if (this.distinct > this.highWaterMark) {
355             int newCapacity = chooseGrowCapacity(this.distinct + 1,
356                     this.minLoadFactor, this.maxLoadFactor);
357             rehash(newCapacity);
358             return put(key, value);
359         }
360
361         this.table[i] = key;
362         this.values[i] = value;
363         if (this.state[i] == FREE)
364             this.freeEntries--;
365         this.state[i] = FULL;
366         this.distinct++;
367
368         if (this.freeEntries < 1) { // delta
369
int newCapacity = chooseGrowCapacity(this.distinct + 1,
370                     this.minLoadFactor, this.maxLoadFactor);
371             rehash(newCapacity);
372         }
373
374         return true;
375     }
376
377     /**
378      * Rehashes the contents of the receiver into a new table with a smaller or
379      * larger capacity. This method is called automatically when the number of
380      * keys in the receiver exceeds the high water mark or falls below the low
381      * water mark.
382      */

383     protected void rehash(int newCapacity) {
384         int oldCapacity = table.length;
385         // if (oldCapacity == newCapacity) return;
386

387         int oldTable[] = table;
388         Object JavaDoc oldValues[] = values;
389         byte oldState[] = state;
390
391         int newTable[] = new int[newCapacity];
392         Object JavaDoc newValues[] = new Object JavaDoc[newCapacity];
393         byte newState[] = new byte[newCapacity];
394
395         this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
396         this.highWaterMark = chooseHighWaterMark(newCapacity,
397                 this.maxLoadFactor);
398
399         this.table = newTable;
400         this.values = newValues;
401         this.state = newState;
402         this.freeEntries = newCapacity - this.distinct; // delta
403

404         for (int i = oldCapacity; i-- > 0;) {
405             if (oldState[i] == FULL) {
406                 int element = oldTable[i];
407                 int index = indexOfInsertion(element);
408                 newTable[index] = element;
409                 newValues[index] = oldValues[i];
410                 newState[index] = FULL;
411             }
412         }
413     }
414
415     /**
416      * Removes the given key with its associated element from the receiver, if
417      * present.
418      *
419      * @param key
420      * the key to be removed from the receiver.
421      * @return <tt>true</tt> if the receiver contained the specified key,
422      * <tt>false</tt> otherwise.
423      */

424     public boolean removeKey(int key) {
425         int i = indexOfKey(key);
426         if (i < 0)
427             return false; // key not contained
428

429         this.state[i] = REMOVED;
430         this.values[i] = null; // delta
431
this.distinct--;
432
433         if (this.distinct < this.lowWaterMark) {
434             int newCapacity = chooseShrinkCapacity(this.distinct,
435                     this.minLoadFactor, this.maxLoadFactor);
436             rehash(newCapacity);
437         }
438
439         return true;
440     }
441
442     /**
443      * Initializes the receiver.
444      *
445      * @param initialCapacity
446      * the initial capacity of the receiver.
447      * @param minLoadFactor
448      * the minLoadFactor of the receiver.
449      * @param maxLoadFactor
450      * the maxLoadFactor of the receiver.
451      * @throws IllegalArgumentException
452      * if
453      * <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
454      */

455     protected void setUp(int initialCapacity, double minLoadFactor,
456             double maxLoadFactor) {
457         int capacity = initialCapacity;
458         super.setUp(capacity, minLoadFactor, maxLoadFactor);
459         capacity = nextPrime(capacity);
460         if (capacity == 0)
461             capacity = 1; // open addressing needs at least one FREE slot at any time.
462

463         this.table = new int[capacity];
464         this.values = new Object JavaDoc[capacity];
465         this.state = new byte[capacity];
466
467         // memory will be exhausted long before this pathological case happens, anyway.
468
this.minLoadFactor = minLoadFactor;
469         if (capacity == PrimeFinder.largestPrime)
470             this.maxLoadFactor = 1.0;
471         else
472             this.maxLoadFactor = maxLoadFactor;
473
474         this.distinct = 0;
475         this.freeEntries = capacity; // delta
476

477         // lowWaterMark will be established upon first expansion.
478
// establishing it now (upon instance construction) would immediately make the table shrink upon first put(...).
479
// After all the idea of an "initialCapacity" implies violating lowWaterMarks when an object is young.
480
// See ensureCapacity(...)
481
this.lowWaterMark = 0;
482         this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
483     }
484
485     /**
486      * Trims the capacity of the receiver to be the receiver's current
487      * size. Releases any superfluous internal memory. An application can use this operation to minimize the
488      * storage of the receiver.
489      */

490     public void trimToSize() {
491         // * 1.2 because open addressing's performance exponentially degrades beyond that point
492
// so that even rehashing the table can take very long
493
int newCapacity = nextPrime((int) (1 + 1.2 * size()));
494         if (table.length > newCapacity) {
495             rehash(newCapacity);
496         }
497     }
498
499     /**
500      * Fills all values contained in the receiver into the specified list.
501      * Fills the list, starting at index 0.
502      * After this call returns the specified list has a new size that equals
503      * <tt>this.size()</tt>.
504      * <p>
505      * This method can be used to iterate over the values of the receiver.
506      *
507      * @param list the list to be filled, can have any size.
508      */

509     public void values(ArrayList JavaDoc list) {
510         Object JavaDoc[] val = values;
511         byte[] stat = state;
512
513         for (int i = stat.length; i-- > 0;) {
514             if (stat[i] == FULL)
515                 list.add(val[i]);
516         }
517     }
518     
519 } // end of class IntObjectHashMap
520
Popular Tags