1 /* 2 * Copyright (c) 1994, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.io.*; 29 import java.util.function.BiConsumer; 30 import java.util.function.Function; 31 import java.util.function.BiFunction; 32 import jdk.internal.misc.SharedSecrets; 33 34 /** 35 * This class implements a hash table, which maps keys to values. Any 36 * non-{@code null} object can be used as a key or as a value. <p> 37 * 38 * To successfully store and retrieve objects from a hashtable, the 39 * objects used as keys must implement the {@code hashCode} 40 * method and the {@code equals} method. <p> 41 * 42 * An instance of {@code Hashtable} has two parameters that affect its 43 * performance: <i>initial capacity</i> and <i>load factor</i>. The 44 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 45 * <i>initial capacity</i> is simply the capacity at the time the hash table 46 * is created. Note that the hash table is <i>open</i>: in the case of a "hash 47 * collision", a single bucket stores multiple entries, which must be searched 48 * sequentially. The <i>load factor</i> is a measure of how full the hash 49 * table is allowed to get before its capacity is automatically increased. 50 * The initial capacity and load factor parameters are merely hints to 51 * the implementation. The exact details as to when and whether the rehash 52 * method is invoked are implementation-dependent.<p> 53 * 54 * Generally, the default load factor (.75) offers a good tradeoff between 55 * time and space costs. Higher values decrease the space overhead but 56 * increase the time cost to look up an entry (which is reflected in most 57 * {@code Hashtable} operations, including {@code get} and {@code put}).<p> 58 * 59 * The initial capacity controls a tradeoff between wasted space and the 60 * need for {@code rehash} operations, which are time-consuming. 61 * No {@code rehash} operations will <i>ever</i> occur if the initial 62 * capacity is greater than the maximum number of entries the 63 * {@code Hashtable} will contain divided by its load factor. However, 64 * setting the initial capacity too high can waste space.<p> 65 * 66 * If many entries are to be made into a {@code Hashtable}, 67 * creating it with a sufficiently large capacity may allow the 68 * entries to be inserted more efficiently than letting it perform 69 * automatic rehashing as needed to grow the table. <p> 70 * 71 * This example creates a hashtable of numbers. It uses the names of 72 * the numbers as keys: 73 * <pre> {@code 74 * Hashtable<String, Integer> numbers 75 * = new Hashtable<String, Integer>(); 76 * numbers.put("one", 1); 77 * numbers.put("two", 2); 78 * numbers.put("three", 3);}</pre> 79 * 80 * <p>To retrieve a number, use the following code: 81 * <pre> {@code 82 * Integer n = numbers.get("two"); 83 * if (n != null) { 84 * System.out.println("two = " + n); 85 * }}</pre> 86 * 87 * <p>The iterators returned by the {@code iterator} method of the collections 88 * returned by all of this class's "collection view methods" are 89 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time 90 * after the iterator is created, in any way except through the iterator's own 91 * {@code remove} method, the iterator will throw a {@link 92 * ConcurrentModificationException}. Thus, in the face of concurrent 93 * modification, the iterator fails quickly and cleanly, rather than risking 94 * arbitrary, non-deterministic behavior at an undetermined time in the future. 95 * The Enumerations returned by Hashtable's {@link #keys keys} and 96 * {@link #elements elements} methods are <em>not</em> fail-fast; if the 97 * Hashtable is structurally modified at any time after the enumeration is 98 * created then the results of enumerating are undefined. 99 * 100 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 101 * as it is, generally speaking, impossible to make any hard guarantees in the 102 * presence of unsynchronized concurrent modification. Fail-fast iterators 103 * throw {@code ConcurrentModificationException} on a best-effort basis. 104 * Therefore, it would be wrong to write a program that depended on this 105 * exception for its correctness: <i>the fail-fast behavior of iterators 106 * should be used only to detect bugs.</i> 107 * 108 * <p>As of the Java 2 platform v1.2, this class was retrofitted to 109 * implement the {@link Map} interface, making it a member of the 110 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 111 * 112 * Java Collections Framework</a>. Unlike the new collection 113 * implementations, {@code Hashtable} is synchronized. If a 114 * thread-safe implementation is not needed, it is recommended to use 115 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe 116 * highly-concurrent implementation is desired, then it is recommended 117 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of 118 * {@code Hashtable}. 119 * 120 * @param <K> the type of keys maintained by this map 121 * @param <V> the type of mapped values 122 * 123 * @author Arthur van Hoff 124 * @author Josh Bloch 125 * @author Neal Gafter 126 * @see Object#equals(java.lang.Object) 127 * @see Object#hashCode() 128 * @see Hashtable#rehash() 129 * @see Collection 130 * @see Map 131 * @see HashMap 132 * @see TreeMap 133 * @since 1.0 134 */ 135 public class Hashtable<K,V> 136 extends Dictionary<K,V> 137 implements Map<K,V>, Cloneable, java.io.Serializable { 138 139 /** 140 * The hash table data. 141 */ 142 private transient Entry<?,?>[] table; 143 144 /** 145 * The total number of entries in the hash table. 146 */ 147 private transient int count; 148 149 /** 150 * The table is rehashed when its size exceeds this threshold. (The 151 * value of this field is (int)(capacity * loadFactor).) 152 * 153 * @serial 154 */ 155 private int threshold; 156 157 /** 158 * The load factor for the hashtable. 159 * 160 * @serial 161 */ 162 private float loadFactor; 163 164 /** 165 * The number of times this Hashtable has been structurally modified 166 * Structural modifications are those that change the number of entries in 167 * the Hashtable or otherwise modify its internal structure (e.g., 168 * rehash). This field is used to make iterators on Collection-views of 169 * the Hashtable fail-fast. (See ConcurrentModificationException). 170 */ 171 private transient int modCount = 0; 172 173 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 174 private static final long serialVersionUID = 1421746759512286392L; 175 176 /** 177 * Constructs a new, empty hashtable with the specified initial 178 * capacity and the specified load factor. 179 * 180 * @param initialCapacity the initial capacity of the hashtable. 181 * @param loadFactor the load factor of the hashtable. 182 * @exception IllegalArgumentException if the initial capacity is less 183 * than zero, or if the load factor is nonpositive. 184 */ 185 public Hashtable(int initialCapacity, float loadFactor) { 186 if (initialCapacity < 0) 187 throw new IllegalArgumentException("Illegal Capacity: "+ 188 initialCapacity); 189 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 190 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 191 192 if (initialCapacity==0) 193 initialCapacity = 1; 194 this.loadFactor = loadFactor; 195 table = new Entry<?,?>[initialCapacity]; 196 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 197 } 198 199 /** 200 * Constructs a new, empty hashtable with the specified initial capacity 201 * and default load factor (0.75). 202 * 203 * @param initialCapacity the initial capacity of the hashtable. 204 * @exception IllegalArgumentException if the initial capacity is less 205 * than zero. 206 */ 207 public Hashtable(int initialCapacity) { 208 this(initialCapacity, 0.75f); 209 } 210 211 /** 212 * Constructs a new, empty hashtable with a default initial capacity (11) 213 * and load factor (0.75). 214 */ 215 public Hashtable() { 216 this(11, 0.75f); 217 } 218 219 /** 220 * Constructs a new hashtable with the same mappings as the given 221 * Map. The hashtable is created with an initial capacity sufficient to 222 * hold the mappings in the given Map and a default load factor (0.75). 223 * 224 * @param t the map whose mappings are to be placed in this map. 225 * @throws NullPointerException if the specified map is null. 226 * @since 1.2 227 */ 228 public Hashtable(Map<? extends K, ? extends V> t) { 229 this(Math.max(2*t.size(), 11), 0.75f); 230 putAll(t); 231 } 232 233 /** 234 * A constructor chained from {@link Properties} keeps Hashtable fields 235 * uninitialized since they are not used. 236 * 237 * @param dummy a dummy parameter 238 */ 239 Hashtable(Void dummy) {} 240 241 /** 242 * Returns the number of keys in this hashtable. 243 * 244 * @return the number of keys in this hashtable. 245 */ 246 public synchronized int size() { 247 return count; 248 } 249 250 /** 251 * Tests if this hashtable maps no keys to values. 252 * 253 * @return {@code true} if this hashtable maps no keys to values; 254 * {@code false} otherwise. 255 */ 256 public synchronized boolean isEmpty() { 257 return count == 0; 258 } 259 260 /** 261 * Returns an enumeration of the keys in this hashtable. 262 * Use the Enumeration methods on the returned object to fetch the keys 263 * sequentially. If the hashtable is structurally modified while enumerating 264 * over the keys then the results of enumerating are undefined. 265 * 266 * @return an enumeration of the keys in this hashtable. 267 * @see Enumeration 268 * @see #elements() 269 * @see #keySet() 270 * @see Map 271 */ 272 public synchronized Enumeration<K> keys() { 273 return this.<K>getEnumeration(KEYS); 274 } 275 276 /** 277 * Returns an enumeration of the values in this hashtable. 278 * Use the Enumeration methods on the returned object to fetch the elements 279 * sequentially. If the hashtable is structurally modified while enumerating 280 * over the values then the results of enumerating are undefined. 281 * 282 * @return an enumeration of the values in this hashtable. 283 * @see java.util.Enumeration 284 * @see #keys() 285 * @see #values() 286 * @see Map 287 */ 288 public synchronized Enumeration<V> elements() { 289 return this.<V>getEnumeration(VALUES); 290 } 291 292 /** 293 * Tests if some key maps into the specified value in this hashtable. 294 * This operation is more expensive than the {@link #containsKey 295 * containsKey} method. 296 * 297 * <p>Note that this method is identical in functionality to 298 * {@link #containsValue containsValue}, (which is part of the 299 * {@link Map} interface in the collections framework). 300 * 301 * @param value a value to search for 302 * @return {@code true} if and only if some key maps to the 303 * {@code value} argument in this hashtable as 304 * determined by the {@code equals} method; 305 * {@code false} otherwise. 306 * @exception NullPointerException if the value is {@code null} 307 */ 308 public synchronized boolean contains(Object value) { 309 if (value == null) { 310 throw new NullPointerException(); 311 } 312 313 Entry<?,?>[] tab = table; 314 for (int i = tab.length ; i-- > 0 ;) { 315 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) { 316 if (e.value.equals(value)) { 317 return true; 318 } 319 } 320 } 321 return false; 322 } 323 324 /** 325 * Returns true if this hashtable maps one or more keys to this value. 326 * 327 * <p>Note that this method is identical in functionality to {@link 328 * #contains contains} (which predates the {@link Map} interface). 329 * 330 * @param value value whose presence in this hashtable is to be tested 331 * @return {@code true} if this map maps one or more keys to the 332 * specified value 333 * @throws NullPointerException if the value is {@code null} 334 * @since 1.2 335 */ 336 public boolean containsValue(Object value) { 337 return contains(value); 338 } 339 340 /** 341 * Tests if the specified object is a key in this hashtable. 342 * 343 * @param key possible key 344 * @return {@code true} if and only if the specified object 345 * is a key in this hashtable, as determined by the 346 * {@code equals} method; {@code false} otherwise. 347 * @throws NullPointerException if the key is {@code null} 348 * @see #contains(Object) 349 */ 350 public synchronized boolean containsKey(Object key) { 351 Entry<?,?>[] tab = table; 352 int hash = key.hashCode(); 353 int index = (hash & 0x7FFFFFFF) % tab.length; 354 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 355 if ((e.hash == hash) && e.key.equals(key)) { 356 return true; 357 } 358 } 359 return false; 360 } 361 362 /** 363 * Returns the value to which the specified key is mapped, 364 * or {@code null} if this map contains no mapping for the key. 365 * 366 * <p>More formally, if this map contains a mapping from a key 367 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 368 * then this method returns {@code v}; otherwise it returns 369 * {@code null}. (There can be at most one such mapping.) 370 * 371 * @param key the key whose associated value is to be returned 372 * @return the value to which the specified key is mapped, or 373 * {@code null} if this map contains no mapping for the key 374 * @throws NullPointerException if the specified key is null 375 * @see #put(Object, Object) 376 */ 377 @SuppressWarnings("unchecked") 378 public synchronized V get(Object key) { 379 Entry<?,?>[] tab = table; 380 int hash = key.hashCode(); 381 int index = (hash & 0x7FFFFFFF) % tab.length; 382 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 383 if ((e.hash == hash) && e.key.equals(key)) { 384 return (V)e.value; 385 } 386 } 387 return null; 388 } 389 390 /** 391 * The maximum size of array to allocate. 392 * Some VMs reserve some header words in an array. 393 * Attempts to allocate larger arrays may result in 394 * OutOfMemoryError: Requested array size exceeds VM limit 395 */ 396 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 397 398 /** 399 * Increases the capacity of and internally reorganizes this 400 * hashtable, in order to accommodate and access its entries more 401 * efficiently. This method is called automatically when the 402 * number of keys in the hashtable exceeds this hashtable's capacity 403 * and load factor. 404 */ 405 @SuppressWarnings("unchecked") 406 protected void rehash() { 407 int oldCapacity = table.length; 408 Entry<?,?>[] oldMap = table; 409 410 // overflow-conscious code 411 int newCapacity = (oldCapacity << 1) + 1; 412 if (newCapacity - MAX_ARRAY_SIZE > 0) { 413 if (oldCapacity == MAX_ARRAY_SIZE) 414 // Keep running with MAX_ARRAY_SIZE buckets 415 return; 416 newCapacity = MAX_ARRAY_SIZE; 417 } 418 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; 419 420 modCount++; 421 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 422 table = newMap; 423 424 for (int i = oldCapacity ; i-- > 0 ;) { 425 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { 426 Entry<K,V> e = old; 427 old = old.next; 428 429 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 430 e.next = (Entry<K,V>)newMap[index]; 431 newMap[index] = e; 432 } 433 } 434 } 435 436 private void addEntry(int hash, K key, V value, int index) { 437 Entry<?,?>[] tab = table; 438 if (count >= threshold) { 439 // Rehash the table if the threshold is exceeded 440 rehash(); 441 442 tab = table; 443 hash = key.hashCode(); 444 index = (hash & 0x7FFFFFFF) % tab.length; 445 } 446 447 // Creates the new entry. 448 @SuppressWarnings("unchecked") 449 Entry<K,V> e = (Entry<K,V>) tab[index]; 450 tab[index] = new Entry<>(hash, key, value, e); 451 count++; 452 modCount++; 453 } 454 455 /** 456 * Maps the specified {@code key} to the specified 457 * {@code value} in this hashtable. Neither the key nor the 458 * value can be {@code null}. <p> 459 * 460 * The value can be retrieved by calling the {@code get} method 461 * with a key that is equal to the original key. 462 * 463 * @param key the hashtable key 464 * @param value the value 465 * @return the previous value of the specified key in this hashtable, 466 * or {@code null} if it did not have one 467 * @exception NullPointerException if the key or value is 468 * {@code null} 469 * @see Object#equals(Object) 470 * @see #get(Object) 471 */ 472 public synchronized V put(K key, V value) { 473 // Make sure the value is not null 474 if (value == null) { 475 throw new NullPointerException(); 476 } 477 478 // Makes sure the key is not already in the hashtable. 479 Entry<?,?>[] tab = table; 480 int hash = key.hashCode(); 481 int index = (hash & 0x7FFFFFFF) % tab.length; 482 @SuppressWarnings("unchecked") 483 Entry<K,V> entry = (Entry<K,V>)tab[index]; 484 for(; entry != null ; entry = entry.next) { 485 if ((entry.hash == hash) && entry.key.equals(key)) { 486 V old = entry.value; 487 entry.value = value; 488 return old; 489 } 490 } 491 492 addEntry(hash, key, value, index); 493 return null; 494 } 495 496 /** 497 * Removes the key (and its corresponding value) from this 498 * hashtable. This method does nothing if the key is not in the hashtable. 499 * 500 * @param key the key that needs to be removed 501 * @return the value to which the key had been mapped in this hashtable, 502 * or {@code null} if the key did not have a mapping 503 * @throws NullPointerException if the key is {@code null} 504 */ 505 public synchronized V remove(Object key) { 506 Entry<?,?>[] tab = table; 507 int hash = key.hashCode(); 508 int index = (hash & 0x7FFFFFFF) % tab.length; 509 @SuppressWarnings("unchecked") 510 Entry<K,V> e = (Entry<K,V>)tab[index]; 511 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 512 if ((e.hash == hash) && e.key.equals(key)) { 513 if (prev != null) { 514 prev.next = e.next; 515 } else { 516 tab[index] = e.next; 517 } 518 modCount++; 519 count--; 520 V oldValue = e.value; 521 e.value = null; 522 return oldValue; 523 } 524 } 525 return null; 526 } 527 528 /** 529 * Copies all of the mappings from the specified map to this hashtable. 530 * These mappings will replace any mappings that this hashtable had for any 531 * of the keys currently in the specified map. 532 * 533 * @param t mappings to be stored in this map 534 * @throws NullPointerException if the specified map is null 535 * @since 1.2 536 */ 537 public synchronized void putAll(Map<? extends K, ? extends V> t) { 538 for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) 539 put(e.getKey(), e.getValue()); 540 } 541 542 /** 543 * Clears this hashtable so that it contains no keys. 544 */ 545 public synchronized void clear() { 546 Entry<?,?>[] tab = table; 547 for (int index = tab.length; --index >= 0; ) 548 tab[index] = null; 549 modCount++; 550 count = 0; 551 } 552 553 /** 554 * Creates a shallow copy of this hashtable. All the structure of the 555 * hashtable itself is copied, but the keys and values are not cloned. 556 * This is a relatively expensive operation. 557 * 558 * @return a clone of the hashtable 559 */ 560 public synchronized Object clone() { 561 Hashtable<?,?> t = cloneHashtable(); 562 t.table = new Entry<?,?>[table.length]; 563 for (int i = table.length ; i-- > 0 ; ) { 564 t.table[i] = (table[i] != null) 565 ? (Entry<?,?>) table[i].clone() : null; 566 } 567 t.keySet = null; 568 t.entrySet = null; 569 t.values = null; 570 t.modCount = 0; 571 return t; 572 } 573 574 /** Calls super.clone() */ 575 final Hashtable<?,?> cloneHashtable() { 576 try { 577 return (Hashtable<?,?>)super.clone(); 578 } catch (CloneNotSupportedException e) { 579 // this shouldn't happen, since we are Cloneable 580 throw new InternalError(e); 581 } 582 } 583 584 /** 585 * Returns a string representation of this {@code Hashtable} object 586 * in the form of a set of entries, enclosed in braces and separated 587 * by the ASCII characters "<code> , </code>" (comma and space). Each 588 * entry is rendered as the key, an equals sign {@code =}, and the 589 * associated element, where the {@code toString} method is used to 590 * convert the key and element to strings. 591 * 592 * @return a string representation of this hashtable 593 */ 594 public synchronized String toString() { 595 int max = size() - 1; 596 if (max == -1) 597 return "{}"; 598 599 StringBuilder sb = new StringBuilder(); 600 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 601 602 sb.append('{'); 603 for (int i = 0; ; i++) { 604 Map.Entry<K,V> e = it.next(); 605 K key = e.getKey(); 606 V value = e.getValue(); 607 sb.append(key == this ? "(this Map)" : key.toString()); 608 sb.append('='); 609 sb.append(value == this ? "(this Map)" : value.toString()); 610 611 if (i == max) 612 return sb.append('}').toString(); 613 sb.append(", "); 614 } 615 } 616 617 618 private <T> Enumeration<T> getEnumeration(int type) { 619 if (count == 0) { 620 return Collections.emptyEnumeration(); 621 } else { 622 return new Enumerator<>(type, false); 623 } 624 } 625 626 private <T> Iterator<T> getIterator(int type) { 627 if (count == 0) { 628 return Collections.emptyIterator(); 629 } else { 630 return new Enumerator<>(type, true); 631 } 632 } 633 634 // Views 635 636 /** 637 * Each of these fields are initialized to contain an instance of the 638 * appropriate view the first time this view is requested. The views are 639 * stateless, so there's no reason to create more than one of each. 640 */ 641 private transient volatile Set<K> keySet; 642 private transient volatile Set<Map.Entry<K,V>> entrySet; 643 private transient volatile Collection<V> values; 644 645 /** 646 * Returns a {@link Set} view of the keys contained in this map. 647 * The set is backed by the map, so changes to the map are 648 * reflected in the set, and vice-versa. If the map is modified 649 * while an iteration over the set is in progress (except through 650 * the iterator's own {@code remove} operation), the results of 651 * the iteration are undefined. The set supports element removal, 652 * which removes the corresponding mapping from the map, via the 653 * {@code Iterator.remove}, {@code Set.remove}, 654 * {@code removeAll}, {@code retainAll}, and {@code clear} 655 * operations. It does not support the {@code add} or {@code addAll} 656 * operations. 657 * 658 * @since 1.2 659 */ 660 public Set<K> keySet() { 661 if (keySet == null) 662 keySet = Collections.synchronizedSet(new KeySet(), this); 663 return keySet; 664 } 665 666 private class KeySet extends AbstractSet<K> { 667 public Iterator<K> iterator() { 668 return getIterator(KEYS); 669 } 670 public int size() { 671 return count; 672 } 673 public boolean contains(Object o) { 674 return containsKey(o); 675 } 676 public boolean remove(Object o) { 677 return Hashtable.this.remove(o) != null; 678 } 679 public void clear() { 680 Hashtable.this.clear(); 681 } 682 } 683 684 /** 685 * Returns a {@link Set} view of the mappings contained in this map. 686 * The set is backed by the map, so changes to the map are 687 * reflected in the set, and vice-versa. If the map is modified 688 * while an iteration over the set is in progress (except through 689 * the iterator's own {@code remove} operation, or through the 690 * {@code setValue} operation on a map entry returned by the 691 * iterator) the results of the iteration are undefined. The set 692 * supports element removal, which removes the corresponding 693 * mapping from the map, via the {@code Iterator.remove}, 694 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and 695 * {@code clear} operations. It does not support the 696 * {@code add} or {@code addAll} operations. 697 * 698 * @since 1.2 699 */ 700 public Set<Map.Entry<K,V>> entrySet() { 701 if (entrySet==null) 702 entrySet = Collections.synchronizedSet(new EntrySet(), this); 703 return entrySet; 704 } 705 706 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 707 public Iterator<Map.Entry<K,V>> iterator() { 708 return getIterator(ENTRIES); 709 } 710 711 public boolean add(Map.Entry<K,V> o) { 712 return super.add(o); 713 } 714 715 public boolean contains(Object o) { 716 if (!(o instanceof Map.Entry)) 717 return false; 718 Map.Entry<?,?> entry = (Map.Entry<?,?>)o; 719 Object key = entry.getKey(); 720 Entry<?,?>[] tab = table; 721 int hash = key.hashCode(); 722 int index = (hash & 0x7FFFFFFF) % tab.length; 723 724 for (Entry<?,?> e = tab[index]; e != null; e = e.next) 725 if (e.hash==hash && e.equals(entry)) 726 return true; 727 return false; 728 } 729 730 public boolean remove(Object o) { 731 if (!(o instanceof Map.Entry)) 732 return false; 733 Map.Entry<?,?> entry = (Map.Entry<?,?>) o; 734 Object key = entry.getKey(); 735 Entry<?,?>[] tab = table; 736 int hash = key.hashCode(); 737 int index = (hash & 0x7FFFFFFF) % tab.length; 738 739 @SuppressWarnings("unchecked") 740 Entry<K,V> e = (Entry<K,V>)tab[index]; 741 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 742 if (e.hash==hash && e.equals(entry)) { 743 if (prev != null) 744 prev.next = e.next; 745 else 746 tab[index] = e.next; 747 748 e.value = null; // clear for gc. 749 modCount++; 750 count--; 751 return true; 752 } 753 } 754 return false; 755 } 756 757 public int size() { 758 return count; 759 } 760 761 public void clear() { 762 Hashtable.this.clear(); 763 } 764 } 765 766 /** 767 * Returns a {@link Collection} view of the values contained in this map. 768 * The collection is backed by the map, so changes to the map are 769 * reflected in the collection, and vice-versa. If the map is 770 * modified while an iteration over the collection is in progress 771 * (except through the iterator's own {@code remove} operation), 772 * the results of the iteration are undefined. The collection 773 * supports element removal, which removes the corresponding 774 * mapping from the map, via the {@code Iterator.remove}, 775 * {@code Collection.remove}, {@code removeAll}, 776 * {@code retainAll} and {@code clear} operations. It does not 777 * support the {@code add} or {@code addAll} operations. 778 * 779 * @since 1.2 780 */ 781 public Collection<V> values() { 782 if (values==null) 783 values = Collections.synchronizedCollection(new ValueCollection(), 784 this); 785 return values; 786 } 787 788 private class ValueCollection extends AbstractCollection<V> { 789 public Iterator<V> iterator() { 790 return getIterator(VALUES); 791 } 792 public int size() { 793 return count; 794 } 795 public boolean contains(Object o) { 796 return containsValue(o); 797 } 798 public void clear() { 799 Hashtable.this.clear(); 800 } 801 } 802 803 // Comparison and hashing 804 805 /** 806 * Compares the specified Object with this Map for equality, 807 * as per the definition in the Map interface. 808 * 809 * @param o object to be compared for equality with this hashtable 810 * @return true if the specified Object is equal to this Map 811 * @see Map#equals(Object) 812 * @since 1.2 813 */ 814 public synchronized boolean equals(Object o) { 815 if (o == this) 816 return true; 817 818 if (!(o instanceof Map)) 819 return false; 820 Map<?,?> t = (Map<?,?>) o; 821 if (t.size() != size()) 822 return false; 823 824 try { 825 for (Map.Entry<K, V> e : entrySet()) { 826 K key = e.getKey(); 827 V value = e.getValue(); 828 if (value == null) { 829 if (!(t.get(key) == null && t.containsKey(key))) 830 return false; 831 } else { 832 if (!value.equals(t.get(key))) 833 return false; 834 } 835 } 836 } catch (ClassCastException unused) { 837 return false; 838 } catch (NullPointerException unused) { 839 return false; 840 } 841 842 return true; 843 } 844 845 /** 846 * Returns the hash code value for this Map as per the definition in the 847 * Map interface. 848 * 849 * @see Map#hashCode() 850 * @since 1.2 851 */ 852 public synchronized int hashCode() { 853 /* 854 * This code detects the recursion caused by computing the hash code 855 * of a self-referential hash table and prevents the stack overflow 856 * that would otherwise result. This allows certain 1.1-era 857 * applets with self-referential hash tables to work. This code 858 * abuses the loadFactor field to do double-duty as a hashCode 859 * in progress flag, so as not to worsen the space performance. 860 * A negative load factor indicates that hash code computation is 861 * in progress. 862 */ 863 int h = 0; 864 if (count == 0 || loadFactor < 0) 865 return h; // Returns zero 866 867 loadFactor = -loadFactor; // Mark hashCode computation in progress 868 Entry<?,?>[] tab = table; 869 for (Entry<?,?> entry : tab) { 870 while (entry != null) { 871 h += entry.hashCode(); 872 entry = entry.next; 873 } 874 } 875 876 loadFactor = -loadFactor; // Mark hashCode computation complete 877 878 return h; 879 } 880 881 @Override 882 public synchronized V getOrDefault(Object key, V defaultValue) { 883 V result = get(key); 884 return (null == result) ? defaultValue : result; 885 } 886 887 @SuppressWarnings("unchecked") 888 @Override 889 public synchronized void forEach(BiConsumer<? super K, ? super V> action) { 890 Objects.requireNonNull(action); // explicit check required in case 891 // table is empty. 892 final int expectedModCount = modCount; 893 894 Entry<?, ?>[] tab = table; 895 for (Entry<?, ?> entry : tab) { 896 while (entry != null) { 897 action.accept((K)entry.key, (V)entry.value); 898 entry = entry.next; 899 900 if (expectedModCount != modCount) { 901 throw new ConcurrentModificationException(); 902 } 903 } 904 } 905 } 906 907 @SuppressWarnings("unchecked") 908 @Override 909 public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 910 Objects.requireNonNull(function); // explicit check required in case 911 // table is empty. 912 final int expectedModCount = modCount; 913 914 Entry<K, V>[] tab = (Entry<K, V>[])table; 915 for (Entry<K, V> entry : tab) { 916 while (entry != null) { 917 entry.value = Objects.requireNonNull( 918 function.apply(entry.key, entry.value)); 919 entry = entry.next; 920 921 if (expectedModCount != modCount) { 922 throw new ConcurrentModificationException(); 923 } 924 } 925 } 926 } 927 928 @Override 929 public synchronized V putIfAbsent(K key, V value) { 930 Objects.requireNonNull(value); 931 932 // Makes sure the key is not already in the hashtable. 933 Entry<?,?>[] tab = table; 934 int hash = key.hashCode(); 935 int index = (hash & 0x7FFFFFFF) % tab.length; 936 @SuppressWarnings("unchecked") 937 Entry<K,V> entry = (Entry<K,V>)tab[index]; 938 for (; entry != null; entry = entry.next) { 939 if ((entry.hash == hash) && entry.key.equals(key)) { 940 V old = entry.value; 941 if (old == null) { 942 entry.value = value; 943 } 944 return old; 945 } 946 } 947 948 addEntry(hash, key, value, index); 949 return null; 950 } 951 952 @Override 953 public synchronized boolean remove(Object key, Object value) { 954 Objects.requireNonNull(value); 955 956 Entry<?,?>[] tab = table; 957 int hash = key.hashCode(); 958 int index = (hash & 0x7FFFFFFF) % tab.length; 959 @SuppressWarnings("unchecked") 960 Entry<K,V> e = (Entry<K,V>)tab[index]; 961 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 962 if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) { 963 if (prev != null) { 964 prev.next = e.next; 965 } else { 966 tab[index] = e.next; 967 } 968 e.value = null; // clear for gc 969 modCount++; 970 count--; 971 return true; 972 } 973 } 974 return false; 975 } 976 977 @Override 978 public synchronized boolean replace(K key, V oldValue, V newValue) { 979 Objects.requireNonNull(oldValue); 980 Objects.requireNonNull(newValue); 981 Entry<?,?>[] tab = table; 982 int hash = key.hashCode(); 983 int index = (hash & 0x7FFFFFFF) % tab.length; 984 @SuppressWarnings("unchecked") 985 Entry<K,V> e = (Entry<K,V>)tab[index]; 986 for (; e != null; e = e.next) { 987 if ((e.hash == hash) && e.key.equals(key)) { 988 if (e.value.equals(oldValue)) { 989 e.value = newValue; 990 return true; 991 } else { 992 return false; 993 } 994 } 995 } 996 return false; 997 } 998 999 @Override 1000 public synchronized V replace(K key, V value) { 1001 Objects.requireNonNull(value); 1002 Entry<?,?>[] tab = table; 1003 int hash = key.hashCode(); 1004 int index = (hash & 0x7FFFFFFF) % tab.length; 1005 @SuppressWarnings("unchecked") 1006 Entry<K,V> e = (Entry<K,V>)tab[index]; 1007 for (; e != null; e = e.next) { 1008 if ((e.hash == hash) && e.key.equals(key)) { 1009 V oldValue = e.value; 1010 e.value = value; 1011 return oldValue; 1012 } 1013 } 1014 return null; 1015 } 1016 1017 /** 1018 * {@inheritDoc} 1019 * 1020 * <p>This method will, on a best-effort basis, throw a 1021 * {@link java.util.ConcurrentModificationException} if the mapping 1022 * function modified this map during computation. 1023 * 1024 * @throws ConcurrentModificationException if it is detected that the 1025 * mapping function modified this map 1026 */ 1027 @Override 1028 public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 1029 Objects.requireNonNull(mappingFunction); 1030 1031 Entry<?,?>[] tab = table; 1032 int hash = key.hashCode(); 1033 int index = (hash & 0x7FFFFFFF) % tab.length; 1034 @SuppressWarnings("unchecked") 1035 Entry<K,V> e = (Entry<K,V>)tab[index]; 1036 for (; e != null; e = e.next) { 1037 if (e.hash == hash && e.key.equals(key)) { 1038 // Hashtable not accept null value 1039 return e.value; 1040 } 1041 } 1042 1043 int mc = modCount; 1044 V newValue = mappingFunction.apply(key); 1045 if (mc != modCount) { throw new ConcurrentModificationException(); } 1046 if (newValue != null) { 1047 addEntry(hash, key, newValue, index); 1048 } 1049 1050 return newValue; 1051 } 1052 1053 /** 1054 * {@inheritDoc} 1055 * 1056 * <p>This method will, on a best-effort basis, throw a 1057 * {@link java.util.ConcurrentModificationException} if the remapping 1058 * function modified this map during computation. 1059 * 1060 * @throws ConcurrentModificationException if it is detected that the 1061 * remapping function modified this map 1062 */ 1063 @Override 1064 public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1065 Objects.requireNonNull(remappingFunction); 1066 1067 Entry<?,?>[] tab = table; 1068 int hash = key.hashCode(); 1069 int index = (hash & 0x7FFFFFFF) % tab.length; 1070 @SuppressWarnings("unchecked") 1071 Entry<K,V> e = (Entry<K,V>)tab[index]; 1072 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1073 if (e.hash == hash && e.key.equals(key)) { 1074 int mc = modCount; 1075 V newValue = remappingFunction.apply(key, e.value); 1076 if (mc != modCount) { 1077 throw new ConcurrentModificationException(); 1078 } 1079 if (newValue == null) { 1080 if (prev != null) { 1081 prev.next = e.next; 1082 } else { 1083 tab[index] = e.next; 1084 } 1085 modCount = mc + 1; 1086 count--; 1087 } else { 1088 e.value = newValue; 1089 } 1090 return newValue; 1091 } 1092 } 1093 return null; 1094 } 1095 /** 1096 * {@inheritDoc} 1097 * 1098 * <p>This method will, on a best-effort basis, throw a 1099 * {@link java.util.ConcurrentModificationException} if the remapping 1100 * function modified this map during computation. 1101 * 1102 * @throws ConcurrentModificationException if it is detected that the 1103 * remapping function modified this map 1104 */ 1105 @Override 1106 public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1107 Objects.requireNonNull(remappingFunction); 1108 1109 Entry<?,?>[] tab = table; 1110 int hash = key.hashCode(); 1111 int index = (hash & 0x7FFFFFFF) % tab.length; 1112 @SuppressWarnings("unchecked") 1113 Entry<K,V> e = (Entry<K,V>)tab[index]; 1114 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1115 if (e.hash == hash && Objects.equals(e.key, key)) { 1116 int mc = modCount; 1117 V newValue = remappingFunction.apply(key, e.value); 1118 if (mc != modCount) { 1119 throw new ConcurrentModificationException(); 1120 } 1121 if (newValue == null) { 1122 if (prev != null) { 1123 prev.next = e.next; 1124 } else { 1125 tab[index] = e.next; 1126 } 1127 modCount = mc + 1; 1128 count--; 1129 } else { 1130 e.value = newValue; 1131 } 1132 return newValue; 1133 } 1134 } 1135 1136 int mc = modCount; 1137 V newValue = remappingFunction.apply(key, null); 1138 if (mc != modCount) { throw new ConcurrentModificationException(); } 1139 if (newValue != null) { 1140 addEntry(hash, key, newValue, index); 1141 } 1142 1143 return newValue; 1144 } 1145 1146 /** 1147 * {@inheritDoc} 1148 * 1149 * <p>This method will, on a best-effort basis, throw a 1150 * {@link java.util.ConcurrentModificationException} if the remapping 1151 * function modified this map during computation. 1152 * 1153 * @throws ConcurrentModificationException if it is detected that the 1154 * remapping function modified this map 1155 */ 1156 @Override 1157 public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1158 Objects.requireNonNull(remappingFunction); 1159 1160 Entry<?,?>[] tab = table; 1161 int hash = key.hashCode(); 1162 int index = (hash & 0x7FFFFFFF) % tab.length; 1163 @SuppressWarnings("unchecked") 1164 Entry<K,V> e = (Entry<K,V>)tab[index]; 1165 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1166 if (e.hash == hash && e.key.equals(key)) { 1167 int mc = modCount; 1168 V newValue = remappingFunction.apply(e.value, value); 1169 if (mc != modCount) { 1170 throw new ConcurrentModificationException(); 1171 } 1172 if (newValue == null) { 1173 if (prev != null) { 1174 prev.next = e.next; 1175 } else { 1176 tab[index] = e.next; 1177 } 1178 modCount = mc + 1; 1179 count--; 1180 } else { 1181 e.value = newValue; 1182 } 1183 return newValue; 1184 } 1185 } 1186 1187 if (value != null) { 1188 addEntry(hash, key, value, index); 1189 } 1190 1191 return value; 1192 } 1193 1194 /** 1195 * Save the state of the Hashtable to a stream (i.e., serialize it). 1196 * 1197 * @serialData The <i>capacity</i> of the Hashtable (the length of the 1198 * bucket array) is emitted (int), followed by the 1199 * <i>size</i> of the Hashtable (the number of key-value 1200 * mappings), followed by the key (Object) and value (Object) 1201 * for each key-value mapping represented by the Hashtable 1202 * The key-value mappings are emitted in no particular order. 1203 */ 1204 private void writeObject(java.io.ObjectOutputStream s) 1205 throws IOException { 1206 writeHashtable(s); 1207 } 1208 1209 /** 1210 * Perform serialization of the Hashtable to an ObjectOutputStream. 1211 * The Properties class overrides this method. 1212 */ 1213 void writeHashtable(java.io.ObjectOutputStream s) 1214 throws IOException { 1215 Entry<Object, Object> entryStack = null; 1216 1217 synchronized (this) { 1218 // Write out the threshold and loadFactor 1219 s.defaultWriteObject(); 1220 1221 // Write out the length and count of elements 1222 s.writeInt(table.length); 1223 s.writeInt(count); 1224 1225 // Stack copies of the entries in the table 1226 for (Entry<?, ?> entry : table) { 1227 1228 while (entry != null) { 1229 entryStack = 1230 new Entry<>(0, entry.key, entry.value, entryStack); 1231 entry = entry.next; 1232 } 1233 } 1234 } 1235 1236 // Write out the key/value objects from the stacked entries 1237 while (entryStack != null) { 1238 s.writeObject(entryStack.key); 1239 s.writeObject(entryStack.value); 1240 entryStack = entryStack.next; 1241 } 1242 } 1243 1244 /** 1245 * Called by Properties to write out a simulated threshold and loadfactor. 1246 */ 1247 final void defaultWriteHashtable(java.io.ObjectOutputStream s, int length, 1248 float loadFactor) throws IOException { 1249 this.threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1); 1250 this.loadFactor = loadFactor; 1251 s.defaultWriteObject(); 1252 } 1253 1254 /** 1255 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 1256 */ 1257 private void readObject(java.io.ObjectInputStream s) 1258 throws IOException, ClassNotFoundException { 1259 readHashtable(s); 1260 } 1261 1262 /** 1263 * Perform deserialization of the Hashtable from an ObjectInputStream. 1264 * The Properties class overrides this method. 1265 */ 1266 void readHashtable(java.io.ObjectInputStream s) 1267 throws IOException, ClassNotFoundException { 1268 // Read in the threshold and loadFactor 1269 s.defaultReadObject(); 1270 1271 // Validate loadFactor (ignore threshold - it will be re-computed) 1272 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 1273 throw new StreamCorruptedException("Illegal Load: " + loadFactor); 1274 1275 // Read the original length of the array and number of elements 1276 int origlength = s.readInt(); 1277 int elements = s.readInt(); 1278 1279 // Validate # of elements 1280 if (elements < 0) 1281 throw new StreamCorruptedException("Illegal # of Elements: " + elements); 1282 1283 // Clamp original length to be more than elements / loadFactor 1284 // (this is the invariant enforced with auto-growth) 1285 origlength = Math.max(origlength, (int)(elements / loadFactor) + 1); 1286 1287 // Compute new length with a bit of room 5% + 3 to grow but 1288 // no larger than the clamped original length. Make the length 1289 // odd if it's large enough, this helps distribute the entries. 1290 // Guard against the length ending up zero, that's not valid. 1291 int length = (int)((elements + elements / 20) / loadFactor) + 3; 1292 if (length > elements && (length & 1) == 0) 1293 length--; 1294 length = Math.min(length, origlength); 1295 1296 if (length < 0) { // overflow 1297 length = origlength; 1298 } 1299 1300 // Check Map.Entry[].class since it's the nearest public type to 1301 // what we're actually creating. 1302 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, length); 1303 table = new Entry<?,?>[length]; 1304 threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1); 1305 count = 0; 1306 1307 // Read the number of elements and then all the key/value objects 1308 for (; elements > 0; elements--) { 1309 @SuppressWarnings("unchecked") 1310 K key = (K)s.readObject(); 1311 @SuppressWarnings("unchecked") 1312 V value = (V)s.readObject(); 1313 // sync is eliminated for performance 1314 reconstitutionPut(table, key, value); 1315 } 1316 } 1317 1318 /** 1319 * The put method used by readObject. This is provided because put 1320 * is overridable and should not be called in readObject since the 1321 * subclass will not yet be initialized. 1322 * 1323 * <p>This differs from the regular put method in several ways. No 1324 * checking for rehashing is necessary since the number of elements 1325 * initially in the table is known. The modCount is not incremented and 1326 * there's no synchronization because we are creating a new instance. 1327 * Also, no return value is needed. 1328 */ 1329 private void reconstitutionPut(Entry<?,?>[] tab, K key, V value) 1330 throws StreamCorruptedException 1331 { 1332 if (value == null) { 1333 throw new java.io.StreamCorruptedException(); 1334 } 1335 // Makes sure the key is not already in the hashtable. 1336 // This should not happen in deserialized version. 1337 int hash = key.hashCode(); 1338 int index = (hash & 0x7FFFFFFF) % tab.length; 1339 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 1340 if ((e.hash == hash) && e.key.equals(key)) { 1341 throw new java.io.StreamCorruptedException(); 1342 } 1343 } 1344 // Creates the new entry. 1345 @SuppressWarnings("unchecked") 1346 Entry<K,V> e = (Entry<K,V>)tab[index]; 1347 tab[index] = new Entry<>(hash, key, value, e); 1348 count++; 1349 } 1350 1351 /** 1352 * Hashtable bucket collision list entry 1353 */ 1354 private static class Entry<K,V> implements Map.Entry<K,V> { 1355 final int hash; 1356 final K key; 1357 V value; 1358 Entry<K,V> next; 1359 1360 protected Entry(int hash, K key, V value, Entry<K,V> next) { 1361 this.hash = hash; 1362 this.key = key; 1363 this.value = value; 1364 this.next = next; 1365 } 1366 1367 @SuppressWarnings("unchecked") 1368 protected Object clone() { 1369 return new Entry<>(hash, key, value, 1370 (next==null ? null : (Entry<K,V>) next.clone())); 1371 } 1372 1373 // Map.Entry Ops 1374 1375 public K getKey() { 1376 return key; 1377 } 1378 1379 public V getValue() { 1380 return value; 1381 } 1382 1383 public V setValue(V value) { 1384 if (value == null) 1385 throw new NullPointerException(); 1386 1387 V oldValue = this.value; 1388 this.value = value; 1389 return oldValue; 1390 } 1391 1392 public boolean equals(Object o) { 1393 if (!(o instanceof Map.Entry)) 1394 return false; 1395 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1396 1397 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 1398 (value==null ? e.getValue()==null : value.equals(e.getValue())); 1399 } 1400 1401 public int hashCode() { 1402 return hash ^ Objects.hashCode(value); 1403 } 1404 1405 public String toString() { 1406 return key.toString()+"="+value.toString(); 1407 } 1408 } 1409 1410 // Types of Enumerations/Iterations 1411 private static final int KEYS = 0; 1412 private static final int VALUES = 1; 1413 private static final int ENTRIES = 2; 1414 1415 /** 1416 * A hashtable enumerator class. This class implements both the 1417 * Enumeration and Iterator interfaces, but individual instances 1418 * can be created with the Iterator methods disabled. This is necessary 1419 * to avoid unintentionally increasing the capabilities granted a user 1420 * by passing an Enumeration. 1421 */ 1422 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { 1423 final Entry<?,?>[] table = Hashtable.this.table; 1424 int index = table.length; 1425 Entry<?,?> entry; 1426 Entry<?,?> lastReturned; 1427 final int type; 1428 1429 /** 1430 * Indicates whether this Enumerator is serving as an Iterator 1431 * or an Enumeration. (true -> Iterator). 1432 */ 1433 final boolean iterator; 1434 1435 /** 1436 * The modCount value that the iterator believes that the backing 1437 * Hashtable should have. If this expectation is violated, the iterator 1438 * has detected concurrent modification. 1439 */ 1440 protected int expectedModCount = Hashtable.this.modCount; 1441 1442 Enumerator(int type, boolean iterator) { 1443 this.type = type; 1444 this.iterator = iterator; 1445 } 1446 1447 public boolean hasMoreElements() { 1448 Entry<?,?> e = entry; 1449 int i = index; 1450 Entry<?,?>[] t = table; 1451 /* Use locals for faster loop iteration */ 1452 while (e == null && i > 0) { 1453 e = t[--i]; 1454 } 1455 entry = e; 1456 index = i; 1457 return e != null; 1458 } 1459 1460 @SuppressWarnings("unchecked") 1461 public T nextElement() { 1462 Entry<?,?> et = entry; 1463 int i = index; 1464 Entry<?,?>[] t = table; 1465 /* Use locals for faster loop iteration */ 1466 while (et == null && i > 0) { 1467 et = t[--i]; 1468 } 1469 entry = et; 1470 index = i; 1471 if (et != null) { 1472 Entry<?,?> e = lastReturned = entry; 1473 entry = e.next; 1474 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e); 1475 } 1476 throw new NoSuchElementException("Hashtable Enumerator"); 1477 } 1478 1479 // Iterator methods 1480 public boolean hasNext() { 1481 return hasMoreElements(); 1482 } 1483 1484 public T next() { 1485 if (Hashtable.this.modCount != expectedModCount) 1486 throw new ConcurrentModificationException(); 1487 return nextElement(); 1488 } 1489 1490 public void remove() { 1491 if (!iterator) 1492 throw new UnsupportedOperationException(); 1493 if (lastReturned == null) 1494 throw new IllegalStateException("Hashtable Enumerator"); 1495 if (modCount != expectedModCount) 1496 throw new ConcurrentModificationException(); 1497 1498 synchronized(Hashtable.this) { 1499 Entry<?,?>[] tab = Hashtable.this.table; 1500 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 1501 1502 @SuppressWarnings("unchecked") 1503 Entry<K,V> e = (Entry<K,V>)tab[index]; 1504 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1505 if (e == lastReturned) { 1506 if (prev == null) 1507 tab[index] = e.next; 1508 else 1509 prev.next = e.next; 1510 expectedModCount++; 1511 lastReturned = null; 1512 Hashtable.this.modCount++; 1513 Hashtable.this.count--; 1514 return; 1515 } 1516 } 1517 throw new ConcurrentModificationException(); 1518 } 1519 } 1520 } 1521 }