112 * 113 * @author Arthur van Hoff 114 * @author Josh Bloch 115 * @author Neal Gafter 116 * @see Object#equals(java.lang.Object) 117 * @see Object#hashCode() 118 * @see Hashtable#rehash() 119 * @see Collection 120 * @see Map 121 * @see HashMap 122 * @see TreeMap 123 * @since JDK1.0 124 */ 125 public class Hashtable<K,V> 126 extends Dictionary<K,V> 127 implements Map<K,V>, Cloneable, java.io.Serializable { 128 129 /** 130 * The hash table data. 131 */ 132 private transient Entry[] table; 133 134 /** 135 * The total number of entries in the hash table. 136 */ 137 private transient int count; 138 139 /** 140 * The table is rehashed when its size exceeds this threshold. (The 141 * value of this field is (int)(capacity * loadFactor).) 142 * 143 * @serial 144 */ 145 private int threshold; 146 147 /** 148 * The load factor for the hashtable. 149 * 150 * @serial 151 */ 152 private float loadFactor; 153 154 /** 155 * The number of times this Hashtable has been structurally modified 156 * Structural modifications are those that change the number of entries in 157 * the Hashtable or otherwise modify its internal structure (e.g., 158 * rehash). This field is used to make iterators on Collection-views of 159 * the Hashtable fail-fast. (See ConcurrentModificationException). 160 */ 161 private transient int modCount = 0; 162 163 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 164 private static final long serialVersionUID = 1421746759512286392L; 165 166 /** 167 * Constructs a new, empty hashtable with the specified initial 168 * capacity and the specified load factor. 169 * 170 * @param initialCapacity the initial capacity of the hashtable. 171 * @param loadFactor the load factor of the hashtable. 172 * @exception IllegalArgumentException if the initial capacity is less 173 * than zero, or if the load factor is nonpositive. 174 */ 175 public Hashtable(int initialCapacity, float loadFactor) { 176 if (initialCapacity < 0) 177 throw new IllegalArgumentException("Illegal Capacity: "+ 178 initialCapacity); 179 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 180 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 181 182 if (initialCapacity==0) 183 initialCapacity = 1; 184 this.loadFactor = loadFactor; 185 table = new Entry[initialCapacity]; 186 threshold = (int)(initialCapacity * loadFactor); 187 } 188 189 /** 190 * Constructs a new, empty hashtable with the specified initial capacity 191 * and default load factor (0.75). 192 * 193 * @param initialCapacity the initial capacity of the hashtable. 194 * @exception IllegalArgumentException if the initial capacity is less 195 * than zero. 196 */ 197 public Hashtable(int initialCapacity) { 198 this(initialCapacity, 0.75f); 199 } 200 201 /** 202 * Constructs a new, empty hashtable with a default initial capacity (11) 203 * and load factor (0.75). 204 */ 205 public Hashtable() { 206 this(11, 0.75f); 310 * specified value 311 * @throws NullPointerException if the value is <code>null</code> 312 * @since 1.2 313 */ 314 public boolean containsValue(Object value) { 315 return contains(value); 316 } 317 318 /** 319 * Tests if the specified object is a key in this hashtable. 320 * 321 * @param key possible key 322 * @return <code>true</code> if and only if the specified object 323 * is a key in this hashtable, as determined by the 324 * <tt>equals</tt> method; <code>false</code> otherwise. 325 * @throws NullPointerException if the key is <code>null</code> 326 * @see #contains(Object) 327 */ 328 public synchronized boolean containsKey(Object key) { 329 Entry tab[] = table; 330 int hash = key.hashCode(); 331 int index = (hash & 0x7FFFFFFF) % tab.length; 332 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 333 if ((e.hash == hash) && e.key.equals(key)) { 334 return true; 335 } 336 } 337 return false; 338 } 339 340 /** 341 * Returns the value to which the specified key is mapped, 342 * or {@code null} if this map contains no mapping for the key. 343 * 344 * <p>More formally, if this map contains a mapping from a key 345 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 346 * then this method returns {@code v}; otherwise it returns 347 * {@code null}. (There can be at most one such mapping.) 348 * 349 * @param key the key whose associated value is to be returned 350 * @return the value to which the specified key is mapped, or 351 * {@code null} if this map contains no mapping for the key 352 * @throws NullPointerException if the specified key is null 353 * @see #put(Object, Object) 354 */ 355 public synchronized V get(Object key) { 356 Entry tab[] = table; 357 int hash = key.hashCode(); 358 int index = (hash & 0x7FFFFFFF) % tab.length; 359 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 360 if ((e.hash == hash) && e.key.equals(key)) { 361 return e.value; 362 } 363 } 364 return null; 365 } 366 367 /** 368 * The maximum size of array to allocate. 369 * Some VMs reserve some header words in an array. 370 * Attempts to allocate larger arrays may result in 371 * OutOfMemoryError: Requested array size exceeds VM limit 372 */ 373 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 374 375 /** 376 * Increases the capacity of and internally reorganizes this 377 * hashtable, in order to accommodate and access its entries more 378 * efficiently. This method is called automatically when the 379 * number of keys in the hashtable exceeds this hashtable's capacity 380 * and load factor. 381 */ 382 protected void rehash() { 383 int oldCapacity = table.length; 384 Entry[] oldMap = table; 385 386 // overflow-conscious code 387 int newCapacity = (oldCapacity << 1) + 1; 388 if (newCapacity - MAX_ARRAY_SIZE > 0) { 389 if (oldCapacity == MAX_ARRAY_SIZE) 390 // Keep running with MAX_ARRAY_SIZE buckets 391 return; 392 newCapacity = MAX_ARRAY_SIZE; 393 } 394 Entry[] newMap = new Entry[newCapacity]; 395 396 modCount++; 397 threshold = (int)(newCapacity * loadFactor); 398 table = newMap; 399 400 for (int i = oldCapacity ; i-- > 0 ;) { 401 for (Entry<K,V> old = oldMap[i] ; old != null ; ) { 402 Entry<K,V> e = old; 403 old = old.next; 404 405 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 406 e.next = newMap[index]; 407 newMap[index] = e; 408 } 409 } 410 } 411 412 /** 413 * Maps the specified <code>key</code> to the specified 414 * <code>value</code> in this hashtable. Neither the key nor the 415 * value can be <code>null</code>. <p> 416 * 417 * The value can be retrieved by calling the <code>get</code> method 418 * with a key that is equal to the original key. 419 * 420 * @param key the hashtable key 421 * @param value the value 422 * @return the previous value of the specified key in this hashtable, 423 * or <code>null</code> if it did not have one 424 * @exception NullPointerException if the key or value is 425 * <code>null</code> 426 * @see Object#equals(Object) 427 * @see #get(Object) 428 */ 429 public synchronized V put(K key, V value) { 430 // Make sure the value is not null 431 if (value == null) { 432 throw new NullPointerException(); 433 } 434 435 // Makes sure the key is not already in the hashtable. 436 Entry tab[] = table; 437 int hash = key.hashCode(); 438 int index = (hash & 0x7FFFFFFF) % tab.length; 439 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 440 if ((e.hash == hash) && e.key.equals(key)) { 441 V old = e.value; 442 e.value = value; 443 return old; 444 } 445 } 446 447 modCount++; 448 if (count >= threshold) { 449 // Rehash the table if the threshold is exceeded 450 rehash(); 451 452 tab = table; 453 index = (hash & 0x7FFFFFFF) % tab.length; 454 } 455 456 // Creates the new entry. 457 Entry<K,V> e = tab[index]; 458 tab[index] = new Entry<>(hash, key, value, e); 459 count++; 460 return null; 461 } 462 463 /** 464 * Removes the key (and its corresponding value) from this 465 * hashtable. This method does nothing if the key is not in the hashtable. 466 * 467 * @param key the key that needs to be removed 468 * @return the value to which the key had been mapped in this hashtable, 469 * or <code>null</code> if the key did not have a mapping 470 * @throws NullPointerException if the key is <code>null</code> 471 */ 472 public synchronized V remove(Object key) { 473 Entry tab[] = table; 474 int hash = key.hashCode(); 475 int index = (hash & 0x7FFFFFFF) % tab.length; 476 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 477 if ((e.hash == hash) && e.key.equals(key)) { 478 modCount++; 479 if (prev != null) { 480 prev.next = e.next; 481 } else { 482 tab[index] = e.next; 483 } 484 count--; 485 V oldValue = e.value; 486 e.value = null; 487 return oldValue; 488 } 489 } 490 return null; 491 } 492 493 /** 494 * Copies all of the mappings from the specified map to this hashtable. 661 if (entrySet==null) 662 entrySet = Collections.synchronizedSet(new EntrySet(), this); 663 return entrySet; 664 } 665 666 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 667 public Iterator<Map.Entry<K,V>> iterator() { 668 return getIterator(ENTRIES); 669 } 670 671 public boolean add(Map.Entry<K,V> o) { 672 return super.add(o); 673 } 674 675 public boolean contains(Object o) { 676 if (!(o instanceof Map.Entry)) 677 return false; 678 Map.Entry entry = (Map.Entry)o; 679 Object key = entry.getKey(); 680 Entry[] tab = table; 681 int hash = key.hashCode(); 682 int index = (hash & 0x7FFFFFFF) % tab.length; 683 684 for (Entry e = tab[index]; e != null; e = e.next) 685 if (e.hash==hash && e.equals(entry)) 686 return true; 687 return false; 688 } 689 690 public boolean remove(Object o) { 691 if (!(o instanceof Map.Entry)) 692 return false; 693 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 694 K key = entry.getKey(); 695 Entry[] tab = table; 696 int hash = key.hashCode(); 697 int index = (hash & 0x7FFFFFFF) % tab.length; 698 699 for (Entry<K,V> e = tab[index], prev = null; e != null; 700 prev = e, e = e.next) { 701 if (e.hash==hash && e.equals(entry)) { 702 modCount++; 703 if (prev != null) 704 prev.next = e.next; 705 else 706 tab[index] = e.next; 707 708 count--; 709 e.value = null; 710 return true; 711 } 712 } 713 return false; 714 } 715 716 public int size() { 810 * @see Map#hashCode() 811 * @since 1.2 812 */ 813 public synchronized int hashCode() { 814 /* 815 * This code detects the recursion caused by computing the hash code 816 * of a self-referential hash table and prevents the stack overflow 817 * that would otherwise result. This allows certain 1.1-era 818 * applets with self-referential hash tables to work. This code 819 * abuses the loadFactor field to do double-duty as a hashCode 820 * in progress flag, so as not to worsen the space performance. 821 * A negative load factor indicates that hash code computation is 822 * in progress. 823 */ 824 int h = 0; 825 if (count == 0 || loadFactor < 0) 826 return h; // Returns zero 827 828 loadFactor = -loadFactor; // Mark hashCode computation in progress 829 Entry[] tab = table; 830 for (int i = 0; i < tab.length; i++) 831 for (Entry e = tab[i]; e != null; e = e.next) 832 h += e.key.hashCode() ^ e.value.hashCode(); 833 loadFactor = -loadFactor; // Mark hashCode computation complete 834 835 return h; 836 } 837 838 /** 839 * Save the state of the Hashtable to a stream (i.e., serialize it). 840 * 841 * @serialData The <i>capacity</i> of the Hashtable (the length of the 842 * bucket array) is emitted (int), followed by the 843 * <i>size</i> of the Hashtable (the number of key-value 844 * mappings), followed by the key (Object) and value (Object) 845 * for each key-value mapping represented by the Hashtable 846 * The key-value mappings are emitted in no particular order. 847 */ 848 private void writeObject(java.io.ObjectOutputStream s) 849 throws IOException { 850 Entry<Object, Object> entryStack = null; 851 852 synchronized (this) { 853 // Write out the length, threshold, loadfactor 854 s.defaultWriteObject(); 855 856 // Write out length, count of elements 857 s.writeInt(table.length); 858 s.writeInt(count); 859 860 // Stack copies of the entries in the table 861 for (int index = 0; index < table.length; index++) { 862 Entry entry = table[index]; 863 864 while (entry != null) { 865 entryStack = 866 new Entry<>(0, entry.key, entry.value, entryStack); 867 entry = entry.next; 868 } 869 } 870 } 871 872 // Write out the key/value objects from the stacked entries 873 while (entryStack != null) { 874 s.writeObject(entryStack.key); 875 s.writeObject(entryStack.value); 876 entryStack = entryStack.next; 877 } 878 } 879 880 /** 881 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 882 */ 883 private void readObject(java.io.ObjectInputStream s) 884 throws IOException, ClassNotFoundException 885 { 886 // Read in the length, threshold, and loadfactor 887 s.defaultReadObject(); 888 889 // Read the original length of the array and number of elements 890 int origlength = s.readInt(); 891 int elements = s.readInt(); 892 893 // Compute new size with a bit of room 5% to grow but 894 // no larger than the original size. Make the length 895 // odd if it's large enough, this helps distribute the entries. 896 // Guard against the length ending up zero, that's not valid. 897 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 898 if (length > elements && (length & 1) == 0) 899 length--; 900 if (origlength > 0 && length > origlength) 901 length = origlength; 902 903 Entry[] table = new Entry[length]; 904 count = 0; 905 906 // Read the number of elements and then all the key/value objects 907 for (; elements > 0; elements--) { 908 K key = (K)s.readObject(); 909 V value = (V)s.readObject(); 910 // synch could be eliminated for performance 911 reconstitutionPut(table, key, value); 912 } 913 this.table = table; 914 } 915 916 /** 917 * The put method used by readObject. This is provided because put 918 * is overridable and should not be called in readObject since the 919 * subclass will not yet be initialized. 920 * 921 * <p>This differs from the regular put method in several ways. No 922 * checking for rehashing is necessary since the number of elements 923 * initially in the table is known. The modCount is not incremented 924 * because we are creating a new instance. Also, no return value 925 * is needed. 926 */ 927 private void reconstitutionPut(Entry[] tab, K key, V value) 928 throws StreamCorruptedException 929 { 930 if (value == null) { 931 throw new java.io.StreamCorruptedException(); 932 } 933 // Makes sure the key is not already in the hashtable. 934 // This should not happen in deserialized version. 935 int hash = key.hashCode(); 936 int index = (hash & 0x7FFFFFFF) % tab.length; 937 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 938 if ((e.hash == hash) && e.key.equals(key)) { 939 throw new java.io.StreamCorruptedException(); 940 } 941 } 942 // Creates the new entry. 943 Entry<K,V> e = tab[index]; 944 tab[index] = new Entry<>(hash, key, value, e); 945 count++; 946 } 947 948 /** 949 * Hashtable collision list. 950 */ 951 private static class Entry<K,V> implements Map.Entry<K,V> { 952 int hash; 953 K key; 954 V value; 955 Entry<K,V> next; 956 957 protected Entry(int hash, K key, V value, Entry<K,V> next) { 958 this.hash = hash; 959 this.key = key; 960 this.value = value; 961 this.next = next; 962 } 963 964 protected Object clone() { 965 return new Entry<>(hash, key, value, 966 (next==null ? null : (Entry<K,V>) next.clone())); 967 } 968 969 // Map.Entry Ops 971 public K getKey() { 972 return key; 973 } 974 975 public V getValue() { 976 return value; 977 } 978 979 public V setValue(V value) { 980 if (value == null) 981 throw new NullPointerException(); 982 983 V oldValue = this.value; 984 this.value = value; 985 return oldValue; 986 } 987 988 public boolean equals(Object o) { 989 if (!(o instanceof Map.Entry)) 990 return false; 991 Map.Entry e = (Map.Entry)o; 992 993 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 994 (value==null ? e.getValue()==null : value.equals(e.getValue())); 995 } 996 997 public int hashCode() { 998 return hash ^ (value==null ? 0 : value.hashCode()); 999 } 1000 1001 public String toString() { 1002 return key.toString()+"="+value.toString(); 1003 } 1004 } 1005 1006 // Types of Enumerations/Iterations 1007 private static final int KEYS = 0; 1008 private static final int VALUES = 1; 1009 private static final int ENTRIES = 2; 1010 1011 /** 1012 * A hashtable enumerator class. This class implements both the 1013 * Enumeration and Iterator interfaces, but individual instances 1014 * can be created with the Iterator methods disabled. This is necessary 1015 * to avoid unintentionally increasing the capabilities granted a user 1016 * by passing an Enumeration. 1017 */ 1018 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { | 112 * 113 * @author Arthur van Hoff 114 * @author Josh Bloch 115 * @author Neal Gafter 116 * @see Object#equals(java.lang.Object) 117 * @see Object#hashCode() 118 * @see Hashtable#rehash() 119 * @see Collection 120 * @see Map 121 * @see HashMap 122 * @see TreeMap 123 * @since JDK1.0 124 */ 125 public class Hashtable<K,V> 126 extends Dictionary<K,V> 127 implements Map<K,V>, Cloneable, java.io.Serializable { 128 129 /** 130 * The hash table data. 131 */ 132 private transient Entry<K,V>[] table; 133 134 /** 135 * The total number of entries in the hash table. 136 */ 137 private transient int count; 138 139 /** 140 * The table is rehashed when its size exceeds this threshold. (The 141 * value of this field is (int)(capacity * loadFactor).) 142 * 143 * @serial 144 */ 145 private int threshold; 146 147 /** 148 * The load factor for the hashtable. 149 * 150 * @serial 151 */ 152 private float loadFactor; 153 154 /** 155 * The number of times this Hashtable has been structurally modified 156 * Structural modifications are those that change the number of entries in 157 * the Hashtable or otherwise modify its internal structure (e.g., 158 * rehash). This field is used to make iterators on Collection-views of 159 * the Hashtable fail-fast. (See ConcurrentModificationException). 160 */ 161 private transient int modCount = 0; 162 163 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 164 private static final long serialVersionUID = 1421746759512286392L; 165 166 /** 167 * The default threshold of capacity above which alternate hashing is used. 168 * Alternative hashing reduces the incidence of collisions due to weak hash 169 * code calculation. 170 * <p/> 171 * This value may be overridden by defining the system property 172 * {@code java.util.althashing.threshold}. A property value of {@code 1} 173 * forces alternative hashing to be used at all times whereas 174 * {@code 2147483648 } ({@code Integer.MAX_VALUE}) value ensures that 175 * alternative hashing is never used. 176 */ 177 static final int ALTERNATE_HASHING_THRESHOLD_DEFAULT = 0; 178 179 /** 180 * holds values which can't be initialized until after VM is booted. 181 */ 182 private static class Holder { 183 184 /** 185 * Table capacity above which to switch to use alternate hashing. 186 */ 187 static final int ALTERNATE_HASHING_THRESHOLD; 188 189 static { 190 String altThreshold = java.security.AccessController.doPrivileged( 191 new sun.security.action.GetPropertyAction( 192 "jdk.map.althashing.threshold")); 193 194 int threshold; 195 try { 196 threshold = (null != altThreshold) 197 ? Integer.parseInt(altThreshold) 198 : 1; 199 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 ALTERNATE_HASHING_THRESHOLD = threshold; 212 } 213 } 214 215 /** 216 * If {@code true} then perform alternate hashing to reduce the incidence of 217 * collisions due to weak hash code calculation. 218 */ 219 transient boolean useAltHashing; 220 221 // Unsafe mechanics 222 private static final sun.misc.Unsafe UNSAFE; 223 private static final long HASHMASK_OFFSET; 224 225 static { 226 try { 227 UNSAFE = sun.misc.Unsafe.getUnsafe(); 228 HASHMASK_OFFSET = UNSAFE.objectFieldOffset( 229 Hashtable.class.getDeclaredField("hashMask")); 230 } catch (NoSuchFieldException | SecurityException e) { 231 throw new Error(e); 232 } 233 } 234 235 /** 236 * A random mask value that is used for hashcode values associated with this 237 * instance to make hash collisions harder to find. 238 */ 239 transient final int hashMask = sun.misc.Hashing.makeHashMask(this); 240 241 private int hash(Object k) { 242 int h; 243 if (useAltHashing) { 244 if (k.getClass() == String.class) { 245 h = sun.misc.Hashing.stringHash32((String) k); 246 } else { 247 h = k.hashCode(); 248 249 // This function ensures that hashCodes that differ only by 250 // constant multiples at each bit position have a bounded 251 // number of collisions (approximately 8 at default load factor). 252 h ^= (h >>> 20) ^ (h >>> 12); 253 h ^= (h >>> 7) ^ (h >>> 4); 254 } 255 h ^= hashMask; 256 } else { 257 h = k.hashCode(); 258 } 259 260 return h; 261 } 262 263 /** 264 * Constructs a new, empty hashtable with the specified initial 265 * capacity and the specified load factor. 266 * 267 * @param initialCapacity the initial capacity of the hashtable. 268 * @param loadFactor the load factor of the hashtable. 269 * @exception IllegalArgumentException if the initial capacity is less 270 * than zero, or if the load factor is nonpositive. 271 */ 272 public Hashtable(int initialCapacity, float loadFactor) { 273 if (initialCapacity < 0) 274 throw new IllegalArgumentException("Illegal Capacity: "+ 275 initialCapacity); 276 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 277 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 278 279 if (initialCapacity==0) 280 initialCapacity = 1; 281 this.loadFactor = loadFactor; 282 table = new Entry[initialCapacity]; 283 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 284 useAltHashing = sun.misc.VM.isBooted() && 285 (initialCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD); 286 } 287 288 /** 289 * Constructs a new, empty hashtable with the specified initial capacity 290 * and default load factor (0.75). 291 * 292 * @param initialCapacity the initial capacity of the hashtable. 293 * @exception IllegalArgumentException if the initial capacity is less 294 * than zero. 295 */ 296 public Hashtable(int initialCapacity) { 297 this(initialCapacity, 0.75f); 298 } 299 300 /** 301 * Constructs a new, empty hashtable with a default initial capacity (11) 302 * and load factor (0.75). 303 */ 304 public Hashtable() { 305 this(11, 0.75f); 409 * specified value 410 * @throws NullPointerException if the value is <code>null</code> 411 * @since 1.2 412 */ 413 public boolean containsValue(Object value) { 414 return contains(value); 415 } 416 417 /** 418 * Tests if the specified object is a key in this hashtable. 419 * 420 * @param key possible key 421 * @return <code>true</code> if and only if the specified object 422 * is a key in this hashtable, as determined by the 423 * <tt>equals</tt> method; <code>false</code> otherwise. 424 * @throws NullPointerException if the key is <code>null</code> 425 * @see #contains(Object) 426 */ 427 public synchronized boolean containsKey(Object key) { 428 Entry tab[] = table; 429 int hash = hash(key); 430 int index = (hash & 0x7FFFFFFF) % tab.length; 431 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 432 if ((e.hash == hash) && e.key.equals(key)) { 433 return true; 434 } 435 } 436 return false; 437 } 438 439 /** 440 * Returns the value to which the specified key is mapped, 441 * or {@code null} if this map contains no mapping for the key. 442 * 443 * <p>More formally, if this map contains a mapping from a key 444 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 445 * then this method returns {@code v}; otherwise it returns 446 * {@code null}. (There can be at most one such mapping.) 447 * 448 * @param key the key whose associated value is to be returned 449 * @return the value to which the specified key is mapped, or 450 * {@code null} if this map contains no mapping for the key 451 * @throws NullPointerException if the specified key is null 452 * @see #put(Object, Object) 453 */ 454 public synchronized V get(Object key) { 455 Entry tab[] = table; 456 int hash = hash(key); 457 int index = (hash & 0x7FFFFFFF) % tab.length; 458 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 459 if ((e.hash == hash) && e.key.equals(key)) { 460 return e.value; 461 } 462 } 463 return null; 464 } 465 466 /** 467 * The maximum size of array to allocate. 468 * Some VMs reserve some header words in an array. 469 * Attempts to allocate larger arrays may result in 470 * OutOfMemoryError: Requested array size exceeds VM limit 471 */ 472 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 473 474 /** 475 * Increases the capacity of and internally reorganizes this 476 * hashtable, in order to accommodate and access its entries more 477 * efficiently. This method is called automatically when the 478 * number of keys in the hashtable exceeds this hashtable's capacity 479 * and load factor. 480 */ 481 protected void rehash() { 482 int oldCapacity = table.length; 483 Entry<K,V>[] oldMap = table; 484 485 // overflow-conscious code 486 int newCapacity = (oldCapacity << 1) + 1; 487 if (newCapacity - MAX_ARRAY_SIZE > 0) { 488 if (oldCapacity == MAX_ARRAY_SIZE) 489 // Keep running with MAX_ARRAY_SIZE buckets 490 return; 491 newCapacity = MAX_ARRAY_SIZE; 492 } 493 Entry<K,V>[] newMap = new Entry[newCapacity]; 494 495 modCount++; 496 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 497 boolean currentAltHashing = useAltHashing; 498 useAltHashing = sun.misc.VM.isBooted() && 499 (newCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD); 500 boolean rehash = currentAltHashing ^ useAltHashing; 501 502 table = newMap; 503 504 for (int i = oldCapacity ; i-- > 0 ;) { 505 for (Entry<K,V> old = oldMap[i] ; old != null ; ) { 506 Entry<K,V> e = old; 507 old = old.next; 508 509 if(rehash) { 510 e.hash = hash(e.key); 511 } 512 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 513 e.next = newMap[index]; 514 newMap[index] = e; 515 } 516 } 517 } 518 519 /** 520 * Maps the specified <code>key</code> to the specified 521 * <code>value</code> in this hashtable. Neither the key nor the 522 * value can be <code>null</code>. <p> 523 * 524 * The value can be retrieved by calling the <code>get</code> method 525 * with a key that is equal to the original key. 526 * 527 * @param key the hashtable key 528 * @param value the value 529 * @return the previous value of the specified key in this hashtable, 530 * or <code>null</code> if it did not have one 531 * @exception NullPointerException if the key or value is 532 * <code>null</code> 533 * @see Object#equals(Object) 534 * @see #get(Object) 535 */ 536 public synchronized V put(K key, V value) { 537 // Make sure the value is not null 538 if (value == null) { 539 throw new NullPointerException(); 540 } 541 542 // Makes sure the key is not already in the hashtable. 543 Entry tab[] = table; 544 int hash = hash(key); 545 int index = (hash & 0x7FFFFFFF) % tab.length; 546 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 547 if ((e.hash == hash) && e.key.equals(key)) { 548 V old = e.value; 549 e.value = value; 550 return old; 551 } 552 } 553 554 modCount++; 555 if (count >= threshold) { 556 // Rehash the table if the threshold is exceeded 557 rehash(); 558 559 tab = table; 560 hash = hash(key); 561 index = (hash & 0x7FFFFFFF) % tab.length; 562 } 563 564 // Creates the new entry. 565 Entry<K,V> e = tab[index]; 566 tab[index] = new Entry<>(hash, key, value, e); 567 count++; 568 return null; 569 } 570 571 /** 572 * Removes the key (and its corresponding value) from this 573 * hashtable. This method does nothing if the key is not in the hashtable. 574 * 575 * @param key the key that needs to be removed 576 * @return the value to which the key had been mapped in this hashtable, 577 * or <code>null</code> if the key did not have a mapping 578 * @throws NullPointerException if the key is <code>null</code> 579 */ 580 public synchronized V remove(Object key) { 581 Entry tab[] = table; 582 int hash = hash(key); 583 int index = (hash & 0x7FFFFFFF) % tab.length; 584 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 585 if ((e.hash == hash) && e.key.equals(key)) { 586 modCount++; 587 if (prev != null) { 588 prev.next = e.next; 589 } else { 590 tab[index] = e.next; 591 } 592 count--; 593 V oldValue = e.value; 594 e.value = null; 595 return oldValue; 596 } 597 } 598 return null; 599 } 600 601 /** 602 * Copies all of the mappings from the specified map to this hashtable. 769 if (entrySet==null) 770 entrySet = Collections.synchronizedSet(new EntrySet(), this); 771 return entrySet; 772 } 773 774 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 775 public Iterator<Map.Entry<K,V>> iterator() { 776 return getIterator(ENTRIES); 777 } 778 779 public boolean add(Map.Entry<K,V> o) { 780 return super.add(o); 781 } 782 783 public boolean contains(Object o) { 784 if (!(o instanceof Map.Entry)) 785 return false; 786 Map.Entry entry = (Map.Entry)o; 787 Object key = entry.getKey(); 788 Entry[] tab = table; 789 int hash = hash(key); 790 int index = (hash & 0x7FFFFFFF) % tab.length; 791 792 for (Entry e = tab[index]; e != null; e = e.next) 793 if (e.hash==hash && e.equals(entry)) 794 return true; 795 return false; 796 } 797 798 public boolean remove(Object o) { 799 if (!(o instanceof Map.Entry)) 800 return false; 801 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 802 K key = entry.getKey(); 803 Entry[] tab = table; 804 int hash = hash(key); 805 int index = (hash & 0x7FFFFFFF) % tab.length; 806 807 for (Entry<K,V> e = tab[index], prev = null; e != null; 808 prev = e, e = e.next) { 809 if (e.hash==hash && e.equals(entry)) { 810 modCount++; 811 if (prev != null) 812 prev.next = e.next; 813 else 814 tab[index] = e.next; 815 816 count--; 817 e.value = null; 818 return true; 819 } 820 } 821 return false; 822 } 823 824 public int size() { 918 * @see Map#hashCode() 919 * @since 1.2 920 */ 921 public synchronized int hashCode() { 922 /* 923 * This code detects the recursion caused by computing the hash code 924 * of a self-referential hash table and prevents the stack overflow 925 * that would otherwise result. This allows certain 1.1-era 926 * applets with self-referential hash tables to work. This code 927 * abuses the loadFactor field to do double-duty as a hashCode 928 * in progress flag, so as not to worsen the space performance. 929 * A negative load factor indicates that hash code computation is 930 * in progress. 931 */ 932 int h = 0; 933 if (count == 0 || loadFactor < 0) 934 return h; // Returns zero 935 936 loadFactor = -loadFactor; // Mark hashCode computation in progress 937 Entry[] tab = table; 938 for (Entry<K,V> entry : tab) 939 while (entry != null) { 940 h += entry.hashCode(); 941 entry = entry.next; 942 } 943 loadFactor = -loadFactor; // Mark hashCode computation complete 944 945 return h; 946 } 947 948 /** 949 * Save the state of the Hashtable to a stream (i.e., serialize it). 950 * 951 * @serialData The <i>capacity</i> of the Hashtable (the length of the 952 * bucket array) is emitted (int), followed by the 953 * <i>size</i> of the Hashtable (the number of key-value 954 * mappings), followed by the key (Object) and value (Object) 955 * for each key-value mapping represented by the Hashtable 956 * The key-value mappings are emitted in no particular order. 957 */ 958 private void writeObject(java.io.ObjectOutputStream s) 959 throws IOException { 960 Entry<K, V> entryStack = null; 961 962 synchronized (this) { 963 // Write out the length, threshold, loadfactor 964 s.defaultWriteObject(); 965 966 // Write out length, count of elements 967 s.writeInt(table.length); 968 s.writeInt(count); 969 970 // Stack copies of the entries in the table 971 for (int index = 0; index < table.length; index++) { 972 Entry<K,V> entry = table[index]; 973 974 while (entry != null) { 975 entryStack = 976 new Entry<>(0, entry.key, entry.value, entryStack); 977 entry = entry.next; 978 } 979 } 980 } 981 982 // Write out the key/value objects from the stacked entries 983 while (entryStack != null) { 984 s.writeObject(entryStack.key); 985 s.writeObject(entryStack.value); 986 entryStack = entryStack.next; 987 } 988 } 989 990 /** 991 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 992 */ 993 private void readObject(java.io.ObjectInputStream s) 994 throws IOException, ClassNotFoundException 995 { 996 // Read in the length, threshold, and loadfactor 997 s.defaultReadObject(); 998 999 // set hashMask 1000 UNSAFE.putIntVolatile(this, HASHMASK_OFFSET, 1001 sun.misc.Hashing.makeHashMask(this)); 1002 1003 // Read the original length of the array and number of elements 1004 int origlength = s.readInt(); 1005 int elements = s.readInt(); 1006 1007 // Compute new size with a bit of room 5% to grow but 1008 // no larger than the original size. Make the length 1009 // odd if it's large enough, this helps distribute the entries. 1010 // Guard against the length ending up zero, that's not valid. 1011 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 1012 if (length > elements && (length & 1) == 0) 1013 length--; 1014 if (origlength > 0 && length > origlength) 1015 length = origlength; 1016 1017 Entry<K,V>[] table = new Entry[length]; 1018 threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1); 1019 count = 0; 1020 useAltHashing = sun.misc.VM.isBooted() && 1021 (length >= Holder.ALTERNATE_HASHING_THRESHOLD); 1022 1023 // Read the number of elements and then all the key/value objects 1024 for (; elements > 0; elements--) { 1025 K key = (K)s.readObject(); 1026 V value = (V)s.readObject(); 1027 // synch could be eliminated for performance 1028 reconstitutionPut(table, key, value); 1029 } 1030 this.table = table; 1031 } 1032 1033 /** 1034 * The put method used by readObject. This is provided because put 1035 * is overridable and should not be called in readObject since the 1036 * subclass will not yet be initialized. 1037 * 1038 * <p>This differs from the regular put method in several ways. No 1039 * checking for rehashing is necessary since the number of elements 1040 * initially in the table is known. The modCount is not incremented 1041 * because we are creating a new instance. Also, no return value 1042 * is needed. 1043 */ 1044 private void reconstitutionPut(Entry<K,V>[] tab, K key, V value) 1045 throws StreamCorruptedException 1046 { 1047 if (value == null) { 1048 throw new java.io.StreamCorruptedException(); 1049 } 1050 // Makes sure the key is not already in the hashtable. 1051 // This should not happen in deserialized version. 1052 int hash = hash(key); 1053 int index = (hash & 0x7FFFFFFF) % tab.length; 1054 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 1055 if ((e.hash == hash) && e.key.equals(key)) { 1056 throw new java.io.StreamCorruptedException(); 1057 } 1058 } 1059 // Creates the new entry. 1060 Entry<K,V> e = tab[index]; 1061 tab[index] = new Entry<>(hash, key, value, e); 1062 count++; 1063 } 1064 1065 /** 1066 * Hashtable bucket collision list entry 1067 */ 1068 private static class Entry<K,V> implements Map.Entry<K,V> { 1069 int hash; 1070 K key; 1071 V value; 1072 Entry<K,V> next; 1073 1074 protected Entry(int hash, K key, V value, Entry<K,V> next) { 1075 this.hash = hash; 1076 this.key = key; 1077 this.value = value; 1078 this.next = next; 1079 } 1080 1081 protected Object clone() { 1082 return new Entry<>(hash, key, value, 1083 (next==null ? null : (Entry<K,V>) next.clone())); 1084 } 1085 1086 // Map.Entry Ops 1088 public K getKey() { 1089 return key; 1090 } 1091 1092 public V getValue() { 1093 return value; 1094 } 1095 1096 public V setValue(V value) { 1097 if (value == null) 1098 throw new NullPointerException(); 1099 1100 V oldValue = this.value; 1101 this.value = value; 1102 return oldValue; 1103 } 1104 1105 public boolean equals(Object o) { 1106 if (!(o instanceof Map.Entry)) 1107 return false; 1108 Map.Entry<?,?> e = (Map.Entry)o; 1109 1110 return key.equals(e.getKey()) && value.equals(e.getValue()); 1111 } 1112 1113 public int hashCode() { 1114 return hash ^ value.hashCode(); 1115 } 1116 1117 public String toString() { 1118 return key.toString()+"="+value.toString(); 1119 } 1120 } 1121 1122 // Types of Enumerations/Iterations 1123 private static final int KEYS = 0; 1124 private static final int VALUES = 1; 1125 private static final int ENTRIES = 2; 1126 1127 /** 1128 * A hashtable enumerator class. This class implements both the 1129 * Enumeration and Iterator interfaces, but individual instances 1130 * can be created with the Iterator methods disabled. This is necessary 1131 * to avoid unintentionally increasing the capabilities granted a user 1132 * by passing an Enumeration. 1133 */ 1134 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { |