1 /* 2 * Copyright (c) 1994, 2011, 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 23 * questions. 24 */ 25 26 package java.util; 27 import java.io.*; 28 29 /** 30 * This class implements a hash table, which maps keys to values. Any 31 * non-<code>null</code> object can be used as a key or as a value. <p> 32 * 33 * To successfully store and retrieve objects from a hashtable, the 34 * objects used as keys must implement the <code>hashCode</code> 35 * method and the <code>equals</code> method. <p> 36 * 37 * An instance of <code>Hashtable</code> has two parameters that affect its 38 * performance: <i>initial capacity</i> and <i>load factor</i>. The 39 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 40 * <i>initial capacity</i> is simply the capacity at the time the hash table 41 * is created. Note that the hash table is <i>open</i>: in the case of a "hash 42 * collision", a single bucket stores multiple entries, which must be searched 43 * sequentially. The <i>load factor</i> is a measure of how full the hash 44 * table is allowed to get before its capacity is automatically increased. 45 * The initial capacity and load factor parameters are merely hints to 46 * the implementation. The exact details as to when and whether the rehash 47 * method is invoked are implementation-dependent.<p> 48 * 49 * Generally, the default load factor (.75) offers a good tradeoff between 50 * time and space costs. Higher values decrease the space overhead but 51 * increase the time cost to look up an entry (which is reflected in most 52 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p> 53 * 54 * The initial capacity controls a tradeoff between wasted space and the 55 * need for <code>rehash</code> operations, which are time-consuming. 56 * No <code>rehash</code> operations will <i>ever</i> occur if the initial 57 * capacity is greater than the maximum number of entries the 58 * <tt>Hashtable</tt> will contain divided by its load factor. However, 59 * setting the initial capacity too high can waste space.<p> 60 * 61 * If many entries are to be made into a <code>Hashtable</code>, 62 * creating it with a sufficiently large capacity may allow the 63 * entries to be inserted more efficiently than letting it perform 64 * automatic rehashing as needed to grow the table. <p> 65 * 66 * This example creates a hashtable of numbers. It uses the names of 67 * the numbers as keys: 68 * <pre> {@code 69 * Hashtable<String, Integer> numbers 70 * = new Hashtable<String, Integer>(); 71 * numbers.put("one", 1); 72 * numbers.put("two", 2); 73 * numbers.put("three", 3);}</pre> 74 * 75 * <p>To retrieve a number, use the following code: 76 * <pre> {@code 77 * Integer n = numbers.get("two"); 78 * if (n != null) { 79 * System.out.println("two = " + n); 80 * }}</pre> 81 * 82 * <p>The iterators returned by the <tt>iterator</tt> method of the collections 83 * returned by all of this class's "collection view methods" are 84 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time 85 * after the iterator is created, in any way except through the iterator's own 86 * <tt>remove</tt> method, the iterator will throw a {@link 87 * ConcurrentModificationException}. Thus, in the face of concurrent 88 * modification, the iterator fails quickly and cleanly, rather than risking 89 * arbitrary, non-deterministic behavior at an undetermined time in the future. 90 * The Enumerations returned by Hashtable's keys and elements methods are 91 * <em>not</em> fail-fast. 92 * 93 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 94 * as it is, generally speaking, impossible to make any hard guarantees in the 95 * presence of unsynchronized concurrent modification. Fail-fast iterators 96 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 97 * Therefore, it would be wrong to write a program that depended on this 98 * exception for its correctness: <i>the fail-fast behavior of iterators 99 * should be used only to detect bugs.</i> 100 * 101 * <p>As of the Java 2 platform v1.2, this class was retrofitted to 102 * implement the {@link Map} interface, making it a member of the 103 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 104 * 105 * Java Collections Framework</a>. Unlike the new collection 106 * implementations, {@code Hashtable} is synchronized. If a 107 * thread-safe implementation is not needed, it is recommended to use 108 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe 109 * highly-concurrent implementation is desired, then it is recommended 110 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of 111 * {@code Hashtable}. 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); 306 } 307 308 /** 309 * Constructs a new hashtable with the same mappings as the given 310 * Map. The hashtable is created with an initial capacity sufficient to 311 * hold the mappings in the given Map and a default load factor (0.75). 312 * 313 * @param t the map whose mappings are to be placed in this map. 314 * @throws NullPointerException if the specified map is null. 315 * @since 1.2 316 */ 317 public Hashtable(Map<? extends K, ? extends V> t) { 318 this(Math.max(2*t.size(), 11), 0.75f); 319 putAll(t); 320 } 321 322 /** 323 * Returns the number of keys in this hashtable. 324 * 325 * @return the number of keys in this hashtable. 326 */ 327 public synchronized int size() { 328 return count; 329 } 330 331 /** 332 * Tests if this hashtable maps no keys to values. 333 * 334 * @return <code>true</code> if this hashtable maps no keys to values; 335 * <code>false</code> otherwise. 336 */ 337 public synchronized boolean isEmpty() { 338 return count == 0; 339 } 340 341 /** 342 * Returns an enumeration of the keys in this hashtable. 343 * 344 * @return an enumeration of the keys in this hashtable. 345 * @see Enumeration 346 * @see #elements() 347 * @see #keySet() 348 * @see Map 349 */ 350 public synchronized Enumeration<K> keys() { 351 return this.<K>getEnumeration(KEYS); 352 } 353 354 /** 355 * Returns an enumeration of the values in this hashtable. 356 * Use the Enumeration methods on the returned object to fetch the elements 357 * sequentially. 358 * 359 * @return an enumeration of the values in this hashtable. 360 * @see java.util.Enumeration 361 * @see #keys() 362 * @see #values() 363 * @see Map 364 */ 365 public synchronized Enumeration<V> elements() { 366 return this.<V>getEnumeration(VALUES); 367 } 368 369 /** 370 * Tests if some key maps into the specified value in this hashtable. 371 * This operation is more expensive than the {@link #containsKey 372 * containsKey} method. 373 * 374 * <p>Note that this method is identical in functionality to 375 * {@link #containsValue containsValue}, (which is part of the 376 * {@link Map} interface in the collections framework). 377 * 378 * @param value a value to search for 379 * @return <code>true</code> if and only if some key maps to the 380 * <code>value</code> argument in this hashtable as 381 * determined by the <tt>equals</tt> method; 382 * <code>false</code> otherwise. 383 * @exception NullPointerException if the value is <code>null</code> 384 */ 385 public synchronized boolean contains(Object value) { 386 if (value == null) { 387 throw new NullPointerException(); 388 } 389 390 Entry tab[] = table; 391 for (int i = tab.length ; i-- > 0 ;) { 392 for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) { 393 if (e.value.equals(value)) { 394 return true; 395 } 396 } 397 } 398 return false; 399 } 400 401 /** 402 * Returns true if this hashtable maps one or more keys to this value. 403 * 404 * <p>Note that this method is identical in functionality to {@link 405 * #contains contains} (which predates the {@link Map} interface). 406 * 407 * @param value value whose presence in this hashtable is to be tested 408 * @return <tt>true</tt> if this map maps one or more keys to the 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. 603 * These mappings will replace any mappings that this hashtable had for any 604 * of the keys currently in the specified map. 605 * 606 * @param t mappings to be stored in this map 607 * @throws NullPointerException if the specified map is null 608 * @since 1.2 609 */ 610 public synchronized void putAll(Map<? extends K, ? extends V> t) { 611 for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) 612 put(e.getKey(), e.getValue()); 613 } 614 615 /** 616 * Clears this hashtable so that it contains no keys. 617 */ 618 public synchronized void clear() { 619 Entry tab[] = table; 620 modCount++; 621 for (int index = tab.length; --index >= 0; ) 622 tab[index] = null; 623 count = 0; 624 } 625 626 /** 627 * Creates a shallow copy of this hashtable. All the structure of the 628 * hashtable itself is copied, but the keys and values are not cloned. 629 * This is a relatively expensive operation. 630 * 631 * @return a clone of the hashtable 632 */ 633 public synchronized Object clone() { 634 try { 635 Hashtable<K,V> t = (Hashtable<K,V>) super.clone(); 636 t.table = new Entry[table.length]; 637 for (int i = table.length ; i-- > 0 ; ) { 638 t.table[i] = (table[i] != null) 639 ? (Entry<K,V>) table[i].clone() : null; 640 } 641 t.keySet = null; 642 t.entrySet = null; 643 t.values = null; 644 t.modCount = 0; 645 return t; 646 } catch (CloneNotSupportedException e) { 647 // this shouldn't happen, since we are Cloneable 648 throw new InternalError(); 649 } 650 } 651 652 /** 653 * Returns a string representation of this <tt>Hashtable</tt> object 654 * in the form of a set of entries, enclosed in braces and separated 655 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 656 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 657 * associated element, where the <tt>toString</tt> method is used to 658 * convert the key and element to strings. 659 * 660 * @return a string representation of this hashtable 661 */ 662 public synchronized String toString() { 663 int max = size() - 1; 664 if (max == -1) 665 return "{}"; 666 667 StringBuilder sb = new StringBuilder(); 668 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 669 670 sb.append('{'); 671 for (int i = 0; ; i++) { 672 Map.Entry<K,V> e = it.next(); 673 K key = e.getKey(); 674 V value = e.getValue(); 675 sb.append(key == this ? "(this Map)" : key.toString()); 676 sb.append('='); 677 sb.append(value == this ? "(this Map)" : value.toString()); 678 679 if (i == max) 680 return sb.append('}').toString(); 681 sb.append(", "); 682 } 683 } 684 685 686 private <T> Enumeration<T> getEnumeration(int type) { 687 if (count == 0) { 688 return Collections.emptyEnumeration(); 689 } else { 690 return new Enumerator<>(type, false); 691 } 692 } 693 694 private <T> Iterator<T> getIterator(int type) { 695 if (count == 0) { 696 return Collections.emptyIterator(); 697 } else { 698 return new Enumerator<>(type, true); 699 } 700 } 701 702 // Views 703 704 /** 705 * Each of these fields are initialized to contain an instance of the 706 * appropriate view the first time this view is requested. The views are 707 * stateless, so there's no reason to create more than one of each. 708 */ 709 private transient volatile Set<K> keySet = null; 710 private transient volatile Set<Map.Entry<K,V>> entrySet = null; 711 private transient volatile Collection<V> values = null; 712 713 /** 714 * Returns a {@link Set} view of the keys contained in this map. 715 * The set is backed by the map, so changes to the map are 716 * reflected in the set, and vice-versa. If the map is modified 717 * while an iteration over the set is in progress (except through 718 * the iterator's own <tt>remove</tt> operation), the results of 719 * the iteration are undefined. The set supports element removal, 720 * which removes the corresponding mapping from the map, via the 721 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 722 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 723 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 724 * operations. 725 * 726 * @since 1.2 727 */ 728 public Set<K> keySet() { 729 if (keySet == null) 730 keySet = Collections.synchronizedSet(new KeySet(), this); 731 return keySet; 732 } 733 734 private class KeySet extends AbstractSet<K> { 735 public Iterator<K> iterator() { 736 return getIterator(KEYS); 737 } 738 public int size() { 739 return count; 740 } 741 public boolean contains(Object o) { 742 return containsKey(o); 743 } 744 public boolean remove(Object o) { 745 return Hashtable.this.remove(o) != null; 746 } 747 public void clear() { 748 Hashtable.this.clear(); 749 } 750 } 751 752 /** 753 * Returns a {@link Set} view of the mappings contained in this map. 754 * The set is backed by the map, so changes to the map are 755 * reflected in the set, and vice-versa. If the map is modified 756 * while an iteration over the set is in progress (except through 757 * the iterator's own <tt>remove</tt> operation, or through the 758 * <tt>setValue</tt> operation on a map entry returned by the 759 * iterator) the results of the iteration are undefined. The set 760 * supports element removal, which removes the corresponding 761 * mapping from the map, via the <tt>Iterator.remove</tt>, 762 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 763 * <tt>clear</tt> operations. It does not support the 764 * <tt>add</tt> or <tt>addAll</tt> operations. 765 * 766 * @since 1.2 767 */ 768 public Set<Map.Entry<K,V>> entrySet() { 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() { 825 return count; 826 } 827 828 public void clear() { 829 Hashtable.this.clear(); 830 } 831 } 832 833 /** 834 * Returns a {@link Collection} view of the values contained in this map. 835 * The collection is backed by the map, so changes to the map are 836 * reflected in the collection, and vice-versa. If the map is 837 * modified while an iteration over the collection is in progress 838 * (except through the iterator's own <tt>remove</tt> operation), 839 * the results of the iteration are undefined. The collection 840 * supports element removal, which removes the corresponding 841 * mapping from the map, via the <tt>Iterator.remove</tt>, 842 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 843 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 844 * support the <tt>add</tt> or <tt>addAll</tt> operations. 845 * 846 * @since 1.2 847 */ 848 public Collection<V> values() { 849 if (values==null) 850 values = Collections.synchronizedCollection(new ValueCollection(), 851 this); 852 return values; 853 } 854 855 private class ValueCollection extends AbstractCollection<V> { 856 public Iterator<V> iterator() { 857 return getIterator(VALUES); 858 } 859 public int size() { 860 return count; 861 } 862 public boolean contains(Object o) { 863 return containsValue(o); 864 } 865 public void clear() { 866 Hashtable.this.clear(); 867 } 868 } 869 870 // Comparison and hashing 871 872 /** 873 * Compares the specified Object with this Map for equality, 874 * as per the definition in the Map interface. 875 * 876 * @param o object to be compared for equality with this hashtable 877 * @return true if the specified Object is equal to this Map 878 * @see Map#equals(Object) 879 * @since 1.2 880 */ 881 public synchronized boolean equals(Object o) { 882 if (o == this) 883 return true; 884 885 if (!(o instanceof Map)) 886 return false; 887 Map<K,V> t = (Map<K,V>) o; 888 if (t.size() != size()) 889 return false; 890 891 try { 892 Iterator<Map.Entry<K,V>> i = entrySet().iterator(); 893 while (i.hasNext()) { 894 Map.Entry<K,V> e = i.next(); 895 K key = e.getKey(); 896 V value = e.getValue(); 897 if (value == null) { 898 if (!(t.get(key)==null && t.containsKey(key))) 899 return false; 900 } else { 901 if (!value.equals(t.get(key))) 902 return false; 903 } 904 } 905 } catch (ClassCastException unused) { 906 return false; 907 } catch (NullPointerException unused) { 908 return false; 909 } 910 911 return true; 912 } 913 914 /** 915 * Returns the hash code value for this Map as per the definition in the 916 * Map interface. 917 * 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 1087 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> { 1135 Entry[] table = Hashtable.this.table; 1136 int index = table.length; 1137 Entry<K,V> entry = null; 1138 Entry<K,V> lastReturned = null; 1139 int type; 1140 1141 /** 1142 * Indicates whether this Enumerator is serving as an Iterator 1143 * or an Enumeration. (true -> Iterator). 1144 */ 1145 boolean iterator; 1146 1147 /** 1148 * The modCount value that the iterator believes that the backing 1149 * Hashtable should have. If this expectation is violated, the iterator 1150 * has detected concurrent modification. 1151 */ 1152 protected int expectedModCount = modCount; 1153 1154 Enumerator(int type, boolean iterator) { 1155 this.type = type; 1156 this.iterator = iterator; 1157 } 1158 1159 public boolean hasMoreElements() { 1160 Entry<K,V> e = entry; 1161 int i = index; 1162 Entry[] t = table; 1163 /* Use locals for faster loop iteration */ 1164 while (e == null && i > 0) { 1165 e = t[--i]; 1166 } 1167 entry = e; 1168 index = i; 1169 return e != null; 1170 } 1171 1172 public T nextElement() { 1173 Entry<K,V> et = entry; 1174 int i = index; 1175 Entry[] t = table; 1176 /* Use locals for faster loop iteration */ 1177 while (et == null && i > 0) { 1178 et = t[--i]; 1179 } 1180 entry = et; 1181 index = i; 1182 if (et != null) { 1183 Entry<K,V> e = lastReturned = entry; 1184 entry = e.next; 1185 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e); 1186 } 1187 throw new NoSuchElementException("Hashtable Enumerator"); 1188 } 1189 1190 // Iterator methods 1191 public boolean hasNext() { 1192 return hasMoreElements(); 1193 } 1194 1195 public T next() { 1196 if (modCount != expectedModCount) 1197 throw new ConcurrentModificationException(); 1198 return nextElement(); 1199 } 1200 1201 public void remove() { 1202 if (!iterator) 1203 throw new UnsupportedOperationException(); 1204 if (lastReturned == null) 1205 throw new IllegalStateException("Hashtable Enumerator"); 1206 if (modCount != expectedModCount) 1207 throw new ConcurrentModificationException(); 1208 1209 synchronized(Hashtable.this) { 1210 Entry[] tab = Hashtable.this.table; 1211 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 1212 1213 for (Entry<K,V> e = tab[index], prev = null; e != null; 1214 prev = e, e = e.next) { 1215 if (e == lastReturned) { 1216 modCount++; 1217 expectedModCount++; 1218 if (prev == null) 1219 tab[index] = e.next; 1220 else 1221 prev.next = e.next; 1222 count--; 1223 lastReturned = null; 1224 return; 1225 } 1226 } 1227 throw new ConcurrentModificationException(); 1228 } 1229 } 1230 } 1231 }