199 // disable alternative hashing if -1
200 if (threshold == -1) {
201 threshold = Integer.MAX_VALUE;
202 }
203
204 if (threshold < 0) {
205 throw new IllegalArgumentException("value must be positive integer.");
206 }
207 } catch(IllegalArgumentException failed) {
208 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
209 }
210
211 ALTERNATIVE_HASHING_THRESHOLD = threshold;
212 }
213 }
214
215 /**
216 * If {@code true} then perform alternative hashing of String keys to reduce
217 * the incidence of collisions due to weak hash code calculation.
218 */
219 transient boolean useAltHashing;
220
221 // Unsafe mechanics
222 /**
223 * Unsafe utilities
224 */
225 private static final sun.misc.Unsafe UNSAFE;
226
227 /**
228 * Offset of "final" hashSeed field we must set in readObject() method.
229 */
230 private static final long HASHSEED_OFFSET;
231
232 static {
233 try {
234 UNSAFE = sun.misc.Unsafe.getUnsafe();
235 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
236 Hashtable.class.getDeclaredField("hashSeed"));
237 } catch (NoSuchFieldException | SecurityException e) {
238 throw new Error("Failed to record hashSeed offset", e);
239 }
240 }
241
242 /**
243 * A randomizing value associated with this instance that is applied to
244 * hash code of keys to make hash collisions harder to find.
245 */
246 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
247
248 private int hash(Object k) {
249 if (useAltHashing) {
250 if (k.getClass() == String.class) {
251 return sun.misc.Hashing.stringHash32((String) k);
252 } else {
253 int h = hashSeed ^ k.hashCode();
254
255 // This function ensures that hashCodes that differ only by
256 // constant multiples at each bit position have a bounded
257 // number of collisions (approximately 8 at default load factor).
258 h ^= (h >>> 20) ^ (h >>> 12);
259 return h ^ (h >>> 7) ^ (h >>> 4);
260 }
261 } else {
262 return k.hashCode();
263 }
264 }
265
266 /**
267 * Constructs a new, empty hashtable with the specified initial
268 * capacity and the specified load factor.
269 *
270 * @param initialCapacity the initial capacity of the hashtable.
271 * @param loadFactor the load factor of the hashtable.
272 * @exception IllegalArgumentException if the initial capacity is less
273 * than zero, or if the load factor is nonpositive.
274 */
275 public Hashtable(int initialCapacity, float loadFactor) {
276 if (initialCapacity < 0)
277 throw new IllegalArgumentException("Illegal Capacity: "+
278 initialCapacity);
279 if (loadFactor <= 0 || Float.isNaN(loadFactor))
280 throw new IllegalArgumentException("Illegal Load: "+loadFactor);
281
282 if (initialCapacity==0)
283 initialCapacity = 1;
284 this.loadFactor = loadFactor;
285 table = new Entry[initialCapacity];
286 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
287 useAltHashing = sun.misc.VM.isBooted() &&
288 (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
289 }
290
291 /**
292 * Constructs a new, empty hashtable with the specified initial capacity
293 * and default load factor (0.75).
294 *
295 * @param initialCapacity the initial capacity of the hashtable.
296 * @exception IllegalArgumentException if the initial capacity is less
297 * than zero.
298 */
299 public Hashtable(int initialCapacity) {
300 this(initialCapacity, 0.75f);
301 }
302
303 /**
304 * Constructs a new, empty hashtable with a default initial capacity (11)
305 * and load factor (0.75).
306 */
307 public Hashtable() {
308 this(11, 0.75f);
480 * efficiently. This method is called automatically when the
481 * number of keys in the hashtable exceeds this hashtable's capacity
482 * and load factor.
483 */
484 protected void rehash() {
485 int oldCapacity = table.length;
486 Entry<K,V>[] oldMap = table;
487
488 // overflow-conscious code
489 int newCapacity = (oldCapacity << 1) + 1;
490 if (newCapacity - MAX_ARRAY_SIZE > 0) {
491 if (oldCapacity == MAX_ARRAY_SIZE)
492 // Keep running with MAX_ARRAY_SIZE buckets
493 return;
494 newCapacity = MAX_ARRAY_SIZE;
495 }
496 Entry<K,V>[] newMap = new Entry[newCapacity];
497
498 modCount++;
499 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
500 boolean currentAltHashing = useAltHashing;
501 useAltHashing = sun.misc.VM.isBooted() &&
502 (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
503 boolean rehash = currentAltHashing ^ useAltHashing;
504
505 table = newMap;
506
507 for (int i = oldCapacity ; i-- > 0 ;) {
508 for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
509 Entry<K,V> e = old;
510 old = old.next;
511
512 if (rehash) {
513 e.hash = hash(e.key);
514 }
515 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
516 e.next = newMap[index];
517 newMap[index] = e;
518 }
519 }
520 }
521
522 /**
523 * Maps the specified <code>key</code> to the specified
982 }
983 }
984
985 // Write out the key/value objects from the stacked entries
986 while (entryStack != null) {
987 s.writeObject(entryStack.key);
988 s.writeObject(entryStack.value);
989 entryStack = entryStack.next;
990 }
991 }
992
993 /**
994 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
995 */
996 private void readObject(java.io.ObjectInputStream s)
997 throws IOException, ClassNotFoundException
998 {
999 // Read in the length, threshold, and loadfactor
1000 s.defaultReadObject();
1001
1002 // set hashSeed
1003 UNSAFE.putIntVolatile(this, HASHSEED_OFFSET,
1004 sun.misc.Hashing.randomHashSeed(this));
1005
1006 // Read the original length of the array and number of elements
1007 int origlength = s.readInt();
1008 int elements = s.readInt();
1009
1010 // Compute new size with a bit of room 5% to grow but
1011 // no larger than the original size. Make the length
1012 // odd if it's large enough, this helps distribute the entries.
1013 // Guard against the length ending up zero, that's not valid.
1014 int length = (int)(elements * loadFactor) + (elements / 20) + 3;
1015 if (length > elements && (length & 1) == 0)
1016 length--;
1017 if (origlength > 0 && length > origlength)
1018 length = origlength;
1019
1020 Entry<K,V>[] table = new Entry[length];
1021 threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
1022 count = 0;
1023 useAltHashing = sun.misc.VM.isBooted() &&
1024 (length >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
1025
1026 // Read the number of elements and then all the key/value objects
1027 for (; elements > 0; elements--) {
1028 K key = (K)s.readObject();
1029 V value = (V)s.readObject();
1030 // synch could be eliminated for performance
1031 reconstitutionPut(table, key, value);
1032 }
1033 this.table = table;
1034 }
1035
1036 /**
1037 * The put method used by readObject. This is provided because put
1038 * is overridable and should not be called in readObject since the
1039 * subclass will not yet be initialized.
1040 *
1041 * <p>This differs from the regular put method in several ways. No
1042 * checking for rehashing is necessary since the number of elements
1043 * initially in the table is known. The modCount is not incremented
1044 * because we are creating a new instance. Also, no return value
1045 * is needed.
1046 */
1047 private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
1048 throws StreamCorruptedException
1049 {
1050 if (value == null) {
1051 throw new java.io.StreamCorruptedException();
1052 }
1053 // Makes sure the key is not already in the hashtable.
|
199 // disable alternative hashing if -1
200 if (threshold == -1) {
201 threshold = Integer.MAX_VALUE;
202 }
203
204 if (threshold < 0) {
205 throw new IllegalArgumentException("value must be positive integer.");
206 }
207 } catch(IllegalArgumentException failed) {
208 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
209 }
210
211 ALTERNATIVE_HASHING_THRESHOLD = threshold;
212 }
213 }
214
215 /**
216 * If {@code true} then perform alternative hashing of String keys to reduce
217 * the incidence of collisions due to weak hash code calculation.
218 */
219 transient boolean useAltHashing = false;
220
221 /**
222 * A randomizing value associated with this instance that is applied to
223 * hash code of keys to make hash collisions harder to find.
224 */
225 transient int hashSeed;
226
227 /**
228 * Initialize the hashing mask value.
229 */
230 final boolean initHashSeedAsNeeded(int capacity) {
231 boolean currentAltHashing = useAltHashing;
232 useAltHashing = sun.misc.VM.isBooted() &&
233 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
234 boolean switching = currentAltHashing ^ useAltHashing;
235 if (switching) {
236 hashSeed = useAltHashing
237 ? sun.misc.Hashing.randomHashSeed(this)
238 : 0;
239 }
240 return switching;
241 }
242
243 private int hash(Object k) {
244 // We don't test for useAltHashing because hashSeed will be zero if
245 // alternative hashing is disabled.
246 return hashSeed ^ k.hashCode();
247 }
248
249 /**
250 * Constructs a new, empty hashtable with the specified initial
251 * capacity and the specified load factor.
252 *
253 * @param initialCapacity the initial capacity of the hashtable.
254 * @param loadFactor the load factor of the hashtable.
255 * @exception IllegalArgumentException if the initial capacity is less
256 * than zero, or if the load factor is nonpositive.
257 */
258 public Hashtable(int initialCapacity, float loadFactor) {
259 if (initialCapacity < 0)
260 throw new IllegalArgumentException("Illegal Capacity: "+
261 initialCapacity);
262 if (loadFactor <= 0 || Float.isNaN(loadFactor))
263 throw new IllegalArgumentException("Illegal Load: "+loadFactor);
264
265 if (initialCapacity==0)
266 initialCapacity = 1;
267 this.loadFactor = loadFactor;
268 table = new Entry[initialCapacity];
269 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
270 initHashSeedAsNeeded(initialCapacity);
271 }
272
273 /**
274 * Constructs a new, empty hashtable with the specified initial capacity
275 * and default load factor (0.75).
276 *
277 * @param initialCapacity the initial capacity of the hashtable.
278 * @exception IllegalArgumentException if the initial capacity is less
279 * than zero.
280 */
281 public Hashtable(int initialCapacity) {
282 this(initialCapacity, 0.75f);
283 }
284
285 /**
286 * Constructs a new, empty hashtable with a default initial capacity (11)
287 * and load factor (0.75).
288 */
289 public Hashtable() {
290 this(11, 0.75f);
462 * efficiently. This method is called automatically when the
463 * number of keys in the hashtable exceeds this hashtable's capacity
464 * and load factor.
465 */
466 protected void rehash() {
467 int oldCapacity = table.length;
468 Entry<K,V>[] oldMap = table;
469
470 // overflow-conscious code
471 int newCapacity = (oldCapacity << 1) + 1;
472 if (newCapacity - MAX_ARRAY_SIZE > 0) {
473 if (oldCapacity == MAX_ARRAY_SIZE)
474 // Keep running with MAX_ARRAY_SIZE buckets
475 return;
476 newCapacity = MAX_ARRAY_SIZE;
477 }
478 Entry<K,V>[] newMap = new Entry[newCapacity];
479
480 modCount++;
481 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
482 boolean rehash = initHashSeedAsNeeded(newCapacity);
483
484 table = newMap;
485
486 for (int i = oldCapacity ; i-- > 0 ;) {
487 for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
488 Entry<K,V> e = old;
489 old = old.next;
490
491 if (rehash) {
492 e.hash = hash(e.key);
493 }
494 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
495 e.next = newMap[index];
496 newMap[index] = e;
497 }
498 }
499 }
500
501 /**
502 * Maps the specified <code>key</code> to the specified
961 }
962 }
963
964 // Write out the key/value objects from the stacked entries
965 while (entryStack != null) {
966 s.writeObject(entryStack.key);
967 s.writeObject(entryStack.value);
968 entryStack = entryStack.next;
969 }
970 }
971
972 /**
973 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
974 */
975 private void readObject(java.io.ObjectInputStream s)
976 throws IOException, ClassNotFoundException
977 {
978 // Read in the length, threshold, and loadfactor
979 s.defaultReadObject();
980
981 // Read the original length of the array and number of elements
982 int origlength = s.readInt();
983 int elements = s.readInt();
984
985 // Compute new size with a bit of room 5% to grow but
986 // no larger than the original size. Make the length
987 // odd if it's large enough, this helps distribute the entries.
988 // Guard against the length ending up zero, that's not valid.
989 int length = (int)(elements * loadFactor) + (elements / 20) + 3;
990 if (length > elements && (length & 1) == 0)
991 length--;
992 if (origlength > 0 && length > origlength)
993 length = origlength;
994
995 Entry<K,V>[] newTable = new Entry[length];
996 threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
997 count = 0;
998 initHashSeedAsNeeded(length);
999
1000 // Read the number of elements and then all the key/value objects
1001 for (; elements > 0; elements--) {
1002 K key = (K)s.readObject();
1003 V value = (V)s.readObject();
1004 // synch could be eliminated for performance
1005 reconstitutionPut(newTable, key, value);
1006 }
1007 this.table = newTable;
1008 }
1009
1010 /**
1011 * The put method used by readObject. This is provided because put
1012 * is overridable and should not be called in readObject since the
1013 * subclass will not yet be initialized.
1014 *
1015 * <p>This differs from the regular put method in several ways. No
1016 * checking for rehashing is necessary since the number of elements
1017 * initially in the table is known. The modCount is not incremented
1018 * because we are creating a new instance. Also, no return value
1019 * is needed.
1020 */
1021 private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
1022 throws StreamCorruptedException
1023 {
1024 if (value == null) {
1025 throw new java.io.StreamCorruptedException();
1026 }
1027 // Makes sure the key is not already in the hashtable.
|