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