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