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