Java > Open Source Codes > jodd > util > collection > IntHashMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags