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