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  ;
12  import java.util.Arrays  ;
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   {
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   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   clone() {
115         try {
116             IntObjectHashMap copy = (IntObjectHashMap) super.clone();
117             copy.table = (int[]) copy.table.clone();
118             copy.values = (Object  []) copy.values.clone();
119             copy.state = (byte[]) copy.state.clone();
120             return copy;
121         } catch (CloneNotSupportedException   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   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   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   value) {
279         final Object   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   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   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   oldValues[] = values;
389         byte oldState[] = state;
390 
391         int newTable[] = new int[newCapacity];
392         Object   newValues[] = new Object  [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  [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   list) {
510         Object  [] 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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags