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