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 18package java.util; 19 20import java.io.IOException; 21import java.io.InvalidObjectException; 22import java.io.ObjectInputStream; 23import java.io.ObjectOutputStream; 24import java.io.ObjectStreamField; 25import 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 */ 37public 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") 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 */ 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 = 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 */ 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 */ 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 */ 180 private void constructorPutAll(Map<? extends K, ? extends V> map) { 181 for (Entry<? extends K, ? extends V> e : map.entrySet()) { 182 constructorPut(e.getKey(), e.getValue()); 183 } 184 } 185 186 /** 187 * Returns an appropriate capacity for the specified initial size. Does 188 * not round the result up to a power of two; the caller must do this! 189 * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). 190 */ 191 private static int capacityForInitSize(int size) { 192 int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth 193 194 // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY 195 return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; 196 } 197 198 /** 199 * Returns a new {@code Hashtable} with the same key/value pairs, capacity 200 * and load factor. 201 * 202 * @return a shallow copy of this {@code Hashtable}. 203 * @see java.lang.Cloneable 204 */ 205 @SuppressWarnings("unchecked") 206 @Override public synchronized Object clone() { 207 /* 208 * This could be made more efficient. It unnecessarily hashes all of 209 * the elements in the map. 210 */ 211 Hashtable<K, V> result; 212 try { 213 result = (Hashtable<K, V>) super.clone(); 214 } catch (CloneNotSupportedException e) { 215 throw new AssertionError(e); 216 } 217 218 // Restore clone to empty state, retaining our capacity and threshold 219 result.makeTable(table.length); 220 result.size = 0; 221 result.keySet = null; 222 result.entrySet = null; 223 result.values = null; 224 225 result.constructorPutAll(this); 226 return result; 227 } 228 229 /** 230 * Returns true if this {@code Hashtable} has no key/value pairs. 231 * 232 * @return {@code true} if this {@code Hashtable} has no key/value pairs, 233 * {@code false} otherwise. 234 * @see #size 235 */ 236 public synchronized boolean isEmpty() { 237 return size == 0; 238 } 239 240 /** 241 * Returns the number of key/value pairs in this {@code Hashtable}. 242 * 243 * @return the number of key/value pairs in this {@code Hashtable}. 244 * @see #elements 245 * @see #keys 246 */ 247 public synchronized int size() { 248 return size; 249 } 250 251 /** 252 * Returns the value associated with the specified key in this 253 * {@code Hashtable}. 254 * 255 * @param key 256 * the key of the value returned. 257 * @return the value associated with the specified key, or {@code null} if 258 * the specified key does not exist. 259 * @see #put 260 */ 261 public synchronized V get(Object key) { 262 // Doug Lea's supplemental secondaryHash function (inlined) 263 int hash = key.hashCode(); 264 hash ^= (hash >>> 20) ^ (hash >>> 12); 265 hash ^= (hash >>> 7) ^ (hash >>> 4); 266 267 HashtableEntry<K, V>[] tab = table; 268 for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 269 e != null; e = e.next) { 270 K eKey = e.key; 271 if (eKey == key || (e.hash == hash && key.equals(eKey))) { 272 return e.value; 273 } 274 } 275 return null; 276 } 277 278 /** 279 * Returns true if this {@code Hashtable} contains the specified object as a 280 * key of one of the key/value pairs. 281 * 282 * @param key 283 * the object to look for as a key in this {@code Hashtable}. 284 * @return {@code true} if object is a key in this {@code Hashtable}, 285 * {@code false} otherwise. 286 * @see #contains 287 * @see java.lang.Object#equals 288 */ 289 public synchronized boolean containsKey(Object key) { 290 // Doug Lea's supplemental secondaryHash function (inlined) 291 int hash = key.hashCode(); 292 hash ^= (hash >>> 20) ^ (hash >>> 12); 293 hash ^= (hash >>> 7) ^ (hash >>> 4); 294 295 HashtableEntry<K, V>[] tab = table; 296 for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 297 e != null; e = e.next) { 298 K eKey = e.key; 299 if (eKey == key || (e.hash == hash && key.equals(eKey))) { 300 return true; 301 } 302 } 303 return false; 304 } 305 306 /** 307 * Searches this {@code Hashtable} for the specified value. 308 * 309 * @param value 310 * the object to search for. 311 * @return {@code true} if {@code value} is a value of this 312 * {@code Hashtable}, {@code false} otherwise. 313 */ 314 public synchronized boolean containsValue(Object value) { 315 if (value == null) { 316 throw new NullPointerException("value == null"); 317 } 318 319 HashtableEntry[] tab = table; 320 int len = tab.length; 321 322 for (int i = 0; i < len; i++) { 323 for (HashtableEntry e = tab[i]; e != null; e = e.next) { 324 if (value.equals(e.value)) { 325 return true; 326 } 327 } 328 } 329 return false; 330 } 331 332 /** 333 * Returns true if this {@code Hashtable} contains the specified object as 334 * the value of at least one of the key/value pairs. 335 * 336 * @param value 337 * the object to look for as a value in this {@code Hashtable}. 338 * @return {@code true} if object is a value in this {@code Hashtable}, 339 * {@code false} otherwise. 340 * @see #containsKey 341 * @see java.lang.Object#equals 342 */ 343 public boolean contains(Object value) { 344 return containsValue(value); 345 } 346 347 /** 348 * Associate the specified value with the specified key in this 349 * {@code Hashtable}. If the key already exists, the old value is replaced. 350 * The key and value cannot be null. 351 * 352 * @param key 353 * the key to add. 354 * @param value 355 * the value to add. 356 * @return the old value associated with the specified key, or {@code null} 357 * if the key did not exist. 358 * @see #elements 359 * @see #get 360 * @see #keys 361 * @see java.lang.Object#equals 362 */ 363 public synchronized V put(K key, V value) { 364 if (key == null) { 365 throw new NullPointerException("key == null"); 366 } else if (value == null) { 367 throw new NullPointerException("value == null"); 368 } 369 int hash = secondaryHash(key.hashCode()); 370 HashtableEntry<K, V>[] tab = table; 371 int index = hash & (tab.length - 1); 372 HashtableEntry<K, V> first = tab[index]; 373 for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 374 if (e.hash == hash && key.equals(e.key)) { 375 V oldValue = e.value; 376 e.value = value; 377 return oldValue; 378 } 379 } 380 381 // No entry for key is present; create one 382 modCount++; 383 if (size++ > threshold) { 384 rehash(); // Does nothing!! 385 tab = doubleCapacity(); 386 index = hash & (tab.length - 1); 387 first = tab[index]; 388 } 389 tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 390 return null; 391 } 392 393 /** 394 * This method is just like put, except that it doesn't do things that 395 * are inappropriate or unnecessary for constructors and pseudo-constructors 396 * (i.e., clone, readObject). In particular, this method does not check to 397 * ensure that capacity is sufficient, and does not increment modCount. 398 */ 399 private void constructorPut(K key, V value) { 400 if (key == null) { 401 throw new NullPointerException("key == null"); 402 } else if (value == null) { 403 throw new NullPointerException("value == null"); 404 } 405 int hash = secondaryHash(key.hashCode()); 406 HashtableEntry<K, V>[] tab = table; 407 int index = hash & (tab.length - 1); 408 HashtableEntry<K, V> first = tab[index]; 409 for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 410 if (e.hash == hash && key.equals(e.key)) { 411 e.value = value; 412 return; 413 } 414 } 415 416 // No entry for key is present; create one 417 tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 418 size++; 419 } 420 421 /** 422 * Copies every mapping to this {@code Hashtable} from the specified map. 423 * 424 * @param map 425 * the map to copy mappings from. 426 */ 427 public synchronized void putAll(Map<? extends K, ? extends V> map) { 428 ensureCapacity(map.size()); 429 for (Entry<? extends K, ? extends V> e : map.entrySet()) { 430 put(e.getKey(), e.getValue()); 431 } 432 } 433 434 /** 435 * Ensures that the hash table has sufficient capacity to store the 436 * specified number of mappings, with room to grow. If not, it increases the 437 * capacity as appropriate. Like doubleCapacity, this method moves existing 438 * entries to new buckets as appropriate. Unlike doubleCapacity, this method 439 * can grow the table by factors of 2^n for n > 1. Hopefully, a single call 440 * to this method will be faster than multiple calls to doubleCapacity. 441 * 442 * <p>This method is called only by putAll. 443 */ 444 private void ensureCapacity(int numMappings) { 445 int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings)); 446 HashtableEntry<K, V>[] oldTable = table; 447 int oldCapacity = oldTable.length; 448 if (newCapacity <= oldCapacity) { 449 return; 450 } 451 452 rehash(); // Does nothing!! 453 454 if (newCapacity == oldCapacity * 2) { 455 doubleCapacity(); 456 return; 457 } 458 459 // We're growing by at least 4x, rehash in the obvious way 460 HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 461 if (size != 0) { 462 int newMask = newCapacity - 1; 463 for (int i = 0; i < oldCapacity; i++) { 464 for (HashtableEntry<K, V> e = oldTable[i]; e != null;) { 465 HashtableEntry<K, V> oldNext = e.next; 466 int newIndex = e.hash & newMask; 467 HashtableEntry<K, V> newNext = newTable[newIndex]; 468 newTable[newIndex] = e; 469 e.next = newNext; 470 e = oldNext; 471 } 472 } 473 } 474 } 475 476 /** 477 * Increases the capacity of this {@code Hashtable}. This method is called 478 * when the size of this {@code Hashtable} exceeds the load factor. 479 */ 480 protected void rehash() { 481 /* 482 * This method has no testable semantics, other than that it gets 483 * called from time to time. 484 */ 485 } 486 487 /** 488 * Allocate a table of the given capacity and set the threshold accordingly. 489 * @param newCapacity must be a power of two 490 */ 491 private HashtableEntry<K, V>[] makeTable(int newCapacity) { 492 @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable 493 = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity]; 494 table = newTable; 495 threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity 496 return newTable; 497 } 498 499 /** 500 * Doubles the capacity of the hash table. Existing entries are placed in 501 * the correct bucket on the enlarged table. If the current capacity is, 502 * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which 503 * will be new unless we were already at MAXIMUM_CAPACITY. 504 */ 505 private HashtableEntry<K, V>[] doubleCapacity() { 506 HashtableEntry<K, V>[] oldTable = table; 507 int oldCapacity = oldTable.length; 508 if (oldCapacity == MAXIMUM_CAPACITY) { 509 return oldTable; 510 } 511 int newCapacity = oldCapacity * 2; 512 HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 513 if (size == 0) { 514 return newTable; 515 } 516 517 for (int j = 0; j < oldCapacity; j++) { 518 /* 519 * Rehash the bucket using the minimum number of field writes. 520 * This is the most subtle and delicate code in the class. 521 */ 522 HashtableEntry<K, V> e = oldTable[j]; 523 if (e == null) { 524 continue; 525 } 526 int highBit = e.hash & oldCapacity; 527 HashtableEntry<K, V> broken = null; 528 newTable[j | highBit] = e; 529 for (HashtableEntry<K,V> n = e.next; n != null; e = n, n = n.next) { 530 int nextHighBit = n.hash & oldCapacity; 531 if (nextHighBit != highBit) { 532 if (broken == null) 533 newTable[j | nextHighBit] = n; 534 else 535 broken.next = n; 536 broken = e; 537 highBit = nextHighBit; 538 } 539 } 540 if (broken != null) 541 broken.next = null; 542 } 543 return newTable; 544 } 545 546 /** 547 * Removes the key/value pair with the specified key from this 548 * {@code Hashtable}. 549 * 550 * @param key 551 * the key to remove. 552 * @return the value associated with the specified key, or {@code null} if 553 * the specified key did not exist. 554 * @see #get 555 * @see #put 556 */ 557 public synchronized V remove(Object key) { 558 int hash = secondaryHash(key.hashCode()); 559 HashtableEntry<K, V>[] tab = table; 560 int index = hash & (tab.length - 1); 561 for (HashtableEntry<K, V> e = tab[index], prev = null; 562 e != null; prev = e, e = e.next) { 563 if (e.hash == hash && key.equals(e.key)) { 564 if (prev == null) { 565 tab[index] = e.next; 566 } else { 567 prev.next = e.next; 568 } 569 modCount++; 570 size--; 571 return e.value; 572 } 573 } 574 return null; 575 } 576 577 /** 578 * Removes all key/value pairs from this {@code Hashtable}, leaving the 579 * size zero and the capacity unchanged. 580 * 581 * @see #isEmpty 582 * @see #size 583 */ 584 public synchronized void clear() { 585 if (size != 0) { 586 Arrays.fill(table, null); 587 modCount++; 588 size = 0; 589 } 590 } 591 592 /** 593 * Returns a set of the keys contained in this {@code Hashtable}. The set 594 * is backed by this {@code Hashtable} so changes to one are reflected by 595 * the other. The set does not support adding. 596 * 597 * @return a set of the keys. 598 */ 599 public synchronized Set<K> keySet() { 600 Set<K> ks = keySet; 601 return (ks != null) ? ks : (keySet = new KeySet()); 602 } 603 604 /** 605 * Returns a collection of the values contained in this {@code Hashtable}. 606 * The collection is backed by this {@code Hashtable} so changes to one are 607 * reflected by the other. The collection does not support adding. 608 * 609 * @return a collection of the values. 610 */ 611 public synchronized Collection<V> values() { 612 Collection<V> vs = values; 613 return (vs != null) ? vs : (values = new Values()); 614 } 615 616 /** 617 * Returns a set of the mappings contained in this {@code Hashtable}. Each 618 * element in the set is a {@link Map.Entry}. The set is backed by this 619 * {@code Hashtable} so changes to one are reflected by the other. The set 620 * does not support adding. 621 * 622 * @return a set of the mappings. 623 */ 624 public synchronized Set<Entry<K, V>> entrySet() { 625 Set<Entry<K, V>> es = entrySet; 626 return (es != null) ? es : (entrySet = new EntrySet()); 627 } 628 629 630 /** 631 * Returns an enumeration on the keys of this {@code Hashtable} instance. 632 * The results of the enumeration may be affected if the contents of this 633 * {@code Hashtable} are modified. 634 * 635 * @return an enumeration of the keys of this {@code Hashtable}. 636 * @see #elements 637 * @see #size 638 * @see Enumeration 639 */ 640 public synchronized Enumeration<K> keys() { 641 return new KeyEnumeration(); 642 } 643 644 /** 645 * Returns an enumeration on the values of this {@code Hashtable}. The 646 * results of the Enumeration may be affected if the contents of this 647 * {@code Hashtable} are modified. 648 * 649 * @return an enumeration of the values of this {@code Hashtable}. 650 * @see #keys 651 * @see #size 652 * @see Enumeration 653 */ 654 public synchronized Enumeration<V> elements() { 655 return new ValueEnumeration(); 656 } 657 658 /** 659 * Note: technically the methods of this class should synchronize the 660 * backing map. However, this would require them to have a reference 661 * to it, which would cause considerable bloat. Moreover, the RI 662 * behaves the same way. 663 */ 664 private static class HashtableEntry<K, V> implements Entry<K, V> { 665 final K key; 666 V value; 667 final int hash; 668 HashtableEntry<K, V> next; 669 670 HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) { 671 this.key = key; 672 this.value = value; 673 this.hash = hash; 674 this.next = next; 675 } 676 677 public final K getKey() { 678 return key; 679 } 680 681 public final V getValue() { 682 return value; 683 } 684 685 public final V setValue(V value) { 686 if (value == null) { 687 throw new NullPointerException("value == null"); 688 } 689 V oldValue = this.value; 690 this.value = value; 691 return oldValue; 692 } 693 694 @Override public final boolean equals(Object o) { 695 if (!(o instanceof Entry)) { 696 return false; 697 } 698 Entry<?, ?> e = (Entry<?, ?>) o; 699 return key.equals(e.getKey()) && value.equals(e.getValue()); 700 } 701 702 @Override public final int hashCode() { 703 return key.hashCode() ^ value.hashCode(); 704 } 705 706 @Override public final String toString() { 707 return key + "=" + value; 708 } 709 } 710 711 private abstract class HashIterator { 712 int nextIndex; 713 HashtableEntry<K, V> nextEntry; 714 HashtableEntry<K, V> lastEntryReturned; 715 int expectedModCount = modCount; 716 717 HashIterator() { 718 HashtableEntry<K, V>[] tab = table; 719 HashtableEntry<K, V> next = null; 720 while (next == null && nextIndex < tab.length) { 721 next = tab[nextIndex++]; 722 } 723 nextEntry = next; 724 } 725 726 public boolean hasNext() { 727 return nextEntry != null; 728 } 729 730 HashtableEntry<K, V> nextEntry() { 731 if (modCount != expectedModCount) 732 throw new ConcurrentModificationException(); 733 if (nextEntry == null) 734 throw new NoSuchElementException(); 735 736 HashtableEntry<K, V> entryToReturn = nextEntry; 737 HashtableEntry<K, V>[] tab = table; 738 HashtableEntry<K, V> next = entryToReturn.next; 739 while (next == null && nextIndex < tab.length) { 740 next = tab[nextIndex++]; 741 } 742 nextEntry = next; 743 return lastEntryReturned = entryToReturn; 744 } 745 746 HashtableEntry<K, V> nextEntryNotFailFast() { 747 if (nextEntry == null) 748 throw new NoSuchElementException(); 749 750 HashtableEntry<K, V> entryToReturn = nextEntry; 751 HashtableEntry<K, V>[] tab = table; 752 HashtableEntry<K, V> next = entryToReturn.next; 753 while (next == null && nextIndex < tab.length) { 754 next = tab[nextIndex++]; 755 } 756 nextEntry = next; 757 return lastEntryReturned = entryToReturn; 758 } 759 760 public void remove() { 761 if (lastEntryReturned == null) 762 throw new IllegalStateException(); 763 if (modCount != expectedModCount) 764 throw new ConcurrentModificationException(); 765 Hashtable.this.remove(lastEntryReturned.key); 766 lastEntryReturned = null; 767 expectedModCount = modCount; 768 } 769 } 770 771 private final class KeyIterator extends HashIterator 772 implements Iterator<K> { 773 public K next() { return nextEntry().key; } 774 } 775 776 private final class ValueIterator extends HashIterator 777 implements Iterator<V> { 778 public V next() { return nextEntry().value; } 779 } 780 781 private final class EntryIterator extends HashIterator 782 implements Iterator<Entry<K, V>> { 783 public Entry<K, V> next() { return nextEntry(); } 784 } 785 786 private final class KeyEnumeration extends HashIterator 787 implements Enumeration<K> { 788 public boolean hasMoreElements() { return hasNext(); } 789 public K nextElement() { return nextEntryNotFailFast().key; } 790 } 791 792 private final class ValueEnumeration extends HashIterator 793 implements Enumeration<V> { 794 public boolean hasMoreElements() { return hasNext(); } 795 public V nextElement() { return nextEntryNotFailFast().value; } 796 } 797 798 /** 799 * Returns true if this map contains the specified mapping. 800 */ 801 private synchronized boolean containsMapping(Object key, Object value) { 802 int hash = secondaryHash(key.hashCode()); 803 HashtableEntry<K, V>[] tab = table; 804 int index = hash & (tab.length - 1); 805 for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) { 806 if (e.hash == hash && e.key.equals(key)) { 807 return e.value.equals(value); 808 } 809 } 810 return false; // No entry for key 811 } 812 813 /** 814 * Removes the mapping from key to value and returns true if this mapping 815 * exists; otherwise, returns does nothing and returns false. 816 */ 817 private synchronized boolean removeMapping(Object key, Object value) { 818 int hash = secondaryHash(key.hashCode()); 819 HashtableEntry<K, V>[] tab = table; 820 int index = hash & (tab.length - 1); 821 for (HashtableEntry<K, V> e = tab[index], prev = null; 822 e != null; prev = e, e = e.next) { 823 if (e.hash == hash && e.key.equals(key)) { 824 if (!e.value.equals(value)) { 825 return false; // Map has wrong value for key 826 } 827 if (prev == null) { 828 tab[index] = e.next; 829 } else { 830 prev.next = e.next; 831 } 832 modCount++; 833 size--; 834 return true; 835 } 836 } 837 return false; // No entry for key 838 } 839 840 /** 841 * Compares this {@code Hashtable} with the specified object and indicates 842 * if they are equal. In order to be equal, {@code object} must be an 843 * instance of Map and contain the same key/value pairs. 844 * 845 * @param object 846 * the object to compare with this object. 847 * @return {@code true} if the specified object is equal to this Map, 848 * {@code false} otherwise. 849 * @see #hashCode 850 */ 851 @Override public synchronized boolean equals(Object object) { 852 return (object instanceof Map) && 853 entrySet().equals(((Map<?, ?>)object).entrySet()); 854 } 855 856 @Override public synchronized int hashCode() { 857 int result = 0; 858 for (Entry<K, V> e : entrySet()) { 859 K key = e.getKey(); 860 V value = e.getValue(); 861 if (key == this || value == this) { 862 continue; 863 } 864 result += (key != null ? key.hashCode() : 0) 865 ^ (value != null ? value.hashCode() : 0); 866 } 867 return result; 868 } 869 870 /** 871 * A rough estimate of the number of characters per entry, for use 872 * when creating a string buffer in the toString method. 873 */ 874 private static final int CHARS_PER_ENTRY = 15; 875 876 /** 877 * Returns the string representation of this {@code Hashtable}. 878 * 879 * @return the string representation of this {@code Hashtable}. 880 */ 881 @Override public synchronized String toString() { 882 StringBuilder result = new StringBuilder(CHARS_PER_ENTRY * size); 883 result.append('{'); 884 Iterator<Entry<K, V>> i = entrySet().iterator(); 885 boolean hasMore = i.hasNext(); 886 while (hasMore) { 887 Entry<K, V> entry = i.next(); 888 889 K key = entry.getKey(); 890 result.append(key == this ? "(this Map)" : key.toString()); 891 892 result.append('='); 893 894 V value = entry.getValue(); 895 result.append(value == this ? "(this Map)" : value.toString()); 896 897 if (hasMore = i.hasNext()) { 898 result.append(", "); 899 } 900 } 901 902 result.append('}'); 903 return result.toString(); 904 } 905 906 private final class KeySet extends AbstractSet<K> { 907 public Iterator<K> iterator() { 908 return new KeyIterator(); 909 } 910 public int size() { 911 return Hashtable.this.size(); 912 } 913 public boolean contains(Object o) { 914 return containsKey(o); 915 } 916 public boolean remove(Object o) { 917 synchronized (Hashtable.this) { 918 int oldSize = size; 919 Hashtable.this.remove(o); 920 return size != oldSize; 921 } 922 } 923 public void clear() { 924 Hashtable.this.clear(); 925 } 926 public boolean removeAll(Collection<?> collection) { 927 synchronized (Hashtable.this) { 928 return super.removeAll(collection); 929 } 930 } 931 public boolean retainAll(Collection<?> collection) { 932 synchronized (Hashtable.this) { 933 return super.retainAll(collection); 934 } 935 } 936 public boolean containsAll(Collection<?> collection) { 937 synchronized (Hashtable.this) { 938 return super.containsAll(collection); 939 } 940 } 941 public boolean equals(Object object) { 942 synchronized (Hashtable.this) { 943 return super.equals(object); 944 } 945 } 946 public int hashCode() { 947 synchronized (Hashtable.this) { 948 return super.hashCode(); 949 } 950 } 951 public String toString() { 952 synchronized (Hashtable.this) { 953 return super.toString(); 954 } 955 } 956 public Object[] toArray() { 957 synchronized (Hashtable.this) { 958 return super.toArray(); 959 } 960 } 961 public <T> T[] toArray(T[] a) { 962 synchronized (Hashtable.this) { 963 return super.toArray(a); 964 } 965 } 966 } 967 968 private final class Values extends AbstractCollection<V> { 969 public Iterator<V> iterator() { 970 return new ValueIterator(); 971 } 972 public int size() { 973 return Hashtable.this.size(); 974 } 975 public boolean contains(Object o) { 976 return containsValue(o); 977 } 978 public void clear() { 979 Hashtable.this.clear(); 980 } 981 public boolean containsAll(Collection<?> collection) { 982 synchronized (Hashtable.this) { 983 return super.containsAll(collection); 984 } 985 } 986 public String toString() { 987 synchronized (Hashtable.this) { 988 return super.toString(); 989 } 990 } 991 public Object[] toArray() { 992 synchronized (Hashtable.this) { 993 return super.toArray(); 994 } 995 } 996 public <T> T[] toArray(T[] a) { 997 synchronized (Hashtable.this) { 998 return super.toArray(a); 999 } 1000 } 1001 } 1002 1003 private final class EntrySet extends AbstractSet<Entry<K, V>> { 1004 public Iterator<Entry<K, V>> iterator() { 1005 return new EntryIterator(); 1006 } 1007 public boolean contains(Object o) { 1008 if (!(o instanceof Entry)) 1009 return false; 1010 Entry<?, ?> e = (Entry<?, ?>) o; 1011 return containsMapping(e.getKey(), e.getValue()); 1012 } 1013 public boolean remove(Object o) { 1014 if (!(o instanceof Entry)) 1015 return false; 1016 Entry<?, ?> e = (Entry<?, ?>)o; 1017 return removeMapping(e.getKey(), e.getValue()); 1018 } 1019 public int size() { 1020 return Hashtable.this.size(); 1021 } 1022 public void clear() { 1023 Hashtable.this.clear(); 1024 } 1025 public boolean removeAll(Collection<?> collection) { 1026 synchronized (Hashtable.this) { 1027 return super.removeAll(collection); 1028 } 1029 } 1030 public boolean retainAll(Collection<?> collection) { 1031 synchronized (Hashtable.this) { 1032 return super.retainAll(collection); 1033 } 1034 } 1035 public boolean containsAll(Collection<?> collection) { 1036 synchronized (Hashtable.this) { 1037 return super.containsAll(collection); 1038 } 1039 } 1040 public boolean equals(Object object) { 1041 synchronized (Hashtable.this) { 1042 return super.equals(object); 1043 } 1044 } 1045 public int hashCode() { 1046 return Hashtable.this.hashCode(); 1047 } 1048 public String toString() { 1049 synchronized (Hashtable.this) { 1050 return super.toString(); 1051 } 1052 } 1053 public Object[] toArray() { 1054 synchronized (Hashtable.this) { 1055 return super.toArray(); 1056 } 1057 } 1058 public <T> T[] toArray(T[] a) { 1059 synchronized (Hashtable.this) { 1060 return super.toArray(a); 1061 } 1062 } 1063 } 1064 1065 /** 1066 * Applies a supplemental hash function to a given hashCode, which defends 1067 * against poor quality hash functions. This is critical because Hashtable 1068 * uses power-of-two length hash tables, that otherwise encounter collisions 1069 * for hashCodes that do not differ in lower or upper bits. 1070 */ 1071 private static int secondaryHash(int h) { 1072 // Doug Lea's supplemental hash function 1073 h ^= (h >>> 20) ^ (h >>> 12); 1074 return h ^ (h >>> 7) ^ (h >>> 4); 1075 } 1076 1077 /** 1078 * Returns the smallest power of two >= its argument, with several caveats: 1079 * If the argument is negative but not Integer.MIN_VALUE, the method returns 1080 * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method 1081 * returns Integer.MIN_VALUE. If the argument is zero, the method returns 1082 * zero. 1083 */ 1084 private static int roundUpToPowerOfTwo(int i) { 1085 i--; // If input is a power of two, shift its high-order bit right 1086 1087 // "Smear" the high-order bit all the way to the right 1088 i |= i >>> 1; 1089 i |= i >>> 2; 1090 i |= i >>> 4; 1091 i |= i >>> 8; 1092 i |= i >>> 16; 1093 1094 return i + 1; 1095 } 1096 1097 private static final long serialVersionUID = 1421746759512286392L; 1098 1099 private static final ObjectStreamField[] serialPersistentFields = { 1100 new ObjectStreamField("threshold", int.class), 1101 new ObjectStreamField("loadFactor", float.class), 1102 }; 1103 1104 private synchronized void writeObject(ObjectOutputStream stream) 1105 throws IOException { 1106 // Emulate loadFactor field for other implementations to read 1107 ObjectOutputStream.PutField fields = stream.putFields(); 1108 fields.put("threshold", (int) (DEFAULT_LOAD_FACTOR * table.length)); 1109 fields.put("loadFactor", DEFAULT_LOAD_FACTOR); 1110 stream.writeFields(); 1111 1112 stream.writeInt(table.length); // Capacity 1113 stream.writeInt(size); 1114 for (Entry<K, V> e : entrySet()) { 1115 stream.writeObject(e.getKey()); 1116 stream.writeObject(e.getValue()); 1117 } 1118 } 1119 1120 private void readObject(ObjectInputStream stream) throws IOException, 1121 ClassNotFoundException { 1122 stream.defaultReadObject(); 1123 int capacity = stream.readInt(); 1124 if (capacity < 0) { 1125 throw new InvalidObjectException("Capacity: " + capacity); 1126 } 1127 if (capacity < MINIMUM_CAPACITY) { 1128 capacity = MINIMUM_CAPACITY; 1129 } else if (capacity > MAXIMUM_CAPACITY) { 1130 capacity = MAXIMUM_CAPACITY; 1131 } else { 1132 capacity = roundUpToPowerOfTwo(capacity); 1133 } 1134 makeTable(capacity); 1135 1136 int size = stream.readInt(); 1137 if (size < 0) { 1138 throw new InvalidObjectException("Size: " + size); 1139 } 1140 1141 for (int i = 0; i < size; i++) { 1142 @SuppressWarnings("unchecked") K key = (K) stream.readObject(); 1143 @SuppressWarnings("unchecked") V val = (V) stream.readObject(); 1144 constructorPut(key, val); 1145 } 1146 } 1147} 1148