Java > Open Source Codes > java > util > HashMap


1 /*
2  * @(#)HashMap.java 1.68 06/06/27
3  *
4  * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package java.util;
9 import java.io.*;
10
11 /**
12  * Hash table based implementation of the <tt>Map</tt> interface. This
13  * implementation provides all of the optional map operations, and permits
14  * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
15  * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
16  * unsynchronized and permits nulls.) This class makes no guarantees as to
17  * the order of the map; in particular, it does not guarantee that the order
18  * will remain constant over time.
19  *
20  * <p>This implementation provides constant-time performance for the basic
21  * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
22  * disperses the elements properly among the buckets. Iteration over
23  * collection views requires time proportional to the "capacity" of the
24  * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
25  * of key-value mappings). Thus, it's very important not to set the initial
26  * capacity too high (or the load factor too low) if iteration performance is
27  * important.
28  *
29  * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
30  * performance: <i>initial capacity</i> and <i>load factor</i>. The
31  * <i>capacity</i> is the number of buckets in the hash table, and the initial
32  * capacity is simply the capacity at the time the hash table is created. The
33  * <i>load factor</i> is a measure of how full the hash table is allowed to
34  * get before its capacity is automatically increased. When the number of
35  * entries in the hash table exceeds the product of the load factor and the
36  * current capacity, the capacity is roughly doubled by calling the
37  * <tt>rehash</tt> method.
38  *
39  * <p>As a general rule, the default load factor (.75) offers a good tradeoff
40  * between time and space costs. Higher values decrease the space overhead
41  * but increase the lookup cost (reflected in most of the operations of the
42  * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
43  * expected number of entries in the map and its load factor should be taken
44  * into account when setting its initial capacity, so as to minimize the
45  * number of <tt>rehash</tt> operations. If the initial capacity is greater
46  * than the maximum number of entries divided by the load factor, no
47  * <tt>rehash</tt> operations will ever occur.
48  *
49  * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
50  * creating it with a sufficiently large capacity will allow the mappings to
51  * be stored more efficiently than letting it perform automatic rehashing as
52  * needed to grow the table.
53  *
54  * <p><b>Note that this implementation is not synchronized.</b> If multiple
55  * threads access this map concurrently, and at least one of the threads
56  * modifies the map structurally, it <i>must</i> be synchronized externally.
57  * (A structural modification is any operation that adds or deletes one or
58  * more mappings; merely changing the value associated with a key that an
59  * instance already contains is not a structural modification.) This is
60  * typically accomplished by synchronizing on some object that naturally
61  * encapsulates the map. If no such object exists, the map should be
62  * "wrapped" using the <tt>Collections.synchronizedMap</tt> method. This is
63  * best done at creation time, to prevent accidental unsynchronized access to
64  * the map: <pre> Map m = Collections.synchronizedMap(new HashMap(...));
65  * </pre>
66  *
67  * <p>The iterators returned by all of this class's "collection view methods"
68  * are <i>fail-fast</i>: if the map is structurally modified at any time after
69  * the iterator is created, in any way except through the iterator's own
70  * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
71  * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
72  * modification, the iterator fails quickly and cleanly, rather than risking
73  * arbitrary, non-deterministic behavior at an undetermined time in the
74  * future.
75  *
76  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
77  * as it is, generally speaking, impossible to make any hard guarantees in the
78  * presence of unsynchronized concurrent modification. Fail-fast iterators
79  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
80  * Therefore, it would be wrong to write a program that depended on this
81  * exception for its correctness: <i>the fail-fast behavior of iterators
82  * should be used only to detect bugs.</i>
83  *
84  * <p>This class is a member of the
85  * <a HREF="{@docRoot}/../guide/collections/index.html">
86  * Java Collections Framework</a>.
87  *
88  * @author Doug Lea
89  * @author Josh Bloch
90  * @author Arthur van Hoff
91  * @author Neal Gafter
92  * @version 1.65, 03/03/05
93  * @see Object#hashCode()
94  * @see Collection
95  * @see Map
96  * @see TreeMap
97  * @see Hashtable
98  * @since 1.2
99  */
100
101 public class HashMap<K,V>
102     extends AbstractMap <K,V>
103     implements Map <K,V>, Cloneable , Serializable
104 {
105
106     /**
107      * The default initial capacity - MUST be a power of two.
108      */
109     static final int DEFAULT_INITIAL_CAPACITY = 16;
110
111     /**
112      * The maximum capacity, used if a higher value is implicitly specified
113      * by either of the constructors with arguments.
114      * MUST be a power of two <= 1<<30.
115      */
116     static final int MAXIMUM_CAPACITY = 1 << 30;
117
118     /**
119      * The load factor used when none specified in constructor.
120      **/
121     static final float DEFAULT_LOAD_FACTOR = 0.75f;
122
123     /**
124      * The table, resized as necessary. Length MUST Always be a power of two.
125      */
126     transient Entry[] table;
127
128     /**
129      * The number of key-value mappings contained in this identity hash map.
130      */
131     transient int size;
132   
133     /**
134      * The next size value at which to resize (capacity * load factor).
135      * @serial
136      */
137     int threshold;
138   
139     /**
140      * The load factor for the hash table.
141      *
142      * @serial
143      */
144     final float loadFactor;
145
146     /**
147      * The number of times this HashMap has been structurally modified
148      * Structural modifications are those that change the number of mappings in
149      * the HashMap or otherwise modify its internal structure (e.g.,
150      * rehash). This field is used to make iterators on Collection-views of
151      * the HashMap fail-fast. (See ConcurrentModificationException).
152      */
153     transient volatile int modCount;
154
155     /**
156      * Constructs an empty <tt>HashMap</tt> with the specified initial
157      * capacity and load factor.
158      *
159      * @param initialCapacity The initial capacity.
160      * @param loadFactor The load factor.
161      * @throws IllegalArgumentException if the initial capacity is negative
162      * or the load factor is nonpositive.
163      */
164     public HashMap(int initialCapacity, float loadFactor) {
165         if (initialCapacity < 0)
166             throw new IllegalArgumentException ("Illegal initial capacity: " +
167                                                initialCapacity);
168         if (initialCapacity > MAXIMUM_CAPACITY)
169             initialCapacity = MAXIMUM_CAPACITY;
170         if (loadFactor <= 0 || Float.isNaN(loadFactor))
171             throw new IllegalArgumentException ("Illegal load factor: " +
172                                                loadFactor);
173
174         // Find a power of 2 >= initialCapacity
175 int capacity = 1;
176         while (capacity < initialCapacity)
177             capacity <<= 1;
178     
179         this.loadFactor = loadFactor;
180         threshold = (int)(capacity * loadFactor);
181         table = new Entry[capacity];
182         init();
183     }
184   
185     /**
186      * Constructs an empty <tt>HashMap</tt> with the specified initial
187      * capacity and the default load factor (0.75).
188      *
189      * @param initialCapacity the initial capacity.
190      * @throws IllegalArgumentException if the initial capacity is negative.
191      */
192     public HashMap(int initialCapacity) {
193         this(initialCapacity, DEFAULT_LOAD_FACTOR);
194     }
195
196     /**
197      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
198      * (16) and the default load factor (0.75).
199      */
200     public HashMap() {
201         this.loadFactor = DEFAULT_LOAD_FACTOR;
202         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
203         table = new Entry[DEFAULT_INITIAL_CAPACITY];
204         init();
205     }
206
207     /**
208      * Constructs a new <tt>HashMap</tt> with the same mappings as the
209      * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
210      * default load factor (0.75) and an initial capacity sufficient to
211      * hold the mappings in the specified <tt>Map</tt>.
212      *
213      * @param m the map whose mappings are to be placed in this map.
214      * @throws NullPointerException if the specified map is null.
215      */
216     public HashMap(Map <? extends K, ? extends V> m) {
217         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
218                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
219         putAllForCreate(m);
220     }
221
222     // internal utilities
223
224     /**
225      * Initialization hook for subclasses. This method is called
226      * in all constructors and pseudo-constructors (clone, readObject)
227      * after HashMap has been initialized but before any entries have
228      * been inserted. (In the absence of this method, readObject would
229      * require explicit knowledge of subclasses.)
230      */
231     void init() {
232     }
233
234     /**
235      * Value representing null keys inside tables.
236      */
237     static final Object NULL_KEY = new Object ();
238
239     /**
240      * Returns internal representation for key. Use NULL_KEY if key is null.
241      */
242     static <T> T maskNull(T key) {
243         return key == null ? (T)NULL_KEY : key;
244     }
245
246     /**
247      * Returns key represented by specified internal representation.
248      */
249     static <T> T unmaskNull(T key) {
250         return (key == NULL_KEY ? null : key);
251     }
252
253     /**
254      * Whether to prefer the old supplemental hash function, for
255      * compatibility with broken applications that rely on the
256      * internal hashing order.
257      *
258      * Set to true only by hotspot when invoked via
259      * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
260      */
261     private static final boolean useNewHash;
262     static { useNewHash = false; }
263
264     private static int oldHash(int h) {
265         h += ~(h << 9);
266         h ^= (h >>> 14);
267         h += (h << 4);
268         h ^= (h >>> 10);
269         return h;
270     }
271
272     private static int newHash(int h) {
273         // This function ensures that hashCodes that differ only by
274 // constant multiples at each bit position have a bounded
275 // number of collisions (approximately 8 at default load factor).
276 h ^= (h >>> 20) ^ (h >>> 12);
277         return h ^ (h >>> 7) ^ (h >>> 4);
278     }
279
280     /**
281      * Applies a supplemental hash function to a given hashCode, which
282      * defends against poor quality hash functions. This is critical
283      * because HashMap uses power-of-two length hash tables, that
284      * otherwise encounter collisions for hashCodes that do not differ
285      * in lower bits.
286      */
287     static int hash(int h) {
288     return useNewHash ? newHash(h) : oldHash(h);
289     }
290
291     static int hash(Object key) {
292     return hash(key.hashCode());
293     }
294
295     /**
296      * Check for equality of non-null reference x and possibly-null y.
297      */
298     static boolean eq(Object x, Object y) {
299         return x == y || x.equals(y);
300     }
301
302     /**
303      * Returns index for hash code h.
304      */
305     static int indexFor(int h, int length) {
306         return h & (length-1);
307     }
308  
309     /**
310      * Returns the number of key-value mappings in this map.
311      *
312      * @return the number of key-value mappings in this map.
313      */
314     public int size() {
315         return size;
316     }
317   
318     /**
319      * Returns <tt>true</tt> if this map contains no key-value mappings.
320      *
321      * @return <tt>true</tt> if this map contains no key-value mappings.
322      */
323     public boolean isEmpty() {
324         return size == 0;
325     }
326
327     /**
328      * Returns the value to which the specified key is mapped in this identity
329      * hash map, or <tt>null</tt> if the map contains no mapping for this key.
330      * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
331      * that the map contains no mapping for the key; it is also possible that
332      * the map explicitly maps the key to <tt>null</tt>. The
333      * <tt>containsKey</tt> method may be used to distinguish these two cases.
334      *
335      * @param key the key whose associated value is to be returned.
336      * @return the value to which this map maps the specified key, or
337      * <tt>null</tt> if the map contains no mapping for this key.
338      * @see #put(Object, Object)
339      */
340     public V get(Object key) {
341     if (key == null)
342         return getForNullKey();
343         int hash = hash(key.hashCode());
344         for (Entry<K,V> e = table[indexFor(hash, table.length)];
345              e != null;
346              e = e.next) {
347             Object k;
348             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
349                 return e.value;
350         }
351         return null;
352     }
353
354     private V getForNullKey() {
355         int hash = hash(NULL_KEY.hashCode());
356         int i = indexFor(hash, table.length);
357         Entry<K,V> e = table[i];
358         while (true) {
359             if (e == null)
360                 return null;
361             if (e.key == NULL_KEY)
362                 return e.value;
363             e = e.next;
364         }
365     }
366
367     /**
368      * Returns <tt>true</tt> if this map contains a mapping for the
369      * specified key.
370      *
371      * @param key The key whose presence in this map is to be tested
372      * @return <tt>true</tt> if this map contains a mapping for the specified
373      * key.
374      */
375     public boolean containsKey(Object key) {
376         Object k = maskNull(key);
377         int hash = hash(k.hashCode());
378         int i = indexFor(hash, table.length);
379         Entry e = table[i];
380         while (e != null) {
381             if (e.hash == hash && eq(k, e.key))
382                 return true;
383             e = e.next;
384         }
385         return false;
386     }
387
388     /**
389      * Returns the entry associated with the specified key in the
390      * HashMap. Returns null if the HashMap contains no mapping
391      * for this key.
392      */
393     Entry<K,V> getEntry(Object key) {
394         Object k = maskNull(key);
395         int hash = hash(k.hashCode());
396         int i = indexFor(hash, table.length);
397         Entry<K,V> e = table[i];
398         while (e != null && !(e.hash == hash && eq(k, e.key)))
399             e = e.next;
400         return e;
401     }
402   
403     /**
404      * Associates the specified value with the specified key in this map.
405      * If the map previously contained a mapping for this key, the old
406      * value is replaced.
407      *
408      * @param key key with which the specified value is to be associated.
409      * @param value value to be associated with the specified key.
410      * @return previous value associated with specified key, or <tt>null</tt>
411      * if there was no mapping for key. A <tt>null</tt> return can
412      * also indicate that the HashMap previously associated
413      * <tt>null</tt> with the specified key.
414      */
415     public V put(K key, V value) {
416     if (key == null)
417         return putForNullKey(value);
418         int hash = hash(key.hashCode());
419         int i = indexFor(hash, table.length);
420         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
421             Object k;
422             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
423                 V oldValue = e.value;
424                 e.value = value;
425                 e.recordAccess(this);
426                 return oldValue;
427             }
428         }
429
430         modCount++;
431         addEntry(hash, key, value, i);
432         return null;
433     }
434
435     private V putForNullKey(V value) {
436         int hash = hash(NULL_KEY.hashCode());
437         int i = indexFor(hash, table.length);
438
439         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
440             if (e.key == NULL_KEY) {
441                 V oldValue = e.value;
442                 e.value = value;
443                 e.recordAccess(this);
444                 return oldValue;
445             }
446         }
447
448         modCount++;
449         addEntry(hash, (K) NULL_KEY, value, i);
450         return null;
451     }
452
453     /**
454      * This method is used instead of put by constructors and
455      * pseudoconstructors (clone, readObject). It does not resize the table,
456      * check for comodification, etc. It calls createEntry rather than
457      * addEntry.
458      */
459     private void putForCreate(K key, V value) {
460         K k = maskNull(key);
461         int hash = hash(k.hashCode());
462         int i = indexFor(hash, table.length);
463
464         /**
465          * Look for preexisting entry for key. This will never happen for
466          * clone or deserialize. It will only happen for construction if the
467          * input Map is a sorted map whose ordering is inconsistent w/ equals.
468          */
469         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
470             if (e.hash == hash && eq(k, e.key)) {
471                 e.value = value;
472                 return;
473             }
474         }
475
476         createEntry(hash, k, value, i);
477     }
478
479     void putAllForCreate(Map <? extends K, ? extends V> m) {
480         for (Iterator <? extends Map.Entry <? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
481             Map.Entry <? extends K, ? extends V> e = i.next();
482             putForCreate(e.getKey(), e.getValue());
483         }
484     }
485
486     /**
487      * Rehashes the contents of this map into a new array with a
488      * larger capacity. This method is called automatically when the
489      * number of keys in this map reaches its threshold.
490      *
491      * If current capacity is MAXIMUM_CAPACITY, this method does not
492      * resize the map, but sets threshold to Integer.MAX_VALUE.
493      * This has the effect of preventing future calls.
494      *
495      * @param newCapacity the new capacity, MUST be a power of two;
496      * must be greater than current capacity unless current
497      * capacity is MAXIMUM_CAPACITY (in which case value
498      * is irrelevant).
499      */
500     void resize(int newCapacity) {
501         Entry[] oldTable = table;
502         int oldCapacity = oldTable.length;
503         if (oldCapacity == MAXIMUM_CAPACITY) {
504             threshold = Integer.MAX_VALUE;
505             return;
506         }
507
508         Entry[] newTable = new Entry[newCapacity];
509         transfer(newTable);
510         table = newTable;
511         threshold = (int)(newCapacity * loadFactor);
512     }
513
514     /**
515      * Transfer all entries from current table to newTable.
516      */
517     void transfer(Entry[] newTable) {
518         Entry[] src = table;
519         int newCapacity = newTable.length;
520         for (int j = 0; j < src.length; j++) {
521             Entry<K,V> e = src[j];
522             if (e != null) {
523                 src[j] = null;
524                 do {
525                     Entry<K,V> next = e.next;
526                     int i = indexFor(e.hash, newCapacity);
527                     e.next = newTable[i];
528                     newTable[i] = e;
529                     e = next;
530                 } while (e != null);
531             }
532         }
533     }
534
535     /**
536      * Copies all of the mappings from the specified map to this map
537      * These mappings will replace any mappings that
538      * this map had for any of the keys currently in the specified map.
539      *
540      * @param m mappings to be stored in this map.
541      * @throws NullPointerException if the specified map is null.
542      */
543     public void putAll(Map <? extends K, ? extends V> m) {
544         int numKeysToBeAdded = m.size();
545         if (numKeysToBeAdded == 0)
546             return;
547
548         /*
549          * Expand the map if the map if the number of mappings to be added
550          * is greater than or equal to threshold. This is conservative; the
551          * obvious condition is (m.size() + size) >= threshold, but this
552          * condition could result in a map with twice the appropriate capacity,
553          * if the keys to be added overlap with the keys already in this map.
554          * By using the conservative calculation, we subject ourself
555          * to at most one extra resize.
556          */
557         if (numKeysToBeAdded > threshold) {
558             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
559             if (targetCapacity > MAXIMUM_CAPACITY)
560                 targetCapacity = MAXIMUM_CAPACITY;
561             int newCapacity = table.length;
562             while (newCapacity < targetCapacity)
563                 newCapacity <<= 1;
564             if (newCapacity > table.length)
565                 resize(newCapacity);
566         }
567
568         for (Iterator <? extends Map.Entry <? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
569             Map.Entry <? extends K, ? extends V> e = i.next();
570             put(e.getKey(), e.getValue());
571         }
572     }
573   
574     /**
575      * Removes the mapping for this key from this map if present.
576      *
577      * @param key key whose mapping is to be removed from the map.
578      * @return previous value associated with specified key, or <tt>null</tt>
579      * if there was no mapping for key. A <tt>null</tt> return can
580      * also indicate that the map previously associated <tt>null</tt>
581      * with the specified key.
582      */
583     public V remove(Object key) {
584         Entry<K,V> e = removeEntryForKey(key);
585         return (e == null ? null : e.value);
586     }
587
588     /**
589      * Removes and returns the entry associated with the specified key
590      * in the HashMap. Returns null if the HashMap contains no mapping
591      * for this key.
592      */
593     Entry<K,V> removeEntryForKey(Object key) {
594         Object k = maskNull(key);
595         int hash = hash(k.hashCode());
596         int i = indexFor(hash, table.length);
597         Entry<K,V> prev = table[i];
598         Entry<K,V> e = prev;
599
600         while (e != null) {
601             Entry<K,V> next = e.next;
602             if (e.hash == hash && eq(k, e.key)) {
603                 modCount++;
604                 size--;
605                 if (prev == e)
606                     table[i] = next;
607                 else
608                     prev.next = next;
609                 e.recordRemoval(this);
610                 return e;
611             }
612             prev = e;
613             e = next;
614         }
615    
616         return e;
617     }
618
619     /**
620      * Special version of remove for EntrySet.
621      */
622     Entry<K,V> removeMapping(Object o) {
623         if (!(o instanceof Map.Entry ))
624             return null;
625
626         Map.Entry <K,V> entry = (Map.Entry <K,V>) o;
627         Object k = maskNull(entry.getKey());
628         int hash = hash(k.hashCode());
629         int i = indexFor(hash, table.length);
630         Entry<K,V> prev = table[i];
631         Entry<K,V> e = prev;
632
633         while (e != null) {
634             Entry<K,V> next = e.next;
635             if (e.hash == hash && e.equals(entry)) {
636                 modCount++;
637                 size--;
638                 if (prev == e)
639                     table[i] = next;
640                 else
641                     prev.next = next;
642                 e.recordRemoval(this);
643                 return e;
644             }
645             prev = e;
646             e = next;
647         }
648    
649         return e;
650     }
651
652     /**
653      * Removes all mappings from this map.
654      */
655     public void clear() {
656         modCount++;
657         Entry[] tab = table;
658         for (int i = 0; i < tab.length; i++)
659             tab[i] = null;
660         size = 0;
661     }
662
663     /**
664      * Returns <tt>true</tt> if this map maps one or more keys to the
665      * specified value.
666      *
667      * @param value value whose presence in this map is to be tested.
668      * @return <tt>true</tt> if this map maps one or more keys to the
669      * specified value.
670      */
671     public boolean containsValue(Object value) {
672     if (value == null)
673             return containsNullValue();
674
675     Entry[] tab = table;
676         for (int i = 0; i < tab.length ; i++)
677             for (Entry e = tab[i] ; e != null ; e = e.next)
678                 if (value.equals(e.value))
679                     return true;
680     return false;
681     }
682
683     /**
684      * Special-case code for containsValue with null argument
685      **/
686     private boolean containsNullValue() {
687     Entry[] tab = table;
688         for (int i = 0; i < tab.length ; i++)
689             for (Entry e = tab[i] ; e != null ; e = e.next)
690                 if (e.value == null)
691                     return true;
692     return false;
693     }
694
695     /**
696      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
697      * values themselves are not cloned.
698      *
699      * @return a shallow copy of this map.
700      */
701     public Object clone() {
702         HashMap <K,V> result = null;
703     try {
704         result = (HashMap <K,V>)super.clone();
705     } catch (CloneNotSupportedException e) {
706         // assert false;
707 }
708         result.table = new Entry[table.length];
709         result.entrySet = null;
710         result.modCount = 0;
711         result.size = 0;
712         result.init();
713         result.putAllForCreate(this);
714
715         return result;
716     }
717
718     static class Entry<K,V> implements Map.Entry <K,V> {
719         final K key;
720         V value;
721         final int hash;
722         Entry<K,V> next;
723
724         /**
725          * Create new entry.
726          */
727         Entry(int h, K k, V v, Entry<K,V> n) {
728             value = v;
729             next = n;
730             key = k;
731             hash = h;
732         }
733
734         public K getKey() {
735             return HashMap.<K>unmaskNull(key);
736         }
737
738         public V getValue() {
739             return value;
740         }
741     
742         public V setValue(V newValue) {
743         V oldValue = value;
744             value = newValue;
745             return oldValue;
746         }
747     
748         public boolean equals(Object o) {
749             if (!(o instanceof Map.Entry ))
750                 return false;
751             Map.Entry e = (Map.Entry )o;
752             Object k1 = getKey();
753             Object k2 = e.getKey();
754             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
755                 Object v1 = getValue();
756                 Object v2 = e.getValue();
757                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
758                     return true;
759             }
760             return false;
761         }
762     
763         public int hashCode() {
764             return (key==NULL_KEY ? 0 : key.hashCode()) ^
765                    (value==null ? 0 : value.hashCode());
766         }
767     
768         public String toString() {
769             return getKey() + "=" + getValue();
770         }
771
772         /**
773          * This method is invoked whenever the value in an entry is
774          * overwritten by an invocation of put(k,v) for a key k that's already
775          * in the HashMap.
776          */
777         void recordAccess(HashMap <K,V> m) {
778         }
779
780         /**
781          * This method is invoked whenever the entry is
782          * removed from the table.
783          */
784         void recordRemoval(HashMap <K,V> m) {
785         }
786     }
787
788     /**
789      * Add a new entry with the specified key, value and hash code to
790      * the specified bucket. It is the responsibility of this
791      * method to resize the table if appropriate.
792      *
793      * Subclass overrides this to alter the behavior of put method.
794      */
795     void addEntry(int hash, K key, V value, int bucketIndex) {
796     Entry<K,V> e = table[bucketIndex];
797         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
798         if (size++ >= threshold)
799             resize(2 * table.length);
800     }
801
802     /**
803      * Like addEntry except that this version is used when creating entries
804      * as part of Map construction or "pseudo-construction" (cloning,
805      * deserialization). This version needn't worry about resizing the table.
806      *
807      * Subclass overrides this to alter the behavior of HashMap(Map),
808      * clone, and readObject.
809      */
810     void createEntry(int hash, K key, V value, int bucketIndex) {
811     Entry<K,V> e = table[bucketIndex];
812         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
813         size++;
814     }
815
816     private abstract class HashIterator<E> implements Iterator <E> {
817         Entry<K,V> next; // next entry to return
818 int expectedModCount; // For fast-fail
819 int index; // current slot
820 Entry<K,V> current; // current entry
821
822         HashIterator() {
823             expectedModCount = modCount;
824             Entry[] t = table;
825             int i = t.length;
826             Entry<K,V> n = null;
827             if (size != 0) { // advance to first entry
828 while (i > 0 && (n = t[--i]) == null)
829                     ;
830             }
831             next = n;
832             index = i;
833         }
834
835         public boolean hasNext() {
836             return next != null;
837         }
838
839         Entry<K,V> nextEntry() {
840             if (modCount != expectedModCount)
841                 throw new ConcurrentModificationException ();
842             Entry<K,V> e = next;
843             if (e == null)
844                 throw new NoSuchElementException ();
845                 
846             Entry<K,V> n = e.next;
847             Entry[] t = table;
848             int i = index;
849             while (n == null && i > 0)
850                 n = t[--i];
851             index = i;
852             next = n;
853             return current = e;
854         }
855
856         public void remove() {
857             if (current == null)
858                 throw new IllegalStateException ();
859             if (modCount != expectedModCount)
860                 throw new ConcurrentModificationException ();
861             Object k = current.key;
862             current = null;
863             HashMap.this.removeEntryForKey(k);
864             expectedModCount = modCount;
865         }
866
867     }
868
869     private class ValueIterator extends HashIterator<V> {
870         public V next() {
871             return nextEntry().value;
872         }
873     }
874
875     private class KeyIterator extends HashIterator<K> {
876         public K next() {
877             return nextEntry().getKey();
878         }
879     }
880
881     private class EntryIterator extends HashIterator<Map.Entry <K,V>> {
882         public Map.Entry <K,V> next() {
883             return nextEntry();
884         }
885     }
886
887     // Subclass overrides these to alter behavior of views' iterator() method
888 Iterator <K> newKeyIterator() {
889         return new KeyIterator();
890     }
891     Iterator <V> newValueIterator() {
892         return new ValueIterator();
893     }
894     Iterator <Map.Entry <K,V>> newEntryIterator() {
895         return new EntryIterator();
896     }
897
898
899     // Views
900
901     private transient Set <Map.Entry <K,V>> entrySet = null;
902
903     /**
904      * Returns a set view of the keys contained in this map. The set is
905      * backed by the map, so changes to the map are reflected in the set, and
906      * vice-versa. The set supports element removal, which removes the
907      * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
908      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
909      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
910      * <tt>addAll</tt> operations.
911      *
912      * @return a set view of the keys contained in this map.
913      */
914     public Set <K> keySet() {
915         Set <K> ks = keySet;
916         return (ks != null ? ks : (keySet = new KeySet()));
917     }
918
919     private class KeySet extends AbstractSet <K> {
920         public Iterator <K> iterator() {
921             return newKeyIterator();
922         }
923         public int size() {
924             return size;
925         }
926         public boolean contains(Object o) {
927             return containsKey(o);
928         }
929         public boolean remove(Object o) {
930             return HashMap.this.removeEntryForKey(o) != null;
931         }
932         public void clear() {
933             HashMap.this.clear();
934         }
935     }
936
937     /**
938      * Returns a collection view of the values contained in this map. The
939      * collection is backed by the map, so changes to the map are reflected in
940      * the collection, and vice-versa. The collection supports element
941      * removal, which removes the corresponding mapping from this map, via the
942      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
943      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
944      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
945      *
946      * @return a collection view of the values contained in this map.
947      */
948     public Collection <V> values() {
949         Collection <V> vs = values;
950         return (vs != null ? vs : (values = new Values()));
951     }
952
953     private class Values extends AbstractCollection <V> {
954         public Iterator <V> iterator() {
955             return newValueIterator();
956         }
957         public int size() {
958             return size;
959         }
960         public boolean contains(Object o) {
961             return containsValue(o);
962         }
963         public void clear() {
964             HashMap.this.clear();
965         }
966     }
967
968     /**
969      * Returns a collection view of the mappings contained in this map. Each
970      * element in the returned collection is a <tt>Map.Entry</tt>. The
971      * collection is backed by the map, so changes to the map are reflected in
972      * the collection, and vice-versa. The collection supports element
973      * removal, which removes the corresponding mapping from the map, via the
974      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
975      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
976      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
977      *
978      * @return a collection view of the mappings contained in this map.
979      * @see Map.Entry
980      */
981     public Set <Map.Entry <K,V>> entrySet() {
982         Set <Map.Entry <K,V>> es = entrySet;
983         return (es != null ? es : (entrySet = (Set <Map.Entry <K,V>>) (Set ) new EntrySet()));
984     }
985
986     private class EntrySet extends AbstractSet /*<Map.Entry<K,V>>*/ {
987         public Iterator /*<Map.Entry<K,V>>*/ iterator() {
988             return newEntryIterator();
989         }
990         public boolean contains(Object o) {
991             if (!(o instanceof Map.Entry ))
992                 return false;
993             Map.Entry <K,V> e = (Map.Entry <K,V>) o;
994             Entry<K,V> candidate = getEntry(e.getKey());
995             return candidate != null && candidate.equals(e);
996         }
997         public boolean remove(Object o) {
998             return removeMapping(o) != null;
999         }
1000        public int size() {
1001            return size;
1002        }
1003        public void clear() {
1004            HashMap.this.clear();
1005        }
1006    }
1007
1008    /**
1009     * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1010     * serialize it).
1011     *
1012     * @serialData The <i>capacity</i> of the HashMap (the length of the
1013     * bucket array) is emitted (int), followed by the
1014     * <i>size</i> of the HashMap (the number of key-value
1015     * mappings), followed by the key (Object) and value (Object)
1016     * for each key-value mapping represented by the HashMap
1017     * The key-value mappings are emitted in the order that they
1018     * are returned by <tt>entrySet().iterator()</tt>.
1019     *
1020     */
1021    private void writeObject(java.io.ObjectOutputStream s)
1022        throws IOException
1023    {
1024    Iterator <Map.Entry <K,V>> i = entrySet().iterator();
1025
1026    // Write out the threshold, loadfactor, and any hidden stuff
1027 s.defaultWriteObject();
1028
1029    // Write out number of buckets
1030 s.writeInt(table.length);
1031
1032    // Write out size (number of Mappings)
1033 s.writeInt(size);
1034
1035        // Write out keys and values (alternating)
1036 while (i.hasNext()) {
1037            Map.Entry <K,V> e = i.next();
1038            s.writeObject(e.getKey());
1039            s.writeObject(e.getValue());
1040        }
1041    }
1042
1043    private static final long serialVersionUID = 362498820763181265L;
1044
1045    /**
1046     * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
1047     * deserialize it).
1048     */
1049    private void readObject(java.io.ObjectInputStream s)
1050         throws IOException, ClassNotFoundException
1051    {
1052    // Read in the threshold, loadfactor, and any hidden stuff
1053 s.defaultReadObject();
1054
1055    // Read in number of buckets and allocate the bucket array;
1056 int numBuckets = s.readInt();
1057    table = new Entry[numBuckets];
1058
1059        init(); // Give subclass a chance to do its thing.
1060
1061    // Read in size (number of Mappings)
1062 int size = s.readInt();
1063
1064    // Read the keys and values, and put the mappings in the HashMap
1065 for (int i=0; i<size; i++) {
1066        K key = (K) s.readObject();
1067        V value = (V) s.readObject();
1068        putForCreate(key, value);
1069    }
1070    }
1071
1072    // These methods are used when serializing HashSets
1073 int capacity() { return table.length; }
1074    float loadFactor() { return loadFactor; }
1075}
1076

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags