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