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
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
178 private static class Holder {
179 /**
180 *
181 */
182 static final sun.misc.Unsafe UNSAFE;
183
184 /**
185 * Offset of "final" hashSeed field we must set in
186 * readObject() method.
187 */
188 static final long HASHSEED_OFFSET;
189
190 static {
191 try {
192 UNSAFE = sun.misc.Unsafe.getUnsafe();
193 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
194 HashMap.class.getDeclaredField("hashSeed"));
195 } catch (NoSuchFieldException | SecurityException e) {
196 throw new InternalError("Failed to record hashSeed offset", e);
197 }
198 }
199 }
200
201 /**
202 * A randomizing value associated with this instance that is applied to
203 * hash code of keys to make hash collisions harder to find.
204 */
205 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
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) {
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
552 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
553 put(e.getKey(), e.getValue());
554 }
555
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 &&
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 */
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
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 * 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).
163 * @serial
164 */
165 int threshold;
166
167 /**
168 * The load factor for the hash table.
169 *
170 * @serial
171 */
172 final float loadFactor;
173
174 /**
175 * The number of times this HashMap has been structurally modified
176 * Structural modifications are those that change the number of mappings in
177 * the HashMap or otherwise modify its internal structure (e.g.,
178 * rehash). This field is used to make iterators on Collection-views of
179 * the HashMap fail-fast. (See ConcurrentModificationException).
180 */
181 transient int modCount;
182
183 private static class Holder {
184 /**
185 *
186 */
187 static final sun.misc.Unsafe UNSAFE;
188
189 /**
190 * Offset of "final" hashSeed field we must set in
191 * readObject() method.
192 */
193 static final long HASHSEED_OFFSET;
194
195 /**
196 * Offset of "final" initialCapacity field we must set in
197 * readObject() method.
198 */
199 static final long INITIAL_CAPACITY_OFFSET;
200
201 static {
202 try {
203 UNSAFE = sun.misc.Unsafe.getUnsafe();
204 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
205 HashMap.class.getDeclaredField("hashSeed"));
206 INITIAL_CAPACITY_OFFSET = UNSAFE.objectFieldOffset(
207 HashMap.class.getDeclaredField("initialCapacity"));
208 } catch (NoSuchFieldException | SecurityException e) {
209 throw new InternalError("Failed to record field offset", e);
210 }
211 }
212 }
213
214 /**
215 * A randomizing value associated with this instance that is applied to
216 * hash code of keys to make hash collisions harder to find.
217 */
218 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
219
220 /**
221 * The requested initial capacity increased to a power of two.
222 */
223 transient final int initialCapacity;
224
225 /**
226 * Constructs an empty <tt>HashMap</tt> with the specified initial
227 * capacity and load factor.
228 *
229 * @param initialCapacity the initial capacity
230 * @param loadFactor the load factor
231 * @throws IllegalArgumentException if the initial capacity is negative
232 * or the load factor is nonpositive
233 */
234 public HashMap(int initialCapacity, float loadFactor) {
235 if (initialCapacity < 0)
236 throw new IllegalArgumentException("Illegal initial capacity: " +
237 initialCapacity);
238 if (initialCapacity > MAXIMUM_CAPACITY)
239 initialCapacity = MAXIMUM_CAPACITY;
240 if (loadFactor <= 0 || Float.isNaN(loadFactor))
241 throw new IllegalArgumentException("Illegal load factor: " +
242 loadFactor);
243
244 // Find a power of 2 >= initialCapacity
245 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
246 ? capacity
247 : 1;
248 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
249
250 this.loadFactor = loadFactor;
251 threshold = 0;
252 this.initialCapacity = capacity;
253 init();
254 }
255
256 /**
257 * Constructs an empty <tt>HashMap</tt> with the specified initial
258 * capacity and the default load factor (0.75).
259 *
260 * @param initialCapacity the initial capacity.
261 * @throws IllegalArgumentException if the initial capacity is negative.
262 */
263 public HashMap(int initialCapacity) {
264 this(initialCapacity, DEFAULT_LOAD_FACTOR);
265 }
266
267 /**
268 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
269 * (16) and the default load factor (0.75).
270 */
271 public HashMap() {
272 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
273 }
274
275 /**
276 * Constructs a new <tt>HashMap</tt> with the same mappings as the
277 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
278 * default load factor (0.75) and an initial capacity sufficient to
279 * hold the mappings in the specified <tt>Map</tt>.
280 *
281 * @param m the map whose mappings are to be placed in this map
282 * @throws NullPointerException if the specified map is null
283 */
284 public HashMap(Map<? extends K, ? extends V> m) {
285 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
286 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
287 inflateTable();
288
289 putAllForCreate(m);
290 }
291
292 /**
293 * Inflate the table
294 */
295 final void inflateTable() {
296 threshold = (int)Math.min(initialCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
297 table = new Entry[initialCapacity];
298 }
299 // internal utilities
300
301 /**
302 * Initialization hook for subclasses. This method is called
303 * in all constructors and pseudo-constructors (clone, readObject)
304 * after HashMap has been initialized but before any entries have
305 * been inserted. (In the absence of this method, readObject would
306 * require explicit knowledge of subclasses.)
307 */
308 void init() {
309 }
310
311 /**
312 * Retrieve object hash code and applies a supplemental hash function to the
313 * result hash, which defends against poor quality hash functions. This is
314 * critical because HashMap uses power-of-two length hash tables, that
315 * otherwise encounter collisions for hashCodes that do not differ
316 * in lower bits.
317 */
318 final int hash(Object k) {
380
381 /**
382 * Returns <tt>true</tt> if this map contains a mapping for the
383 * specified key.
384 *
385 * @param key The key whose presence in this map is to be tested
386 * @return <tt>true</tt> if this map contains a mapping for the specified
387 * key.
388 */
389 public boolean containsKey(Object key) {
390 return getEntry(key) != null;
391 }
392
393 /**
394 * Returns the entry associated with the specified key in the
395 * HashMap. Returns null if the HashMap contains no mapping
396 * for the key.
397 */
398 @SuppressWarnings("unchecked")
399 final Entry<K,V> getEntry(Object key) {
400 if (isEmpty()) {
401 return null;
402 }
403
404 int hash = (key == null) ? 0 : hash(key);
405 for (Entry<?,?> e = table[indexFor(hash, table.length)];
406 e != null;
407 e = e.next) {
408 Object k;
409 if (e.hash == hash &&
410 ((k = e.key) == key || (key != null && key.equals(k))))
411 return (Entry<K,V>)e;
412 }
413 return null;
414 }
415
416 /**
417 * Associates the specified value with the specified key in this map.
418 * If the map previously contained a mapping for the key, the old
419 * value is replaced.
420 *
421 * @param key key with which the specified value is to be associated
422 * @param value value to be associated with the specified key
423 * @return the previous value associated with <tt>key</tt>, or
424 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
425 * (A <tt>null</tt> return can also indicate that the map
426 * previously associated <tt>null</tt> with <tt>key</tt>.)
427 */
428 public V put(K key, V value) {
429 if (table == EMPTY_TABLE) {
430 inflateTable();
431 }
432 if (key == null)
433 return putForNullKey(value);
434 int hash = hash(key);
435 int i = indexFor(hash, table.length);
436 @SuppressWarnings("unchecked")
437 Entry<K,V> e = (Entry<K,V>)table[i];
438 for(; e != null; e = e.next) {
439 Object k;
440 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
441 V oldValue = e.value;
442 e.value = value;
443 e.recordAccess(this);
444 return oldValue;
445 }
446 }
447
448 modCount++;
449 addEntry(hash, key, value, i);
450 return null;
451 }
546 newTable[i] = e;
547 e = next;
548 }
549 }
550 Arrays.fill(table, null);
551 }
552
553 /**
554 * Copies all of the mappings from the specified map to this map.
555 * These mappings will replace any mappings that this map had for
556 * any of the keys currently in the specified map.
557 *
558 * @param m mappings to be stored in this map
559 * @throws NullPointerException if the specified map is null
560 */
561 public void putAll(Map<? extends K, ? extends V> m) {
562 int numKeysToBeAdded = m.size();
563 if (numKeysToBeAdded == 0)
564 return;
565
566 if (table == EMPTY_TABLE) {
567 inflateTable();
568 }
569
570 /*
571 * Expand the map if the map if the number of mappings to be added
572 * is greater than or equal to threshold. This is conservative; the
573 * obvious condition is (m.size() + size) >= threshold, but this
574 * condition could result in a map with twice the appropriate capacity,
575 * if the keys to be added overlap with the keys already in this map.
576 * By using the conservative calculation, we subject ourself
577 * to at most one extra resize.
578 */
579 if (numKeysToBeAdded > threshold) {
580 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
581 if (targetCapacity > MAXIMUM_CAPACITY)
582 targetCapacity = MAXIMUM_CAPACITY;
583 int newCapacity = table.length;
584 while (newCapacity < targetCapacity)
585 newCapacity <<= 1;
586 if (newCapacity > table.length)
587 resize(newCapacity);
588 }
589
590 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
591 put(e.getKey(), e.getValue());
592 }
593
594 /**
595 * Removes the mapping for the specified key from this map if present.
596 *
597 * @param key key whose mapping is to be removed from the map
598 * @return the previous value associated with <tt>key</tt>, or
599 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
600 * (A <tt>null</tt> return can also indicate that the map
601 * previously associated <tt>null</tt> with <tt>key</tt>.)
602 */
603 public V remove(Object key) {
604 if(isEmpty()) {
605 return null;
606 }
607 Entry<K,V> e = removeEntryForKey(key);
608 return (e == null ? null : e.value);
609 }
610
611 /**
612 * Removes and returns the entry associated with the specified key
613 * in the HashMap. Returns null if the HashMap contains no mapping
614 * for this key.
615 */
616 final Entry<K,V> removeEntryForKey(Object key) {
617 int hash = (key == null) ? 0 : hash(key);
618 int i = indexFor(hash, table.length);
619 @SuppressWarnings("unchecked")
620 Entry<K,V> prev = (Entry<K,V>)table[i];
621 Entry<K,V> e = prev;
622
623 while (e != null) {
624 Entry<K,V> next = e.next;
625 Object k;
626 if (e.hash == hash &&
631 table[i] = next;
632 else
633 prev.next = next;
634 e.recordRemoval(this);
635 return e;
636 }
637 prev = e;
638 e = next;
639 }
640
641 return e;
642 }
643
644 /**
645 * Special version of remove for EntrySet using {@code Map.Entry.equals()}
646 * for matching.
647 */
648 final Entry<K,V> removeMapping(Object o) {
649 if (!(o instanceof Map.Entry))
650 return null;
651 if(isEmpty()) {
652 return null;
653 }
654
655 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
656 Object key = entry.getKey();
657 int hash = (key == null) ? 0 : hash(key);
658 int i = indexFor(hash, table.length);
659 @SuppressWarnings("unchecked")
660 Entry<K,V> prev = (Entry<K,V>)table[i];
661 Entry<K,V> e = prev;
662
663 while (e != null) {
664 Entry<K,V> next = e.next;
665 if (e.hash == hash && e.equals(entry)) {
666 modCount++;
667 size--;
668 if (prev == e)
669 table[i] = next;
670 else
671 prev.next = next;
672 e.recordRemoval(this);
673 return e;
674 }
675 prev = e;
676 e = next;
677 }
678
679 return e;
680 }
681
682 /**
683 * Removes all of the mappings from this map.
684 * The map will be empty after this call returns.
685 */
686 public void clear() {
687 modCount++;
688 Arrays.fill(table, null);
689 size = 0;
690 }
691
692 /**
693 * Returns <tt>true</tt> if this map maps one or more keys to the
694 * specified value.
695 *
696 * @param value value whose presence in this map is to be tested
697 * @return <tt>true</tt> if this map maps one or more keys to the
698 * specified value
699 */
700 public boolean containsValue(Object value) {
701 if(isEmpty()) {
702 return false;
703 }
704
705 if (value == null)
706 return containsNullValue();
707
708 Entry<?,?>[] tab = table;
709 for (int i = 0; i < tab.length ; i++)
710 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
711 if (value.equals(e.value))
712 return true;
713 return false;
714 }
715
716 /**
717 * Special-case code for containsValue with null argument
718 */
719 private boolean containsNullValue() {
720 Entry<?,?>[] tab = table;
721 for (int i = 0; i < tab.length ; i++)
722 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
723 if (e.value == null)
724 return true;
725 return false;
726 }
727
728 /**
729 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
730 * values themselves are not cloned.
731 *
732 * @return a shallow copy of this map
733 */
734 @SuppressWarnings("unchecked")
735 public Object clone() {
736 HashMap<K,V> result = null;
737 try {
738 result = (HashMap<K,V>)super.clone();
739 } catch (CloneNotSupportedException e) {
740 // assert false;
741 }
742 result.table = (table == EMPTY_TABLE)
743 ? EMPTY_TABLE
744 : new Entry<?,?>[table.length];
745 result.entrySet = null;
746 result.modCount = 0;
747 result.size = 0;
748 result.init();
749 result.putAllForCreate(this);
750
751 return result;
752 }
753
754 static class Entry<K,V> implements Map.Entry<K,V> {
755 final K key;
756 V value;
757 Entry<K,V> next;
758 final int hash;
759
760 /**
761 * Creates new entry.
762 */
763 Entry(int h, K k, V v, Entry<K,V> n) {
764 value = v;
780 value = newValue;
781 return oldValue;
782 }
783
784 public final boolean equals(Object o) {
785 if (!(o instanceof Map.Entry))
786 return false;
787 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
788 Object k1 = getKey();
789 Object k2 = e.getKey();
790 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
791 Object v1 = getValue();
792 Object v2 = e.getValue();
793 if (v1 == v2 || (v1 != null && v1.equals(v2)))
794 return true;
795 }
796 return false;
797 }
798
799 public final int hashCode() {
800 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
801 }
802
803 public final String toString() {
804 return getKey() + "=" + getValue();
805 }
806
807 /**
808 * This method is invoked whenever the value in an entry is
809 * overwritten by an invocation of put(k,v) for a key k that's already
810 * in the HashMap.
811 */
812 void recordAccess(HashMap<K,V> m) {
813 }
814
815 /**
816 * This method is invoked whenever the entry is
817 * removed from the table.
818 */
819 void recordRemoval(HashMap<K,V> m) {
820 }
1047 }
1048 public void clear() {
1049 HashMap.this.clear();
1050 }
1051 }
1052
1053 /**
1054 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1055 * serialize it).
1056 *
1057 * @serialData The <i>capacity</i> of the HashMap (the length of the
1058 * bucket array) is emitted (int), followed by the
1059 * <i>size</i> (an int, the number of key-value
1060 * mappings), followed by the key (Object) and value (Object)
1061 * for each key-value mapping. The key-value mappings are
1062 * emitted in no particular order.
1063 */
1064 private void writeObject(java.io.ObjectOutputStream s)
1065 throws IOException
1066 {
1067 // Write out the threshold, loadfactor, and any hidden stuff
1068 s.defaultWriteObject();
1069
1070 // Write out number of buckets
1071 if (table==EMPTY_TABLE)
1072 s.writeInt(initialCapacity); // power of 2.
1073 else
1074 s.writeInt(table.length);
1075
1076 // Write out size (number of Mappings)
1077 s.writeInt(size);
1078
1079 // Write out keys and values (alternating)
1080 if (size > 0) {
1081 for(Map.Entry<K,V> e : entrySet0()) {
1082 s.writeObject(e.getKey());
1083 s.writeObject(e.getValue());
1084 }
1085 }
1086 }
1087
1088 private static final long serialVersionUID = 362498820763181265L;
1089
1090 /**
1091 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1092 * deserialize it).
1093 */
1096 {
1097 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1098 s.defaultReadObject();
1099 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1100 throw new InvalidObjectException("Illegal load factor: " +
1101 loadFactor);
1102
1103 // set hashMask
1104 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1105 sun.misc.Hashing.randomHashSeed(this));
1106
1107 // Read in number of buckets and allocate the bucket array;
1108 s.readInt(); // ignored
1109
1110 // Read number of mappings
1111 int mappings = s.readInt();
1112 if (mappings < 0)
1113 throw new InvalidObjectException("Illegal mappings count: " +
1114 mappings);
1115
1116 int mappingsCapacity = Math.max((int) Math.min(
1117 // capacity chosen by number of mappings
1118 // and desired load (if >= 0.25)
1119 mappings * Math.min(1 / loadFactor, 4.0f),
1120 // we have limits...
1121 HashMap.MAXIMUM_CAPACITY), 0);
1122 // Find a power of 2 >= mappingCapacity
1123 int capacity = (capacity = Integer.highestOneBit(mappingsCapacity)) != 0
1124 ? capacity
1125 : 1;
1126 capacity <<= (Integer.bitCount(mappingsCapacity) > 1) ? 1 : 0;
1127 Holder.UNSAFE.putIntVolatile(this, Holder.INITIAL_CAPACITY_OFFSET,
1128 capacity);
1129
1130 if(mappings > 0) {
1131 inflateTable();
1132 } else {
1133 table = EMPTY_TABLE;
1134 threshold = 0;
1135 }
1136
1137 init(); // Give subclass a chance to do its thing.
1138
1139 // Read the keys and values, and put the mappings in the HashMap
1140 for (int i=0; i<mappings; i++) {
1141 @SuppressWarnings("unchecked")
1142 K key = (K) s.readObject();
1143 @SuppressWarnings("unchecked")
1144 V value = (V) s.readObject();
1145 putForCreate(key, value);
1146 }
1147 }
1148
1149 // These methods are used when serializing HashSets
1150 int capacity() { return table.length; }
1151 float loadFactor() { return loadFactor; }
1152 }
|