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 * Returns the number of keys in this hashtable. 234 * 235 * @return the number of keys in this hashtable. 236 */ 237 public synchronized int size() { 238 return count; 239 } 240 241 /** 242 * Tests if this hashtable maps no keys to values. 243 * 244 * @return <code>true</code> if this hashtable maps no keys to values; 245 * <code>false</code> otherwise. 246 */ 247 public synchronized boolean isEmpty() { 248 return count == 0; 249 } 250 251 /** 252 * Returns an enumeration of the keys in this hashtable. 253 * Use the Enumeration methods on the returned object to fetch the keys 254 * sequentially. If the hashtable is structurally modified while enumerating 255 * over the keys then the results of enumerating are undefined. 256 * 257 * @return an enumeration of the keys in this hashtable. 258 * @see Enumeration 259 * @see #elements() 260 * @see #keySet() 261 * @see Map 262 */ 263 public synchronized Enumeration<K> keys() { 264 return this.<K>getEnumeration(KEYS); 265 } 266 267 /** 268 * Returns an enumeration of the values in this hashtable. 269 * Use the Enumeration methods on the returned object to fetch the elements 270 * sequentially. If the hashtable is structurally modified while enumerating 271 * over the values then the results of enumerating are undefined. 272 * 273 * @return an enumeration of the values in this hashtable. 274 * @see java.util.Enumeration 275 * @see #keys() 276 * @see #values() 277 * @see Map 278 */ 279 public synchronized Enumeration<V> elements() { 280 return this.<V>getEnumeration(VALUES); 281 } 282 283 /** 284 * Tests if some key maps into the specified value in this hashtable. 285 * This operation is more expensive than the {@link #containsKey 286 * containsKey} method. 287 * 288 * <p>Note that this method is identical in functionality to 289 * {@link #containsValue containsValue}, (which is part of the 290 * {@link Map} interface in the collections framework). 291 * 292 * @param value a value to search for 293 * @return <code>true</code> if and only if some key maps to the 294 * <code>value</code> argument in this hashtable as 295 * determined by the <tt>equals</tt> method; 296 * <code>false</code> otherwise. 297 * @exception NullPointerException if the value is <code>null</code> 298 */ 299 public synchronized boolean contains(Object value) { 300 if (value == null) { 301 throw new NullPointerException(); 302 } 303 304 Entry<?,?> tab[] = table; 305 for (int i = tab.length ; i-- > 0 ;) { 306 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) { 307 if (e.value.equals(value)) { 308 return true; 309 } 310 } 311 } 312 return false; 313 } 314 315 /** 316 * Returns true if this hashtable maps one or more keys to this value. 317 * 318 * <p>Note that this method is identical in functionality to {@link 319 * #contains contains} (which predates the {@link Map} interface). 320 * 321 * @param value value whose presence in this hashtable is to be tested 322 * @return <tt>true</tt> if this map maps one or more keys to the 323 * specified value 324 * @throws NullPointerException if the value is <code>null</code> 325 * @since 1.2 326 */ 327 public boolean containsValue(Object value) { 328 return contains(value); 329 } 330 331 /** 332 * Tests if the specified object is a key in this hashtable. 333 * 334 * @param key possible key 335 * @return <code>true</code> if and only if the specified object 336 * is a key in this hashtable, as determined by the 337 * <tt>equals</tt> method; <code>false</code> otherwise. 338 * @throws NullPointerException if the key is <code>null</code> 339 * @see #contains(Object) 340 */ 341 public synchronized boolean containsKey(Object key) { 342 Entry<?,?> tab[] = table; 343 int hash = key.hashCode(); 344 int index = (hash & 0x7FFFFFFF) % tab.length; 345 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 346 if ((e.hash == hash) && e.key.equals(key)) { 347 return true; 348 } 349 } 350 return false; 351 } 352 353 /** 354 * Returns the value to which the specified key is mapped, 355 * or {@code null} if this map contains no mapping for the key. 356 * 357 * <p>More formally, if this map contains a mapping from a key 358 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 359 * then this method returns {@code v}; otherwise it returns 360 * {@code null}. (There can be at most one such mapping.) 361 * 362 * @param key the key whose associated value is to be returned 363 * @return the value to which the specified key is mapped, or 364 * {@code null} if this map contains no mapping for the key 365 * @throws NullPointerException if the specified key is null 366 * @see #put(Object, Object) 367 */ 368 @SuppressWarnings("unchecked") 369 public synchronized V get(Object key) { 370 Entry<?,?> tab[] = table; 371 int hash = key.hashCode(); 372 int index = (hash & 0x7FFFFFFF) % tab.length; 373 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 374 if ((e.hash == hash) && e.key.equals(key)) { 375 return (V)e.value; 376 } 377 } 378 return null; 379 } 380 381 /** 382 * The maximum size of array to allocate. 383 * Some VMs reserve some header words in an array. 384 * Attempts to allocate larger arrays may result in 385 * OutOfMemoryError: Requested array size exceeds VM limit 386 */ 387 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 388 389 /** 390 * Increases the capacity of and internally reorganizes this 391 * hashtable, in order to accommodate and access its entries more 392 * efficiently. This method is called automatically when the 393 * number of keys in the hashtable exceeds this hashtable's capacity 394 * and load factor. 395 */ 396 @SuppressWarnings("unchecked") 397 protected void rehash() { 398 int oldCapacity = table.length; 399 Entry<?,?>[] oldMap = table; 400 401 // overflow-conscious code 402 int newCapacity = (oldCapacity << 1) + 1; 403 if (newCapacity - MAX_ARRAY_SIZE > 0) { 404 if (oldCapacity == MAX_ARRAY_SIZE) 405 // Keep running with MAX_ARRAY_SIZE buckets 406 return; 407 newCapacity = MAX_ARRAY_SIZE; 408 } 409 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; 410 411 modCount++; 412 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 413 table = newMap; 414 415 for (int i = oldCapacity ; i-- > 0 ;) { 416 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { 417 Entry<K,V> e = old; 418 old = old.next; 419 420 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 421 e.next = (Entry<K,V>)newMap[index]; 422 newMap[index] = e; 423 } 424 } 425 } 426 427 private void addEntry(int hash, K key, V value, int index) { 428 Entry<?,?> tab[] = table; 429 if (count >= threshold) { 430 // Rehash the table if the threshold is exceeded 431 rehash(); 432 433 tab = table; 434 hash = key.hashCode(); 435 index = (hash & 0x7FFFFFFF) % tab.length; 436 } 437 438 // Creates the new entry. 439 @SuppressWarnings("unchecked") 440 Entry<K,V> e = (Entry<K,V>) tab[index]; 441 tab[index] = new Entry<>(hash, key, value, e); 442 count++; 443 modCount++; 444 } 445 446 /** 447 * Maps the specified <code>key</code> to the specified 448 * <code>value</code> in this hashtable. Neither the key nor the 449 * value can be <code>null</code>. <p> 450 * 451 * The value can be retrieved by calling the <code>get</code> method 452 * with a key that is equal to the original key. 453 * 454 * @param key the hashtable key 455 * @param value the value 456 * @return the previous value of the specified key in this hashtable, 457 * or <code>null</code> if it did not have one 458 * @exception NullPointerException if the key or value is 459 * <code>null</code> 460 * @see Object#equals(Object) 461 * @see #get(Object) 462 */ 463 public synchronized V put(K key, V value) { 464 // Make sure the value is not null 465 if (value == null) { 466 throw new NullPointerException(); 467 } 468 469 // Makes sure the key is not already in the hashtable. 470 Entry<?,?> tab[] = table; 471 int hash = key.hashCode(); 472 int index = (hash & 0x7FFFFFFF) % tab.length; 473 @SuppressWarnings("unchecked") 474 Entry<K,V> entry = (Entry<K,V>)tab[index]; 475 for(; entry != null ; entry = entry.next) { 476 if ((entry.hash == hash) && entry.key.equals(key)) { 477 V old = entry.value; 478 entry.value = value; 479 return old; 480 } 481 } 482 483 addEntry(hash, key, value, index); 484 return null; 485 } 486 487 /** 488 * Removes the key (and its corresponding value) from this 489 * hashtable. This method does nothing if the key is not in the hashtable. 490 * 491 * @param key the key that needs to be removed 492 * @return the value to which the key had been mapped in this hashtable, 493 * or <code>null</code> if the key did not have a mapping 494 * @throws NullPointerException if the key is <code>null</code> 495 */ 496 public synchronized V remove(Object key) { 497 Entry<?,?> tab[] = table; 498 int hash = key.hashCode(); 499 int index = (hash & 0x7FFFFFFF) % tab.length; 500 @SuppressWarnings("unchecked") 501 Entry<K,V> e = (Entry<K,V>)tab[index]; 502 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 503 if ((e.hash == hash) && e.key.equals(key)) { 504 if (prev != null) { 505 prev.next = e.next; 506 } else { 507 tab[index] = e.next; 508 } 509 modCount++; 510 count--; 511 V oldValue = e.value; 512 e.value = null; 513 return oldValue; 514 } 515 } 516 return null; 517 } 518 519 /** 520 * Copies all of the mappings from the specified map to this hashtable. 521 * These mappings will replace any mappings that this hashtable had for any 522 * of the keys currently in the specified map. 523 * 524 * @param t mappings to be stored in this map 525 * @throws NullPointerException if the specified map is null 526 * @since 1.2 527 */ 528 public synchronized void putAll(Map<? extends K, ? extends V> t) { 529 for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) 530 put(e.getKey(), e.getValue()); 531 } 532 533 /** 534 * Clears this hashtable so that it contains no keys. 535 */ 536 public synchronized void clear() { 537 Entry<?,?> tab[] = table; 538 for (int index = tab.length; --index >= 0; ) 539 tab[index] = null; 540 modCount++; 541 count = 0; 542 } 543 544 /** 545 * Creates a shallow copy of this hashtable. All the structure of the 546 * hashtable itself is copied, but the keys and values are not cloned. 547 * This is a relatively expensive operation. 548 * 549 * @return a clone of the hashtable 550 */ 551 public synchronized Object clone() { 552 try { 553 Hashtable<?,?> t = (Hashtable<?,?>)super.clone(); 554 t.table = new Entry<?,?>[table.length]; 555 for (int i = table.length ; i-- > 0 ; ) { 556 t.table[i] = (table[i] != null) 557 ? (Entry<?,?>) table[i].clone() : null; 558 } 559 t.keySet = null; 560 t.entrySet = null; 561 t.values = null; 562 t.modCount = 0; 563 return t; 564 } catch (CloneNotSupportedException e) { 565 // this shouldn't happen, since we are Cloneable 566 throw new InternalError(e); 567 } 568 } 569 570 /** 571 * Returns a string representation of this <tt>Hashtable</tt> object 572 * in the form of a set of entries, enclosed in braces and separated 573 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 574 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 575 * associated element, where the <tt>toString</tt> method is used to 576 * convert the key and element to strings. 577 * 578 * @return a string representation of this hashtable 579 */ 580 public synchronized String toString() { 581 int max = size() - 1; 582 if (max == -1) 583 return "{}"; 584 585 StringBuilder sb = new StringBuilder(); 586 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 587 588 sb.append('{'); 589 for (int i = 0; ; i++) { 590 Map.Entry<K,V> e = it.next(); 591 K key = e.getKey(); 592 V value = e.getValue(); 593 sb.append(key == this ? "(this Map)" : key.toString()); 594 sb.append('='); 595 sb.append(value == this ? "(this Map)" : value.toString()); 596 597 if (i == max) 598 return sb.append('}').toString(); 599 sb.append(", "); 600 } 601 } 602 603 604 private <T> Enumeration<T> getEnumeration(int type) { 605 if (count == 0) { 606 return Collections.emptyEnumeration(); 607 } else { 608 return new Enumerator<>(type, false); 609 } 610 } 611 612 private <T> Iterator<T> getIterator(int type) { 613 if (count == 0) { 614 return Collections.emptyIterator(); 615 } else { 616 return new Enumerator<>(type, true); 617 } 618 } 619 620 // Views 621 622 /** 623 * Each of these fields are initialized to contain an instance of the 624 * appropriate view the first time this view is requested. The views are 625 * stateless, so there's no reason to create more than one of each. 626 */ 627 private transient volatile Set<K> keySet; 628 private transient volatile Set<Map.Entry<K,V>> entrySet; 629 private transient volatile Collection<V> values; 630 631 /** 632 * Returns a {@link Set} view of the keys contained in this map. 633 * The set is backed by the map, so changes to the map are 634 * reflected in the set, and vice-versa. If the map is modified 635 * while an iteration over the set is in progress (except through 636 * the iterator's own <tt>remove</tt> operation), the results of 637 * the iteration are undefined. The set supports element removal, 638 * which removes the corresponding mapping from the map, via the 639 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 640 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 641 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 642 * operations. 643 * 644 * @since 1.2 645 */ 646 public Set<K> keySet() { 647 if (keySet == null) 648 keySet = Collections.synchronizedSet(new KeySet(), this); 649 return keySet; 650 } 651 652 private class KeySet extends AbstractSet<K> { 653 public Iterator<K> iterator() { 654 return getIterator(KEYS); 655 } 656 public int size() { 657 return count; 658 } 659 public boolean contains(Object o) { 660 return containsKey(o); 661 } 662 public boolean remove(Object o) { 663 return Hashtable.this.remove(o) != null; 664 } 665 public void clear() { 666 Hashtable.this.clear(); 667 } 668 } 669 670 /** 671 * Returns a {@link Set} view of the mappings contained in this map. 672 * The set is backed by the map, so changes to the map are 673 * reflected in the set, and vice-versa. If the map is modified 674 * while an iteration over the set is in progress (except through 675 * the iterator's own <tt>remove</tt> operation, or through the 676 * <tt>setValue</tt> operation on a map entry returned by the 677 * iterator) the results of the iteration are undefined. The set 678 * supports element removal, which removes the corresponding 679 * mapping from the map, via the <tt>Iterator.remove</tt>, 680 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 681 * <tt>clear</tt> operations. It does not support the 682 * <tt>add</tt> or <tt>addAll</tt> operations. 683 * 684 * @since 1.2 685 */ 686 public Set<Map.Entry<K,V>> entrySet() { 687 if (entrySet==null) 688 entrySet = Collections.synchronizedSet(new EntrySet(), this); 689 return entrySet; 690 } 691 692 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 693 public Iterator<Map.Entry<K,V>> iterator() { 694 return getIterator(ENTRIES); 695 } 696 697 public boolean add(Map.Entry<K,V> o) { 698 return super.add(o); 699 } 700 701 public boolean contains(Object o) { 702 if (!(o instanceof Map.Entry)) 703 return false; 704 Map.Entry<?,?> entry = (Map.Entry<?,?>)o; 705 Object key = entry.getKey(); 706 Entry<?,?>[] tab = table; 707 int hash = key.hashCode(); 708 int index = (hash & 0x7FFFFFFF) % tab.length; 709 710 for (Entry<?,?> e = tab[index]; e != null; e = e.next) 711 if (e.hash==hash && e.equals(entry)) 712 return true; 713 return false; 714 } 715 716 public boolean remove(Object o) { 717 if (!(o instanceof Map.Entry)) 718 return false; 719 Map.Entry<?,?> entry = (Map.Entry<?,?>) o; 720 Object key = entry.getKey(); 721 Entry<?,?>[] tab = table; 722 int hash = key.hashCode(); 723 int index = (hash & 0x7FFFFFFF) % tab.length; 724 725 @SuppressWarnings("unchecked") 726 Entry<K,V> e = (Entry<K,V>)tab[index]; 727 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 728 if (e.hash==hash && e.equals(entry)) { 729 if (prev != null) 730 prev.next = e.next; 731 else 732 tab[index] = e.next; 733 734 e.value = null; // clear for gc. 735 modCount++; 736 count--; 737 return true; 738 } 739 } 740 return false; 741 } 742 743 public int size() { 744 return count; 745 } 746 747 public void clear() { 748 Hashtable.this.clear(); 749 } 750 } 751 752 /** 753 * Returns a {@link Collection} view of the values contained in this map. 754 * The collection is backed by the map, so changes to the map are 755 * reflected in the collection, and vice-versa. If the map is 756 * modified while an iteration over the collection is in progress 757 * (except through the iterator's own <tt>remove</tt> operation), 758 * the results of the iteration are undefined. The collection 759 * supports element removal, which removes the corresponding 760 * mapping from the map, via the <tt>Iterator.remove</tt>, 761 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 762 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 763 * support the <tt>add</tt> or <tt>addAll</tt> operations. 764 * 765 * @since 1.2 766 */ 767 public Collection<V> values() { 768 if (values==null) 769 values = Collections.synchronizedCollection(new ValueCollection(), 770 this); 771 return values; 772 } 773 774 private class ValueCollection extends AbstractCollection<V> { 775 public Iterator<V> iterator() { 776 return getIterator(VALUES); 777 } 778 public int size() { 779 return count; 780 } 781 public boolean contains(Object o) { 782 return containsValue(o); 783 } 784 public void clear() { 785 Hashtable.this.clear(); 786 } 787 } 788 789 // Comparison and hashing 790 791 /** 792 * Compares the specified Object with this Map for equality, 793 * as per the definition in the Map interface. 794 * 795 * @param o object to be compared for equality with this hashtable 796 * @return true if the specified Object is equal to this Map 797 * @see Map#equals(Object) 798 * @since 1.2 799 */ 800 public synchronized boolean equals(Object o) { 801 if (o == this) 802 return true; 803 804 if (!(o instanceof Map)) 805 return false; 806 Map<?,?> t = (Map<?,?>) o; 807 if (t.size() != size()) 808 return false; 809 810 try { 811 for (Map.Entry<K, V> e : entrySet()) { 812 K key = e.getKey(); 813 V value = e.getValue(); 814 if (value == null) { 815 if (!(t.get(key) == null && t.containsKey(key))) 816 return false; 817 } else { 818 if (!value.equals(t.get(key))) 819 return false; 820 } 821 } 822 } catch (ClassCastException unused) { 823 return false; 824 } catch (NullPointerException unused) { 825 return false; 826 } 827 828 return true; 829 } 830 831 /** 832 * Returns the hash code value for this Map as per the definition in the 833 * Map interface. 834 * 835 * @see Map#hashCode() 836 * @since 1.2 837 */ 838 public synchronized int hashCode() { 839 /* 840 * This code detects the recursion caused by computing the hash code 841 * of a self-referential hash table and prevents the stack overflow 842 * that would otherwise result. This allows certain 1.1-era 843 * applets with self-referential hash tables to work. This code 844 * abuses the loadFactor field to do double-duty as a hashCode 845 * in progress flag, so as not to worsen the space performance. 846 * A negative load factor indicates that hash code computation is 847 * in progress. 848 */ 849 int h = 0; 850 if (count == 0 || loadFactor < 0) 851 return h; // Returns zero 852 853 loadFactor = -loadFactor; // Mark hashCode computation in progress 854 Entry<?,?>[] tab = table; 855 for (Entry<?,?> entry : tab) { 856 while (entry != null) { 857 h += entry.hashCode(); 858 entry = entry.next; 859 } 860 } 861 862 loadFactor = -loadFactor; // Mark hashCode computation complete 863 864 return h; 865 } 866 867 @Override 868 public synchronized V getOrDefault(Object key, V defaultValue) { 869 V result = get(key); 870 return (null == result) ? defaultValue : result; 871 } 872 873 @SuppressWarnings("unchecked") 874 @Override 875 public synchronized void forEach(BiConsumer<? super K, ? super V> action) { 876 Objects.requireNonNull(action); // explicit check required in case 877 // table is empty. 878 final int expectedModCount = modCount; 879 880 Entry<?, ?>[] tab = table; 881 for (Entry<?, ?> entry : tab) { 882 while (entry != null) { 883 action.accept((K)entry.key, (V)entry.value); 884 entry = entry.next; 885 886 if (expectedModCount != modCount) { 887 throw new ConcurrentModificationException(); 888 } 889 } 890 } 891 } 892 893 @SuppressWarnings("unchecked") 894 @Override 895 public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 896 Objects.requireNonNull(function); // explicit check required in case 897 // table is empty. 898 final int expectedModCount = modCount; 899 900 Entry<K, V>[] tab = (Entry<K, V>[])table; 901 for (Entry<K, V> entry : tab) { 902 while (entry != null) { 903 entry.value = Objects.requireNonNull( 904 function.apply(entry.key, entry.value)); 905 entry = entry.next; 906 907 if (expectedModCount != modCount) { 908 throw new ConcurrentModificationException(); 909 } 910 } 911 } 912 } 913 914 @Override 915 public synchronized V putIfAbsent(K key, V value) { 916 Objects.requireNonNull(value); 917 918 // Makes sure the key is not already in the hashtable. 919 Entry<?,?> tab[] = table; 920 int hash = key.hashCode(); 921 int index = (hash & 0x7FFFFFFF) % tab.length; 922 @SuppressWarnings("unchecked") 923 Entry<K,V> entry = (Entry<K,V>)tab[index]; 924 for (; entry != null; entry = entry.next) { 925 if ((entry.hash == hash) && entry.key.equals(key)) { 926 V old = entry.value; 927 if (old == null) { 928 entry.value = value; 929 } 930 return old; 931 } 932 } 933 934 addEntry(hash, key, value, index); 935 return null; 936 } 937 938 @Override 939 public synchronized boolean remove(Object key, Object value) { 940 Objects.requireNonNull(value); 941 942 Entry<?,?> tab[] = table; 943 int hash = key.hashCode(); 944 int index = (hash & 0x7FFFFFFF) % tab.length; 945 @SuppressWarnings("unchecked") 946 Entry<K,V> e = (Entry<K,V>)tab[index]; 947 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 948 if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) { 949 if (prev != null) { 950 prev.next = e.next; 951 } else { 952 tab[index] = e.next; 953 } 954 e.value = null; // clear for gc 955 modCount++; 956 count--; 957 return true; 958 } 959 } 960 return false; 961 } 962 963 @Override 964 public synchronized boolean replace(K key, V oldValue, V newValue) { 965 Objects.requireNonNull(oldValue); 966 Objects.requireNonNull(newValue); 967 Entry<?,?> tab[] = table; 968 int hash = key.hashCode(); 969 int index = (hash & 0x7FFFFFFF) % tab.length; 970 @SuppressWarnings("unchecked") 971 Entry<K,V> e = (Entry<K,V>)tab[index]; 972 for (; e != null; e = e.next) { 973 if ((e.hash == hash) && e.key.equals(key)) { 974 if (e.value.equals(oldValue)) { 975 e.value = newValue; 976 return true; 977 } else { 978 return false; 979 } 980 } 981 } 982 return false; 983 } 984 985 @Override 986 public synchronized V replace(K key, V value) { 987 Objects.requireNonNull(value); 988 Entry<?,?> tab[] = table; 989 int hash = key.hashCode(); 990 int index = (hash & 0x7FFFFFFF) % tab.length; 991 @SuppressWarnings("unchecked") 992 Entry<K,V> e = (Entry<K,V>)tab[index]; 993 for (; e != null; e = e.next) { 994 if ((e.hash == hash) && e.key.equals(key)) { 995 V oldValue = e.value; 996 e.value = value; 997 return oldValue; 998 } 999 } 1000 return null; 1001 } 1002 1003 /** 1004 * {@inheritDoc} 1005 * 1006 * <p>This method will, on a best-effort basis, throw a 1007 * {@link java.util.ConcurrentModificationException} if the mapping 1008 * function modified this map during computation. 1009 * 1010 * @throws ConcurrentModificationException if it is detected that the 1011 * mapping function modified this map 1012 */ 1013 @Override 1014 public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 1015 Objects.requireNonNull(mappingFunction); 1016 1017 Entry<?,?> tab[] = table; 1018 int hash = key.hashCode(); 1019 int index = (hash & 0x7FFFFFFF) % tab.length; 1020 @SuppressWarnings("unchecked") 1021 Entry<K,V> e = (Entry<K,V>)tab[index]; 1022 for (; e != null; e = e.next) { 1023 if (e.hash == hash && e.key.equals(key)) { 1024 // Hashtable not accept null value 1025 return e.value; 1026 } 1027 } 1028 1029 int mc = modCount; 1030 V newValue = mappingFunction.apply(key); 1031 if (mc != modCount) { throw new ConcurrentModificationException(); } 1032 if (newValue != null) { 1033 addEntry(hash, key, newValue, index); 1034 } 1035 1036 return newValue; 1037 } 1038 1039 /** 1040 * {@inheritDoc} 1041 * 1042 * <p>This method will, on a best-effort basis, throw a 1043 * {@link java.util.ConcurrentModificationException} if the remapping 1044 * function modified this map during computation. 1045 * 1046 * @throws ConcurrentModificationException if it is detected that the 1047 * remapping function modified this map 1048 */ 1049 @Override 1050 public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1051 Objects.requireNonNull(remappingFunction); 1052 1053 Entry<?,?> tab[] = table; 1054 int hash = key.hashCode(); 1055 int index = (hash & 0x7FFFFFFF) % tab.length; 1056 @SuppressWarnings("unchecked") 1057 Entry<K,V> e = (Entry<K,V>)tab[index]; 1058 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1059 if (e.hash == hash && e.key.equals(key)) { 1060 int mc = modCount; 1061 V newValue = remappingFunction.apply(key, e.value); 1062 if (mc != modCount) { 1063 throw new ConcurrentModificationException(); 1064 } 1065 if (newValue == null) { 1066 if (prev != null) { 1067 prev.next = e.next; 1068 } else { 1069 tab[index] = e.next; 1070 } 1071 modCount = mc + 1; 1072 count--; 1073 } else { 1074 e.value = newValue; 1075 } 1076 return newValue; 1077 } 1078 } 1079 return null; 1080 } 1081 /** 1082 * {@inheritDoc} 1083 * 1084 * <p>This method will, on a best-effort basis, throw a 1085 * {@link java.util.ConcurrentModificationException} if the remapping 1086 * function modified this map during computation. 1087 * 1088 * @throws ConcurrentModificationException if it is detected that the 1089 * remapping function modified this map 1090 */ 1091 @Override 1092 public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1093 Objects.requireNonNull(remappingFunction); 1094 1095 Entry<?,?> tab[] = table; 1096 int hash = key.hashCode(); 1097 int index = (hash & 0x7FFFFFFF) % tab.length; 1098 @SuppressWarnings("unchecked") 1099 Entry<K,V> e = (Entry<K,V>)tab[index]; 1100 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1101 if (e.hash == hash && Objects.equals(e.key, key)) { 1102 int mc = modCount; 1103 V newValue = remappingFunction.apply(key, e.value); 1104 if (mc != modCount) { 1105 throw new ConcurrentModificationException(); 1106 } 1107 if (newValue == null) { 1108 if (prev != null) { 1109 prev.next = e.next; 1110 } else { 1111 tab[index] = e.next; 1112 } 1113 modCount = mc + 1; 1114 count--; 1115 } else { 1116 e.value = newValue; 1117 } 1118 return newValue; 1119 } 1120 } 1121 1122 int mc = modCount; 1123 V newValue = remappingFunction.apply(key, null); 1124 if (mc != modCount) { throw new ConcurrentModificationException(); } 1125 if (newValue != null) { 1126 addEntry(hash, key, newValue, index); 1127 } 1128 1129 return newValue; 1130 } 1131 1132 /** 1133 * {@inheritDoc} 1134 * 1135 * <p>This method will, on a best-effort basis, throw a 1136 * {@link java.util.ConcurrentModificationException} if the remapping 1137 * function modified this map during computation. 1138 * 1139 * @throws ConcurrentModificationException if it is detected that the 1140 * remapping function modified this map 1141 */ 1142 @Override 1143 public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1144 Objects.requireNonNull(remappingFunction); 1145 1146 Entry<?,?> tab[] = table; 1147 int hash = key.hashCode(); 1148 int index = (hash & 0x7FFFFFFF) % tab.length; 1149 @SuppressWarnings("unchecked") 1150 Entry<K,V> e = (Entry<K,V>)tab[index]; 1151 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1152 if (e.hash == hash && e.key.equals(key)) { 1153 int mc = modCount; 1154 V newValue = remappingFunction.apply(e.value, value); 1155 if (mc != modCount) { 1156 throw new ConcurrentModificationException(); 1157 } 1158 if (newValue == null) { 1159 if (prev != null) { 1160 prev.next = e.next; 1161 } else { 1162 tab[index] = e.next; 1163 } 1164 modCount = mc + 1; 1165 count--; 1166 } else { 1167 e.value = newValue; 1168 } 1169 return newValue; 1170 } 1171 } 1172 1173 if (value != null) { 1174 addEntry(hash, key, value, index); 1175 } 1176 1177 return value; 1178 } 1179 1180 /** 1181 * Save the state of the Hashtable to a stream (i.e., serialize it). 1182 * 1183 * @serialData The <i>capacity</i> of the Hashtable (the length of the 1184 * bucket array) is emitted (int), followed by the 1185 * <i>size</i> of the Hashtable (the number of key-value 1186 * mappings), followed by the key (Object) and value (Object) 1187 * for each key-value mapping represented by the Hashtable 1188 * The key-value mappings are emitted in no particular order. 1189 */ 1190 private void writeObject(java.io.ObjectOutputStream s) 1191 throws IOException { 1192 Entry<Object, Object> entryStack = null; 1193 1194 synchronized (this) { 1195 // Write out the threshold and loadFactor 1196 s.defaultWriteObject(); 1197 1198 // Write out the length and count of elements 1199 s.writeInt(table.length); 1200 s.writeInt(count); 1201 1202 // Stack copies of the entries in the table 1203 for (Entry<?, ?> entry : table) { 1204 1205 while (entry != null) { 1206 entryStack = 1207 new Entry<>(0, entry.key, entry.value, entryStack); 1208 entry = entry.next; 1209 } 1210 } 1211 } 1212 1213 // Write out the key/value objects from the stacked entries 1214 while (entryStack != null) { 1215 s.writeObject(entryStack.key); 1216 s.writeObject(entryStack.value); 1217 entryStack = entryStack.next; 1218 } 1219 } 1220 1221 /** 1222 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 1223 */ 1224 private void readObject(java.io.ObjectInputStream s) 1225 throws IOException, ClassNotFoundException 1226 { 1227 // Read in the threshold and loadFactor 1228 s.defaultReadObject(); 1229 1230 // Validate loadFactor (ignore threshold - it will be re-computed) 1231 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 1232 throw new StreamCorruptedException("Illegal Load: " + loadFactor); 1233 1234 // Read the original length of the array and number of elements 1235 int origlength = s.readInt(); 1236 int elements = s.readInt(); 1237 1238 // Validate # of elements 1239 if (elements < 0) 1240 throw new StreamCorruptedException("Illegal # of Elements: " + elements); 1241 1242 // Clamp original length to be more than elements / loadFactor 1243 // (this is the invariant enforced with auto-growth) 1244 origlength = Math.max(origlength, (int)(elements / loadFactor) + 1); 1245 1246 // Compute new length with a bit of room 5% + 3 to grow but 1247 // no larger than the clamped original length. Make the length 1248 // odd if it's large enough, this helps distribute the entries. 1249 // Guard against the length ending up zero, that's not valid. 1250 int length = (int)((elements + elements / 20) / loadFactor) + 3; 1251 if (length > elements && (length & 1) == 0) 1252 length--; 1253 length = Math.min(length, origlength); 1254 table = new Entry<?,?>[length]; 1255 threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1); 1256 count = 0; 1257 1258 // Read the number of elements and then all the key/value objects 1259 for (; elements > 0; elements--) { 1260 @SuppressWarnings("unchecked") 1261 K key = (K)s.readObject(); 1262 @SuppressWarnings("unchecked") 1263 V value = (V)s.readObject(); 1264 // sync is eliminated for performance 1265 reconstitutionPut(table, key, value); 1266 } 1267 } 1268 1269 /** 1270 * The put method used by readObject. This is provided because put 1271 * is overridable and should not be called in readObject since the 1272 * subclass will not yet be initialized. 1273 * 1274 * <p>This differs from the regular put method in several ways. No 1275 * checking for rehashing is necessary since the number of elements 1276 * initially in the table is known. The modCount is not incremented and 1277 * there's no synchronization because we are creating a new instance. 1278 * Also, no return value is needed. 1279 */ 1280 private void reconstitutionPut(Entry<?,?>[] tab, K key, V value) 1281 throws StreamCorruptedException 1282 { 1283 if (value == null) { 1284 throw new java.io.StreamCorruptedException(); 1285 } 1286 // Makes sure the key is not already in the hashtable. 1287 // This should not happen in deserialized version. 1288 int hash = key.hashCode(); 1289 int index = (hash & 0x7FFFFFFF) % tab.length; 1290 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 1291 if ((e.hash == hash) && e.key.equals(key)) { 1292 throw new java.io.StreamCorruptedException(); 1293 } 1294 } 1295 // Creates the new entry. 1296 @SuppressWarnings("unchecked") 1297 Entry<K,V> e = (Entry<K,V>)tab[index]; 1298 tab[index] = new Entry<>(hash, key, value, e); 1299 count++; 1300 } 1301 1302 /** 1303 * Hashtable bucket collision list entry 1304 */ 1305 private static class Entry<K,V> implements Map.Entry<K,V> { 1306 final int hash; 1307 final K key; 1308 V value; 1309 Entry<K,V> next; 1310 1311 protected Entry(int hash, K key, V value, Entry<K,V> next) { 1312 this.hash = hash; 1313 this.key = key; 1314 this.value = value; 1315 this.next = next; 1316 } 1317 1318 @SuppressWarnings("unchecked") 1319 protected Object clone() { 1320 return new Entry<>(hash, key, value, 1321 (next==null ? null : (Entry<K,V>) next.clone())); 1322 } 1323 1324 // Map.Entry Ops 1325 1326 public K getKey() { 1327 return key; 1328 } 1329 1330 public V getValue() { 1331 return value; 1332 } 1333 1334 public V setValue(V value) { 1335 if (value == null) 1336 throw new NullPointerException(); 1337 1338 V oldValue = this.value; 1339 this.value = value; 1340 return oldValue; 1341 } 1342 1343 public boolean equals(Object o) { 1344 if (!(o instanceof Map.Entry)) 1345 return false; 1346 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1347 1348 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 1349 (value==null ? e.getValue()==null : value.equals(e.getValue())); 1350 } 1351 1352 public int hashCode() { 1353 return hash ^ Objects.hashCode(value); 1354 } 1355 1356 public String toString() { 1357 return key.toString()+"="+value.toString(); 1358 } 1359 } 1360 1361 // Types of Enumerations/Iterations 1362 private static final int KEYS = 0; 1363 private static final int VALUES = 1; 1364 private static final int ENTRIES = 2; 1365 1366 /** 1367 * A hashtable enumerator class. This class implements both the 1368 * Enumeration and Iterator interfaces, but individual instances 1369 * can be created with the Iterator methods disabled. This is necessary 1370 * to avoid unintentionally increasing the capabilities granted a user 1371 * by passing an Enumeration. 1372 */ 1373 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { 1374 final Entry<?,?>[] table = Hashtable.this.table; 1375 int index = table.length; 1376 Entry<?,?> entry; 1377 Entry<?,?> lastReturned; 1378 final int type; 1379 1380 /** 1381 * Indicates whether this Enumerator is serving as an Iterator 1382 * or an Enumeration. (true -> Iterator). 1383 */ 1384 final boolean iterator; 1385 1386 /** 1387 * The modCount value that the iterator believes that the backing 1388 * Hashtable should have. If this expectation is violated, the iterator 1389 * has detected concurrent modification. 1390 */ 1391 protected int expectedModCount = Hashtable.this.modCount; 1392 1393 Enumerator(int type, boolean iterator) { 1394 this.type = type; 1395 this.iterator = iterator; 1396 } 1397 1398 public boolean hasMoreElements() { 1399 Entry<?,?> e = entry; 1400 int i = index; 1401 Entry<?,?>[] t = table; 1402 /* Use locals for faster loop iteration */ 1403 while (e == null && i > 0) { 1404 e = t[--i]; 1405 } 1406 entry = e; 1407 index = i; 1408 return e != null; 1409 } 1410 1411 @SuppressWarnings("unchecked") 1412 public T nextElement() { 1413 Entry<?,?> et = entry; 1414 int i = index; 1415 Entry<?,?>[] t = table; 1416 /* Use locals for faster loop iteration */ 1417 while (et == null && i > 0) { 1418 et = t[--i]; 1419 } 1420 entry = et; 1421 index = i; 1422 if (et != null) { 1423 Entry<?,?> e = lastReturned = entry; 1424 entry = e.next; 1425 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e); 1426 } 1427 throw new NoSuchElementException("Hashtable Enumerator"); 1428 } 1429 1430 // Iterator methods 1431 public boolean hasNext() { 1432 return hasMoreElements(); 1433 } 1434 1435 public T next() { 1436 if (Hashtable.this.modCount != expectedModCount) 1437 throw new ConcurrentModificationException(); 1438 return nextElement(); 1439 } 1440 1441 public void remove() { 1442 if (!iterator) 1443 throw new UnsupportedOperationException(); 1444 if (lastReturned == null) 1445 throw new IllegalStateException("Hashtable Enumerator"); 1446 if (modCount != expectedModCount) 1447 throw new ConcurrentModificationException(); 1448 1449 synchronized(Hashtable.this) { 1450 Entry<?,?>[] tab = Hashtable.this.table; 1451 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 1452 1453 @SuppressWarnings("unchecked") 1454 Entry<K,V> e = (Entry<K,V>)tab[index]; 1455 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) { 1456 if (e == lastReturned) { 1457 if (prev == null) 1458 tab[index] = e.next; 1459 else 1460 prev.next = e.next; 1461 expectedModCount++; 1462 lastReturned = null; 1463 Hashtable.this.modCount++; 1464 Hashtable.this.count--; 1465 return; 1466 } 1467 } 1468 throw new ConcurrentModificationException(); 1469 } 1470 } 1471 } 1472 }