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).
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 ALTERNATIVE_HASHING_THRESHOLD = threshold;
223 }
224 }
225
226 /**
227 * If {@code true} then perform alternative hashing of String keys to reduce
228 * the incidence of collisions due to weak hash code calculation.
229 */
230 transient boolean useAltHashing = false;
231
232 /**
233 * A randomizing value associated with this instance that is applied to
234 * hash code of keys to make hash collisions harder to find. Initialized via
235 * sun.misc.Unsafe when needed.
236 */
237 transient int hashSeed = 0;
238
239 /**
240 * Constructs an empty <tt>HashMap</tt> with the specified initial
241 * capacity and load factor.
242 *
243 * @param initialCapacity the initial capacity
244 * @param loadFactor the load factor
245 * @throws IllegalArgumentException if the initial capacity is negative
246 * or the load factor is nonpositive
247 */
248 public HashMap(int initialCapacity, float loadFactor) {
249 if (initialCapacity < 0)
250 throw new IllegalArgumentException("Illegal initial capacity: " +
251 initialCapacity);
252 if (initialCapacity > MAXIMUM_CAPACITY)
253 initialCapacity = MAXIMUM_CAPACITY;
254 if (loadFactor <= 0 || Float.isNaN(loadFactor))
255 throw new IllegalArgumentException("Illegal load factor: " +
256 loadFactor);
257
258 // Find a power of 2 >= initialCapacity
259 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
260 ? capacity
261 : 1;
262 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
263
264 this.loadFactor = loadFactor;
265 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
266 table = new Entry[capacity];
267 initHashSeedAsNeeded(capacity);
268 init();
269 }
270
271 /**
272 * Constructs an empty <tt>HashMap</tt> with the specified initial
273 * capacity and the default load factor (0.75).
274 *
275 * @param initialCapacity the initial capacity.
276 * @throws IllegalArgumentException if the initial capacity is negative.
277 */
278 public HashMap(int initialCapacity) {
279 this(initialCapacity, DEFAULT_LOAD_FACTOR);
280 }
281
282 /**
283 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
284 * (16) and the default load factor (0.75).
285 */
286 public HashMap() {
287 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
298 */
299 public HashMap(Map<? extends K, ? extends V> m) {
300 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
301 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
302 putAllForCreate(m);
303 }
304
305 // internal utilities
306
307 /**
308 * Initialization hook for subclasses. This method is called
309 * in all constructors and pseudo-constructors (clone, readObject)
310 * after HashMap has been initialized but before any entries have
311 * been inserted. (In the absence of this method, readObject would
312 * require explicit knowledge of subclasses.)
313 */
314 void init() {
315 }
316
317 /**
318 * Initialize the hashing mask value. We defer initialization until we
319 * really need it.
320 */
321 final boolean initHashSeedAsNeeded(int capacity) {
322 boolean currentAltHashing = useAltHashing;
323 useAltHashing = sun.misc.VM.isBooted() &&
324 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
325 boolean switching = currentAltHashing ^ useAltHashing;
326 if (switching) {
327 hashSeed = useAltHashing
328 ? sun.misc.Hashing.randomHashSeed(this)
329 : 0;
330 }
331 return switching;
332 }
333
334 /**
335 * Retrieve object hash code and applies a supplemental hash function to the
336 * result hash, which defends against poor quality hash functions. This is
337 * critical because HashMap uses power-of-two length hash tables, that
338 * otherwise encounter collisions for hashCodes that do not differ
339 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
340 */
341 final int hash(Object k) {
342 int h = 0;
343 if (useAltHashing) {
344 if (k instanceof String) {
345 return sun.misc.Hashing.stringHash32((String) k);
346 }
347 h = hashSeed;
348 }
349
350 h ^= k.hashCode();
351
352 // This function ensures that hashCodes that differ only by
353 // constant multiples at each bit position have a bounded
354 // number of collisions (approximately 8 at default load factor).
539 * number of keys in this map reaches its threshold.
540 *
541 * If current capacity is MAXIMUM_CAPACITY, this method does not
542 * resize the map, but sets threshold to Integer.MAX_VALUE.
543 * This has the effect of preventing future calls.
544 *
545 * @param newCapacity the new capacity, MUST be a power of two;
546 * must be greater than current capacity unless current
547 * capacity is MAXIMUM_CAPACITY (in which case value
548 * is irrelevant).
549 */
550 void resize(int newCapacity) {
551 Entry[] oldTable = table;
552 int oldCapacity = oldTable.length;
553 if (oldCapacity == MAXIMUM_CAPACITY) {
554 threshold = Integer.MAX_VALUE;
555 return;
556 }
557
558 Entry[] newTable = new Entry[newCapacity];
559 transfer(newTable, initHashSeedAsNeeded(newCapacity));
560 table = newTable;
561 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
562 }
563
564 /**
565 * Transfers all entries from current table to newTable.
566 */
567 void transfer(Entry[] newTable, boolean rehash) {
568 int newCapacity = newTable.length;
569 for (Entry<K,V> e : table) {
570 while(null != e) {
571 Entry<K,V> next = e.next;
572 if (rehash) {
573 e.hash = null == e.key ? 0 : hash(e.key);
574 }
575 int i = indexFor(e.hash, newCapacity);
576 e.next = newTable[i];
577 newTable[i] = e;
578 e = next;
579 }
793 value = newValue;
794 return oldValue;
795 }
796
797 public final boolean equals(Object o) {
798 if (!(o instanceof Map.Entry))
799 return false;
800 Map.Entry e = (Map.Entry)o;
801 Object k1 = getKey();
802 Object k2 = e.getKey();
803 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
804 Object v1 = getValue();
805 Object v2 = e.getValue();
806 if (v1 == v2 || (v1 != null && v1.equals(v2)))
807 return true;
808 }
809 return false;
810 }
811
812 public final int hashCode() {
813 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
814 }
815
816 public final String toString() {
817 return getKey() + "=" + getValue();
818 }
819
820 /**
821 * This method is invoked whenever the value in an entry is
822 * overwritten by an invocation of put(k,v) for a key k that's already
823 * in the HashMap.
824 */
825 void recordAccess(HashMap<K,V> m) {
826 }
827
828 /**
829 * This method is invoked whenever the entry is
830 * removed from the table.
831 */
832 void recordRemoval(HashMap<K,V> m) {
833 }
1094 s.writeObject(e.getValue());
1095 }
1096 }
1097 }
1098
1099 private static final long serialVersionUID = 362498820763181265L;
1100
1101 /**
1102 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1103 * deserialize it).
1104 */
1105 private void readObject(java.io.ObjectInputStream s)
1106 throws IOException, ClassNotFoundException
1107 {
1108 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1109 s.defaultReadObject();
1110 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1111 throw new InvalidObjectException("Illegal load factor: " +
1112 loadFactor);
1113
1114 // Read in number of buckets and allocate the bucket array;
1115 s.readInt(); // ignored
1116
1117 // Read number of mappings
1118 int mappings = s.readInt();
1119 if (mappings < 0)
1120 throw new InvalidObjectException("Illegal mappings count: " +
1121 mappings);
1122
1123 int initialCapacity = (int) Math.min(
1124 // capacity chosen by number of mappings
1125 // and desired load (if >= 0.25)
1126 mappings * Math.min(1 / loadFactor, 4.0f),
1127 // we have limits...
1128 HashMap.MAXIMUM_CAPACITY);
1129 // find smallest power of two which holds all mappings
1130 int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
1131 ? capacity
1132 : 1;
1133 capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
1134
1135 table = new Entry[capacity];
1136 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
1137 initHashSeedAsNeeded(capacity);
1138
1139 init(); // Give subclass a chance to do its thing.
1140
1141 // Read the keys and values, and put the mappings in the HashMap
1142 for (int i=0; i<mappings; i++) {
1143 K key = (K) s.readObject();
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 }
|