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