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