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