175 */
176 transient int modCount;
177
178 /**
179 * The default threshold of map capacity above which alternative hashing is
180 * used for String keys. Alternative hashing reduces the incidence of
181 * collisions due to weak hash code calculation for String keys.
182 * <p/>
183 * This value may be overridden by defining the system property
184 * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
185 * forces alternative hashing to be used at all times whereas
186 * {@code -1} value ensures that alternative hashing is never used.
187 */
188 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
189
190 /**
191 * holds values which can't be initialized until after VM is booted.
192 */
193 private static class Holder {
194
195 // Unsafe mechanics
196 /**
197 * Unsafe utilities
198 */
199 static final sun.misc.Unsafe UNSAFE;
200
201 /**
202 * Offset of "final" hashSeed field we must set in readObject() method.
203 */
204 static final long HASHSEED_OFFSET;
205
206 /**
207 * Table capacity above which to switch to use alternative hashing.
208 */
209 static final int ALTERNATIVE_HASHING_THRESHOLD;
210
211 static {
212 String altThreshold = java.security.AccessController.doPrivileged(
213 new sun.security.action.GetPropertyAction(
214 "jdk.map.althashing.threshold"));
215
216 int threshold;
217 try {
218 threshold = (null != altThreshold)
219 ? Integer.parseInt(altThreshold)
220 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
221
222 // disable alternative hashing if -1
223 if (threshold == -1) {
224 threshold = Integer.MAX_VALUE;
225 }
226
227 if (threshold < 0) {
228 throw new IllegalArgumentException("value must be positive integer.");
229 }
230 } catch(IllegalArgumentException failed) {
231 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
232 }
233 ALTERNATIVE_HASHING_THRESHOLD = threshold;
234
235 try {
236 UNSAFE = sun.misc.Unsafe.getUnsafe();
237 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
238 HashMap.class.getDeclaredField("hashSeed"));
239 } catch (NoSuchFieldException | SecurityException e) {
240 throw new Error("Failed to record hashSeed offset", e);
241 }
242 }
243 }
244
245 /**
246 * If {@code true} then perform alternative hashing of String keys to reduce
247 * the incidence of collisions due to weak hash code calculation.
248 */
249 transient boolean useAltHashing;
250
251 /**
252 * A randomizing value associated with this instance that is applied to
253 * hash code of keys to make hash collisions harder to find.
254 */
255 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
256
257 /**
258 * Constructs an empty <tt>HashMap</tt> with the specified initial
259 * capacity and load factor.
260 *
261 * @param initialCapacity the initial capacity
262 * @param loadFactor the load factor
263 * @throws IllegalArgumentException if the initial capacity is negative
264 * or the load factor is nonpositive
265 */
266 public HashMap(int initialCapacity, float loadFactor) {
267 if (initialCapacity < 0)
268 throw new IllegalArgumentException("Illegal initial capacity: " +
269 initialCapacity);
270 if (initialCapacity > MAXIMUM_CAPACITY)
271 initialCapacity = MAXIMUM_CAPACITY;
272 if (loadFactor <= 0 || Float.isNaN(loadFactor))
273 throw new IllegalArgumentException("Illegal load factor: " +
274 loadFactor);
275
276 // Find a power of 2 >= initialCapacity
277 int capacity = 1;
278 while (capacity < initialCapacity)
279 capacity <<= 1;
280
281 this.loadFactor = loadFactor;
282 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
283 table = new Entry[capacity];
284 useAltHashing = sun.misc.VM.isBooted() &&
285 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
286 init();
287 }
288
289 /**
290 * Constructs an empty <tt>HashMap</tt> with the specified initial
291 * capacity and the default load factor (0.75).
292 *
293 * @param initialCapacity the initial capacity.
294 * @throws IllegalArgumentException if the initial capacity is negative.
295 */
296 public HashMap(int initialCapacity) {
297 this(initialCapacity, DEFAULT_LOAD_FACTOR);
298 }
299
300 /**
301 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
302 * (16) and the default load factor (0.75).
303 */
304 public HashMap() {
305 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
316 */
317 public HashMap(Map<? extends K, ? extends V> m) {
318 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
319 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
320 putAllForCreate(m);
321 }
322
323 // internal utilities
324
325 /**
326 * Initialization hook for subclasses. This method is called
327 * in all constructors and pseudo-constructors (clone, readObject)
328 * after HashMap has been initialized but before any entries have
329 * been inserted. (In the absence of this method, readObject would
330 * require explicit knowledge of subclasses.)
331 */
332 void init() {
333 }
334
335 /**
336 * Retrieve object hash code and applies a supplemental hash function to the
337 * result hash, which defends against poor quality hash functions. This is
338 * critical because HashMap uses power-of-two length hash tables, that
339 * otherwise encounter collisions for hashCodes that do not differ
340 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
341 */
342 final int hash(Object k) {
343 int h = 0;
344 if (useAltHashing) {
345 if (k instanceof String) {
346 return sun.misc.Hashing.stringHash32((String) k);
347 }
348 h = hashSeed;
349 }
350
351 h ^= k.hashCode();
352
353 // This function ensures that hashCodes that differ only by
354 // constant multiples at each bit position have a bounded
355 // number of collisions (approximately 8 at default load factor).
356 h ^= (h >>> 20) ^ (h >>> 12);
357 return h ^ (h >>> 7) ^ (h >>> 4);
358 }
359
360 /**
361 * Returns index for hash code h.
362 */
363 static int indexFor(int h, int length) {
364 return h & (length-1);
365 }
366
367 /**
368 * Returns the number of key-value mappings in this map.
369 *
540 * number of keys in this map reaches its threshold.
541 *
542 * If current capacity is MAXIMUM_CAPACITY, this method does not
543 * resize the map, but sets threshold to Integer.MAX_VALUE.
544 * This has the effect of preventing future calls.
545 *
546 * @param newCapacity the new capacity, MUST be a power of two;
547 * must be greater than current capacity unless current
548 * capacity is MAXIMUM_CAPACITY (in which case value
549 * is irrelevant).
550 */
551 void resize(int newCapacity) {
552 Entry[] oldTable = table;
553 int oldCapacity = oldTable.length;
554 if (oldCapacity == MAXIMUM_CAPACITY) {
555 threshold = Integer.MAX_VALUE;
556 return;
557 }
558
559 Entry[] newTable = new Entry[newCapacity];
560 boolean oldAltHashing = useAltHashing;
561 useAltHashing |= sun.misc.VM.isBooted() &&
562 (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
563 boolean rehash = oldAltHashing ^ useAltHashing;
564 transfer(newTable, rehash);
565 table = newTable;
566 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
567 }
568
569 /**
570 * Transfers all entries from current table to newTable.
571 */
572 void transfer(Entry[] newTable, boolean rehash) {
573 int newCapacity = newTable.length;
574 for (Entry<K,V> e : table) {
575 while(null != e) {
576 Entry<K,V> next = e.next;
577 if (rehash) {
578 e.hash = null == e.key ? 0 : hash(e.key);
579 }
580 int i = indexFor(e.hash, newCapacity);
581 e.next = newTable[i];
582 newTable[i] = e;
583 e = next;
584 }
798 value = newValue;
799 return oldValue;
800 }
801
802 public final boolean equals(Object o) {
803 if (!(o instanceof Map.Entry))
804 return false;
805 Map.Entry e = (Map.Entry)o;
806 Object k1 = getKey();
807 Object k2 = e.getKey();
808 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
809 Object v1 = getValue();
810 Object v2 = e.getValue();
811 if (v1 == v2 || (v1 != null && v1.equals(v2)))
812 return true;
813 }
814 return false;
815 }
816
817 public final int hashCode() {
818 return (key==null ? 0 : key.hashCode()) ^
819 (value==null ? 0 : value.hashCode());
820 }
821
822 public final String toString() {
823 return getKey() + "=" + getValue();
824 }
825
826 /**
827 * This method is invoked whenever the value in an entry is
828 * overwritten by an invocation of put(k,v) for a key k that's already
829 * in the HashMap.
830 */
831 void recordAccess(HashMap<K,V> m) {
832 }
833
834 /**
835 * This method is invoked whenever the entry is
836 * removed from the table.
837 */
838 void recordRemoval(HashMap<K,V> m) {
839 }
1100 s.writeObject(e.getValue());
1101 }
1102 }
1103 }
1104
1105 private static final long serialVersionUID = 362498820763181265L;
1106
1107 /**
1108 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1109 * deserialize it).
1110 */
1111 private void readObject(java.io.ObjectInputStream s)
1112 throws IOException, ClassNotFoundException
1113 {
1114 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1115 s.defaultReadObject();
1116 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1117 throw new InvalidObjectException("Illegal load factor: " +
1118 loadFactor);
1119
1120 // set hashSeed (can only happen after VM boot)
1121 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1122 sun.misc.Hashing.randomHashSeed(this));
1123
1124 // Read in number of buckets and allocate the bucket array;
1125 s.readInt(); // ignored
1126
1127 // Read number of mappings
1128 int mappings = s.readInt();
1129 if (mappings < 0)
1130 throw new InvalidObjectException("Illegal mappings count: " +
1131 mappings);
1132
1133 int initialCapacity = (int) Math.min(
1134 // capacity chosen by number of mappings
1135 // and desired load (if >= 0.25)
1136 mappings * Math.min(1 / loadFactor, 4.0f),
1137 // we have limits...
1138 HashMap.MAXIMUM_CAPACITY);
1139 int capacity = 1;
1140 // find smallest power of two which holds all mappings
1141 while (capacity < initialCapacity) {
1142 capacity <<= 1;
1143 }
1144
1145 table = new Entry[capacity];
1146 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
1147 useAltHashing = sun.misc.VM.isBooted() &&
1148 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
1149
1150 init(); // Give subclass a chance to do its thing.
1151
1152 // Read the keys and values, and put the mappings in the HashMap
1153 for (int i=0; i<mappings; i++) {
1154 K key = (K) s.readObject();
1155 V value = (V) s.readObject();
1156 putForCreate(key, value);
1157 }
1158 }
1159
1160 // These methods are used when serializing HashSets
1161 int capacity() { return table.length; }
1162 float loadFactor() { return loadFactor; }
1163 }
|
175 */
176 transient int modCount;
177
178 /**
179 * The default threshold of map capacity above which alternative hashing is
180 * used for String keys. Alternative hashing reduces the incidence of
181 * collisions due to weak hash code calculation for String keys.
182 * <p/>
183 * This value may be overridden by defining the system property
184 * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
185 * forces alternative hashing to be used at all times whereas
186 * {@code -1} value ensures that alternative hashing is never used.
187 */
188 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
189
190 /**
191 * holds values which can't be initialized until after VM is booted.
192 */
193 private static class Holder {
194
195 /**
196 * Table capacity above which to switch to use alternative hashing.
197 */
198 static final int ALTERNATIVE_HASHING_THRESHOLD;
199
200 static {
201 String altThreshold = java.security.AccessController.doPrivileged(
202 new sun.security.action.GetPropertyAction(
203 "jdk.map.althashing.threshold"));
204
205 int threshold;
206 try {
207 threshold = (null != altThreshold)
208 ? Integer.parseInt(altThreshold)
209 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
210
211 // disable alternative hashing if -1
212 if (threshold == -1) {
213 threshold = Integer.MAX_VALUE;
214 }
215
216 if (threshold < 0) {
217 throw new IllegalArgumentException("value must be positive integer.");
218 }
219 } catch(IllegalArgumentException failed) {
220 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
221 }
222
223 ALTERNATIVE_HASHING_THRESHOLD = threshold;
224 }
225 }
226
227 /**
228 * A randomizing value associated with this instance that is applied to
229 * hash code of keys to make hash collisions harder to find. If 0 then
230 * alternative hashing is disabled.
231 */
232 transient int hashSeed = 0;
233
234 /**
235 * Constructs an empty <tt>HashMap</tt> with the specified initial
236 * capacity and load factor.
237 *
238 * @param initialCapacity the initial capacity
239 * @param loadFactor the load factor
240 * @throws IllegalArgumentException if the initial capacity is negative
241 * or the load factor is nonpositive
242 */
243 public HashMap(int initialCapacity, float loadFactor) {
244 if (initialCapacity < 0)
245 throw new IllegalArgumentException("Illegal initial capacity: " +
246 initialCapacity);
247 if (initialCapacity > MAXIMUM_CAPACITY)
248 initialCapacity = MAXIMUM_CAPACITY;
249 if (loadFactor <= 0 || Float.isNaN(loadFactor))
250 throw new IllegalArgumentException("Illegal load factor: " +
251 loadFactor);
252
253 // Find a power of 2 >= initialCapacity
254 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
255 ? capacity
256 : 1;
257 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
258
259 this.loadFactor = loadFactor;
260 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
261 table = new Entry[capacity];
262 initHashSeedAsNeeded(capacity);
263 init();
264 }
265
266 /**
267 * Constructs an empty <tt>HashMap</tt> with the specified initial
268 * capacity and the default load factor (0.75).
269 *
270 * @param initialCapacity the initial capacity.
271 * @throws IllegalArgumentException if the initial capacity is negative.
272 */
273 public HashMap(int initialCapacity) {
274 this(initialCapacity, DEFAULT_LOAD_FACTOR);
275 }
276
277 /**
278 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
279 * (16) and the default load factor (0.75).
280 */
281 public HashMap() {
282 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
293 */
294 public HashMap(Map<? extends K, ? extends V> m) {
295 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
296 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
297 putAllForCreate(m);
298 }
299
300 // internal utilities
301
302 /**
303 * Initialization hook for subclasses. This method is called
304 * in all constructors and pseudo-constructors (clone, readObject)
305 * after HashMap has been initialized but before any entries have
306 * been inserted. (In the absence of this method, readObject would
307 * require explicit knowledge of subclasses.)
308 */
309 void init() {
310 }
311
312 /**
313 * Initialize the hashing mask value. We defer initialization until we
314 * really need it.
315 */
316 final boolean initHashSeedAsNeeded(int capacity) {
317 boolean currentAltHashing = hashSeed != 0;
318 boolean useAltHashing = sun.misc.VM.isBooted() &&
319 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
320 boolean switching = currentAltHashing ^ useAltHashing;
321 if (switching) {
322 hashSeed = useAltHashing
323 ? sun.misc.Hashing.randomHashSeed(this)
324 : 0;
325 }
326 return switching;
327 }
328
329 /**
330 * Retrieve object hash code and applies a supplemental hash function to the
331 * result hash, which defends against poor quality hash functions. This is
332 * critical because HashMap uses power-of-two length hash tables, that
333 * otherwise encounter collisions for hashCodes that do not differ
334 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
335 */
336 final int hash(Object k) {
337 int h = hashSeed;
338 if (0 != h && k instanceof String) {
339 return sun.misc.Hashing.stringHash32((String) k);
340 }
341
342 h ^= k.hashCode();
343
344 // This function ensures that hashCodes that differ only by
345 // constant multiples at each bit position have a bounded
346 // number of collisions (approximately 8 at default load factor).
347 h ^= (h >>> 20) ^ (h >>> 12);
348 return h ^ (h >>> 7) ^ (h >>> 4);
349 }
350
351 /**
352 * Returns index for hash code h.
353 */
354 static int indexFor(int h, int length) {
355 return h & (length-1);
356 }
357
358 /**
359 * Returns the number of key-value mappings in this map.
360 *
531 * number of keys in this map reaches its threshold.
532 *
533 * If current capacity is MAXIMUM_CAPACITY, this method does not
534 * resize the map, but sets threshold to Integer.MAX_VALUE.
535 * This has the effect of preventing future calls.
536 *
537 * @param newCapacity the new capacity, MUST be a power of two;
538 * must be greater than current capacity unless current
539 * capacity is MAXIMUM_CAPACITY (in which case value
540 * is irrelevant).
541 */
542 void resize(int newCapacity) {
543 Entry[] oldTable = table;
544 int oldCapacity = oldTable.length;
545 if (oldCapacity == MAXIMUM_CAPACITY) {
546 threshold = Integer.MAX_VALUE;
547 return;
548 }
549
550 Entry[] newTable = new Entry[newCapacity];
551 transfer(newTable, initHashSeedAsNeeded(newCapacity));
552 table = newTable;
553 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
554 }
555
556 /**
557 * Transfers all entries from current table to newTable.
558 */
559 void transfer(Entry[] newTable, boolean rehash) {
560 int newCapacity = newTable.length;
561 for (Entry<K,V> e : table) {
562 while(null != e) {
563 Entry<K,V> next = e.next;
564 if (rehash) {
565 e.hash = null == e.key ? 0 : hash(e.key);
566 }
567 int i = indexFor(e.hash, newCapacity);
568 e.next = newTable[i];
569 newTable[i] = e;
570 e = next;
571 }
785 value = newValue;
786 return oldValue;
787 }
788
789 public final boolean equals(Object o) {
790 if (!(o instanceof Map.Entry))
791 return false;
792 Map.Entry e = (Map.Entry)o;
793 Object k1 = getKey();
794 Object k2 = e.getKey();
795 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
796 Object v1 = getValue();
797 Object v2 = e.getValue();
798 if (v1 == v2 || (v1 != null && v1.equals(v2)))
799 return true;
800 }
801 return false;
802 }
803
804 public final int hashCode() {
805 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
806 }
807
808 public final String toString() {
809 return getKey() + "=" + getValue();
810 }
811
812 /**
813 * This method is invoked whenever the value in an entry is
814 * overwritten by an invocation of put(k,v) for a key k that's already
815 * in the HashMap.
816 */
817 void recordAccess(HashMap<K,V> m) {
818 }
819
820 /**
821 * This method is invoked whenever the entry is
822 * removed from the table.
823 */
824 void recordRemoval(HashMap<K,V> m) {
825 }
1086 s.writeObject(e.getValue());
1087 }
1088 }
1089 }
1090
1091 private static final long serialVersionUID = 362498820763181265L;
1092
1093 /**
1094 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1095 * deserialize it).
1096 */
1097 private void readObject(java.io.ObjectInputStream s)
1098 throws IOException, ClassNotFoundException
1099 {
1100 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1101 s.defaultReadObject();
1102 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1103 throw new InvalidObjectException("Illegal load factor: " +
1104 loadFactor);
1105
1106 // Read in number of buckets and allocate the bucket array;
1107 s.readInt(); // ignored
1108
1109 // Read number of mappings
1110 int mappings = s.readInt();
1111 if (mappings < 0)
1112 throw new InvalidObjectException("Illegal mappings count: " +
1113 mappings);
1114
1115 int initialCapacity = (int) Math.min(
1116 // capacity chosen by number of mappings
1117 // and desired load (if >= 0.25)
1118 mappings * Math.min(1 / loadFactor, 4.0f),
1119 // we have limits...
1120 HashMap.MAXIMUM_CAPACITY);
1121 // find smallest power of two which holds all mappings
1122 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
1123 ? capacity
1124 : 1;
1125 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
1126
1127 table = new Entry[capacity];
1128 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
1129 initHashSeedAsNeeded(capacity);
1130
1131 init(); // Give subclass a chance to do its thing.
1132
1133 // Read the keys and values, and put the mappings in the HashMap
1134 for (int i=0; i<mappings; i++) {
1135 K key = (K) s.readObject();
1136 V value = (V) s.readObject();
1137 putForCreate(key, value);
1138 }
1139 }
1140
1141 // These methods are used when serializing HashSets
1142 int capacity() { return table.length; }
1143 float loadFactor() { return loadFactor; }
1144 }
|