Hashtable.java revision c3a9db83a352d92d5a6e0098f22bde07e34a1d3b
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27package java.util; 28 29import java.io.*; 30import java.util.function.BiConsumer; 31 32/** 33 * This class implements a hash table, which maps keys to values. Any 34 * non-<code>null</code> object can be used as a key or as a value. <p> 35 * 36 * To successfully store and retrieve objects from a hashtable, the 37 * objects used as keys must implement the <code>hashCode</code> 38 * method and the <code>equals</code> method. <p> 39 * 40 * An instance of <code>Hashtable</code> has two parameters that affect its 41 * performance: <i>initial capacity</i> and <i>load factor</i>. The 42 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 43 * <i>initial capacity</i> is simply the capacity at the time the hash table 44 * is created. Note that the hash table is <i>open</i>: in the case of a "hash 45 * collision", a single bucket stores multiple entries, which must be searched 46 * sequentially. The <i>load factor</i> is a measure of how full the hash 47 * table is allowed to get before its capacity is automatically increased. 48 * The initial capacity and load factor parameters are merely hints to 49 * the implementation. The exact details as to when and whether the rehash 50 * method is invoked are implementation-dependent.<p> 51 * 52 * Generally, the default load factor (.75) offers a good tradeoff between 53 * time and space costs. Higher values decrease the space overhead but 54 * increase the time cost to look up an entry (which is reflected in most 55 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p> 56 * 57 * The initial capacity controls a tradeoff between wasted space and the 58 * need for <code>rehash</code> operations, which are time-consuming. 59 * No <code>rehash</code> operations will <i>ever</i> occur if the initial 60 * capacity is greater than the maximum number of entries the 61 * <tt>Hashtable</tt> will contain divided by its load factor. However, 62 * setting the initial capacity too high can waste space.<p> 63 * 64 * If many entries are to be made into a <code>Hashtable</code>, 65 * creating it with a sufficiently large capacity may allow the 66 * entries to be inserted more efficiently than letting it perform 67 * automatic rehashing as needed to grow the table. <p> 68 * 69 * This example creates a hashtable of numbers. It uses the names of 70 * the numbers as keys: 71 * <pre> {@code 72 * Hashtable<String, Integer> numbers 73 * = new Hashtable<String, Integer>(); 74 * numbers.put("one", 1); 75 * numbers.put("two", 2); 76 * numbers.put("three", 3);}</pre> 77 * 78 * <p>To retrieve a number, use the following code: 79 * <pre> {@code 80 * Integer n = numbers.get("two"); 81 * if (n != null) { 82 * System.out.println("two = " + n); 83 * }}</pre> 84 * 85 * <p>The iterators returned by the <tt>iterator</tt> method of the collections 86 * returned by all of this class's "collection view methods" are 87 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time 88 * after the iterator is created, in any way except through the iterator's own 89 * <tt>remove</tt> method, the iterator will throw a {@link 90 * ConcurrentModificationException}. Thus, in the face of concurrent 91 * modification, the iterator fails quickly and cleanly, rather than risking 92 * arbitrary, non-deterministic behavior at an undetermined time in the future. 93 * The Enumerations returned by Hashtable's keys and elements methods are 94 * <em>not</em> fail-fast. 95 * 96 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 97 * as it is, generally speaking, impossible to make any hard guarantees in the 98 * presence of unsynchronized concurrent modification. Fail-fast iterators 99 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 100 * Therefore, it would be wrong to write a program that depended on this 101 * exception for its correctness: <i>the fail-fast behavior of iterators 102 * should be used only to detect bugs.</i> 103 * 104 * <p>As of the Java 2 platform v1.2, this class was retrofitted to 105 * implement the {@link Map} interface, making it a member of the 106 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 107 * 108 * Java Collections Framework</a>. Unlike the new collection 109 * implementations, {@code Hashtable} is synchronized. If a 110 * thread-safe implementation is not needed, it is recommended to use 111 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe 112 * highly-concurrent implementation is desired, then it is recommended 113 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of 114 * {@code Hashtable}. 115 * 116 * @author Arthur van Hoff 117 * @author Josh Bloch 118 * @author Neal Gafter 119 * @see Object#equals(java.lang.Object) 120 * @see Object#hashCode() 121 * @see Hashtable#rehash() 122 * @see Collection 123 * @see Map 124 * @see HashMap 125 * @see TreeMap 126 * @since JDK1.0 127 */ 128public class Hashtable<K,V> 129 extends Dictionary<K,V> 130 implements Map<K,V>, Cloneable, java.io.Serializable { 131 132 /** 133 * The hash table data. 134 */ 135 private transient HashtableEntry<K,V>[] table; 136 137 /** 138 * The total number of entries in the hash table. 139 */ 140 private transient int count; 141 142 /** 143 * The table is rehashed when its size exceeds this threshold. (The 144 * value of this field is (int)(capacity * loadFactor).) 145 * 146 * @serial 147 */ 148 private int threshold; 149 150 /** 151 * The load factor for the hashtable. 152 * 153 * @serial 154 */ 155 private float loadFactor; 156 157 /** 158 * The number of times this Hashtable has been structurally modified 159 * Structural modifications are those that change the number of entries in 160 * the Hashtable or otherwise modify its internal structure (e.g., 161 * rehash). This field is used to make iterators on Collection-views of 162 * the Hashtable fail-fast. (See ConcurrentModificationException). 163 */ 164 private transient int modCount = 0; 165 166 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 167 private static final long serialVersionUID = 1421746759512286392L; 168 169 /** 170 * The default threshold of map capacity above which alternative hashing is 171 * used for String keys. Alternative hashing reduces the incidence of 172 * collisions due to weak hash code calculation for String keys. 173 * <p> 174 * This value may be overridden by defining the system property 175 * {@code jdk.map.althashing.threshold}. A property value of {@code 1} 176 * forces alternative hashing to be used at all times whereas 177 * {@code -1} value ensures that alternative hashing is never used. 178 */ 179 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; 180 181 /** 182 * holds values which can't be initialized until after VM is booted. 183 */ 184 private static class Holder { 185 186 /** 187 * Table capacity above which to switch to use alternative hashing. 188 */ 189 static final int ALTERNATIVE_HASHING_THRESHOLD; 190 191 static { 192 String altThreshold = java.security.AccessController.doPrivileged( 193 new sun.security.action.GetPropertyAction( 194 "jdk.map.althashing.threshold")); 195 196 int threshold; 197 try { 198 threshold = (null != altThreshold) 199 ? Integer.parseInt(altThreshold) 200 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; 201 202 // disable alternative hashing if -1 203 if (threshold == -1) { 204 threshold = Integer.MAX_VALUE; 205 } 206 207 if (threshold < 0) { 208 throw new IllegalArgumentException("value must be positive integer."); 209 } 210 } catch(IllegalArgumentException failed) { 211 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); 212 } 213 214 ALTERNATIVE_HASHING_THRESHOLD = threshold; 215 } 216 } 217 218 /** 219 * A randomizing value associated with this instance that is applied to 220 * hash code of keys to make hash collisions harder to find. 221 */ 222 transient int hashSeed; 223 224 /** 225 * Initialize the hashing mask value. 226 */ 227 final boolean initHashSeedAsNeeded(int capacity) { 228 boolean currentAltHashing = hashSeed != 0; 229 boolean useAltHashing = sun.misc.VM.isBooted() && 230 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 231 boolean switching = currentAltHashing ^ useAltHashing; 232 if (switching) { 233 hashSeed = useAltHashing 234 ? sun.misc.Hashing.randomHashSeed(this) 235 : 0; 236 } 237 return switching; 238 } 239 240 private int hash(Object k) { 241 // hashSeed will be zero if alternative hashing is disabled. 242 return hashSeed ^ k.hashCode(); 243 } 244 245 /** 246 * Constructs a new, empty hashtable with the specified initial 247 * capacity and the specified load factor. 248 * 249 * @param initialCapacity the initial capacity of the hashtable. 250 * @param loadFactor the load factor of the hashtable. 251 * @exception IllegalArgumentException if the initial capacity is less 252 * than zero, or if the load factor is nonpositive. 253 */ 254 public Hashtable(int initialCapacity, float loadFactor) { 255 if (initialCapacity < 0) 256 throw new IllegalArgumentException("Illegal Capacity: "+ 257 initialCapacity); 258 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 259 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 260 261 if (initialCapacity==0) 262 initialCapacity = 1; 263 this.loadFactor = loadFactor; 264 table = new HashtableEntry[initialCapacity]; 265 threshold = (initialCapacity <= MAX_ARRAY_SIZE + 1) ? initialCapacity : MAX_ARRAY_SIZE + 1; 266 initHashSeedAsNeeded(initialCapacity); 267 } 268 269 /** 270 * Constructs a new, empty hashtable with the specified initial capacity 271 * and default load factor (0.75). 272 * 273 * @param initialCapacity the initial capacity of the hashtable. 274 * @exception IllegalArgumentException if the initial capacity is less 275 * than zero. 276 */ 277 public Hashtable(int initialCapacity) { 278 this(initialCapacity, 0.75f); 279 } 280 281 /** 282 * Constructs a new, empty hashtable with a default initial capacity (11) 283 * and load factor (0.75). 284 */ 285 public Hashtable() { 286 this(11, 0.75f); 287 } 288 289 /** 290 * Constructs a new hashtable with the same mappings as the given 291 * Map. The hashtable is created with an initial capacity sufficient to 292 * hold the mappings in the given Map and a default load factor (0.75). 293 * 294 * @param t the map whose mappings are to be placed in this map. 295 * @throws NullPointerException if the specified map is null. 296 * @since 1.2 297 */ 298 public Hashtable(Map<? extends K, ? extends V> t) { 299 this(Math.max(2*t.size(), 11), 0.75f); 300 putAll(t); 301 } 302 303 /** 304 * Returns the number of keys in this hashtable. 305 * 306 * @return the number of keys in this hashtable. 307 */ 308 public synchronized int size() { 309 return count; 310 } 311 312 /** 313 * Tests if this hashtable maps no keys to values. 314 * 315 * @return <code>true</code> if this hashtable maps no keys to values; 316 * <code>false</code> otherwise. 317 */ 318 public synchronized boolean isEmpty() { 319 return count == 0; 320 } 321 322 /** 323 * Returns an enumeration of the keys in this hashtable. 324 * 325 * @return an enumeration of the keys in this hashtable. 326 * @see Enumeration 327 * @see #elements() 328 * @see #keySet() 329 * @see Map 330 */ 331 public synchronized Enumeration<K> keys() { 332 return this.<K>getEnumeration(KEYS); 333 } 334 335 /** 336 * Returns an enumeration of the values in this hashtable. 337 * Use the Enumeration methods on the returned object to fetch the elements 338 * sequentially. 339 * 340 * @return an enumeration of the values in this hashtable. 341 * @see java.util.Enumeration 342 * @see #keys() 343 * @see #values() 344 * @see Map 345 */ 346 public synchronized Enumeration<V> elements() { 347 return this.<V>getEnumeration(VALUES); 348 } 349 350 /** 351 * Tests if some key maps into the specified value in this hashtable. 352 * This operation is more expensive than the {@link #containsKey 353 * containsKey} method. 354 * 355 * <p>Note that this method is identical in functionality to 356 * {@link #containsValue containsValue}, (which is part of the 357 * {@link Map} interface in the collections framework). 358 * 359 * @param value a value to search for 360 * @return <code>true</code> if and only if some key maps to the 361 * <code>value</code> argument in this hashtable as 362 * determined by the <tt>equals</tt> method; 363 * <code>false</code> otherwise. 364 * @exception NullPointerException if the value is <code>null</code> 365 */ 366 public synchronized boolean contains(Object value) { 367 if (value == null) { 368 throw new NullPointerException(); 369 } 370 371 HashtableEntry tab[] = table; 372 for (int i = tab.length ; i-- > 0 ;) { 373 for (HashtableEntry<K,V> e = tab[i] ; e != null ; e = e.next) { 374 if (e.value.equals(value)) { 375 return true; 376 } 377 } 378 } 379 return false; 380 } 381 382 /** 383 * Returns true if this hashtable maps one or more keys to this value. 384 * 385 * <p>Note that this method is identical in functionality to {@link 386 * #contains contains} (which predates the {@link Map} interface). 387 * 388 * @param value value whose presence in this hashtable is to be tested 389 * @return <tt>true</tt> if this map maps one or more keys to the 390 * specified value 391 * @throws NullPointerException if the value is <code>null</code> 392 * @since 1.2 393 */ 394 public boolean containsValue(Object value) { 395 return contains(value); 396 } 397 398 /** 399 * Tests if the specified object is a key in this hashtable. 400 * 401 * @param key possible key 402 * @return <code>true</code> if and only if the specified object 403 * is a key in this hashtable, as determined by the 404 * <tt>equals</tt> method; <code>false</code> otherwise. 405 * @throws NullPointerException if the key is <code>null</code> 406 * @see #contains(Object) 407 */ 408 public synchronized boolean containsKey(Object key) { 409 HashtableEntry tab[] = table; 410 int hash = hash(key); 411 int index = (hash & 0x7FFFFFFF) % tab.length; 412 for (HashtableEntry<K,V> e = tab[index] ; e != null ; e = e.next) { 413 if ((e.hash == hash) && e.key.equals(key)) { 414 return true; 415 } 416 } 417 return false; 418 } 419 420 /** 421 * Returns the value to which the specified key is mapped, 422 * or {@code null} if this map contains no mapping for the key. 423 * 424 * <p>More formally, if this map contains a mapping from a key 425 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 426 * then this method returns {@code v}; otherwise it returns 427 * {@code null}. (There can be at most one such mapping.) 428 * 429 * @param key the key whose associated value is to be returned 430 * @return the value to which the specified key is mapped, or 431 * {@code null} if this map contains no mapping for the key 432 * @throws NullPointerException if the specified key is null 433 * @see #put(Object, Object) 434 */ 435 public synchronized V get(Object key) { 436 HashtableEntry tab[] = table; 437 int hash = hash(key); 438 int index = (hash & 0x7FFFFFFF) % tab.length; 439 for (HashtableEntry<K,V> e = tab[index] ; e != null ; e = e.next) { 440 if ((e.hash == hash) && e.key.equals(key)) { 441 return e.value; 442 } 443 } 444 return null; 445 } 446 447 /** 448 * The maximum size of array to allocate. 449 * Some VMs reserve some header words in an array. 450 * Attempts to allocate larger arrays may result in 451 * OutOfMemoryError: Requested array size exceeds VM limit 452 */ 453 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 454 455 /** 456 * Increases the capacity of and internally reorganizes this 457 * hashtable, in order to accommodate and access its entries more 458 * efficiently. This method is called automatically when the 459 * number of keys in the hashtable exceeds this hashtable's capacity 460 * and load factor. 461 */ 462 protected void rehash() { 463 int oldCapacity = table.length; 464 HashtableEntry<K,V>[] oldMap = table; 465 466 // overflow-conscious code 467 int newCapacity = (oldCapacity << 1) + 1; 468 if (newCapacity - MAX_ARRAY_SIZE > 0) { 469 if (oldCapacity == MAX_ARRAY_SIZE) 470 // Keep running with MAX_ARRAY_SIZE buckets 471 return; 472 newCapacity = MAX_ARRAY_SIZE; 473 } 474 HashtableEntry<K,V>[] newMap = new HashtableEntry[newCapacity]; 475 476 modCount++; 477 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 478 boolean rehash = initHashSeedAsNeeded(newCapacity); 479 480 table = newMap; 481 482 for (int i = oldCapacity ; i-- > 0 ;) { 483 for (HashtableEntry<K,V> old = oldMap[i] ; old != null ; ) { 484 HashtableEntry<K,V> e = old; 485 old = old.next; 486 487 if (rehash) { 488 e.hash = hash(e.key); 489 } 490 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 491 e.next = newMap[index]; 492 newMap[index] = e; 493 } 494 } 495 } 496 497 /** 498 * Maps the specified <code>key</code> to the specified 499 * <code>value</code> in this hashtable. Neither the key nor the 500 * value can be <code>null</code>. <p> 501 * 502 * The value can be retrieved by calling the <code>get</code> method 503 * with a key that is equal to the original key. 504 * 505 * @param key the hashtable key 506 * @param value the value 507 * @return the previous value of the specified key in this hashtable, 508 * or <code>null</code> if it did not have one 509 * @exception NullPointerException if the key or value is 510 * <code>null</code> 511 * @see Object#equals(Object) 512 * @see #get(Object) 513 */ 514 public synchronized V put(K key, V value) { 515 // Make sure the value is not null 516 if (value == null) { 517 throw new NullPointerException(); 518 } 519 520 // Makes sure the key is not already in the hashtable. 521 HashtableEntry tab[] = table; 522 int hash = hash(key); 523 int index = (hash & 0x7FFFFFFF) % tab.length; 524 for (HashtableEntry<K,V> e = tab[index] ; e != null ; e = e.next) { 525 if ((e.hash == hash) && e.key.equals(key)) { 526 V old = e.value; 527 e.value = value; 528 return old; 529 } 530 } 531 532 modCount++; 533 if (count >= threshold) { 534 // Rehash the table if the threshold is exceeded 535 rehash(); 536 537 tab = table; 538 hash = hash(key); 539 index = (hash & 0x7FFFFFFF) % tab.length; 540 } 541 542 // Creates the new entry. 543 HashtableEntry<K,V> e = tab[index]; 544 tab[index] = new HashtableEntry<>(hash, key, value, e); 545 count++; 546 return null; 547 } 548 549 /** 550 * Removes the key (and its corresponding value) from this 551 * hashtable. This method does nothing if the key is not in the hashtable. 552 * 553 * @param key the key that needs to be removed 554 * @return the value to which the key had been mapped in this hashtable, 555 * or <code>null</code> if the key did not have a mapping 556 * @throws NullPointerException if the key is <code>null</code> 557 */ 558 public synchronized V remove(Object key) { 559 HashtableEntry tab[] = table; 560 int hash = hash(key); 561 int index = (hash & 0x7FFFFFFF) % tab.length; 562 for (HashtableEntry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 563 if ((e.hash == hash) && e.key.equals(key)) { 564 modCount++; 565 if (prev != null) { 566 prev.next = e.next; 567 } else { 568 tab[index] = e.next; 569 } 570 count--; 571 V oldValue = e.value; 572 e.value = null; 573 return oldValue; 574 } 575 } 576 return null; 577 } 578 579 /** 580 * Copies all of the mappings from the specified map to this hashtable. 581 * These mappings will replace any mappings that this hashtable had for any 582 * of the keys currently in the specified map. 583 * 584 * @param t mappings to be stored in this map 585 * @throws NullPointerException if the specified map is null 586 * @since 1.2 587 */ 588 public synchronized void putAll(Map<? extends K, ? extends V> t) { 589 for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) 590 put(e.getKey(), e.getValue()); 591 } 592 593 /** 594 * Clears this hashtable so that it contains no keys. 595 */ 596 public synchronized void clear() { 597 HashtableEntry tab[] = table; 598 modCount++; 599 for (int index = tab.length; --index >= 0; ) 600 tab[index] = null; 601 count = 0; 602 } 603 604 /** 605 * Creates a shallow copy of this hashtable. All the structure of the 606 * hashtable itself is copied, but the keys and values are not cloned. 607 * This is a relatively expensive operation. 608 * 609 * @return a clone of the hashtable 610 */ 611 public synchronized Object clone() { 612 try { 613 Hashtable<K,V> t = (Hashtable<K,V>) super.clone(); 614 t.table = new HashtableEntry[table.length]; 615 for (int i = table.length ; i-- > 0 ; ) { 616 t.table[i] = (table[i] != null) 617 ? (HashtableEntry<K,V>) table[i].clone() : null; 618 } 619 t.keySet = null; 620 t.entrySet = null; 621 t.values = null; 622 t.modCount = 0; 623 return t; 624 } catch (CloneNotSupportedException e) { 625 // this shouldn't happen, since we are Cloneable 626 throw new InternalError(); 627 } 628 } 629 630 /** 631 * Returns a string representation of this <tt>Hashtable</tt> object 632 * in the form of a set of entries, enclosed in braces and separated 633 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 634 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 635 * associated element, where the <tt>toString</tt> method is used to 636 * convert the key and element to strings. 637 * 638 * @return a string representation of this hashtable 639 */ 640 public synchronized String toString() { 641 int max = size() - 1; 642 if (max == -1) 643 return "{}"; 644 645 StringBuilder sb = new StringBuilder(); 646 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 647 648 sb.append('{'); 649 for (int i = 0; ; i++) { 650 Map.Entry<K,V> e = it.next(); 651 K key = e.getKey(); 652 V value = e.getValue(); 653 sb.append(key == this ? "(this Map)" : key.toString()); 654 sb.append('='); 655 sb.append(value == this ? "(this Map)" : value.toString()); 656 657 if (i == max) 658 return sb.append('}').toString(); 659 sb.append(", "); 660 } 661 } 662 663 664 private <T> Enumeration<T> getEnumeration(int type) { 665 if (count == 0) { 666 return Collections.emptyEnumeration(); 667 } else { 668 return new Enumerator<>(type, false); 669 } 670 } 671 672 private <T> Iterator<T> getIterator(int type) { 673 if (count == 0) { 674 return Collections.emptyIterator(); 675 } else { 676 return new Enumerator<>(type, true); 677 } 678 } 679 680 // Views 681 682 /** 683 * Each of these fields are initialized to contain an instance of the 684 * appropriate view the first time this view is requested. The views are 685 * stateless, so there's no reason to create more than one of each. 686 */ 687 private transient volatile Set<K> keySet = null; 688 private transient volatile Set<Map.Entry<K,V>> entrySet = null; 689 private transient volatile Collection<V> values = null; 690 691 /** 692 * Returns a {@link Set} view of the keys contained in this map. 693 * The set is backed by the map, so changes to the map are 694 * reflected in the set, and vice-versa. If the map is modified 695 * while an iteration over the set is in progress (except through 696 * the iterator's own <tt>remove</tt> operation), the results of 697 * the iteration are undefined. The set supports element removal, 698 * which removes the corresponding mapping from the map, via the 699 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 700 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 701 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 702 * operations. 703 * 704 * @since 1.2 705 */ 706 public Set<K> keySet() { 707 if (keySet == null) 708 keySet = Collections.synchronizedSet(new KeySet(), this); 709 return keySet; 710 } 711 712 private class KeySet extends AbstractSet<K> { 713 public Iterator<K> iterator() { 714 return getIterator(KEYS); 715 } 716 public int size() { 717 return count; 718 } 719 public boolean contains(Object o) { 720 return containsKey(o); 721 } 722 public boolean remove(Object o) { 723 return Hashtable.this.remove(o) != null; 724 } 725 public void clear() { 726 Hashtable.this.clear(); 727 } 728 } 729 730 /** 731 * Returns a {@link Set} view of the mappings contained in this map. 732 * The set is backed by the map, so changes to the map are 733 * reflected in the set, and vice-versa. If the map is modified 734 * while an iteration over the set is in progress (except through 735 * the iterator's own <tt>remove</tt> operation, or through the 736 * <tt>setValue</tt> operation on a map entry returned by the 737 * iterator) the results of the iteration are undefined. The set 738 * supports element removal, which removes the corresponding 739 * mapping from the map, via the <tt>Iterator.remove</tt>, 740 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 741 * <tt>clear</tt> operations. It does not support the 742 * <tt>add</tt> or <tt>addAll</tt> operations. 743 * 744 * @since 1.2 745 */ 746 public Set<Map.Entry<K,V>> entrySet() { 747 if (entrySet==null) 748 entrySet = Collections.synchronizedSet(new EntrySet(), this); 749 return entrySet; 750 } 751 752 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 753 public Iterator<Map.Entry<K,V>> iterator() { 754 return getIterator(ENTRIES); 755 } 756 757 public boolean add(Map.Entry<K,V> o) { 758 return super.add(o); 759 } 760 761 public boolean contains(Object o) { 762 if (!(o instanceof Map.Entry)) 763 return false; 764 Map.Entry entry = (Map.Entry)o; 765 Object key = entry.getKey(); 766 HashtableEntry[] tab = table; 767 int hash = hash(key); 768 int index = (hash & 0x7FFFFFFF) % tab.length; 769 770 for (HashtableEntry e = tab[index]; e != null; e = e.next) 771 if (e.hash==hash && e.equals(entry)) 772 return true; 773 return false; 774 } 775 776 public boolean remove(Object o) { 777 if (!(o instanceof Map.Entry)) 778 return false; 779 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 780 K key = entry.getKey(); 781 HashtableEntry[] tab = table; 782 int hash = hash(key); 783 int index = (hash & 0x7FFFFFFF) % tab.length; 784 785 for (HashtableEntry<K,V> e = tab[index], prev = null; e != null; 786 prev = e, e = e.next) { 787 if (e.hash==hash && e.equals(entry)) { 788 modCount++; 789 if (prev != null) 790 prev.next = e.next; 791 else 792 tab[index] = e.next; 793 794 count--; 795 e.value = null; 796 return true; 797 } 798 } 799 return false; 800 } 801 802 public int size() { 803 return count; 804 } 805 806 public void clear() { 807 Hashtable.this.clear(); 808 } 809 } 810 811 /** 812 * Returns a {@link Collection} view of the values contained in this map. 813 * The collection is backed by the map, so changes to the map are 814 * reflected in the collection, and vice-versa. If the map is 815 * modified while an iteration over the collection is in progress 816 * (except through the iterator's own <tt>remove</tt> operation), 817 * the results of the iteration are undefined. The collection 818 * supports element removal, which removes the corresponding 819 * mapping from the map, via the <tt>Iterator.remove</tt>, 820 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 821 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 822 * support the <tt>add</tt> or <tt>addAll</tt> operations. 823 * 824 * @since 1.2 825 */ 826 public Collection<V> values() { 827 if (values==null) 828 values = Collections.synchronizedCollection(new ValueCollection(), 829 this); 830 return values; 831 } 832 833 private class ValueCollection extends AbstractCollection<V> { 834 public Iterator<V> iterator() { 835 return getIterator(VALUES); 836 } 837 public int size() { 838 return count; 839 } 840 public boolean contains(Object o) { 841 return containsValue(o); 842 } 843 public void clear() { 844 Hashtable.this.clear(); 845 } 846 } 847 848 // Comparison and hashing 849 850 /** 851 * Compares the specified Object with this Map for equality, 852 * as per the definition in the Map interface. 853 * 854 * @param o object to be compared for equality with this hashtable 855 * @return true if the specified Object is equal to this Map 856 * @see Map#equals(Object) 857 * @since 1.2 858 */ 859 public synchronized boolean equals(Object o) { 860 if (o == this) 861 return true; 862 863 if (!(o instanceof Map)) 864 return false; 865 Map<K,V> t = (Map<K,V>) o; 866 if (t.size() != size()) 867 return false; 868 869 try { 870 Iterator<Map.Entry<K,V>> i = entrySet().iterator(); 871 while (i.hasNext()) { 872 Map.Entry<K,V> e = i.next(); 873 K key = e.getKey(); 874 V value = e.getValue(); 875 if (value == null) { 876 if (!(t.get(key)==null && t.containsKey(key))) 877 return false; 878 } else { 879 if (!value.equals(t.get(key))) 880 return false; 881 } 882 } 883 } catch (ClassCastException unused) { 884 return false; 885 } catch (NullPointerException unused) { 886 return false; 887 } 888 889 return true; 890 } 891 892 /** 893 * Returns the hash code value for this Map as per the definition in the 894 * Map interface. 895 * 896 * @see Map#hashCode() 897 * @since 1.2 898 */ 899 public synchronized int hashCode() { 900 /* 901 * This code detects the recursion caused by computing the hash code 902 * of a self-referential hash table and prevents the stack overflow 903 * that would otherwise result. This allows certain 1.1-era 904 * applets with self-referential hash tables to work. This code 905 * abuses the loadFactor field to do double-duty as a hashCode 906 * in progress flag, so as not to worsen the space performance. 907 * A negative load factor indicates that hash code computation is 908 * in progress. 909 */ 910 int h = 0; 911 if (count == 0 || loadFactor < 0) 912 return h; // Returns zero 913 914 loadFactor = -loadFactor; // Mark hashCode computation in progress 915 HashtableEntry[] tab = table; 916 for (HashtableEntry<K,V> entry : tab) 917 while (entry != null) { 918 h += entry.hashCode(); 919 entry = entry.next; 920 } 921 loadFactor = -loadFactor; // Mark hashCode computation complete 922 923 return h; 924 } 925 926 @SuppressWarnings("unchecked") 927 @Override 928 public synchronized void forEach(BiConsumer<? super K, ? super V> action) { 929 Objects.requireNonNull(action); // explicit check required in case 930 // table is empty. 931 final int expectedModCount = modCount; 932 933 HashtableEntry<?, ?>[] tab = table; 934 for (HashtableEntry<?, ?> entry : tab) { 935 while (entry != null) { 936 action.accept((K)entry.key, (V)entry.value); 937 entry = entry.next; 938 939 if (expectedModCount != modCount) { 940 throw new ConcurrentModificationException(); 941 } 942 } 943 } 944 } 945 946 /** 947 * Save the state of the Hashtable to a stream (i.e., serialize it). 948 * 949 * @serialData The <i>capacity</i> of the Hashtable (the length of the 950 * bucket array) is emitted (int), followed by the 951 * <i>size</i> of the Hashtable (the number of key-value 952 * mappings), followed by the key (Object) and value (Object) 953 * for each key-value mapping represented by the Hashtable 954 * The key-value mappings are emitted in no particular order. 955 */ 956 private void writeObject(java.io.ObjectOutputStream s) 957 throws IOException { 958 HashtableEntry<K, V> entryStack = null; 959 960 synchronized (this) { 961 // Write out the length, threshold, loadfactor 962 s.defaultWriteObject(); 963 964 // Write out length, count of elements 965 s.writeInt(table.length); 966 s.writeInt(count); 967 968 // Stack copies of the entries in the table 969 for (int index = 0; index < table.length; index++) { 970 HashtableEntry<K,V> entry = table[index]; 971 972 while (entry != null) { 973 entryStack = 974 new HashtableEntry<>(0, entry.key, entry.value, entryStack); 975 entry = entry.next; 976 } 977 } 978 } 979 980 // Write out the key/value objects from the stacked entries 981 while (entryStack != null) { 982 s.writeObject(entryStack.key); 983 s.writeObject(entryStack.value); 984 entryStack = entryStack.next; 985 } 986 } 987 988 /** 989 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 990 */ 991 private void readObject(java.io.ObjectInputStream s) 992 throws IOException, ClassNotFoundException 993 { 994 // Read in the length, threshold, and loadfactor 995 s.defaultReadObject(); 996 997 // Read the original length of the array and number of elements 998 int origlength = s.readInt(); 999 int elements = s.readInt(); 1000 1001 // Compute new size with a bit of room 5% to grow but 1002 // no larger than the original size. Make the length 1003 // odd if it's large enough, this helps distribute the entries. 1004 // Guard against the length ending up zero, that's not valid. 1005 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 1006 if (length > elements && (length & 1) == 0) 1007 length--; 1008 if (origlength > 0 && length > origlength) 1009 length = origlength; 1010 1011 HashtableEntry<K,V>[] newTable = new HashtableEntry[length]; 1012 threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1); 1013 count = 0; 1014 initHashSeedAsNeeded(length); 1015 1016 // Read the number of elements and then all the key/value objects 1017 for (; elements > 0; elements--) { 1018 K key = (K)s.readObject(); 1019 V value = (V)s.readObject(); 1020 // synch could be eliminated for performance 1021 reconstitutionPut(newTable, key, value); 1022 } 1023 this.table = newTable; 1024 } 1025 1026 /** 1027 * The put method used by readObject. This is provided because put 1028 * is overridable and should not be called in readObject since the 1029 * subclass will not yet be initialized. 1030 * 1031 * <p>This differs from the regular put method in several ways. No 1032 * checking for rehashing is necessary since the number of elements 1033 * initially in the table is known. The modCount is not incremented 1034 * because we are creating a new instance. Also, no return value 1035 * is needed. 1036 */ 1037 private void reconstitutionPut(HashtableEntry<K,V>[] tab, K key, V value) 1038 throws StreamCorruptedException 1039 { 1040 if (value == null) { 1041 throw new java.io.StreamCorruptedException(); 1042 } 1043 // Makes sure the key is not already in the hashtable. 1044 // This should not happen in deserialized version. 1045 int hash = hash(key); 1046 int index = (hash & 0x7FFFFFFF) % tab.length; 1047 for (HashtableEntry<K,V> e = tab[index] ; e != null ; e = e.next) { 1048 if ((e.hash == hash) && e.key.equals(key)) { 1049 throw new java.io.StreamCorruptedException(); 1050 } 1051 } 1052 // Creates the new entry. 1053 HashtableEntry<K,V> e = tab[index]; 1054 tab[index] = new HashtableEntry<>(hash, key, value, e); 1055 count++; 1056 } 1057 1058 /** 1059 * Hashtable bucket collision list entry 1060 */ 1061 static class HashtableEntry<K,V> implements Map.Entry<K,V> { 1062 int hash; 1063 final K key; 1064 V value; 1065 HashtableEntry<K,V> next; 1066 1067 protected HashtableEntry(int hash, K key, V value, HashtableEntry<K,V> next) { 1068 this.hash = hash; 1069 this.key = key; 1070 this.value = value; 1071 this.next = next; 1072 } 1073 1074 protected Object clone() { 1075 return new HashtableEntry<>(hash, key, value, 1076 (next==null ? null : (HashtableEntry<K,V>) next.clone())); 1077 } 1078 1079 // Map.Entry Ops 1080 1081 public K getKey() { 1082 return key; 1083 } 1084 1085 public V getValue() { 1086 return value; 1087 } 1088 1089 public V setValue(V value) { 1090 if (value == null) 1091 throw new NullPointerException(); 1092 1093 V oldValue = this.value; 1094 this.value = value; 1095 return oldValue; 1096 } 1097 1098 public boolean equals(Object o) { 1099 if (!(o instanceof Map.Entry)) 1100 return false; 1101 Map.Entry<?,?> e = (Map.Entry)o; 1102 1103 return key.equals(e.getKey()) && value.equals(e.getValue()); 1104 } 1105 1106 public int hashCode() { 1107 return (Objects.hashCode(key) ^ Objects.hashCode(value)); 1108 } 1109 1110 public String toString() { 1111 return key.toString()+"="+value.toString(); 1112 } 1113 } 1114 1115 // Types of Enumerations/Iterations 1116 private static final int KEYS = 0; 1117 private static final int VALUES = 1; 1118 private static final int ENTRIES = 2; 1119 1120 /** 1121 * A hashtable enumerator class. This class implements both the 1122 * Enumeration and Iterator interfaces, but individual instances 1123 * can be created with the Iterator methods disabled. This is necessary 1124 * to avoid unintentionally increasing the capabilities granted a user 1125 * by passing an Enumeration. 1126 */ 1127 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { 1128 HashtableEntry[] table = Hashtable.this.table; 1129 int index = table.length; 1130 HashtableEntry<K,V> entry = null; 1131 HashtableEntry<K,V> lastReturned = null; 1132 int type; 1133 1134 /** 1135 * Indicates whether this Enumerator is serving as an Iterator 1136 * or an Enumeration. (true -> Iterator). 1137 */ 1138 boolean iterator; 1139 1140 /** 1141 * The modCount value that the iterator believes that the backing 1142 * Hashtable should have. If this expectation is violated, the iterator 1143 * has detected concurrent modification. 1144 */ 1145 protected int expectedModCount = modCount; 1146 1147 Enumerator(int type, boolean iterator) { 1148 this.type = type; 1149 this.iterator = iterator; 1150 } 1151 1152 public boolean hasMoreElements() { 1153 HashtableEntry<K,V> e = entry; 1154 int i = index; 1155 HashtableEntry[] t = table; 1156 /* Use locals for faster loop iteration */ 1157 while (e == null && i > 0) { 1158 e = t[--i]; 1159 } 1160 entry = e; 1161 index = i; 1162 return e != null; 1163 } 1164 1165 public T nextElement() { 1166 HashtableEntry<K,V> et = entry; 1167 int i = index; 1168 HashtableEntry[] t = table; 1169 /* Use locals for faster loop iteration */ 1170 while (et == null && i > 0) { 1171 et = t[--i]; 1172 } 1173 entry = et; 1174 index = i; 1175 if (et != null) { 1176 HashtableEntry<K,V> e = lastReturned = entry; 1177 entry = e.next; 1178 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e); 1179 } 1180 throw new NoSuchElementException("Hashtable Enumerator"); 1181 } 1182 1183 // Iterator methods 1184 public boolean hasNext() { 1185 return hasMoreElements(); 1186 } 1187 1188 public T next() { 1189 if (modCount != expectedModCount) 1190 throw new ConcurrentModificationException(); 1191 return nextElement(); 1192 } 1193 1194 public void remove() { 1195 if (!iterator) 1196 throw new UnsupportedOperationException(); 1197 if (lastReturned == null) 1198 throw new IllegalStateException("Hashtable Enumerator"); 1199 if (modCount != expectedModCount) 1200 throw new ConcurrentModificationException(); 1201 1202 synchronized(Hashtable.this) { 1203 HashtableEntry[] tab = Hashtable.this.table; 1204 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 1205 1206 for (HashtableEntry<K,V> e = tab[index], prev = null; e != null; 1207 prev = e, e = e.next) { 1208 if (e == lastReturned) { 1209 modCount++; 1210 expectedModCount++; 1211 if (prev == null) 1212 tab[index] = e.next; 1213 else 1214 prev.next = e.next; 1215 count--; 1216 lastReturned = null; 1217 return; 1218 } 1219 } 1220 throw new ConcurrentModificationException(); 1221 } 1222 } 1223 } 1224} 1225