1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package java.util; 19 20 import java.io.IOException; 21 import java.io.InvalidObjectException; 22 import java.io.ObjectInputStream; 23 import java.io.ObjectOutputStream; 24 import java.io.ObjectStreamField; 25 import java.io.Serializable; 26 27 /** 28 * Hashtable is a synchronized implementation of {@link Map}. All optional operations are supported. 29 * 30 * <p>Neither keys nor values can be null. (Use {@code HashMap} or {@code LinkedHashMap} if you 31 * need null keys or values.) 32 * 33 * @param <K> the type of keys maintained by this map 34 * @param <V> the type of mapped values 35 * @see HashMap 36 */ 37 public class Hashtable<K, V> extends Dictionary<K, V> 38 implements Map<K, V>, Cloneable, Serializable { 39 /** 40 * Min capacity (other than zero) for a Hashtable. Must be a power of two 41 * greater than 1 (and less than 1 << 30). 42 */ 43 private static final int MINIMUM_CAPACITY = 4; 44 45 /** 46 * Max capacity for a Hashtable. Must be a power of two >= MINIMUM_CAPACITY. 47 */ 48 private static final int MAXIMUM_CAPACITY = 1 << 30; 49 50 /** 51 * An empty table shared by all zero-capacity maps (typically from default 52 * constructor). It is never written to, and replaced on first put. Its size 53 * is set to half the minimum, so that the first resize will create a 54 * minimum-sized table. 55 */ 56 private static final Entry[] EMPTY_TABLE 57 = new HashtableEntry[MINIMUM_CAPACITY >>> 1]; 58 59 /** 60 * The default load factor. Note that this implementation ignores the 61 * load factor, but cannot do away with it entirely because it's 62 * mentioned in the API. 63 * 64 * <p>Note that this constant has no impact on the behavior of the program, 65 * but it is emitted as part of the serialized form. The load factor of 66 * .75 is hardwired into the program, which uses cheap shifts in place of 67 * expensive division. 68 */ 69 private static final float DEFAULT_LOAD_FACTOR = .75F; 70 71 /** 72 * The hash table. 73 */ 74 private transient HashtableEntry<K, V>[] table; 75 76 /** 77 * The number of mappings in this hash map. 78 */ 79 private transient int size; 80 81 /** 82 * Incremented by "structural modifications" to allow (best effort) 83 * detection of concurrent modification. 84 */ 85 private transient int modCount; 86 87 /** 88 * The table is rehashed when its size exceeds this threshold. 89 * The value of this field is generally .75 * capacity, except when 90 * the capacity is zero, as described in the EMPTY_TABLE declaration 91 * above. 92 */ 93 private transient int threshold; 94 95 // Views - lazily initialized 96 private transient Set<K> keySet; 97 private transient Set<Entry<K, V>> entrySet; 98 private transient Collection<V> values; 99 100 /** 101 * Constructs a new {@code Hashtable} using the default capacity and load 102 * factor. 103 */ 104 @SuppressWarnings("unchecked") Hashtable()105 public Hashtable() { 106 table = (HashtableEntry<K, V>[]) EMPTY_TABLE; 107 threshold = -1; // Forces first put invocation to replace EMPTY_TABLE 108 } 109 110 /** 111 * Constructs a new {@code Hashtable} using the specified capacity and the 112 * default load factor. 113 * 114 * @param capacity 115 * the initial capacity. 116 */ Hashtable(int capacity)117 public Hashtable(int capacity) { 118 if (capacity < 0) { 119 throw new IllegalArgumentException("Capacity: " + capacity); 120 } 121 122 if (capacity == 0) { 123 @SuppressWarnings("unchecked") 124 HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[]) EMPTY_TABLE; 125 table = tab; 126 threshold = -1; // Forces first put() to replace EMPTY_TABLE 127 return; 128 } 129 130 if (capacity < MINIMUM_CAPACITY) { 131 capacity = MINIMUM_CAPACITY; 132 } else if (capacity > MAXIMUM_CAPACITY) { 133 capacity = MAXIMUM_CAPACITY; 134 } else { 135 capacity = Collections.roundUpToPowerOfTwo(capacity); 136 } 137 makeTable(capacity); 138 } 139 140 /** 141 * Constructs a new {@code Hashtable} using the specified capacity and load 142 * factor. 143 * 144 * @param capacity 145 * the initial capacity. 146 * @param loadFactor 147 * the initial load factor. 148 */ Hashtable(int capacity, float loadFactor)149 public Hashtable(int capacity, float loadFactor) { 150 this(capacity); 151 152 if (loadFactor <= 0 || Float.isNaN(loadFactor)) { 153 throw new IllegalArgumentException("Load factor: " + loadFactor); 154 } 155 156 /* 157 * Note that this implementation ignores loadFactor; it always uses 158 * a load factor of 3/4. This simplifies the code and generally 159 * improves performance. 160 */ 161 } 162 163 /** 164 * Constructs a new instance of {@code Hashtable} containing the mappings 165 * from the specified map. 166 * 167 * @param map 168 * the mappings to add. 169 */ Hashtable(Map<? extends K, ? extends V> map)170 public Hashtable(Map<? extends K, ? extends V> map) { 171 this(capacityForInitSize(map.size())); 172 constructorPutAll(map); 173 } 174 175 /** 176 * Inserts all of the elements of map into this Hashtable in a manner 177 * suitable for use by constructors and pseudo-constructors (i.e., clone, 178 * readObject). 179 */ constructorPutAll(Map<? extends K, ? extends V> map)180 private void constructorPutAll(Map<? extends K, ? extends V> map) { 181 if (table == EMPTY_TABLE) { 182 doubleCapacity(); // Don't do unchecked puts to a shared table. 183 } 184 for (Entry<? extends K, ? extends V> e : map.entrySet()) { 185 constructorPut(e.getKey(), e.getValue()); 186 } 187 } 188 189 /** 190 * Returns an appropriate capacity for the specified initial size. Does 191 * not round the result up to a power of two; the caller must do this! 192 * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). 193 */ capacityForInitSize(int size)194 private static int capacityForInitSize(int size) { 195 int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth 196 197 // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY 198 return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; 199 } 200 201 /** 202 * Returns a new {@code Hashtable} with the same key/value pairs, capacity 203 * and load factor. 204 * 205 * @return a shallow copy of this {@code Hashtable}. 206 * @see java.lang.Cloneable 207 */ 208 @SuppressWarnings("unchecked") clone()209 @Override public synchronized Object clone() { 210 /* 211 * This could be made more efficient. It unnecessarily hashes all of 212 * the elements in the map. 213 */ 214 Hashtable<K, V> result; 215 try { 216 result = (Hashtable<K, V>) super.clone(); 217 } catch (CloneNotSupportedException e) { 218 throw new AssertionError(e); 219 } 220 221 // Restore clone to empty state, retaining our capacity and threshold 222 result.makeTable(table.length); 223 result.size = 0; 224 result.keySet = null; 225 result.entrySet = null; 226 result.values = null; 227 228 result.constructorPutAll(this); 229 return result; 230 } 231 232 /** 233 * Returns true if this {@code Hashtable} has no key/value pairs. 234 * 235 * @return {@code true} if this {@code Hashtable} has no key/value pairs, 236 * {@code false} otherwise. 237 * @see #size 238 */ isEmpty()239 public synchronized boolean isEmpty() { 240 return size == 0; 241 } 242 243 /** 244 * Returns the number of key/value pairs in this {@code Hashtable}. 245 * 246 * @return the number of key/value pairs in this {@code Hashtable}. 247 * @see #elements 248 * @see #keys 249 */ size()250 public synchronized int size() { 251 return size; 252 } 253 254 /** 255 * Returns the value associated with the specified key in this 256 * {@code Hashtable}. 257 * 258 * @param key 259 * the key of the value returned. 260 * @return the value associated with the specified key, or {@code null} if 261 * the specified key does not exist. 262 * @see #put 263 */ get(Object key)264 public synchronized V get(Object key) { 265 int hash = Collections.secondaryHash(key); 266 HashtableEntry<K, V>[] tab = table; 267 for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 268 e != null; e = e.next) { 269 K eKey = e.key; 270 if (eKey == key || (e.hash == hash && key.equals(eKey))) { 271 return e.value; 272 } 273 } 274 return null; 275 } 276 277 /** 278 * Returns true if this {@code Hashtable} contains the specified object as a 279 * key of one of the key/value pairs. 280 * 281 * @param key 282 * the object to look for as a key in this {@code Hashtable}. 283 * @return {@code true} if object is a key in this {@code Hashtable}, 284 * {@code false} otherwise. 285 * @see #contains 286 * @see java.lang.Object#equals 287 */ containsKey(Object key)288 public synchronized boolean containsKey(Object key) { 289 int hash = Collections.secondaryHash(key); 290 HashtableEntry<K, V>[] tab = table; 291 for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 292 e != null; e = e.next) { 293 K eKey = e.key; 294 if (eKey == key || (e.hash == hash && key.equals(eKey))) { 295 return true; 296 } 297 } 298 return false; 299 } 300 301 /** 302 * Searches this {@code Hashtable} for the specified value. 303 * 304 * @param value 305 * the object to search for. 306 * @return {@code true} if {@code value} is a value of this 307 * {@code Hashtable}, {@code false} otherwise. 308 */ containsValue(Object value)309 public synchronized boolean containsValue(Object value) { 310 if (value == null) { 311 throw new NullPointerException("value == null"); 312 } 313 314 HashtableEntry[] tab = table; 315 int len = tab.length; 316 317 for (int i = 0; i < len; i++) { 318 for (HashtableEntry e = tab[i]; e != null; e = e.next) { 319 if (value.equals(e.value)) { 320 return true; 321 } 322 } 323 } 324 return false; 325 } 326 327 /** 328 * Returns true if this {@code Hashtable} contains the specified object as 329 * the value of at least one of the key/value pairs. 330 * 331 * @param value 332 * the object to look for as a value in this {@code Hashtable}. 333 * @return {@code true} if object is a value in this {@code Hashtable}, 334 * {@code false} otherwise. 335 * @see #containsKey 336 * @see java.lang.Object#equals 337 */ contains(Object value)338 public boolean contains(Object value) { 339 return containsValue(value); 340 } 341 342 /** 343 * Associate the specified value with the specified key in this 344 * {@code Hashtable}. If the key already exists, the old value is replaced. 345 * The key and value cannot be null. 346 * 347 * @param key 348 * the key to add. 349 * @param value 350 * the value to add. 351 * @return the old value associated with the specified key, or {@code null} 352 * if the key did not exist. 353 * @see #elements 354 * @see #get 355 * @see #keys 356 * @see java.lang.Object#equals 357 */ put(K key, V value)358 public synchronized V put(K key, V value) { 359 if (key == null) { 360 throw new NullPointerException("key == null"); 361 } else if (value == null) { 362 throw new NullPointerException("value == null"); 363 } 364 int hash = Collections.secondaryHash(key); 365 HashtableEntry<K, V>[] tab = table; 366 int index = hash & (tab.length - 1); 367 HashtableEntry<K, V> first = tab[index]; 368 for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 369 if (e.hash == hash && key.equals(e.key)) { 370 V oldValue = e.value; 371 e.value = value; 372 return oldValue; 373 } 374 } 375 376 // No entry for key is present; create one 377 modCount++; 378 if (size++ > threshold) { 379 rehash(); // Does nothing!! 380 tab = doubleCapacity(); 381 index = hash & (tab.length - 1); 382 first = tab[index]; 383 } 384 tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 385 return null; 386 } 387 388 /** 389 * This method is just like put, except that it doesn't do things that 390 * are inappropriate or unnecessary for constructors and pseudo-constructors 391 * (i.e., clone, readObject). In particular, this method does not check to 392 * ensure that capacity is sufficient, and does not increment modCount. 393 */ constructorPut(K key, V value)394 private void constructorPut(K key, V value) { 395 if (key == null) { 396 throw new NullPointerException("key == null"); 397 } else if (value == null) { 398 throw new NullPointerException("value == null"); 399 } 400 int hash = Collections.secondaryHash(key); 401 HashtableEntry<K, V>[] tab = table; 402 int index = hash & (tab.length - 1); 403 HashtableEntry<K, V> first = tab[index]; 404 for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 405 if (e.hash == hash && key.equals(e.key)) { 406 e.value = value; 407 return; 408 } 409 } 410 411 // No entry for key is present; create one 412 tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 413 size++; 414 } 415 416 /** 417 * Copies every mapping to this {@code Hashtable} from the specified map. 418 * 419 * @param map 420 * the map to copy mappings from. 421 */ putAll(Map<? extends K, ? extends V> map)422 public synchronized void putAll(Map<? extends K, ? extends V> map) { 423 ensureCapacity(map.size()); 424 for (Entry<? extends K, ? extends V> e : map.entrySet()) { 425 put(e.getKey(), e.getValue()); 426 } 427 } 428 429 /** 430 * Ensures that the hash table has sufficient capacity to store the 431 * specified number of mappings, with room to grow. If not, it increases the 432 * capacity as appropriate. Like doubleCapacity, this method moves existing 433 * entries to new buckets as appropriate. Unlike doubleCapacity, this method 434 * can grow the table by factors of 2^n for n > 1. Hopefully, a single call 435 * to this method will be faster than multiple calls to doubleCapacity. 436 * 437 * <p>This method is called only by putAll. 438 */ ensureCapacity(int numMappings)439 private void ensureCapacity(int numMappings) { 440 int newCapacity = Collections.roundUpToPowerOfTwo(capacityForInitSize(numMappings)); 441 HashtableEntry<K, V>[] oldTable = table; 442 int oldCapacity = oldTable.length; 443 if (newCapacity <= oldCapacity) { 444 return; 445 } 446 447 rehash(); // Does nothing!! 448 449 if (newCapacity == oldCapacity * 2) { 450 doubleCapacity(); 451 return; 452 } 453 454 // We're growing by at least 4x, rehash in the obvious way 455 HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 456 if (size != 0) { 457 int newMask = newCapacity - 1; 458 for (int i = 0; i < oldCapacity; i++) { 459 for (HashtableEntry<K, V> e = oldTable[i]; e != null;) { 460 HashtableEntry<K, V> oldNext = e.next; 461 int newIndex = e.hash & newMask; 462 HashtableEntry<K, V> newNext = newTable[newIndex]; 463 newTable[newIndex] = e; 464 e.next = newNext; 465 e = oldNext; 466 } 467 } 468 } 469 } 470 471 /** 472 * Increases the capacity of this {@code Hashtable}. This method is called 473 * when the size of this {@code Hashtable} exceeds the load factor. 474 */ rehash()475 protected void rehash() { 476 /* 477 * This method has no testable semantics, other than that it gets 478 * called from time to time. 479 */ 480 } 481 482 /** 483 * Allocate a table of the given capacity and set the threshold accordingly. 484 * @param newCapacity must be a power of two 485 */ makeTable(int newCapacity)486 private HashtableEntry<K, V>[] makeTable(int newCapacity) { 487 @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable 488 = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity]; 489 table = newTable; 490 threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity 491 return newTable; 492 } 493 494 /** 495 * Doubles the capacity of the hash table. Existing entries are placed in 496 * the correct bucket on the enlarged table. If the current capacity is, 497 * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which 498 * will be new unless we were already at MAXIMUM_CAPACITY. 499 */ doubleCapacity()500 private HashtableEntry<K, V>[] doubleCapacity() { 501 HashtableEntry<K, V>[] oldTable = table; 502 int oldCapacity = oldTable.length; 503 if (oldCapacity == MAXIMUM_CAPACITY) { 504 return oldTable; 505 } 506 int newCapacity = oldCapacity * 2; 507 HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 508 if (size == 0) { 509 return newTable; 510 } 511 512 for (int j = 0; j < oldCapacity; j++) { 513 /* 514 * Rehash the bucket using the minimum number of field writes. 515 * This is the most subtle and delicate code in the class. 516 */ 517 HashtableEntry<K, V> e = oldTable[j]; 518 if (e == null) { 519 continue; 520 } 521 int highBit = e.hash & oldCapacity; 522 HashtableEntry<K, V> broken = null; 523 newTable[j | highBit] = e; 524 for (HashtableEntry<K,V> n = e.next; n != null; e = n, n = n.next) { 525 int nextHighBit = n.hash & oldCapacity; 526 if (nextHighBit != highBit) { 527 if (broken == null) 528 newTable[j | nextHighBit] = n; 529 else 530 broken.next = n; 531 broken = e; 532 highBit = nextHighBit; 533 } 534 } 535 if (broken != null) 536 broken.next = null; 537 } 538 return newTable; 539 } 540 541 /** 542 * Removes the key/value pair with the specified key from this 543 * {@code Hashtable}. 544 * 545 * @param key 546 * the key to remove. 547 * @return the value associated with the specified key, or {@code null} if 548 * the specified key did not exist. 549 * @see #get 550 * @see #put 551 */ remove(Object key)552 public synchronized V remove(Object key) { 553 int hash = Collections.secondaryHash(key); 554 HashtableEntry<K, V>[] tab = table; 555 int index = hash & (tab.length - 1); 556 for (HashtableEntry<K, V> e = tab[index], prev = null; 557 e != null; prev = e, e = e.next) { 558 if (e.hash == hash && key.equals(e.key)) { 559 if (prev == null) { 560 tab[index] = e.next; 561 } else { 562 prev.next = e.next; 563 } 564 modCount++; 565 size--; 566 return e.value; 567 } 568 } 569 return null; 570 } 571 572 /** 573 * Removes all key/value pairs from this {@code Hashtable}, leaving the 574 * size zero and the capacity unchanged. 575 * 576 * @see #isEmpty 577 * @see #size 578 */ clear()579 public synchronized void clear() { 580 if (size != 0) { 581 Arrays.fill(table, null); 582 modCount++; 583 size = 0; 584 } 585 } 586 587 /** 588 * Returns a set of the keys contained in this {@code Hashtable}. The set 589 * is backed by this {@code Hashtable} so changes to one are reflected by 590 * the other. The set does not support adding. 591 * 592 * @return a set of the keys. 593 */ keySet()594 public synchronized Set<K> keySet() { 595 Set<K> ks = keySet; 596 return (ks != null) ? ks : (keySet = new KeySet()); 597 } 598 599 /** 600 * Returns a collection of the values contained in this {@code Hashtable}. 601 * The collection is backed by this {@code Hashtable} so changes to one are 602 * reflected by the other. The collection does not support adding. 603 * 604 * @return a collection of the values. 605 */ values()606 public synchronized Collection<V> values() { 607 Collection<V> vs = values; 608 return (vs != null) ? vs : (values = new Values()); 609 } 610 611 /** 612 * Returns a set of the mappings contained in this {@code Hashtable}. Each 613 * element in the set is a {@link Map.Entry}. The set is backed by this 614 * {@code Hashtable} so changes to one are reflected by the other. The set 615 * does not support adding. 616 * 617 * @return a set of the mappings. 618 */ entrySet()619 public synchronized Set<Entry<K, V>> entrySet() { 620 Set<Entry<K, V>> es = entrySet; 621 return (es != null) ? es : (entrySet = new EntrySet()); 622 } 623 624 625 /** 626 * Returns an enumeration on the keys of this {@code Hashtable} instance. 627 * The results of the enumeration may be affected if the contents of this 628 * {@code Hashtable} are modified. 629 * 630 * @return an enumeration of the keys of this {@code Hashtable}. 631 * @see #elements 632 * @see #size 633 * @see Enumeration 634 */ keys()635 public synchronized Enumeration<K> keys() { 636 return new KeyEnumeration(); 637 } 638 639 /** 640 * Returns an enumeration on the values of this {@code Hashtable}. The 641 * results of the Enumeration may be affected if the contents of this 642 * {@code Hashtable} are modified. 643 * 644 * @return an enumeration of the values of this {@code Hashtable}. 645 * @see #keys 646 * @see #size 647 * @see Enumeration 648 */ elements()649 public synchronized Enumeration<V> elements() { 650 return new ValueEnumeration(); 651 } 652 653 /** 654 * Note: technically the methods of this class should synchronize the 655 * backing map. However, this would require them to have a reference 656 * to it, which would cause considerable bloat. Moreover, the RI 657 * behaves the same way. 658 */ 659 private static class HashtableEntry<K, V> implements Entry<K, V> { 660 final K key; 661 V value; 662 final int hash; 663 HashtableEntry<K, V> next; 664 HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next)665 HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) { 666 this.key = key; 667 this.value = value; 668 this.hash = hash; 669 this.next = next; 670 } 671 getKey()672 public final K getKey() { 673 return key; 674 } 675 getValue()676 public final V getValue() { 677 return value; 678 } 679 setValue(V value)680 public final V setValue(V value) { 681 if (value == null) { 682 throw new NullPointerException("value == null"); 683 } 684 V oldValue = this.value; 685 this.value = value; 686 return oldValue; 687 } 688 equals(Object o)689 @Override public final boolean equals(Object o) { 690 if (!(o instanceof Entry)) { 691 return false; 692 } 693 Entry<?, ?> e = (Entry<?, ?>) o; 694 return key.equals(e.getKey()) && value.equals(e.getValue()); 695 } 696 hashCode()697 @Override public final int hashCode() { 698 return key.hashCode() ^ value.hashCode(); 699 } 700 toString()701 @Override public final String toString() { 702 return key + "=" + value; 703 } 704 } 705 706 private abstract class HashIterator { 707 int nextIndex; 708 HashtableEntry<K, V> nextEntry; 709 HashtableEntry<K, V> lastEntryReturned; 710 int expectedModCount = modCount; 711 HashIterator()712 HashIterator() { 713 HashtableEntry<K, V>[] tab = table; 714 HashtableEntry<K, V> next = null; 715 while (next == null && nextIndex < tab.length) { 716 next = tab[nextIndex++]; 717 } 718 nextEntry = next; 719 } 720 hasNext()721 public boolean hasNext() { 722 return nextEntry != null; 723 } 724 nextEntry()725 HashtableEntry<K, V> nextEntry() { 726 if (modCount != expectedModCount) 727 throw new ConcurrentModificationException(); 728 if (nextEntry == null) 729 throw new NoSuchElementException(); 730 731 HashtableEntry<K, V> entryToReturn = nextEntry; 732 HashtableEntry<K, V>[] tab = table; 733 HashtableEntry<K, V> next = entryToReturn.next; 734 while (next == null && nextIndex < tab.length) { 735 next = tab[nextIndex++]; 736 } 737 nextEntry = next; 738 return lastEntryReturned = entryToReturn; 739 } 740 nextEntryNotFailFast()741 HashtableEntry<K, V> nextEntryNotFailFast() { 742 if (nextEntry == null) 743 throw new NoSuchElementException(); 744 745 HashtableEntry<K, V> entryToReturn = nextEntry; 746 HashtableEntry<K, V>[] tab = table; 747 HashtableEntry<K, V> next = entryToReturn.next; 748 while (next == null && nextIndex < tab.length) { 749 next = tab[nextIndex++]; 750 } 751 nextEntry = next; 752 return lastEntryReturned = entryToReturn; 753 } 754 remove()755 public void remove() { 756 if (lastEntryReturned == null) 757 throw new IllegalStateException(); 758 if (modCount != expectedModCount) 759 throw new ConcurrentModificationException(); 760 Hashtable.this.remove(lastEntryReturned.key); 761 lastEntryReturned = null; 762 expectedModCount = modCount; 763 } 764 } 765 766 private final class KeyIterator extends HashIterator 767 implements Iterator<K> { next()768 public K next() { return nextEntry().key; } 769 } 770 771 private final class ValueIterator extends HashIterator 772 implements Iterator<V> { next()773 public V next() { return nextEntry().value; } 774 } 775 776 private final class EntryIterator extends HashIterator 777 implements Iterator<Entry<K, V>> { next()778 public Entry<K, V> next() { return nextEntry(); } 779 } 780 781 private final class KeyEnumeration extends HashIterator 782 implements Enumeration<K> { hasMoreElements()783 public boolean hasMoreElements() { return hasNext(); } nextElement()784 public K nextElement() { return nextEntryNotFailFast().key; } 785 } 786 787 private final class ValueEnumeration extends HashIterator 788 implements Enumeration<V> { hasMoreElements()789 public boolean hasMoreElements() { return hasNext(); } nextElement()790 public V nextElement() { return nextEntryNotFailFast().value; } 791 } 792 793 /** 794 * Returns true if this map contains the specified mapping. 795 */ containsMapping(Object key, Object value)796 private synchronized boolean containsMapping(Object key, Object value) { 797 int hash = Collections.secondaryHash(key); 798 HashtableEntry<K, V>[] tab = table; 799 int index = hash & (tab.length - 1); 800 for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) { 801 if (e.hash == hash && e.key.equals(key)) { 802 return e.value.equals(value); 803 } 804 } 805 return false; // No entry for key 806 } 807 808 /** 809 * Removes the mapping from key to value and returns true if this mapping 810 * exists; otherwise, returns does nothing and returns false. 811 */ removeMapping(Object key, Object value)812 private synchronized boolean removeMapping(Object key, Object value) { 813 int hash = Collections.secondaryHash(key); 814 HashtableEntry<K, V>[] tab = table; 815 int index = hash & (tab.length - 1); 816 for (HashtableEntry<K, V> e = tab[index], prev = null; 817 e != null; prev = e, e = e.next) { 818 if (e.hash == hash && e.key.equals(key)) { 819 if (!e.value.equals(value)) { 820 return false; // Map has wrong value for key 821 } 822 if (prev == null) { 823 tab[index] = e.next; 824 } else { 825 prev.next = e.next; 826 } 827 modCount++; 828 size--; 829 return true; 830 } 831 } 832 return false; // No entry for key 833 } 834 835 /** 836 * Compares this {@code Hashtable} with the specified object and indicates 837 * if they are equal. In order to be equal, {@code object} must be an 838 * instance of Map and contain the same key/value pairs. 839 * 840 * @param object 841 * the object to compare with this object. 842 * @return {@code true} if the specified object is equal to this Map, 843 * {@code false} otherwise. 844 * @see #hashCode 845 */ equals(Object object)846 @Override public synchronized boolean equals(Object object) { 847 return (object instanceof Map) && 848 entrySet().equals(((Map<?, ?>)object).entrySet()); 849 } 850 hashCode()851 @Override public synchronized int hashCode() { 852 int result = 0; 853 for (Entry<K, V> e : entrySet()) { 854 K key = e.getKey(); 855 V value = e.getValue(); 856 if (key == this || value == this) { 857 continue; 858 } 859 result += (key != null ? key.hashCode() : 0) 860 ^ (value != null ? value.hashCode() : 0); 861 } 862 return result; 863 } 864 865 /** 866 * A rough estimate of the number of characters per entry, for use 867 * when creating a string buffer in the toString method. 868 */ 869 private static final int CHARS_PER_ENTRY = 15; 870 871 /** 872 * Returns the string representation of this {@code Hashtable}. 873 * 874 * @return the string representation of this {@code Hashtable}. 875 */ toString()876 @Override public synchronized String toString() { 877 StringBuilder result = new StringBuilder(CHARS_PER_ENTRY * size); 878 result.append('{'); 879 Iterator<Entry<K, V>> i = entrySet().iterator(); 880 boolean hasMore = i.hasNext(); 881 while (hasMore) { 882 Entry<K, V> entry = i.next(); 883 884 K key = entry.getKey(); 885 result.append(key == this ? "(this Map)" : key.toString()); 886 887 result.append('='); 888 889 V value = entry.getValue(); 890 result.append(value == this ? "(this Map)" : value.toString()); 891 892 if (hasMore = i.hasNext()) { 893 result.append(", "); 894 } 895 } 896 897 result.append('}'); 898 return result.toString(); 899 } 900 901 private final class KeySet extends AbstractSet<K> { iterator()902 public Iterator<K> iterator() { 903 return new KeyIterator(); 904 } size()905 public int size() { 906 return Hashtable.this.size(); 907 } contains(Object o)908 public boolean contains(Object o) { 909 return containsKey(o); 910 } remove(Object o)911 public boolean remove(Object o) { 912 synchronized (Hashtable.this) { 913 int oldSize = size; 914 Hashtable.this.remove(o); 915 return size != oldSize; 916 } 917 } clear()918 public void clear() { 919 Hashtable.this.clear(); 920 } removeAll(Collection<?> collection)921 public boolean removeAll(Collection<?> collection) { 922 synchronized (Hashtable.this) { 923 return super.removeAll(collection); 924 } 925 } retainAll(Collection<?> collection)926 public boolean retainAll(Collection<?> collection) { 927 synchronized (Hashtable.this) { 928 return super.retainAll(collection); 929 } 930 } containsAll(Collection<?> collection)931 public boolean containsAll(Collection<?> collection) { 932 synchronized (Hashtable.this) { 933 return super.containsAll(collection); 934 } 935 } equals(Object object)936 public boolean equals(Object object) { 937 synchronized (Hashtable.this) { 938 return super.equals(object); 939 } 940 } hashCode()941 public int hashCode() { 942 synchronized (Hashtable.this) { 943 return super.hashCode(); 944 } 945 } toString()946 public String toString() { 947 synchronized (Hashtable.this) { 948 return super.toString(); 949 } 950 } toArray()951 public Object[] toArray() { 952 synchronized (Hashtable.this) { 953 return super.toArray(); 954 } 955 } toArray(T[] a)956 public <T> T[] toArray(T[] a) { 957 synchronized (Hashtable.this) { 958 return super.toArray(a); 959 } 960 } 961 } 962 963 private final class Values extends AbstractCollection<V> { iterator()964 public Iterator<V> iterator() { 965 return new ValueIterator(); 966 } size()967 public int size() { 968 return Hashtable.this.size(); 969 } contains(Object o)970 public boolean contains(Object o) { 971 return containsValue(o); 972 } clear()973 public void clear() { 974 Hashtable.this.clear(); 975 } containsAll(Collection<?> collection)976 public boolean containsAll(Collection<?> collection) { 977 synchronized (Hashtable.this) { 978 return super.containsAll(collection); 979 } 980 } toString()981 public String toString() { 982 synchronized (Hashtable.this) { 983 return super.toString(); 984 } 985 } toArray()986 public Object[] toArray() { 987 synchronized (Hashtable.this) { 988 return super.toArray(); 989 } 990 } toArray(T[] a)991 public <T> T[] toArray(T[] a) { 992 synchronized (Hashtable.this) { 993 return super.toArray(a); 994 } 995 } 996 } 997 998 private final class EntrySet extends AbstractSet<Entry<K, V>> { iterator()999 public Iterator<Entry<K, V>> iterator() { 1000 return new EntryIterator(); 1001 } contains(Object o)1002 public boolean contains(Object o) { 1003 if (!(o instanceof Entry)) 1004 return false; 1005 Entry<?, ?> e = (Entry<?, ?>) o; 1006 return containsMapping(e.getKey(), e.getValue()); 1007 } remove(Object o)1008 public boolean remove(Object o) { 1009 if (!(o instanceof Entry)) 1010 return false; 1011 Entry<?, ?> e = (Entry<?, ?>)o; 1012 return removeMapping(e.getKey(), e.getValue()); 1013 } size()1014 public int size() { 1015 return Hashtable.this.size(); 1016 } clear()1017 public void clear() { 1018 Hashtable.this.clear(); 1019 } removeAll(Collection<?> collection)1020 public boolean removeAll(Collection<?> collection) { 1021 synchronized (Hashtable.this) { 1022 return super.removeAll(collection); 1023 } 1024 } retainAll(Collection<?> collection)1025 public boolean retainAll(Collection<?> collection) { 1026 synchronized (Hashtable.this) { 1027 return super.retainAll(collection); 1028 } 1029 } containsAll(Collection<?> collection)1030 public boolean containsAll(Collection<?> collection) { 1031 synchronized (Hashtable.this) { 1032 return super.containsAll(collection); 1033 } 1034 } equals(Object object)1035 public boolean equals(Object object) { 1036 synchronized (Hashtable.this) { 1037 return super.equals(object); 1038 } 1039 } hashCode()1040 public int hashCode() { 1041 return Hashtable.this.hashCode(); 1042 } toString()1043 public String toString() { 1044 synchronized (Hashtable.this) { 1045 return super.toString(); 1046 } 1047 } toArray()1048 public Object[] toArray() { 1049 synchronized (Hashtable.this) { 1050 return super.toArray(); 1051 } 1052 } toArray(T[] a)1053 public <T> T[] toArray(T[] a) { 1054 synchronized (Hashtable.this) { 1055 return super.toArray(a); 1056 } 1057 } 1058 } 1059 1060 private static final long serialVersionUID = 1421746759512286392L; 1061 1062 private static final ObjectStreamField[] serialPersistentFields = { 1063 new ObjectStreamField("threshold", int.class), 1064 new ObjectStreamField("loadFactor", float.class), 1065 }; 1066 writeObject(ObjectOutputStream stream)1067 private synchronized void writeObject(ObjectOutputStream stream) 1068 throws IOException { 1069 // Emulate loadFactor field for other implementations to read 1070 ObjectOutputStream.PutField fields = stream.putFields(); 1071 fields.put("threshold", (int) (DEFAULT_LOAD_FACTOR * table.length)); 1072 fields.put("loadFactor", DEFAULT_LOAD_FACTOR); 1073 stream.writeFields(); 1074 1075 stream.writeInt(table.length); // Capacity 1076 stream.writeInt(size); 1077 for (Entry<K, V> e : entrySet()) { 1078 stream.writeObject(e.getKey()); 1079 stream.writeObject(e.getValue()); 1080 } 1081 } 1082 readObject(ObjectInputStream stream)1083 private void readObject(ObjectInputStream stream) throws IOException, 1084 ClassNotFoundException { 1085 stream.defaultReadObject(); 1086 int capacity = stream.readInt(); 1087 if (capacity < 0) { 1088 throw new InvalidObjectException("Capacity: " + capacity); 1089 } 1090 if (capacity < MINIMUM_CAPACITY) { 1091 capacity = MINIMUM_CAPACITY; 1092 } else if (capacity > MAXIMUM_CAPACITY) { 1093 capacity = MAXIMUM_CAPACITY; 1094 } else { 1095 capacity = Collections.roundUpToPowerOfTwo(capacity); 1096 } 1097 makeTable(capacity); 1098 1099 int size = stream.readInt(); 1100 if (size < 0) { 1101 throw new InvalidObjectException("Size: " + size); 1102 } 1103 1104 for (int i = 0; i < size; i++) { 1105 @SuppressWarnings("unchecked") K key = (K) stream.readObject(); 1106 @SuppressWarnings("unchecked") V val = (V) stream.readObject(); 1107 constructorPut(key, val); 1108 } 1109 } 1110 } 1111