1 /*
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
112 * @author Doug Lea
113 * @author Josh Bloch
114 * @author Arthur van Hoff
115 * @author Neal Gafter
116 * @see Object#hashCode()
117 * @see Collection
118 * @see Map
119 * @see TreeMap
120 * @see Hashtable
121 * @since 1.2
122 */
123
124 public class HashMap<K,V>
125 extends AbstractMap<K,V>
126 implements Map<K,V>, Cloneable, Serializable
127 {
128
129 /**
130 * The default initial capacity - MUST be a power of two.
131 */
132 static final int DEFAULT_INITIAL_CAPACITY = 16;
133
134 /**
135 * The maximum capacity, used if a higher value is implicitly specified
136 * by either of the constructors with arguments.
137 * MUST be a power of two <= 1<<30.
138 */
139 static final int MAXIMUM_CAPACITY = 1 << 30;
140
141 /**
142 * The load factor used when none specified in constructor.
143 */
144 static final float DEFAULT_LOAD_FACTOR = 0.75f;
145
146 /**
147 * The table, resized as necessary. Length MUST Always be a power of two.
148 */
149 transient Entry<?,?>[] table;
150
151 /**
152 * The number of key-value mappings contained in this map.
153 */
154 transient int size;
155
156 /**
157 * The next size value at which to resize (capacity * load factor).
158 * @serial
159 */
160 int threshold;
161
162 /**
163 * The load factor for the hash table.
164 *
165 * @serial
166 */
167 final float loadFactor;
168
169 /**
170 * The number of times this HashMap has been structurally modified
171 * Structural modifications are those that change the number of mappings in
172 * the HashMap or otherwise modify its internal structure (e.g.,
173 * rehash). This field is used to make iterators on Collection-views of
174 * the HashMap fail-fast. (See ConcurrentModificationException).
175 */
176 transient int modCount;
177
206
207 /**
208 * Constructs an empty <tt>HashMap</tt> with the specified initial
209 * capacity and load factor.
210 *
211 * @param initialCapacity the initial capacity
212 * @param loadFactor the load factor
213 * @throws IllegalArgumentException if the initial capacity is negative
214 * or the load factor is nonpositive
215 */
216 public HashMap(int initialCapacity, float loadFactor) {
217 if (initialCapacity < 0)
218 throw new IllegalArgumentException("Illegal initial capacity: " +
219 initialCapacity);
220 if (initialCapacity > MAXIMUM_CAPACITY)
221 initialCapacity = MAXIMUM_CAPACITY;
222 if (loadFactor <= 0 || Float.isNaN(loadFactor))
223 throw new IllegalArgumentException("Illegal load factor: " +
224 loadFactor);
225
226 // Find a power of 2 >= initialCapacity
227 int capacity = 1;
228 while (capacity < initialCapacity)
229 capacity <<= 1;
230
231 this.loadFactor = loadFactor;
232 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
233 table = new Entry<?,?>[capacity];
234 init();
235 }
236
237 /**
238 * Constructs an empty <tt>HashMap</tt> with the specified initial
239 * capacity and the default load factor (0.75).
240 *
241 * @param initialCapacity the initial capacity.
242 * @throws IllegalArgumentException if the initial capacity is negative.
243 */
244 public HashMap(int initialCapacity) {
245 this(initialCapacity, DEFAULT_LOAD_FACTOR);
246 }
247
248 /**
249 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
250 * (16) and the default load factor (0.75).
251 */
252 public HashMap() {
253 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
254 }
255
256 /**
257 * Constructs a new <tt>HashMap</tt> with the same mappings as the
258 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
259 * default load factor (0.75) and an initial capacity sufficient to
260 * hold the mappings in the specified <tt>Map</tt>.
261 *
262 * @param m the map whose mappings are to be placed in this map
263 * @throws NullPointerException if the specified map is null
264 */
265 public HashMap(Map<? extends K, ? extends V> m) {
266 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
267 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
268 putAllForCreate(m);
269 }
270
271 // internal utilities
272
273 /**
274 * Initialization hook for subclasses. This method is called
275 * in all constructors and pseudo-constructors (clone, readObject)
276 * after HashMap has been initialized but before any entries have
277 * been inserted. (In the absence of this method, readObject would
278 * require explicit knowledge of subclasses.)
279 */
280 void init() {
281 }
282
283 /**
284 * Retrieve object hash code and applies a supplemental hash function to the
285 * result hash, which defends against poor quality hash functions. This is
286 * critical because HashMap uses power-of-two length hash tables, that
287 * otherwise encounter collisions for hashCodes that do not differ
288 * in lower bits.
289 */
290 final int hash(Object k) {
291 if (k instanceof String) {
292 return ((String) k).hash32();
293 }
294
295 int h = hashSeed ^ k.hashCode();
296
297 // This function ensures that hashCodes that differ only by
298 // constant multiples at each bit position have a bounded
299 // number of collisions (approximately 8 at default load factor).
300 h ^= (h >>> 20) ^ (h >>> 12);
301 return h ^ (h >>> 7) ^ (h >>> 4);
302 }
303
304 /**
305 * Returns index for hash code h.
306 */
307 static int indexFor(int h, int length) {
308 return h & (length-1);
309 }
310
311 /**
312 * Returns the number of key-value mappings in this map.
313 *
314 * @return the number of key-value mappings in this map
315 */
316 public int size() {
317 return size;
318 }
319
320 /**
321 * Returns <tt>true</tt> if this map contains no key-value mappings.
322 *
323 * @return <tt>true</tt> if this map contains no key-value mappings
324 */
325 public boolean isEmpty() {
326 return size == 0;
327 }
352
353 /**
354 * Returns <tt>true</tt> if this map contains a mapping for the
355 * specified key.
356 *
357 * @param key The key whose presence in this map is to be tested
358 * @return <tt>true</tt> if this map contains a mapping for the specified
359 * key.
360 */
361 public boolean containsKey(Object key) {
362 return getEntry(key) != null;
363 }
364
365 /**
366 * Returns the entry associated with the specified key in the
367 * HashMap. Returns null if the HashMap contains no mapping
368 * for the key.
369 */
370 @SuppressWarnings("unchecked")
371 final Entry<K,V> getEntry(Object key) {
372 int hash = (key == null) ? 0 : hash(key);
373 for (Entry<?,?> e = table[indexFor(hash, table.length)];
374 e != null;
375 e = e.next) {
376 Object k;
377 if (e.hash == hash &&
378 ((k = e.key) == key || (key != null && key.equals(k))))
379 return (Entry<K,V>)e;
380 }
381 return null;
382 }
383
384
385 /**
386 * Associates the specified value with the specified key in this map.
387 * If the map previously contained a mapping for the key, the old
388 * value is replaced.
389 *
390 * @param key key with which the specified value is to be associated
391 * @param value value to be associated with the specified key
392 * @return the previous value associated with <tt>key</tt>, or
393 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
394 * (A <tt>null</tt> return can also indicate that the map
395 * previously associated <tt>null</tt> with <tt>key</tt>.)
396 */
397 public V put(K key, V value) {
398 if (key == null)
399 return putForNullKey(value);
400 int hash = hash(key);
401 int i = indexFor(hash, table.length);
402 @SuppressWarnings("unchecked")
403 Entry<K,V> e = (Entry<K,V>)table[i];
404 for(; e != null; e = e.next) {
405 Object k;
406 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
407 V oldValue = e.value;
408 e.value = value;
409 e.recordAccess(this);
410 return oldValue;
411 }
412 }
413
414 modCount++;
415 addEntry(hash, key, value, i);
416 return null;
417 }
512 newTable[i] = e;
513 e = next;
514 }
515 }
516 Arrays.fill(table, null);
517 }
518
519 /**
520 * Copies all of the mappings from the specified map to this map.
521 * These mappings will replace any mappings that this map had for
522 * any of the keys currently in the specified map.
523 *
524 * @param m mappings to be stored in this map
525 * @throws NullPointerException if the specified map is null
526 */
527 public void putAll(Map<? extends K, ? extends V> m) {
528 int numKeysToBeAdded = m.size();
529 if (numKeysToBeAdded == 0)
530 return;
531
532 /*
533 * Expand the map if the map if the number of mappings to be added
534 * is greater than or equal to threshold. This is conservative; the
535 * obvious condition is (m.size() + size) >= threshold, but this
536 * condition could result in a map with twice the appropriate capacity,
537 * if the keys to be added overlap with the keys already in this map.
538 * By using the conservative calculation, we subject ourself
539 * to at most one extra resize.
540 */
541 if (numKeysToBeAdded > threshold) {
542 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
543 if (targetCapacity > MAXIMUM_CAPACITY)
544 targetCapacity = MAXIMUM_CAPACITY;
545 int newCapacity = table.length;
546 while (newCapacity < targetCapacity)
547 newCapacity <<= 1;
548 if (newCapacity > table.length)
549 resize(newCapacity);
550 }
551
556 /**
557 * Removes the mapping for the specified key from this map if present.
558 *
559 * @param key key whose mapping is to be removed from the map
560 * @return the previous value associated with <tt>key</tt>, or
561 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
562 * (A <tt>null</tt> return can also indicate that the map
563 * previously associated <tt>null</tt> with <tt>key</tt>.)
564 */
565 public V remove(Object key) {
566 Entry<K,V> e = removeEntryForKey(key);
567 return (e == null ? null : e.value);
568 }
569
570 /**
571 * Removes and returns the entry associated with the specified key
572 * in the HashMap. Returns null if the HashMap contains no mapping
573 * for this key.
574 */
575 final Entry<K,V> removeEntryForKey(Object key) {
576 int hash = (key == null) ? 0 : hash(key);
577 int i = indexFor(hash, table.length);
578 @SuppressWarnings("unchecked")
579 Entry<K,V> prev = (Entry<K,V>)table[i];
580 Entry<K,V> e = prev;
581
582 while (e != null) {
583 Entry<K,V> next = e.next;
584 Object k;
585 if (e.hash == hash &&
586 ((k = e.key) == key || (key != null && key.equals(k)))) {
587 modCount++;
588 size--;
589 if (prev == e)
590 table[i] = next;
591 else
592 prev.next = next;
593 e.recordRemoval(this);
594 return e;
595 }
596 prev = e;
597 e = next;
598 }
599
600 return e;
601 }
602
603 /**
604 * Special version of remove for EntrySet using {@code Map.Entry.equals()}
605 * for matching.
606 */
607 final Entry<K,V> removeMapping(Object o) {
608 if (!(o instanceof Map.Entry))
609 return null;
610
611 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
612 Object key = entry.getKey();
613 int hash = (key == null) ? 0 : hash(key);
614 int i = indexFor(hash, table.length);
615 @SuppressWarnings("unchecked")
616 Entry<K,V> prev = (Entry<K,V>)table[i];
617 Entry<K,V> e = prev;
618
619 while (e != null) {
620 Entry<K,V> next = e.next;
621 if (e.hash == hash && e.equals(entry)) {
622 modCount++;
623 size--;
624 if (prev == e)
625 table[i] = next;
626 else
627 prev.next = next;
628 e.recordRemoval(this);
629 return e;
630 }
631 prev = e;
632 e = next;
633 }
634
635 return e;
636 }
637
638 /**
639 * Removes all of the mappings from this map.
640 * The map will be empty after this call returns.
641 */
642 public void clear() {
643 modCount++;
644 Entry<?,?>[] tab = table;
645 for (int i = 0; i < tab.length; i++)
646 tab[i] = null;
647 size = 0;
648 }
649
650 /**
651 * Returns <tt>true</tt> if this map maps one or more keys to the
652 * specified value.
653 *
654 * @param value value whose presence in this map is to be tested
655 * @return <tt>true</tt> if this map maps one or more keys to the
656 * specified value
657 */
658 public boolean containsValue(Object value) {
659 if (value == null)
660 return containsNullValue();
661
662 Entry<?,?>[] tab = table;
663 for (int i = 0; i < tab.length ; i++)
664 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
665 if (value.equals(e.value))
666 return true;
667 return false;
668 }
669
670 /**
671 * Special-case code for containsValue with null argument
672 */
673 private boolean containsNullValue() {
674 Entry<?,?>[] tab = table;
675 for (int i = 0; i < tab.length ; i++)
676 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
677 if (e.value == null)
678 return true;
679 return false;
680 }
681
682 /**
683 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
684 * values themselves are not cloned.
685 *
686 * @return a shallow copy of this map
687 */
688 @SuppressWarnings("unchecked")
689 public Object clone() {
690 HashMap<K,V> result = null;
691 try {
692 result = (HashMap<K,V>)super.clone();
693 } catch (CloneNotSupportedException e) {
694 // assert false;
695 }
696 result.table = new Entry<?,?>[table.length];
697 result.entrySet = null;
698 result.modCount = 0;
699 result.size = 0;
700 result.init();
701 result.putAllForCreate(this);
702
703 return result;
704 }
705
706 static class Entry<K,V> implements Map.Entry<K,V> {
707 final K key;
708 V value;
709 Entry<K,V> next;
710 final int hash;
711
712 /**
713 * Creates new entry.
714 */
715 Entry(int h, K k, V v, Entry<K,V> n) {
716 value = v;
732 value = newValue;
733 return oldValue;
734 }
735
736 public final boolean equals(Object o) {
737 if (!(o instanceof Map.Entry))
738 return false;
739 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
740 Object k1 = getKey();
741 Object k2 = e.getKey();
742 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
743 Object v1 = getValue();
744 Object v2 = e.getValue();
745 if (v1 == v2 || (v1 != null && v1.equals(v2)))
746 return true;
747 }
748 return false;
749 }
750
751 public final int hashCode() {
752 return (key==null ? 0 : key.hashCode()) ^
753 (value==null ? 0 : value.hashCode());
754 }
755
756 public final String toString() {
757 return getKey() + "=" + getValue();
758 }
759
760 /**
761 * This method is invoked whenever the value in an entry is
762 * overwritten by an invocation of put(k,v) for a key k that's already
763 * in the HashMap.
764 */
765 void recordAccess(HashMap<K,V> m) {
766 }
767
768 /**
769 * This method is invoked whenever the entry is
770 * removed from the table.
771 */
772 void recordRemoval(HashMap<K,V> m) {
773 }
1000 }
1001 public void clear() {
1002 HashMap.this.clear();
1003 }
1004 }
1005
1006 /**
1007 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1008 * serialize it).
1009 *
1010 * @serialData The <i>capacity</i> of the HashMap (the length of the
1011 * bucket array) is emitted (int), followed by the
1012 * <i>size</i> (an int, the number of key-value
1013 * mappings), followed by the key (Object) and value (Object)
1014 * for each key-value mapping. The key-value mappings are
1015 * emitted in no particular order.
1016 */
1017 private void writeObject(java.io.ObjectOutputStream s)
1018 throws IOException
1019 {
1020 Iterator<Map.Entry<K,V>> i =
1021 (size > 0) ? entrySet0().iterator() : null;
1022
1023 // Write out the threshold, loadfactor, and any hidden stuff
1024 s.defaultWriteObject();
1025
1026 // Write out number of buckets
1027 s.writeInt(table.length);
1028
1029 // Write out size (number of Mappings)
1030 s.writeInt(size);
1031
1032 // Write out keys and values (alternating)
1033 if (size > 0) {
1034 for(Map.Entry<K,V> e : entrySet0()) {
1035 s.writeObject(e.getKey());
1036 s.writeObject(e.getValue());
1037 }
1038 }
1039 }
1040
1041 private static final long serialVersionUID = 362498820763181265L;
1042
1043 /**
1044 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1045 * deserialize it).
1046 */
1047 private void readObject(java.io.ObjectInputStream s)
1048 throws IOException, ClassNotFoundException
1049 {
1050 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1051 s.defaultReadObject();
1052 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1053 throw new InvalidObjectException("Illegal load factor: " +
1054 loadFactor);
1055
1056 // set hashMask
1057 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1058 sun.misc.Hashing.randomHashSeed(this));
1059
1060 // Read in number of buckets and allocate the bucket array;
1061 s.readInt(); // ignored
1062
1063 // Read number of mappings
1064 int mappings = s.readInt();
1065 if (mappings < 0)
1066 throw new InvalidObjectException("Illegal mappings count: " +
1067 mappings);
1068
1069 int initialCapacity = (int) Math.min(
1070 // capacity chosen by number of mappings
1071 // and desired load (if >= 0.25)
1072 mappings * Math.min(1 / loadFactor, 4.0f),
1073 // we have limits...
1074 HashMap.MAXIMUM_CAPACITY);
1075 int capacity = 1;
1076 // find smallest power of two which holds all mappings
1077 while (capacity < initialCapacity) {
1078 capacity <<= 1;
1079 }
1080
1081 table = new Entry<?,?>[capacity];
1082 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
1083 init(); // Give subclass a chance to do its thing.
1084
1085
1086 // Read the keys and values, and put the mappings in the HashMap
1087 for (int i=0; i<mappings; i++) {
1088 @SuppressWarnings("unchecked")
1089 K key = (K) s.readObject();
1090 @SuppressWarnings("unchecked")
1091 V value = (V) s.readObject();
1092 putForCreate(key, value);
1093 }
1094 }
1095
1096 // These methods are used when serializing HashSets
1097 int capacity() { return table.length; }
1098 float loadFactor() { return loadFactor; }
1099 }
|
1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
112 * @author Doug Lea
113 * @author Josh Bloch
114 * @author Arthur van Hoff
115 * @author Neal Gafter
116 * @see Object#hashCode()
117 * @see Collection
118 * @see Map
119 * @see TreeMap
120 * @see Hashtable
121 * @since 1.2
122 */
123
124 public class HashMap<K,V>
125 extends AbstractMap<K,V>
126 implements Map<K,V>, Cloneable, Serializable
127 {
128
129 /**
130 * The default initial capacity - MUST be a power of two.
131 */
132 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
133
134 /**
135 * The maximum capacity, used if a higher value is implicitly specified
136 * by either of the constructors with arguments.
137 * MUST be a power of two <= 1<<30.
138 */
139 static final int MAXIMUM_CAPACITY = 1 << 30;
140
141 /**
142 * The load factor used when none specified in constructor.
143 */
144 static final float DEFAULT_LOAD_FACTOR = 0.75f;
145
146 /**
147 * An empty table instance to share when the table is not inflated.
148 */
149 static final Entry<?,?>[] EMPTY_TABLE = {};
150
151 /**
152 * The table, resized as necessary. Length MUST Always be a power of two.
153 */
154 transient Entry<?,?>[] table = EMPTY_TABLE;
155
156 /**
157 * The number of key-value mappings contained in this map.
158 */
159 transient int size;
160
161 /**
162 * The next size value at which to resize (capacity * load factor). If
163 * table == EMPTY_TABLE then this is the initial capacity at which the
164 * table will be created when inflated.
165 * @serial
166 */
167 int threshold;
168
169 /**
170 * The load factor for the hash table.
171 *
172 * @serial
173 */
174 final float loadFactor;
175
176 /**
177 * The number of times this HashMap has been structurally modified
178 * Structural modifications are those that change the number of mappings in
179 * the HashMap or otherwise modify its internal structure (e.g.,
180 * rehash). This field is used to make iterators on Collection-views of
181 * the HashMap fail-fast. (See ConcurrentModificationException).
182 */
183 transient int modCount;
184
213
214 /**
215 * Constructs an empty <tt>HashMap</tt> with the specified initial
216 * capacity and load factor.
217 *
218 * @param initialCapacity the initial capacity
219 * @param loadFactor the load factor
220 * @throws IllegalArgumentException if the initial capacity is negative
221 * or the load factor is nonpositive
222 */
223 public HashMap(int initialCapacity, float loadFactor) {
224 if (initialCapacity < 0)
225 throw new IllegalArgumentException("Illegal initial capacity: " +
226 initialCapacity);
227 if (initialCapacity > MAXIMUM_CAPACITY)
228 initialCapacity = MAXIMUM_CAPACITY;
229 if (loadFactor <= 0 || Float.isNaN(loadFactor))
230 throw new IllegalArgumentException("Illegal load factor: " +
231 loadFactor);
232
233 this.loadFactor = loadFactor;
234 threshold = initialCapacity;
235 init();
236 }
237
238 /**
239 * Constructs an empty <tt>HashMap</tt> with the specified initial
240 * capacity and the default load factor (0.75).
241 *
242 * @param initialCapacity the initial capacity.
243 * @throws IllegalArgumentException if the initial capacity is negative.
244 */
245 public HashMap(int initialCapacity) {
246 this(initialCapacity, DEFAULT_LOAD_FACTOR);
247 }
248
249 /**
250 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
251 * (16) and the default load factor (0.75).
252 */
253 public HashMap() {
254 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
255 }
256
257 /**
258 * Constructs a new <tt>HashMap</tt> with the same mappings as the
259 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
260 * default load factor (0.75) and an initial capacity sufficient to
261 * hold the mappings in the specified <tt>Map</tt>.
262 *
263 * @param m the map whose mappings are to be placed in this map
264 * @throws NullPointerException if the specified map is null
265 */
266 public HashMap(Map<? extends K, ? extends V> m) {
267 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
268 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
269 inflateTable(threshold);
270
271 putAllForCreate(m);
272 }
273
274 private static int roundUpToPowerOf2(int number) {
275 int rounded = number >= MAXIMUM_CAPACITY
276 ? MAXIMUM_CAPACITY
277 : (rounded = Integer.highestOneBit(number)) != 0
278 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
279 : 1;
280
281 return rounded;
282 }
283
284 /**
285 * Inflate the table
286 */
287 private void inflateTable(int toSize) {
288 // Find a power of 2 >= initialCapacity
289 int capacity = roundUpToPowerOf2(toSize);
290
291 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
292 table = new Entry[capacity];
293 }
294
295 // internal utilities
296
297 /**
298 * Initialization hook for subclasses. This method is called
299 * in all constructors and pseudo-constructors (clone, readObject)
300 * after HashMap has been initialized but before any entries have
301 * been inserted. (In the absence of this method, readObject would
302 * require explicit knowledge of subclasses.)
303 */
304 void init() {
305 }
306
307 /**
308 * Retrieve object hash code and applies a supplemental hash function to the
309 * result hash, which defends against poor quality hash functions. This is
310 * critical because HashMap uses power-of-two length hash tables, that
311 * otherwise encounter collisions for hashCodes that do not differ
312 * in lower bits.
313 */
314 final int hash(Object k) {
315 if (k instanceof String) {
316 return ((String) k).hash32();
317 }
318
319 int h = hashSeed ^ k.hashCode();
320
321 // This function ensures that hashCodes that differ only by
322 // constant multiples at each bit position have a bounded
323 // number of collisions (approximately 8 at default load factor).
324 h ^= (h >>> 20) ^ (h >>> 12);
325 return h ^ (h >>> 7) ^ (h >>> 4);
326 }
327
328 /**
329 * Returns index for hash code h.
330 */
331 static int indexFor(int h, int length) {
332 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
333 return h & (length-1);
334 }
335
336 /**
337 * Returns the number of key-value mappings in this map.
338 *
339 * @return the number of key-value mappings in this map
340 */
341 public int size() {
342 return size;
343 }
344
345 /**
346 * Returns <tt>true</tt> if this map contains no key-value mappings.
347 *
348 * @return <tt>true</tt> if this map contains no key-value mappings
349 */
350 public boolean isEmpty() {
351 return size == 0;
352 }
377
378 /**
379 * Returns <tt>true</tt> if this map contains a mapping for the
380 * specified key.
381 *
382 * @param key The key whose presence in this map is to be tested
383 * @return <tt>true</tt> if this map contains a mapping for the specified
384 * key.
385 */
386 public boolean containsKey(Object key) {
387 return getEntry(key) != null;
388 }
389
390 /**
391 * Returns the entry associated with the specified key in the
392 * HashMap. Returns null if the HashMap contains no mapping
393 * for the key.
394 */
395 @SuppressWarnings("unchecked")
396 final Entry<K,V> getEntry(Object key) {
397 if (isEmpty()) {
398 return null;
399 }
400
401 int hash = (key == null) ? 0 : hash(key);
402 for (Entry<?,?> e = table[indexFor(hash, table.length)];
403 e != null;
404 e = e.next) {
405 Object k;
406 if (e.hash == hash &&
407 ((k = e.key) == key || (key != null && key.equals(k))))
408 return (Entry<K,V>)e;
409 }
410 return null;
411 }
412
413 /**
414 * Associates the specified value with the specified key in this map.
415 * If the map previously contained a mapping for the key, the old
416 * value is replaced.
417 *
418 * @param key key with which the specified value is to be associated
419 * @param value value to be associated with the specified key
420 * @return the previous value associated with <tt>key</tt>, or
421 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
422 * (A <tt>null</tt> return can also indicate that the map
423 * previously associated <tt>null</tt> with <tt>key</tt>.)
424 */
425 public V put(K key, V value) {
426 if (table == EMPTY_TABLE) {
427 inflateTable(threshold);
428 }
429 if (key == null)
430 return putForNullKey(value);
431 int hash = hash(key);
432 int i = indexFor(hash, table.length);
433 @SuppressWarnings("unchecked")
434 Entry<K,V> e = (Entry<K,V>)table[i];
435 for(; e != null; e = e.next) {
436 Object k;
437 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
438 V oldValue = e.value;
439 e.value = value;
440 e.recordAccess(this);
441 return oldValue;
442 }
443 }
444
445 modCount++;
446 addEntry(hash, key, value, i);
447 return null;
448 }
543 newTable[i] = e;
544 e = next;
545 }
546 }
547 Arrays.fill(table, null);
548 }
549
550 /**
551 * Copies all of the mappings from the specified map to this map.
552 * These mappings will replace any mappings that this map had for
553 * any of the keys currently in the specified map.
554 *
555 * @param m mappings to be stored in this map
556 * @throws NullPointerException if the specified map is null
557 */
558 public void putAll(Map<? extends K, ? extends V> m) {
559 int numKeysToBeAdded = m.size();
560 if (numKeysToBeAdded == 0)
561 return;
562
563 if (table == EMPTY_TABLE) {
564 inflateTable(Math.max((int) (numKeysToBeAdded * loadFactor), threshold));
565 }
566
567 /*
568 * Expand the map if the map if the number of mappings to be added
569 * is greater than or equal to threshold. This is conservative; the
570 * obvious condition is (m.size() + size) >= threshold, but this
571 * condition could result in a map with twice the appropriate capacity,
572 * if the keys to be added overlap with the keys already in this map.
573 * By using the conservative calculation, we subject ourself
574 * to at most one extra resize.
575 */
576 if (numKeysToBeAdded > threshold) {
577 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
578 if (targetCapacity > MAXIMUM_CAPACITY)
579 targetCapacity = MAXIMUM_CAPACITY;
580 int newCapacity = table.length;
581 while (newCapacity < targetCapacity)
582 newCapacity <<= 1;
583 if (newCapacity > table.length)
584 resize(newCapacity);
585 }
586
591 /**
592 * Removes the mapping for the specified key from this map if present.
593 *
594 * @param key key whose mapping is to be removed from the map
595 * @return the previous value associated with <tt>key</tt>, or
596 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
597 * (A <tt>null</tt> return can also indicate that the map
598 * previously associated <tt>null</tt> with <tt>key</tt>.)
599 */
600 public V remove(Object key) {
601 Entry<K,V> e = removeEntryForKey(key);
602 return (e == null ? null : e.value);
603 }
604
605 /**
606 * Removes and returns the entry associated with the specified key
607 * in the HashMap. Returns null if the HashMap contains no mapping
608 * for this key.
609 */
610 final Entry<K,V> removeEntryForKey(Object key) {
611 if (isEmpty()) {
612 return null;
613 }
614 int hash = (key == null) ? 0 : hash(key);
615 int i = indexFor(hash, table.length);
616 @SuppressWarnings("unchecked")
617 Entry<K,V> prev = (Entry<K,V>)table[i];
618 Entry<K,V> e = prev;
619
620 while (e != null) {
621 Entry<K,V> next = e.next;
622 Object k;
623 if (e.hash == hash &&
624 ((k = e.key) == key || (key != null && key.equals(k)))) {
625 modCount++;
626 size--;
627 if (prev == e)
628 table[i] = next;
629 else
630 prev.next = next;
631 e.recordRemoval(this);
632 return e;
633 }
634 prev = e;
635 e = next;
636 }
637
638 return e;
639 }
640
641 /**
642 * Special version of remove for EntrySet using {@code Map.Entry.equals()}
643 * for matching.
644 */
645 final Entry<K,V> removeMapping(Object o) {
646 if (isEmpty() || !(o instanceof Map.Entry))
647 return null;
648
649 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
650 Object key = entry.getKey();
651 int hash = (key == null) ? 0 : hash(key);
652 int i = indexFor(hash, table.length);
653 @SuppressWarnings("unchecked")
654 Entry<K,V> prev = (Entry<K,V>)table[i];
655 Entry<K,V> e = prev;
656
657 while (e != null) {
658 Entry<K,V> next = e.next;
659 if (e.hash == hash && e.equals(entry)) {
660 modCount++;
661 size--;
662 if (prev == e)
663 table[i] = next;
664 else
665 prev.next = next;
666 e.recordRemoval(this);
667 return e;
668 }
669 prev = e;
670 e = next;
671 }
672
673 return e;
674 }
675
676 /**
677 * Removes all of the mappings from this map.
678 * The map will be empty after this call returns.
679 */
680 public void clear() {
681 modCount++;
682 Arrays.fill(table, null);
683 size = 0;
684 }
685
686 /**
687 * Returns <tt>true</tt> if this map maps one or more keys to the
688 * specified value.
689 *
690 * @param value value whose presence in this map is to be tested
691 * @return <tt>true</tt> if this map maps one or more keys to the
692 * specified value
693 */
694 public boolean containsValue(Object value) {
695 if (isEmpty()) {
696 return false;
697 }
698
699 if (value == null)
700 return containsNullValue();
701
702 Entry<?,?>[] tab = table;
703 for (int i = 0; i < tab.length ; i++)
704 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
705 if (value.equals(e.value))
706 return true;
707 return false;
708 }
709
710 /**
711 * Special-case code for containsValue with null argument
712 */
713 private boolean containsNullValue() {
714 Entry<?,?>[] tab = table;
715 for (int i = 0; i < tab.length ; i++)
716 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
717 if (e.value == null)
718 return true;
719 return false;
720 }
721
722 /**
723 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
724 * values themselves are not cloned.
725 *
726 * @return a shallow copy of this map
727 */
728 @SuppressWarnings("unchecked")
729 public Object clone() {
730 HashMap<K,V> result = null;
731 try {
732 result = (HashMap<K,V>)super.clone();
733 } catch (CloneNotSupportedException e) {
734 // assert false;
735 }
736 result.table = (table == EMPTY_TABLE)
737 ? EMPTY_TABLE
738 : new Entry<?,?>[table.length];
739 result.entrySet = null;
740 result.modCount = 0;
741 result.size = 0;
742 result.init();
743 result.putAllForCreate(this);
744
745 return result;
746 }
747
748 static class Entry<K,V> implements Map.Entry<K,V> {
749 final K key;
750 V value;
751 Entry<K,V> next;
752 final int hash;
753
754 /**
755 * Creates new entry.
756 */
757 Entry(int h, K k, V v, Entry<K,V> n) {
758 value = v;
774 value = newValue;
775 return oldValue;
776 }
777
778 public final boolean equals(Object o) {
779 if (!(o instanceof Map.Entry))
780 return false;
781 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
782 Object k1 = getKey();
783 Object k2 = e.getKey();
784 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
785 Object v1 = getValue();
786 Object v2 = e.getValue();
787 if (v1 == v2 || (v1 != null && v1.equals(v2)))
788 return true;
789 }
790 return false;
791 }
792
793 public final int hashCode() {
794 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
795 }
796
797 public final String toString() {
798 return getKey() + "=" + getValue();
799 }
800
801 /**
802 * This method is invoked whenever the value in an entry is
803 * overwritten by an invocation of put(k,v) for a key k that's already
804 * in the HashMap.
805 */
806 void recordAccess(HashMap<K,V> m) {
807 }
808
809 /**
810 * This method is invoked whenever the entry is
811 * removed from the table.
812 */
813 void recordRemoval(HashMap<K,V> m) {
814 }
1041 }
1042 public void clear() {
1043 HashMap.this.clear();
1044 }
1045 }
1046
1047 /**
1048 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1049 * serialize it).
1050 *
1051 * @serialData The <i>capacity</i> of the HashMap (the length of the
1052 * bucket array) is emitted (int), followed by the
1053 * <i>size</i> (an int, the number of key-value
1054 * mappings), followed by the key (Object) and value (Object)
1055 * for each key-value mapping. The key-value mappings are
1056 * emitted in no particular order.
1057 */
1058 private void writeObject(java.io.ObjectOutputStream s)
1059 throws IOException
1060 {
1061 // Write out the threshold, loadfactor, and any hidden stuff
1062 s.defaultWriteObject();
1063
1064 // Write out number of buckets
1065 if (table==EMPTY_TABLE) {
1066 s.writeInt(roundUpToPowerOf2(threshold));
1067 } else {
1068 s.writeInt(table.length);
1069 }
1070
1071 // Write out size (number of Mappings)
1072 s.writeInt(size);
1073
1074 // Write out keys and values (alternating)
1075 if (size > 0) {
1076 for(Map.Entry<K,V> e : entrySet0()) {
1077 s.writeObject(e.getKey());
1078 s.writeObject(e.getValue());
1079 }
1080 }
1081 }
1082
1083 private static final long serialVersionUID = 362498820763181265L;
1084
1085 /**
1086 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1087 * deserialize it).
1088 */
1089 private void readObject(java.io.ObjectInputStream s)
1090 throws IOException, ClassNotFoundException
1091 {
1092 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1093 s.defaultReadObject();
1094 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
1095 throw new InvalidObjectException("Illegal load factor: " +
1096 loadFactor);
1097 }
1098
1099 // set other fields that need values
1100 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1101 sun.misc.Hashing.randomHashSeed(this));
1102 table = EMPTY_TABLE;
1103
1104 // Read in number of buckets
1105 int bucketsCapacity = s.readInt();
1106
1107 if (bucketsCapacity < 0) {
1108 throw new InvalidObjectException("Illegal capacity: " + bucketsCapacity);
1109 }
1110
1111 bucketsCapacity = roundUpToPowerOf2(bucketsCapacity);
1112
1113 // Read number of mappings
1114 int mappings = s.readInt();
1115 if (mappings < 0)
1116 throw new InvalidObjectException("Illegal mappings count: " +
1117 mappings);
1118
1119 // capacity chosen by number of mappings and desired load (if >= 0.25)
1120 int mappingsCapacity = (int) Math.min(
1121 mappings * Math.min(1 / loadFactor, 4.0f),
1122 // we have limits...
1123 HashMap.MAXIMUM_CAPACITY);
1124
1125 // capacity is greater of that suggested by loading and buckets
1126 int capacity = Math.max(mappingsCapacity, bucketsCapacity);
1127
1128 // allocate the bucket array;
1129 if (mappings > 0) {
1130 inflateTable(capacity);
1131 } else {
1132 threshold = capacity;
1133 }
1134
1135 init(); // Give subclass a chance to do its thing.
1136
1137 // Read the keys and values, and put the mappings in the HashMap
1138 for (int i=0; i<mappings; i++) {
1139 @SuppressWarnings("unchecked")
1140 K key = (K) s.readObject();
1141 @SuppressWarnings("unchecked")
1142 V value = (V) s.readObject();
1143 putForCreate(key, value);
1144 }
1145 }
1146
1147 // These methods are used when serializing HashSets
1148 int capacity() { return table.length; }
1149 float loadFactor() { return loadFactor; }
1150 }
|