IntHashMap


1   package jodd.util;
2   
3   import java.io.IOException;
4   import java.io.Serializable;
5   import java.util.AbstractCollection;
6   import java.util.AbstractMap;
7   import java.util.AbstractSet;
8   import java.util.Collection;
9   import java.util.ConcurrentModificationException;
10  import java.util.Iterator;
11  import java.util.Map;
12  import java.util.NoSuchElementException;
13  import java.util.Set;
14  
15  /**
16   * A Map that accepts int or Integer keys only. The implementation is based on
17   * <code>java.util.HashMap</code>. IntHashMap is about 25% faster.
18   *
19   * @see java.util.HashMap
20   */
21  
22  public class IntHashMap extends AbstractMap implements Map, Cloneable, Serializable {
23  
24      /**
25       * The hash table data.
26       */
27      private transient Entry table[];
28  
29      /**
30       * The total number of mappings in the hash table.
31       */
32      private transient int count;
33  
34      /**
35       * The table is rehashed when its size exceeds this threshold. (The value of
36       * this field is (int)(capacity * loadFactor).)
37       */
38      private int threshold;
39  
40      /**
41       * The load factor for the hashtable.
42       */
43      private float loadFactor;
44  
45      /**
46       * The number of times this IntHashMap has been structurally modified
47       * Structural modifications are those that change the number of mappings in
48       * the IntHashMap or otherwise modify its internal structure (e.g., rehash).
49       * This field is used to make iterators on Collection-views of the IntHashMap
50       * fail-fast.
51       */
52      private transient int modCount = 0;
53  
54      /**
55       * Constructs a new, empty map with the specified initial
56       * capacity and the specified load factor.
57       *
58       * @param initialCapacity
59       *                   the initial capacity of the IntHashMap.
60       * @param loadFactor the load factor of the IntHashMap
61       *
62       * @throws IllegalArgumentException
63       *                if the initial capacity is less
64       *                than zero, or if the load factor is nonpositive.
65       */
66      public IntHashMap(int initialCapacity, float loadFactor) {
67          if (initialCapacity < 0) {
68              throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity);
69          }
70          if (loadFactor <= 0) {
71              throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor);
72          }
73          if (initialCapacity == 0) {
74              initialCapacity = 1;
75          }
76          this.loadFactor = loadFactor;
77          table = new Entry[initialCapacity];
78          threshold = (int)(initialCapacity * loadFactor);
79      }
80  
81      /**
82       * Constructs a new, empty map with the specified initial capacity
83       * and default load factor, which is 0.75.
84       *
85       * @param initialCapacity
86       *               the initial capacity of the IntHashMap.
87       *
88       * @throws IllegalArgumentException
89       *                if the initial capacity is less
90       *                than zero.
91       */
92      public IntHashMap(int initialCapacity) {
93          this(initialCapacity, 0.75f);
94      }
95  
96      /**
97       * Constructs a new, empty map with a default capacity and load
98       * factor, which is 0.75.
99       */
100     public IntHashMap() {
101         this(101, 0.75f);
102     }
103 
104     /**
105      * Constructs a new map with the same mappings as the given map.  The
106      * map is created with a capacity of twice the number of mappings in
107      * the given map or 11 (whichever is greater), and a default load factor,
108      * which is 0.75.
109      *
110      * @param t
111      */
112     public IntHashMap(Map t) {
113         this(Math.max(2 * t.size(), 11), 0.75f);
114         putAll(t);
115     }
116 
117     /**
118      * Returns the number of key-value mappings in this map.
119      *
120      * @return the number of key-value mappings in this map.
121      */
122     public int size() {
123         return count;
124     }
125 
126     /**
127      * Returns <code>true</code> if this map contains no key-value mappings.
128      *
129      * @return <code>true</code> if this map contains no key-value mappings.
130      */
131     public boolean isEmpty() {
132         return count == 0;
133     }
134 
135     /**
136      * Returns <code>true</code> if this map maps one or more keys to the
137      * specified value.
138      *
139      * @param value  value whose presence in this map is to be tested.
140      *
141      * @return <code>true</code> if this map maps one or more keys to the
142      *         specified value.
143      */
144     public boolean containsValue(Object value) {
145         Entry tab[] = table;
146         if (value == null) {
147             for (int i = tab.length; i-- > 0 ;) {
148                 for (Entry e = tab[i] ; e != null ; e = e.next) {
149                     if (e.value == null) {
150                         return true;
151                     }
152                 }
153             }
154         } else {
155             for (int i = tab.length; i-- > 0 ;) {
156                 for (Entry e = tab[i]; e != null; e = e.next) {
157                     if (value.equals(e.value)) {
158                         return true;
159                     }
160                 }
161             }
162         }
163         return false;
164     }
165 
166     /**
167      * Returns <code>true</code> if this map contains a mapping for the specified
168      * key.
169      *
170      * @param key    key whose presence in this Map is to be tested.
171      *
172      * @return <code>true</code> if this map contains a mapping for the specified
173      *         key.
174      */
175     public boolean containsKey(Object key) {
176         if (key instanceof Number) {
177             return containsKey( ((Number)key).intValue() );
178         } else {
179             return false;
180         }
181     }
182 
183     /**
184      * Returns <code>true</code> if this map contains a mapping for the specified
185      * key.
186      *
187      * @param key    key whose presence in this Map is to be tested.
188      *
189      * @return <code>true</code> if this map contains a mapping for the specified
190      *         key.
191      */
192     public boolean containsKey(int key) {
193         Entry tab[] = table;
194 
195         int index = (key & 0x7FFFFFFF) % tab.length;
196         for (Entry e = tab[index]; e != null; e = e.next) {
197             if (e.key == key) {
198                 return true;
199             }
200         }
201 
202         return false;
203     }
204 
205     /**
206      * Returns the value to which this map maps the specified key. Returns
207      * <code>null</code> if the map contains no mapping for this key. A return
208      * value of <code>null</code> does not <i>necessarily</i> indicate that the
209      * map contains no mapping for the key; it's also possible that the map
210      * explicitly maps the key to <code>null</code>. The <code>containsKey</code>
211      * operation may be used to distinguish these two cases.
212      *
213      * @param key    key whose associated value is to be returned.
214      *
215      * @return the value to which this map maps the specified key.
216      */
217     public Object get(Object key) {
218         if (key instanceof Number) {
219             return get( ((Number)key).intValue() );
220         } else {
221             return null;
222         }
223     }
224 
225     /**
226      * Returns the value to which this map maps the specified key. Returns
227      * <code>null</code> if the map contains no mapping for this key. A return
228      * value of <code>null</code> does not <i>necessarily</i> indicate that the
229      * map contains no mapping for the key; it's also possible that the map
230      * explicitly maps the key to <code>null</code>. The <code>containsKey</code>
231      * operation may be used to distinguish these two cases.
232      *
233      * @param key    key whose associated value is to be returned.
234      *
235      * @return the value to which this map maps the specified key.
236      */
237     public Object get(int key) {
238         Entry tab[] = table;
239 
240         int index = (key & 0x7FFFFFFF) % tab.length;
241         for (Entry e = tab[index]; e != null; e = e.next) {
242             if (e.key == key) {
243                 return e.value;
244             }
245         }
246 
247         return null;
248     }
249 
250     /**
251      * Rehashes the contents of this map into a new <code>IntHashMap</code>
252      * instance with a larger capacity. This method is called automatically when
253      * the number of keys in this map exceeds its capacity and load factor.
254      */
255     private void rehash() {
256         int oldCapacity = table.length;
257         Entry oldMap[] = table;
258 
259         int newCapacity = oldCapacity * 2 + 1;
260         Entry newMap[] = new Entry[newCapacity];
261 
262         modCount++;
263         threshold = (int)(newCapacity * loadFactor);
264         table = newMap;
265 
266         for (int i = oldCapacity ; i-- > 0 ;) {
267             for (Entry old = oldMap[i] ; old != null ; ) {
268                 Entry e = old;
269                 old = old.next;
270 
271                 int index = (e.key & 0x7FFFFFFF) % newCapacity;
272                 e.next = newMap[index];
273                 newMap[index] = e;
274             }
275         }
276     }
277 
278     /**
279      * Associates the specified value with the specified key in this map. If the
280      * map previously contained a mapping for this key, the old value is
281      * replaced.
282      *
283      * @param key    key with which the specified value is to be associated.
284      * @param value  value to be associated with the specified key.
285      *
286      * @return previous value associated with specified key, or <code>null</code> if
287      *         there was no mapping for key. A <code>null</code> return can also indicate
288      *         that the IntHashMap previously associated <code>null</code> with the
289      *         specified key.
290      */
291     public Object put(Object key, Object value) {
292         if (key instanceof Number) {
293             return put( ((Number)key).intValue(), value );
294         } else {
295             throw new UnsupportedOperationException
296             ("IntHashMap key must be a number");
297         }
298     }
299 
300     /**
301      * Associates the specified value with the specified key in this map. If the
302      * map previously contained a mapping for this key, the old value is
303      * replaced.
304      *
305      * @param key    key with which the specified value is to be associated.
306      * @param value  value to be associated with the specified key.
307      *
308      * @return previous value associated with specified key, or <code>null</code> if
309      *         there was no mapping for key. A <code>null</code> return can also indicate
310      *         that the IntHashMap previously associated <code>null</code> with the
311      *         specified key.
312      */
313     public Object put(int key, Object value) {
314         // makes sure the key is not already in the IntHashMap.
315         Entry tab[] = table;
316         int index = 0;
317 
318         index = (key & 0x7FFFFFFF) % tab.length;
319         for (Entry e = tab[index] ; e != null ; e = e.next) {
320             if (e.key == key) {
321                 Object old = e.value;
322                 e.value = value;
323                 return old;
324             }
325         }
326 
327         modCount++;
328         if (count >= threshold) {
329             // rehash the table if the threshold is exceeded
330             rehash();
331 
332             tab = table;
333             index = (key & 0x7FFFFFFF) % tab.length;
334         }
335 
336         // creates the new entry.
337         Entry e = new Entry(key, value, tab[index]);
338         tab[index] = e;
339         count++;
340         return null;
341     }
342 
343     /**
344      * Removes the mapping for this key from this map if present.
345      *
346      * @param key    key whose mapping is to be removed from the map.
347      *
348      * @return previous value associated with specified key, or <code>null</code> if
349      *         there was no mapping for key. A <code>null</code> return can also indicate
350      *         that the map previously associated <code>null</code> with the specified
351      *         key.
352      */
353     public Object remove(Object key) {
354         if (key instanceof Number) {
355             return remove( ((Number)key).intValue() );
356         } else {
357             return null;
358         }
359     }
360 
361     /**
362      * Removes the mapping for this key from this map if present.
363      *
364      * @param key    key whose mapping is to be removed from the map.
365      *
366      * @return previous value associated with specified key, or <code>null</code> if
367      *         there was no mapping for key. A <code>null</code> return can also indicate
368      *         that the map previously associated <code>null</code> with the specified
369      *         key.
370      */
371     public Object remove(int key) {
372         Entry tab[] = table;
373 
374         int index = (key & 0x7FFFFFFF) % tab.length;
375 
376         for (Entry e = tab[index], prev = null; e != null;
377             prev = e, e = e.next) {
378 
379             if (e.key == key) {
380                 modCount++;
381                 if (prev != null) {
382                     prev.next = e.next;
383                 } else {
384                     tab[index] = e.next;
385                 }
386 
387                 count--;
388                 Object oldValue = e.value;
389                 e.value = null;
390                 return oldValue;
391             }
392         }
393 
394         return null;
395     }
396 
397     /**
398      * Copies all of the mappings from the specified map to this one.
399      * These mappings replace any mappings that this map had for any of the
400      * keys currently in the specified Map.
401      *
402      * @param t      Mappings to be stored in this map.
403      */
404     public void putAll(Map t) {
405         Iterator i = t.entrySet().iterator();
406         while (i.hasNext()) {
407             Map.Entry e = (Map.Entry) i.next();
408             put(e.getKey(), e.getValue());
409         }
410     }
411 
412     /**
413      * Removes all mappings from this map.
414      */
415     public void clear() {
416         Entry tab[] = table;
417         modCount++;
418         for (int index = tab.length; --index >= 0; ) {
419             tab[index] = null;
420         }
421         count = 0;
422     }
423 
424     /**
425      * Returns a shallow copy of this <code>IntHashMap</code> instance: the keys and
426      * values themselves are not cloned.
427      *
428      * @return a shallow copy of this map.
429      */
430     public Object clone() {
431         try {
432             IntHashMap t = (IntHashMap)super.clone();
433             t.table = new Entry[table.length];
434             for (int i = table.length ; i-- > 0 ; ) {
435                 t.table[i] = (table[i] != null)
436                              ? (Entry)table[i].clone() : null;
437             }
438             t.keySet = null;
439             t.entrySet = null;
440             t.values = null;
441             t.modCount = 0;
442             return t;
443         } catch (CloneNotSupportedException e) {
444             // this shouldn't happen, since we are Cloneable
445             throw new InternalError();
446         }
447     }
448 
449     // views
450     private transient Set keySet = null;
451     private transient Set entrySet = null;
452     private transient Collection values = null;
453 
454     /**
455      * Returns a set view of the keys contained in this map. The set is backed by
456      * the map, so changes to the map are reflected in the set, and vice-versa.
457      * The set supports element removal, which removes the corresponding mapping
458      * from this map, via the <code>Iterator.remove</code>,
459      * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
460      * and <code>clear</code> operations. It does not support the
461      * <code>add</code> or <code>addAll</code> operations.
462      *
463      * @return a set view of the keys contained in this map.
464      */
465     public Set keySet() {
466         if (keySet == null) {
467             keySet = new AbstractSet() {
468                 public Iterator iterator() {
469                     return new IntHashIterator(KEYS);
470                 }
471                 public int size() {
472                     return count;
473                 }
474                 public boolean contains(Object o) {
475                     return containsKey(o);
476                 }
477                 public boolean remove(Object o) {
478                     return IntHashMap.this.remove(o) != null;
479                 }
480                 public void clear() {
481                     IntHashMap.this.clear();
482                 }
483             };
484         }
485         return keySet;
486     }
487 
488     /**
489      * Returns a collection view of the values contained in this map. The
490      * collection is backed by the map, so changes to the map are reflected in
491      * the collection, and vice-versa. The collection supports element removal,
492      * which removes the corresponding mapping from this map, via the
493      * <code>Iterator.remove</code>, <code>Collection.remove</code>,
494      * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>
495      * operations. It does not support the <code>add</code> or
496      * <code>addAll</code> operations.
497      *
498      * @return a collection view of the values contained in this map.
499      */
500     public Collection values() {
501         if (values==null) {
502             values = new AbstractCollection() {
503                 public Iterator iterator() {
504                     return new IntHashIterator(VALUES);
505                 }
506                 public int size() {
507                     return count;
508                 }
509                 public boolean contains(Object o) {
510                     return containsValue(o);
511                 }
512                 public void clear() {
513                     IntHashMap.this.clear();
514                 }
515             };
516         }
517         return values;
518     }
519 
520     /**
521      * Returns a collection view of the mappings contained in this map. Each
522      * element in the returned collection is a <code>Map.Entry</code>. The
523      * collection is backed by the map, so changes to the map are reflected in
524      * the collection, and vice-versa. The collection supports element removal,
525      * which removes the corresponding mapping from the map, via the
526      * <code>Iterator.remove</code>, <code>Collection.remove</code>,
527      * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>
528      * operations. It does not support the <code>add</code> or
529      * <code>addAll</code> operations.
530      *
531      * @return a collection view of the mappings contained in this map.
532      * @see java.util.Map.Entry
533      */
534     public Set entrySet() {
535         if (entrySet==null) {
536             entrySet = new AbstractSet() {
537                 public Iterator iterator() {
538                     return new IntHashIterator(ENTRIES);
539                 }
540 
541                 public boolean contains(Object o) {
542                     if (!(o instanceof Map.Entry)) {
543                         return false;
544                     }
545                     Map.Entry entry = (Map.Entry)o;
546                     Object key = entry.getKey();
547                     Entry tab[] = table;
548                     int hash = (key==null ? 0 : key.hashCode());
549                     int index = (hash & 0x7FFFFFFF) % tab.length;
550 
551                     for (Entry e = tab[index]; e != null; e = e.next) {
552                         if (e.key == hash && e.equals(entry)) {
553                             return true;
554                         }
555                     }
556                     return false;
557                 }
558 
559                 public boolean remove(Object o) {
560                     if (!(o instanceof Map.Entry))
561                         return false;
562                     Map.Entry entry = (Map.Entry)o;
563                     Object key = entry.getKey();
564                     Entry tab[] = table;
565                     int hash = (key==null ? 0 : key.hashCode());
566                     int index = (hash & 0x7FFFFFFF) % tab.length;
567 
568                     for (Entry e = tab[index], prev = null; e != null;
569                         prev = e, e = e.next) {
570                         if (e.key == hash && e.equals(entry)) {
571                             modCount++;
572                             if (prev != null) {
573                                 prev.next = e.next;
574                             } else {
575                                 tab[index] = e.next;
576                             }
577 
578                             count--;
579                             e.value = null;
580                             return true;
581                         }
582                     }
583                     return false;
584                 }
585 
586                 public int size() {
587                     return count;
588                 }
589 
590                 public void clear() {
591                     IntHashMap.this.clear();
592                 }
593             };
594         }
595 
596         return entrySet;
597     }
598 
599     /**
600      * IntHashMap collision list entry.
601      */
602     private static class Entry implements Map.Entry {
603         int key;
604         Object value;
605         Entry next;
606         private Integer objectKey;
607 
608         Entry(int key, Object value, Entry next) {
609             this.key = key;
610             this.value = value;
611             this.next = next;
612         }
613 
614         protected Object clone() {
615             return new Entry(key, value,
616                              (next==null ? null : (Entry)next.clone()));
617         }
618 
619         // Map.Entry Ops
620 
621         public Object getKey() {
622             return(objectKey != null) ? objectKey :
623             (objectKey = new Integer(key));
624         }
625 
626         public Object getValue() {
627             return value;
628         }
629 
630         public Object setValue(Object value) {
631             Object oldValue = this.value;
632             this.value = value;
633             return oldValue;
634         }
635 
636         public boolean equals(Object o) {
637             if (!(o instanceof Map.Entry)) {
638                 return false;
639             }
640             Map.Entry e = (Map.Entry)o;
641 
642             return(getKey().equals(e.getKey())) &&
643             (value==null ? e.getValue()==null : value.equals(e.getValue()));
644         }
645 
646         public int hashCode() {
647             return key ^ (value==null ? 0 : value.hashCode());
648         }
649 
650         public String toString() {
651             return String.valueOf(key) + "=" + value;
652         }
653     }
654 
655     // types of Iterators
656     private static final int KEYS = 0;
657     private static final int VALUES = 1;
658     private static final int ENTRIES = 2;
659 
660     private class IntHashIterator implements Iterator {
661         Entry[] table = IntHashMap.this.table;
662         int index = table.length;
663         Entry entry = null;
664         Entry lastReturned = null;
665         int type;
666 
667         /**
668          * The modCount value that the iterator believes that the backing
669          * List should have.  If this expectation is violated, the iterator
670          * has detected concurrent modification.
671          */
672         private int expectedModCount = modCount;
673 
674         IntHashIterator(int type) {
675             this.type = type;
676         }
677 
678         public boolean hasNext() {
679             while (entry == null && index > 0) {
680                 entry = table[--index];
681             }
682 
683             return entry != null;
684         }
685 
686         public Object next() {
687             if (modCount != expectedModCount) {
688                 throw new ConcurrentModificationException();
689             }
690 
691             while (entry == null && index > 0) {
692                 entry = table[--index];
693             }
694 
695             if (entry != null) {
696                 Entry e = lastReturned = entry;
697                 entry = e.next;
698                 return type == KEYS ? e.getKey() :
699                 (type == VALUES ? e.value : e);
700             }
701             throw new NoSuchElementException();
702         }
703 
704         public void remove() {
705             if (lastReturned == null) {
706                 throw new IllegalStateException();
707             }
708             if (modCount != expectedModCount) {
709                 throw new ConcurrentModificationException();
710             }
711 
712             Entry[] tab = IntHashMap.this.table;
713             int index = (lastReturned.key & 0x7FFFFFFF) % tab.length;
714 
715             for (Entry e = tab[index], prev = null; e != null;
716                 prev = e, e = e.next) {
717                 if (e == lastReturned) {
718                     modCount++;
719                     expectedModCount++;
720                     if (prev == null) {
721                         tab[index] = e.next;
722                     } else {
723                         prev.next = e.next;
724                     }
725                     count--;
726                     lastReturned = null;
727                     return;
728                 }
729             }
730             throw new ConcurrentModificationException();
731         }
732     }
733 
734     /**
735      * Save the state of the <code>IntHashMap</code> instance to a stream (i.e.,
736      * serialize it).
737      * <p>
738      * Data The <i>capacity</i> of the IntHashMap (the length of the bucket
739      * array) is emitted (int), followed by the <i>size</i> of the IntHashMap
740      * (the number of key-value mappings), followed by the key (Object) and value
741      * (Object) for each key-value mapping represented by the IntHashMap The
742      * key-value mappings are emitted in no particular order.
743      *
744      * @param s
745      *
746      * @exception IOException
747      */
748     private void writeObject(java.io.ObjectOutputStream s) throws IOException {
749         // write out the threshold, loadfactor, and any hidden stuff
750         s.defaultWriteObject();
751 
752         // write out number of buckets
753         s.writeInt(table.length);
754 
755         // write out size (number of Mappings)
756         s.writeInt(count);
757 
758         // write out keys and values (alternating)
759         for (int index = table.length-1; index >= 0; index--) {
760             Entry entry = table[index];
761 
762             while (entry != null) {
763                 s.writeInt(entry.key);
764                 s.writeObject(entry.value);
765                 entry = entry.next;
766             }
767         }
768     }
769 
770     /**
771      * Reconstitute the <code>IntHashMap</code> instance from a stream (i.e.,
772      * deserialize it).
773      *
774      * @param s
775      *
776      * @exception IOException
777      * @exception ClassNotFoundException
778      */
779     private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
780         // read in the threshold, loadfactor, and any hidden stuff
781         s.defaultReadObject();
782 
783         // read in number of buckets and allocate the bucket array;
784         int numBuckets = s.readInt();
785         table = new Entry[numBuckets];
786 
787         // read in size (number of Mappings)
788         int size = s.readInt();
789 
790         // read the keys and values, and put the mappings in the IntHashMap
791         for (int i=0; i<size; i++) {
792             int key = s.readInt();
793             Object value = s.readObject();
794             put(key, value);
795         }
796     }
797 
798     int capacity() {
799         return table.length;
800     }
801 
802     float loadFactor() {
803         return loadFactor;
804     }
805 }
806
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags