KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > cojen > util > IntHashMap


1 /*
2  * Copyright 2005 Brian S O'Neill
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */

16
17 package org.cojen.util;
18
19 import java.util.AbstractCollection JavaDoc;
20 import java.util.AbstractMap JavaDoc;
21 import java.util.AbstractSet JavaDoc;
22 import java.util.Collection JavaDoc;
23 import java.util.ConcurrentModificationException JavaDoc;
24 import java.util.Iterator JavaDoc;
25 import java.util.Map JavaDoc;
26 import java.util.NoSuchElementException JavaDoc;
27 import java.util.Set JavaDoc;
28
29 import java.io.IOException JavaDoc;
30 import java.io.Serializable JavaDoc;
31
32 /**
33  * A Map that accepts int or Integer keys only. This class is not thread-safe.
34  *
35  * @author Brian S O'Neill
36  */

37 public class IntHashMap extends AbstractMap JavaDoc implements Map JavaDoc, Cloneable JavaDoc, Serializable JavaDoc {
38     /**
39      * The hash table data.
40      */

41     private transient Entry table[];
42
43     /**
44      * The total number of mappings in the hash table.
45      */

46     private transient int count;
47
48     /**
49      * The table is rehashed when its size exceeds this threshold. (The
50      * value of this field is (int)(capacity * loadFactor).)
51      *
52      * @serial
53      */

54     private int threshold;
55
56     /**
57      * The load factor for the hashtable.
58      *
59      * @serial
60      */

61     private float loadFactor;
62
63     /**
64      * The number of times this IntHashMap has been structurally modified
65      * Structural modifications are those that change the number of mappings in
66      * the IntHashMap or otherwise modify its internal structure (e.g.,
67      * rehash). This field is used to make iterators on Collection-views of
68      * the IntHashMap fail-fast. (See ConcurrentModificationException).
69      */

70     private transient int modCount = 0;
71
72     /**
73      * Constructs a new, empty map with the specified initial
74      * capacity and the specified load factor.
75      *
76      * @param initialCapacity the initial capacity of the IntHashMap.
77      * @param loadFactor the load factor of the IntHashMap
78      * @throws IllegalArgumentException if the initial capacity is less
79      * than zero, or if the load factor is nonpositive.
80      */

81     public IntHashMap(int initialCapacity, float loadFactor) {
82         if (initialCapacity < 0) {
83             throw new IllegalArgumentException JavaDoc("Illegal Initial Capacity: "+
84                                                initialCapacity);
85         }
86
87         if (loadFactor <= 0) {
88             throw new IllegalArgumentException JavaDoc("Illegal Load factor: "+
89                                                loadFactor);
90         }
91
92         if (initialCapacity==0) {
93             initialCapacity = 1;
94         }
95
96         this.loadFactor = loadFactor;
97         table = new Entry[initialCapacity];
98         threshold = (int)(initialCapacity * loadFactor);
99     }
100
101     /**
102      * Constructs a new, empty map with the specified initial capacity
103      * and default load factor, which is <tt>0.75</tt>.
104      *
105      * @param initialCapacity the initial capacity of the IntHashMap.
106      * @throws IllegalArgumentException if the initial capacity is less
107      * than zero.
108      */

109     public IntHashMap(int initialCapacity) {
110         this(initialCapacity, 0.75f);
111     }
112
113     /**
114      * Constructs a new, empty map with a default capacity and load
115      * factor, which is <tt>0.75</tt>.
116      */

117     public IntHashMap() {
118         this(101, 0.75f);
119     }
120
121     /**
122      * Constructs a new map with the same mappings as the given map. The
123      * map is created with a capacity of twice the number of mappings in
124      * the given map or 11 (whichever is greater), and a default load factor,
125      * which is <tt>0.75</tt>.
126      */

127     public IntHashMap(Map JavaDoc t) {
128         this(Math.max(2 * t.size(), 11), 0.75f);
129         putAll(t);
130     }
131     
132     /**
133      * Returns the number of key-value mappings in this map.
134      *
135      * @return the number of key-value mappings in this map.
136      */

137     public int size() {
138         return count;
139     }
140     
141     /**
142      * Returns <tt>true</tt> if this map contains no key-value mappings.
143      *
144      * @return <tt>true</tt> if this map contains no key-value mappings.
145      */

146     public boolean isEmpty() {
147         return count == 0;
148     }
149     
150     /**
151      * Returns <tt>true</tt> if this map maps one or more keys to the
152      * specified value.
153      *
154      * @param value value whose presence in this map is to be tested.
155      * @return <tt>true</tt> if this map maps one or more keys to the
156      * specified value.
157      */

158     public boolean containsValue(Object JavaDoc value) {
159         Entry tab[] = table;
160         
161         if (value == null) {
162             for (int i = tab.length ; i-- > 0 ;) {
163                 for (Entry e = tab[i] ; e != null ; e = e.next) {
164                     if (e.value == null) {
165                         return true;
166                     }
167                 }
168             }
169         } else {
170             for (int i = tab.length ; i-- > 0 ;) {
171                 for (Entry e = tab[i] ; e != null ; e = e.next) {
172                     if (value.equals(e.value)) {
173                         return true;
174                     }
175                 }
176             }
177         }
178         
179         return false;
180     }
181     
182     /**
183      * Returns <tt>true</tt> if this map contains a mapping for the specified
184      * key.
185      *
186      * @return <tt>true</tt> if this map contains a mapping for the specified
187      * key.
188      * @param key key whose presence in this Map is to be tested.
189      */

190     public boolean containsKey(Integer JavaDoc key) {
191         return containsKey(key.intValue());
192     }
193
194     /**
195      * Returns <tt>true</tt> if this map contains a mapping for the specified
196      * key.
197      *
198      * @return <tt>true</tt> if this map contains a mapping for the specified
199      * key.
200      * @param key key whose presence in this Map is to be tested.
201      */

202     public boolean containsKey(int key) {
203         Entry tab[] = table;
204
205         int index = (key & 0x7fffffff) % tab.length;
206         for (Entry e = tab[index]; e != null; e = e.next) {
207             if (e.key == key) {
208                 return true;
209             }
210         }
211         
212         return false;
213     }
214     
215     /**
216      * Returns the value to which this map maps the specified key. Returns
217      * <tt>null</tt> if the map contains no mapping for this key. A return
218      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
219      * map contains no mapping for the key; it's also possible that the map
220      * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
221      * operation may be used to distinguish these two cases.
222      *
223      * @return the value to which this map maps the specified key.
224      * @param key key whose associated value is to be returned.
225      */

226     public Object JavaDoc get(Integer JavaDoc key) {
227         return get(key.intValue());
228     }
229
230     /**
231      * Returns the value to which this map maps the specified key. Returns
232      * <tt>null</tt> if the map contains no mapping for this key. A return
233      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
234      * map contains no mapping for the key; it's also possible that the map
235      * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
236      * operation may be used to distinguish these two cases.
237      *
238      * @return the value to which this map maps the specified key.
239      * @param key key whose associated value is to be returned.
240      */

241     public Object JavaDoc get(int key) {
242         Entry tab[] = table;
243         
244         int index = (key & 0x7fffffff) % tab.length;
245         for (Entry e = tab[index]; e != null; e = e.next) {
246             if (e.key == key) {
247                 return e.value;
248             }
249         }
250         
251         return null;
252     }
253     
254     /**
255      * Rehashes the contents of this map into a new <tt>IntHashMap</tt> instance
256      * with a larger capacity. This method is called automatically when the
257      * number of keys in this map exceeds its capacity and load factor.
258      */

259     private void rehash() {
260         int oldCapacity = table.length;
261         Entry oldMap[] = table;
262         
263         int newCapacity = oldCapacity * 2 + 1;
264         Entry newMap[] = new Entry[newCapacity];
265         
266         modCount++;
267         threshold = (int)(newCapacity * loadFactor);
268         table = newMap;
269         
270         for (int i = oldCapacity ; i-- > 0 ;) {
271             for (Entry old = oldMap[i] ; old != null ; ) {
272                 Entry e = old;
273                 old = old.next;
274                 
275                 int index = (e.key & 0x7fffffff) % newCapacity;
276                 e.next = newMap[index];
277                 newMap[index] = e;
278             }
279         }
280     }
281     
282     /**
283      * Associates the specified value with the specified key in this map.
284      * If the map previously contained a mapping for this key, the old
285      * value is replaced.
286      *
287      * @param key key with which the specified value is to be associated.
288      * @param value value to be associated with the specified key.
289      * @return previous value associated with specified key, or <tt>null</tt>
290      * if there was no mapping for key. A <tt>null</tt> return can
291      * also indicate that the IntHashMap previously associated
292      * <tt>null</tt> with the specified key.
293      */

294     public Object JavaDoc put(Integer JavaDoc key, Object JavaDoc value) {
295         return put(key.intValue(), value);
296     }
297
298     /**
299      * Associates the specified value with the specified key in this map.
300      * If the map previously contained a mapping for this key, the old
301      * value is replaced.
302      *
303      * @param key key with which the specified value is to be associated.
304      * @param value value to be associated with the specified key.
305      * @return previous value associated with specified key, or <tt>null</tt>
306      * if there was no mapping for key. A <tt>null</tt> return can
307      * also indicate that the IntHashMap previously associated
308      * <tt>null</tt> with the specified key.
309      */

310     public Object JavaDoc put(int key, Object JavaDoc value) {
311         // Makes sure the key is not already in the IntHashMap.
312
Entry tab[] = table;
313         int index = 0;
314         
315         index = (key & 0x7fffffff) % tab.length;
316         for (Entry e = tab[index] ; e != null ; e = e.next) {
317             if (e.key == key) {
318                 Object JavaDoc old = e.value;
319                 e.value = value;
320                 return old;
321             }
322         }
323
324         modCount++;
325         if (count >= threshold) {
326             // Rehash the table if the threshold is exceeded
327
rehash();
328             
329             tab = table;
330             index = (key & 0x7fffffff) % tab.length;
331         }
332         
333         // Creates the new entry.
334
Entry e = new Entry(key, value, tab[index]);
335         tab[index] = e;
336         count++;
337         return null;
338     }
339     
340     /**
341      * Removes the mapping for this key from this map if present.
342      *
343      * @param key key whose mapping is to be removed from the map.
344      * @return previous value associated with specified key, or <tt>null</tt>
345      * if there was no mapping for key. A <tt>null</tt> return can
346      * also indicate that the map previously associated <tt>null</tt>
347      * with the specified key.
348      */

349     public Object JavaDoc remove(Integer JavaDoc key) {
350         return remove(key.intValue());
351     }
352
353     /**
354      * Removes the mapping for this key from this map if present.
355      *
356      * @param key key whose mapping is to be removed from the map.
357      * @return previous value associated with specified key, or <tt>null</tt>
358      * if there was no mapping for key. A <tt>null</tt> return can
359      * also indicate that the map previously associated <tt>null</tt>
360      * with the specified key.
361      */

362     public Object JavaDoc remove(int key) {
363         Entry tab[] = table;
364         
365         int index = (key & 0x7fffffff) % tab.length;
366         
367         for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
368             if (e.key == key) {
369                 modCount++;
370                 if (prev != null) {
371                     prev.next = e.next;
372                 } else {
373                     tab[index] = e.next;
374                 }
375                 
376                 count--;
377                 Object JavaDoc oldValue = e.value;
378                 e.value = null;
379                 return oldValue;
380             }
381         }
382         
383         return null;
384     }
385
386     /**
387      * Removes all mappings from this map.
388      */

389     public void clear() {
390         Entry tab[] = table;
391         modCount++;
392         for (int index = tab.length; --index >= 0; ) {
393             tab[index] = null;
394         }
395         count = 0;
396     }
397     
398     /**
399      * Returns a shallow copy of this <tt>IntHashMap</tt> instance: the keys and
400      * values themselves are not cloned.
401      *
402      * @return a shallow copy of this map.
403      */

404     public Object JavaDoc clone() {
405         try {
406             IntHashMap t = (IntHashMap) super.clone();
407             t.table = new Entry[table.length];
408             for (int i = table.length ; i-- > 0 ; ) {
409                 t.table[i] = (table[i] != null) ? (Entry) table[i].clone() : null;
410             }
411             t.keySet = null;
412             t.entrySet = null;
413             t.values = null;
414             t.modCount = 0;
415             return t;
416         } catch (CloneNotSupportedException JavaDoc e) {
417             // this shouldn't happen, since we are Cloneable
418
throw new InternalError JavaDoc();
419         }
420     }
421     
422     // Views
423

424     private transient Set JavaDoc keySet = null;
425     private transient Set JavaDoc entrySet = null;
426     private transient Collection JavaDoc values = null;
427     
428     /**
429      * Returns a set view of the keys contained in this map. The set is
430      * backed by the map, so changes to the map are reflected in the set, and
431      * vice-versa. The set supports element removal, which removes the
432      * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
433      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
434      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
435      * <tt>addAll</tt> operations.
436      *
437      * @return a set view of the keys contained in this map.
438      */

439     public Set JavaDoc keySet() {
440         if (keySet == null) {
441             keySet = new AbstractSet JavaDoc() {
442                 public Iterator JavaDoc iterator() {
443                     return new IntHashIterator(KEYS);
444                 }
445                 public int size() {
446                     return count;
447                 }
448                 public boolean contains(Object JavaDoc o) {
449                     return containsKey(o);
450                 }
451                 public boolean remove(Object JavaDoc o) {
452                     return IntHashMap.this.remove(o) != null;
453                 }
454                 public void clear() {
455                     IntHashMap.this.clear();
456                 }
457             };
458         }
459         return keySet;
460     }
461     
462     /**
463      * Returns a collection view of the values contained in this map. The
464      * collection is backed by the map, so changes to the map are reflected in
465      * the collection, and vice-versa. The collection supports element
466      * removal, which removes the corresponding mapping from this map, via the
467      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
468      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
469      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
470      *
471      * @return a collection view of the values contained in this map.
472      */

473     public Collection JavaDoc values() {
474         if (values==null) {
475             values = new AbstractCollection JavaDoc() {
476                 public Iterator JavaDoc iterator() {
477                     return (Iterator JavaDoc) new IntHashIterator(VALUES);
478                 }
479                 public int size() {
480                     return count;
481                 }
482                 public boolean contains(Object JavaDoc o) {
483                     return containsValue(o);
484                 }
485                 public void clear() {
486                     IntHashMap.this.clear();
487                 }
488             };
489         }
490         return values;
491     }
492
493     /**
494      * Returns a collection view of the mappings contained in this map. Each
495      * element in the returned collection is a <tt>Map.Entry</tt>. The
496      * collection is backed by the map, so changes to the map are reflected in
497      * the collection, and vice-versa. The collection supports element
498      * removal, which removes the corresponding mapping from the map, via the
499      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
500      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
501      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
502      *
503      * @return a collection view of the mappings contained in this map.
504      */

505     public Set JavaDoc entrySet() {
506         if (entrySet==null) {
507             entrySet = new AbstractSet JavaDoc() {
508                 public Iterator JavaDoc iterator() {
509                     return (Iterator JavaDoc) new IntHashIterator(ENTRIES);
510                 }
511                 
512                 public boolean contains(Object JavaDoc o) {
513                     if (!(o instanceof Map.Entry JavaDoc)) {
514                         return false;
515                     }
516                     Map.Entry JavaDoc entry = (Map.Entry JavaDoc) o;
517                     Integer JavaDoc key = (Integer JavaDoc) entry.getKey();
518                     Entry tab[] = table;
519                     int hash = (key == null ? 0 : key.hashCode());
520                     int index = (hash & 0x7fffffff) % tab.length;
521                     
522                     for (Entry e = tab[index]; e != null; e = e.next) {
523                         if (e.key == hash && e.equals(entry)) {
524                             return true;
525                         }
526                     }
527                     return false;
528                 }
529                 
530                 public boolean remove(Object JavaDoc o) {
531                     if (!(o instanceof Map.Entry JavaDoc)) {
532                         return false;
533                     }
534                     Map.Entry JavaDoc entry = (Map.Entry JavaDoc) o;
535                     Integer JavaDoc key = (Integer JavaDoc) entry.getKey();
536                     Entry tab[] = table;
537                     int hash = (key == null ? 0 : key.hashCode());
538                     int index = (hash & 0x7fffffff) % tab.length;
539                     
540                     for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
541                         if (e.key == hash && e.equals(entry)) {
542                             modCount++;
543                             if (prev != null) {
544                                 prev.next = e.next;
545                             } else {
546                                 tab[index] = e.next;
547                             }
548                             
549                             count--;
550                             e.value = null;
551                             return true;
552                         }
553                     }
554                     return false;
555                 }
556                 
557                 public int size() {
558                     return count;
559                 }
560                 
561                 public void clear() {
562                     IntHashMap.this.clear();
563                 }
564             };
565         }
566         
567         return entrySet;
568     }
569     
570     /**
571      * IntHashMap collision list entry.
572      */

573     private static class Entry implements Map.Entry JavaDoc {
574         int key;
575         Object JavaDoc value;
576         Entry next;
577         private Integer JavaDoc objectKey;
578         
579         Entry(int key, Object JavaDoc value, Entry next) {
580             this.key = key;
581             this.value = value;
582             this.next = next;
583         }
584         
585         protected Object JavaDoc clone() {
586             return new Entry(key, value, (next == null ? null : (Entry) next.clone()));
587         }
588         
589         // Map.Entry Ops
590

591         public Object JavaDoc getKey() {
592             return (objectKey != null) ? objectKey : (objectKey = new Integer JavaDoc(key));
593         }
594         
595         public Object JavaDoc getValue() {
596             return value;
597         }
598         
599         public Object JavaDoc setValue(Object JavaDoc value) {
600             Object JavaDoc oldValue = this.value;
601             this.value = value;
602             return oldValue;
603         }
604         
605         public boolean equals(Object JavaDoc o) {
606             if (!(o instanceof Map.Entry JavaDoc)) {
607                 return false;
608             }
609             Map.Entry JavaDoc e = (Map.Entry JavaDoc) o;
610             
611             return (getKey().equals(e.getKey())) &&
612                 (value==null ? e.getValue()==null : value.equals(e.getValue()));
613         }
614         
615         public int hashCode() {
616             return key ^ (value==null ? 0 : value.hashCode());
617         }
618         
619         public String JavaDoc toString() {
620             return String.valueOf(key) + "=" + value;
621         }
622     }
623     
624     // Types of Iterators
625
private static final int KEYS = 0;
626     private static final int VALUES = 1;
627     private static final int ENTRIES = 2;
628     
629     private class IntHashIterator implements Iterator JavaDoc {
630         Entry[] table = IntHashMap.this.table;
631         int index = table.length;
632         Entry entry;
633         Entry lastReturned;
634         int type;
635         
636         /**
637          * The modCount value that the iterator believes that the backing
638          * List should have. If this expectation is violated, the iterator
639          * has detected concurrent modification.
640          */

641         private int expectedModCount = modCount;
642         
643         IntHashIterator(int type) {
644             this.type = type;
645         }
646         
647         public boolean hasNext() {
648             while (entry == null && index > 0) {
649                 entry = table[--index];
650             }
651             
652             return entry != null;
653         }
654         
655         public Object JavaDoc next() {
656             if (modCount != expectedModCount) {
657                 throw new ConcurrentModificationException JavaDoc();
658             }
659             
660             while (entry == null && index > 0) {
661                 entry = table[--index];
662             }
663             
664             if (entry != null) {
665                 Entry e = lastReturned = entry;
666                 entry = e.next;
667                 return type == KEYS ? e.getKey() : (type == VALUES ? e.value : e);
668             }
669             throw new NoSuchElementException JavaDoc();
670         }
671         
672         public void remove() {
673             if (lastReturned == null) {
674                 throw new IllegalStateException JavaDoc();
675             }
676             if (modCount != expectedModCount) {
677                 throw new ConcurrentModificationException JavaDoc();
678             }
679             
680             Entry[] tab = IntHashMap.this.table;
681             int index = (lastReturned.key & 0x7fffffff) % tab.length;
682             
683             for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
684                 if (e == lastReturned) {
685                     modCount++;
686                     expectedModCount++;
687                     if (prev == null) {
688                         tab[index] = e.next;
689                     } else {
690                         prev.next = e.next;
691                     }
692                     count--;
693                     lastReturned = null;
694                     return;
695                 }
696             }
697             throw new ConcurrentModificationException JavaDoc();
698         }
699     }
700     
701     /**
702      * Save the state of the <tt>IntHashMap</tt> instance to a stream (i.e.,
703      * serialize it).
704      *
705      * @serialData The <i>capacity</i> of the IntHashMap (the length of the
706      * bucket array) is emitted (int), followed by the
707      * <i>size</i> of the IntHashMap (the number of key-value
708      * mappings), followed by the key (Object) and value (Object)
709      * for each key-value mapping represented by the IntHashMap
710      * The key-value mappings are emitted in no particular order.
711      */

712     private void writeObject(java.io.ObjectOutputStream JavaDoc s) throws IOException JavaDoc {
713         // Write out the threshold, loadfactor, and any hidden stuff
714
s.defaultWriteObject();
715         
716         // Write out number of buckets
717
s.writeInt(table.length);
718         
719         // Write out size (number of Mappings)
720
s.writeInt(count);
721         
722         // Write out keys and values (alternating)
723
for (int index = table.length - 1; index >= 0; index--) {
724             Entry entry = table[index];
725             
726             while (entry != null) {
727                 s.writeInt(entry.key);
728                 s.writeObject(entry.value);
729                 entry = entry.next;
730             }
731         }
732     }
733     
734     /**
735      * Reconstitute the <tt>IntHashMap</tt> instance from a stream (i.e.,
736      * deserialize it).
737      */

738     private void readObject(java.io.ObjectInputStream JavaDoc s)
739         throws IOException JavaDoc, ClassNotFoundException JavaDoc
740     {
741         // Read in the threshold, loadfactor, and any hidden stuff
742
s.defaultReadObject();
743         
744         // Read in number of buckets and allocate the bucket array;
745
int numBuckets = s.readInt();
746         table = new Entry[numBuckets];
747         
748         // Read in size (number of Mappings)
749
int size = s.readInt();
750         
751         // Read the keys and values, and put the mappings in the IntHashMap
752
for (int i=0; i<size; i++) {
753             int key = s.readInt();
754             Object JavaDoc value = s.readObject();
755             put(key, value);
756         }
757     }
758     
759     int capacity() {
760         return table.length;
761     }
762     
763     float loadFactor() {
764         return loadFactor;
765     }
766 }
767
Popular Tags