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