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.ObjectInputStream; 22import java.io.ObjectOutputStream; 23import java.io.Serializable; 24 25import org.apache.harmony.luni.internal.nls.Messages; 26 27/** 28 * Hashtable associates keys with values. Both keys and values cannot be null. 29 * The size of the Hashtable is the number of key/value pairs it contains. The 30 * capacity is the number of key/value pairs the Hashtable can hold. The load 31 * factor is a float value which determines how full the Hashtable gets before 32 * expanding the capacity. If the load factor of the Hashtable is exceeded, the 33 * capacity is doubled. 34 * 35 * @see Enumeration 36 * @see java.io.Serializable 37 * @see java.lang.Object#equals 38 * @see java.lang.Object#hashCode 39 * @since Android 1.0 40 */ 41 42public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, 43 Cloneable, Serializable { 44 45 private static final long serialVersionUID = 1421746759512286392L; 46 47 transient int elementCount; 48 49 transient Entry<K, V>[] elementData; 50 51 private float loadFactor; 52 53 private int threshold; 54 55 transient int firstSlot; 56 57 transient int lastSlot = -1; 58 59 transient int modCount; 60 61 private static final Enumeration<?> EMPTY_ENUMERATION = new Enumeration<Object>() { 62 public boolean hasMoreElements() { 63 return false; 64 } 65 66 public Object nextElement() { 67 throw new NoSuchElementException(); 68 } 69 }; 70 71 private static <K, V> Entry<K, V> newEntry(K key, V value, int hash) { 72 return new Entry<K, V>(key, value); 73 } 74 75 private static class Entry<K, V> extends MapEntry<K, V> { 76 Entry<K, V> next; 77 78 final int hashcode; 79 80 Entry(K theKey, V theValue) { 81 super(theKey, theValue); 82 hashcode = theKey.hashCode(); 83 } 84 85 @Override 86 @SuppressWarnings("unchecked") 87 public Object clone() { 88 Entry<K, V> entry = (Entry<K, V>) super.clone(); 89 if (next != null) { 90 entry.next = (Entry<K, V>) next.clone(); 91 } 92 return entry; 93 } 94 95 @Override 96 public V setValue(V object) { 97 if (object == null) { 98 throw new NullPointerException(); 99 } 100 V result = value; 101 value = object; 102 return result; 103 } 104 105 public int getKeyHash() { 106 return key.hashCode(); 107 } 108 109 public boolean equalsKey(Object aKey, int hash) { 110 // BEGIN android-changed 111 // The VM can inline String.equals 112 return hashcode == aKey.hashCode() 113 && (key instanceof String 114 ? ((String) key).equals(aKey) : key.equals(aKey)); 115 // END android-changed 116 } 117 118 @Override 119 public String toString() { 120 return key + "=" + value; //$NON-NLS-1$ 121 } 122 } 123 124 private final class HashIterator<E> implements Iterator<E> { 125 private int position, expectedModCount; 126 127 private final MapEntry.Type<E, K, V> type; 128 129 private Entry<K, V> lastEntry; 130 131 private int lastPosition; 132 133 private boolean canRemove = false; 134 135 HashIterator(MapEntry.Type<E, K, V> value) { 136 type = value; 137 position = lastSlot; 138 expectedModCount = modCount; 139 } 140 141 public boolean hasNext() { 142 if (lastEntry != null && lastEntry.next != null) { 143 return true; 144 } 145 while (position >= firstSlot) { 146 if (elementData[position] == null) { 147 position--; 148 } else { 149 return true; 150 } 151 } 152 return false; 153 } 154 155 public E next() { 156 if (expectedModCount == modCount) { 157 if (lastEntry != null) { 158 lastEntry = lastEntry.next; 159 } 160 if (lastEntry == null) { 161 while (position >= firstSlot 162 && (lastEntry = elementData[position]) == null) { 163 position--; 164 } 165 if (lastEntry != null) { 166 lastPosition = position; 167 // decrement the position so we don't find the same slot 168 // next time 169 position--; 170 } 171 } 172 if (lastEntry != null) { 173 canRemove = true; 174 return type.get(lastEntry); 175 } 176 throw new NoSuchElementException(); 177 } 178 throw new ConcurrentModificationException(); 179 } 180 181 public void remove() { 182 if (expectedModCount == modCount) { 183 if (canRemove) { 184 canRemove = false; 185 synchronized (Hashtable.this) { 186 boolean removed = false; 187 Entry<K, V> entry = elementData[lastPosition]; 188 if (entry == lastEntry) { 189 elementData[lastPosition] = entry.next; 190 removed = true; 191 } else { 192 while (entry != null && entry.next != lastEntry) { 193 entry = entry.next; 194 } 195 if (entry != null) { 196 entry.next = lastEntry.next; 197 removed = true; 198 } 199 } 200 if (removed) { 201 modCount++; 202 elementCount--; 203 expectedModCount++; 204 return; 205 } 206 // the entry must have been (re)moved outside of the 207 // iterator 208 // but this condition wasn't caught by the modCount 209 // check 210 // throw ConcurrentModificationException() outside of 211 // synchronized block 212 } 213 } else { 214 throw new IllegalStateException(); 215 } 216 } 217 throw new ConcurrentModificationException(); 218 } 219 } 220 221 private final class HashEnumerator<E> implements Enumeration<E> { 222 boolean key; 223 224 int start; 225 226 Entry<K, V> entry; 227 228 HashEnumerator(boolean isKey) { 229 key = isKey; 230 start = lastSlot + 1; 231 } 232 233 public boolean hasMoreElements() { 234 if (entry != null) { 235 return true; 236 } 237 while (--start >= firstSlot) { 238 if (elementData[start] != null) { 239 entry = elementData[start]; 240 return true; 241 } 242 } 243 return false; 244 } 245 246 @SuppressWarnings("unchecked") 247 public E nextElement() { 248 if (hasMoreElements()) { 249 Object result = key ? entry.key : entry.value; 250 entry = entry.next; 251 return (E) result; 252 } 253 throw new NoSuchElementException(); 254 } 255 } 256 257 /** 258 * Constructs a new {@code Hashtable} using the default capacity and load 259 * factor. 260 * 261 * @since Android 1.0 262 */ 263 public Hashtable() { 264 this(11); 265 } 266 267 /** 268 * Constructs a new {@code Hashtable} using the specified capacity and the 269 * default load factor. 270 * 271 * @param capacity 272 * the initial capacity. 273 * @since Android 1.0 274 */ 275 public Hashtable(int capacity) { 276 if (capacity >= 0) { 277 elementCount = 0; 278 elementData = newElementArray(capacity == 0 ? 1 : capacity); 279 firstSlot = elementData.length; 280 loadFactor = 0.75f; 281 computeMaxSize(); 282 } else { 283 throw new IllegalArgumentException(); 284 } 285 } 286 287 /** 288 * Constructs a new {@code Hashtable} using the specified capacity and load 289 * factor. 290 * 291 * @param capacity 292 * the initial capacity. 293 * @param loadFactor 294 * the initial load factor. 295 * @since Android 1.0 296 */ 297 public Hashtable(int capacity, float loadFactor) { 298 if (capacity >= 0 && loadFactor > 0) { 299 elementCount = 0; 300 firstSlot = capacity; 301 elementData = newElementArray(capacity == 0 ? 1 : capacity); 302 this.loadFactor = loadFactor; 303 computeMaxSize(); 304 } else { 305 throw new IllegalArgumentException(); 306 } 307 } 308 309 /** 310 * Constructs a new instance of {@code Hashtable} containing the mappings 311 * from the specified map. 312 * 313 * @param map 314 * the mappings to add. 315 * @since Android 1.0 316 */ 317 public Hashtable(Map<? extends K, ? extends V> map) { 318 this(map.size() < 6 ? 11 : (map.size() * 4 / 3) + 11); 319 putAll(map); 320 } 321 322 @SuppressWarnings("unchecked") 323 private Entry<K, V>[] newElementArray(int size) { 324 return new Entry[size]; 325 } 326 327 /** 328 * Removes all key/value pairs from this {@code Hashtable}, leaving the 329 * size zero and the capacity unchanged. 330 * 331 * @see #isEmpty 332 * @see #size 333 * @since Android 1.0 334 */ 335 public synchronized void clear() { 336 elementCount = 0; 337 Arrays.fill(elementData, null); 338 modCount++; 339 } 340 341 /** 342 * Returns a new {@code Hashtable} with the same key/value pairs, capacity 343 * and load factor. 344 * 345 * @return a shallow copy of this {@code Hashtable}. 346 * @see java.lang.Cloneable 347 * @since Android 1.0 348 */ 349 @Override 350 @SuppressWarnings("unchecked") 351 public synchronized Object clone() { 352 try { 353 Hashtable<K, V> hashtable = (Hashtable<K, V>) super.clone(); 354 hashtable.elementData = elementData.clone(); 355 Entry<K, V> entry; 356 for (int i = elementData.length; --i >= 0;) { 357 if ((entry = elementData[i]) != null) { 358 hashtable.elementData[i] = (Entry<K, V>) entry.clone(); 359 } 360 } 361 return hashtable; 362 } catch (CloneNotSupportedException e) { 363 return null; 364 } 365 } 366 367 private void computeMaxSize() { 368 threshold = (int) (elementData.length * loadFactor); 369 } 370 371 /** 372 * Returns true if this {@code Hashtable} contains the specified object as 373 * the value of at least one of the key/value pairs. 374 * 375 * @param value 376 * the object to look for as a value in this {@code Hashtable}. 377 * @return {@code true} if object is a value in this {@code Hashtable}, 378 * {@code false} otherwise. 379 * @see #containsKey 380 * @see java.lang.Object#equals 381 * @since Android 1.0 382 */ 383 public synchronized boolean contains(Object value) { 384 if (value == null) { 385 throw new NullPointerException(); 386 } 387 388 for (int i = elementData.length; --i >= 0;) { 389 Entry<K, V> entry = elementData[i]; 390 while (entry != null) { 391 if (value.equals(entry.value)) { 392 return true; 393 } 394 entry = entry.next; 395 } 396 } 397 return false; 398 } 399 400 /** 401 * Returns true if this {@code Hashtable} contains the specified object as a 402 * key of one of the key/value pairs. 403 * 404 * @param key 405 * the object to look for as a key in this {@code Hashtable}. 406 * @return {@code true} if object is a key in this {@code Hashtable}, 407 * {@code false} otherwise. 408 * @see #contains 409 * @see java.lang.Object#equals 410 * @since Android 1.0 411 */ 412 public synchronized boolean containsKey(Object key) { 413 return getEntry(key) != null; 414 } 415 416 /** 417 * Searches this {@code Hashtable} for the specified value. 418 * 419 * @param value 420 * the object to search for. 421 * @return {@code true} if {@code value} is a value of this 422 * {@code Hashtable}, {@code false} otherwise. 423 * @since Android 1.0 424 */ 425 public boolean containsValue(Object value) { 426 return contains(value); 427 } 428 429 /** 430 * Returns an enumeration on the values of this {@code Hashtable}. The 431 * results of the Enumeration may be affected if the contents of this 432 * {@code Hashtable} are modified. 433 * 434 * @return an enumeration of the values of this {@code Hashtable}. 435 * @see #keys 436 * @see #size 437 * @see Enumeration 438 * @since Android 1.0 439 */ 440 @Override 441 @SuppressWarnings("unchecked") 442 public synchronized Enumeration<V> elements() { 443 if (elementCount == 0) { 444 return (Enumeration<V>) EMPTY_ENUMERATION; 445 } 446 return new HashEnumerator<V>(false); 447 } 448 449 /** 450 * Returns a set of the mappings contained in this {@code Hashtable}. Each 451 * element in the set is a {@link Map.Entry}. The set is backed by this 452 * {@code Hashtable} so changes to one are reflected by the other. The set 453 * does not support adding. 454 * 455 * @return a set of the mappings. 456 * @since Android 1.0 457 */ 458 public Set<Map.Entry<K, V>> entrySet() { 459 return new Collections.SynchronizedSet<Map.Entry<K, V>>( 460 new AbstractSet<Map.Entry<K, V>>() { 461 @Override 462 public int size() { 463 synchronized (Hashtable.this) { 464 return elementCount; 465 } 466 } 467 468 @Override 469 public void clear() { 470 Hashtable.this.clear(); 471 } 472 473 @Override 474 @SuppressWarnings("unchecked") 475 public boolean remove(Object object) { 476 synchronized (Hashtable.this) { 477 if (contains(object)) { 478 Hashtable.this 479 .remove(((Map.Entry<K, V>) object) 480 .getKey()); 481 return true; 482 } 483 return false; 484 } 485 } 486 487 @Override 488 @SuppressWarnings("unchecked") 489 public boolean contains(Object object) { 490 synchronized (Hashtable.this) { 491 Entry<K, V> entry = getEntry(((Map.Entry<K, V>) object) 492 .getKey()); 493 return object.equals(entry); 494 } 495 } 496 497 @Override 498 public Iterator<Map.Entry<K, V>> iterator() { 499 return new HashIterator<Map.Entry<K, V>>( 500 new MapEntry.Type<Map.Entry<K, V>, K, V>() { 501 public Map.Entry<K, V> get( 502 MapEntry<K, V> entry) { 503 return entry; 504 } 505 }); 506 } 507 }, this); 508 } 509 510 /** 511 * Compares this {@code Hashtable} with the specified object and indicates 512 * if they are equal. In order to be equal, {@code object} must be an 513 * instance of Map and contain the same key/value pairs. 514 * 515 * @param object 516 * the object to compare with this object. 517 * @return {@code true} if the specified object is equal to this Map, 518 * {@code false} otherwise. 519 * @see #hashCode 520 * @since Android 1.0 521 */ 522 @Override 523 public synchronized boolean equals(Object object) { 524 if (this == object) { 525 return true; 526 } 527 if (object instanceof Map) { 528 Map<?, ?> map = (Map<?, ?>) object; 529 if (size() != map.size()) { 530 return false; 531 } 532 533 Set<Map.Entry<K, V>> entries = entrySet(); 534 for (Map.Entry<?, ?> e : map.entrySet()) { 535 if (!entries.contains(e)) { 536 return false; 537 } 538 } 539 return true; 540 } 541 return false; 542 } 543 544 /** 545 * Returns the value associated with the specified key in this 546 * {@code Hashtable}. 547 * 548 * @param key 549 * the key of the value returned. 550 * @return the value associated with the specified key, or {@code null} if 551 * the specified key does not exist. 552 * @see #put 553 * @since Android 1.0 554 */ 555 @Override 556 public synchronized V get(Object key) { 557 int hash = key.hashCode(); 558 int index = (hash & 0x7FFFFFFF) % elementData.length; 559 Entry<K, V> entry = elementData[index]; 560 while (entry != null) { 561 if (entry.equalsKey(key, hash)) { 562 return entry.value; 563 } 564 entry = entry.next; 565 } 566 return null; 567 } 568 569 Entry<K, V> getEntry(Object key) { 570 int hash = key.hashCode(); 571 int index = (hash & 0x7FFFFFFF) % elementData.length; 572 Entry<K, V> entry = elementData[index]; 573 while (entry != null) { 574 if (entry.equalsKey(key, hash)) { 575 return entry; 576 } 577 entry = entry.next; 578 } 579 return null; 580 } 581 582 @Override 583 public synchronized int hashCode() { 584 int result = 0; 585 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 586 while (it.hasNext()) { 587 Map.Entry<K, V> entry = it.next(); 588 Object key = entry.getKey(); 589 Object value = entry.getValue(); 590 int hash = (key != this ? key.hashCode() : 0) 591 ^ (value != this ? (value != null ? value.hashCode() : 0) 592 : 0); 593 result += hash; 594 } 595 return result; 596 } 597 598 /** 599 * Returns true if this {@code Hashtable} has no key/value pairs. 600 * 601 * @return {@code true} if this {@code Hashtable} has no key/value pairs, 602 * {@code false} otherwise. 603 * @see #size 604 * @since Android 1.0 605 */ 606 @Override 607 public synchronized boolean isEmpty() { 608 return elementCount == 0; 609 } 610 611 /** 612 * Returns an enumeration on the keys of this {@code Hashtable} instance. 613 * The results of the enumeration may be affected if the contents of this 614 * {@code Hashtable} are modified. 615 * 616 * @return an enumeration of the keys of this {@code Hashtable}. 617 * @see #elements 618 * @see #size 619 * @see Enumeration 620 * @since Android 1.0 621 */ 622 @Override 623 @SuppressWarnings("unchecked") 624 public synchronized Enumeration<K> keys() { 625 if (elementCount == 0) { 626 return (Enumeration<K>) EMPTY_ENUMERATION; 627 } 628 return new HashEnumerator<K>(true); 629 } 630 631 /** 632 * Returns a set of the keys contained in this {@code Hashtable}. The set 633 * is backed by this {@code Hashtable} so changes to one are reflected by 634 * the other. The set does not support adding. 635 * 636 * @return a set of the keys. 637 * @since Android 1.0 638 */ 639 public Set<K> keySet() { 640 return new Collections.SynchronizedSet<K>(new AbstractSet<K>() { 641 @Override 642 public boolean contains(Object object) { 643 synchronized (Hashtable.this) { 644 return containsKey(object); 645 } 646 } 647 648 @Override 649 public int size() { 650 synchronized (Hashtable.this) { 651 return elementCount; 652 } 653 } 654 655 @Override 656 public void clear() { 657 Hashtable.this.clear(); 658 } 659 660 @Override 661 public boolean remove(Object key) { 662 synchronized (Hashtable.this) { 663 if (containsKey(key)) { 664 Hashtable.this.remove(key); 665 return true; 666 } 667 return false; 668 } 669 } 670 671 @Override 672 public Iterator<K> iterator() { 673 return new HashIterator<K>(new MapEntry.Type<K, K, V>() { 674 public K get(MapEntry<K, V> entry) { 675 return entry.key; 676 } 677 }); 678 } 679 }, this); 680 } 681 682 /** 683 * Associate the specified value with the specified key in this 684 * {@code Hashtable}. If the key already exists, the old value is replaced. 685 * The key and value cannot be null. 686 * 687 * @param key 688 * the key to add. 689 * @param value 690 * the value to add. 691 * @return the old value associated with the specified key, or {@code null} 692 * if the key did not exist. 693 * @see #elements 694 * @see #get 695 * @see #keys 696 * @see java.lang.Object#equals 697 * @since Android 1.0 698 */ 699 @Override 700 public synchronized V put(K key, V value) { 701 if (key != null && value != null) { 702 int hash = key.hashCode(); 703 int index = (hash & 0x7FFFFFFF) % elementData.length; 704 Entry<K, V> entry = elementData[index]; 705 while (entry != null && !entry.equalsKey(key, hash)) { 706 entry = entry.next; 707 } 708 if (entry == null) { 709 modCount++; 710 if (++elementCount > threshold) { 711 rehash(); 712 index = (hash & 0x7FFFFFFF) % elementData.length; 713 } 714 if (index < firstSlot) { 715 firstSlot = index; 716 } 717 if (index > lastSlot) { 718 lastSlot = index; 719 } 720 entry = newEntry(key, value, hash); 721 entry.next = elementData[index]; 722 elementData[index] = entry; 723 return null; 724 } 725 V result = entry.value; 726 entry.value = value; 727 return result; 728 } 729 throw new NullPointerException(); 730 } 731 732 /** 733 * Copies every mapping to this {@code Hashtable} from the specified map. 734 * 735 * @param map 736 * the map to copy mappings from. 737 * @since Android 1.0 738 */ 739 public synchronized void putAll(Map<? extends K, ? extends V> map) { 740 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 741 put(entry.getKey(), entry.getValue()); 742 } 743 } 744 745 /** 746 * Increases the capacity of this {@code Hashtable}. This method is called 747 * when the size of this {@code Hashtable} exceeds the load factor. 748 * 749 * @since Android 1.0 750 */ 751 protected void rehash() { 752 int length = (elementData.length << 1) + 1; 753 if (length == 0) { 754 length = 1; 755 } 756 int newFirst = length; 757 int newLast = -1; 758 Entry<K, V>[] newData = newElementArray(length); 759 for (int i = lastSlot + 1; --i >= firstSlot;) { 760 Entry<K, V> entry = elementData[i]; 761 while (entry != null) { 762 int index = (entry.getKeyHash() & 0x7FFFFFFF) % length; 763 if (index < newFirst) { 764 newFirst = index; 765 } 766 if (index > newLast) { 767 newLast = index; 768 } 769 Entry<K, V> next = entry.next; 770 entry.next = newData[index]; 771 newData[index] = entry; 772 entry = next; 773 } 774 } 775 firstSlot = newFirst; 776 lastSlot = newLast; 777 elementData = newData; 778 computeMaxSize(); 779 } 780 781 /** 782 * Removes the key/value pair with the specified key from this 783 * {@code Hashtable}. 784 * 785 * @param key 786 * the key to remove. 787 * @return the value associated with the specified key, or {@code null} if 788 * the specified key did not exist. 789 * @see #get 790 * @see #put 791 * @since Android 1.0 792 */ 793 @Override 794 public synchronized V remove(Object key) { 795 int hash = key.hashCode(); 796 int index = (hash & 0x7FFFFFFF) % elementData.length; 797 Entry<K, V> last = null; 798 Entry<K, V> entry = elementData[index]; 799 while (entry != null && !entry.equalsKey(key, hash)) { 800 last = entry; 801 entry = entry.next; 802 } 803 if (entry != null) { 804 modCount++; 805 if (last == null) { 806 elementData[index] = entry.next; 807 } else { 808 last.next = entry.next; 809 } 810 elementCount--; 811 V result = entry.value; 812 entry.value = null; 813 return result; 814 } 815 return null; 816 } 817 818 /** 819 * Returns the number of key/value pairs in this {@code Hashtable}. 820 * 821 * @return the number of key/value pairs in this {@code Hashtable}. 822 * @see #elements 823 * @see #keys 824 * @since Android 1.0 825 */ 826 @Override 827 public synchronized int size() { 828 return elementCount; 829 } 830 831 /** 832 * Returns the string representation of this {@code Hashtable}. 833 * 834 * @return the string representation of this {@code Hashtable}. 835 * @since Android 1.0 836 */ 837 @Override 838 public synchronized String toString() { 839 if (isEmpty()) { 840 return "{}"; //$NON-NLS-1$ 841 } 842 843 StringBuilder buffer = new StringBuilder(size() * 28); 844 buffer.append('{'); 845 for (int i = lastSlot; i >= firstSlot; i--) { 846 Entry<K, V> entry = elementData[i]; 847 while (entry != null) { 848 if (entry.key != this) { 849 buffer.append(entry.key); 850 } else { 851 // luni.04=this Map 852 buffer.append("(" + Messages.getString("luni.04") + ")"); //$NON-NLS-1$//$NON-NLS-2$//$NON-NLS-3$ 853 } 854 buffer.append('='); 855 if (entry.value != this) { 856 buffer.append(entry.value); 857 } else { 858 // luni.04=this Map 859 buffer.append("(" + Messages.getString("luni.04") + ")"); //$NON-NLS-1$//$NON-NLS-2$//$NON-NLS-3$ 860 } 861 buffer.append(", "); //$NON-NLS-1$ 862 entry = entry.next; 863 } 864 } 865 // Remove the last ", " 866 if (elementCount > 0) { 867 buffer.setLength(buffer.length() - 2); 868 } 869 buffer.append('}'); 870 return buffer.toString(); 871 } 872 873 /** 874 * Returns a collection of the values contained in this {@code Hashtable}. 875 * The collection is backed by this {@code Hashtable} so changes to one are 876 * reflected by the other. The collection does not support adding. 877 * 878 * @return a collection of the values. 879 * @since Android 1.0 880 */ 881 public Collection<V> values() { 882 return new Collections.SynchronizedCollection<V>( 883 new AbstractCollection<V>() { 884 @Override 885 public boolean contains(Object object) { 886 synchronized (Hashtable.this) { 887 return Hashtable.this.contains(object); 888 } 889 } 890 891 @Override 892 public int size() { 893 synchronized (Hashtable.this) { 894 return elementCount; 895 } 896 } 897 898 @Override 899 public void clear() { 900 Hashtable.this.clear(); 901 } 902 903 @Override 904 public Iterator<V> iterator() { 905 return new HashIterator<V>( 906 new MapEntry.Type<V, K, V>() { 907 public V get(MapEntry<K, V> entry) { 908 return entry.value; 909 } 910 }); 911 } 912 }, this); 913 } 914 915 private synchronized void writeObject(ObjectOutputStream stream) 916 throws IOException { 917 stream.defaultWriteObject(); 918 stream.writeInt(elementData.length); 919 stream.writeInt(elementCount); 920 for (int i = elementData.length; --i >= 0;) { 921 Entry<K, V> entry = elementData[i]; 922 while (entry != null) { 923 stream.writeObject(entry.key); 924 stream.writeObject(entry.value); 925 entry = entry.next; 926 } 927 } 928 } 929 930 @SuppressWarnings("unchecked") 931 private void readObject(ObjectInputStream stream) throws IOException, 932 ClassNotFoundException { 933 stream.defaultReadObject(); 934 int length = stream.readInt(); 935 elementData = newElementArray(length); 936 elementCount = stream.readInt(); 937 for (int i = elementCount; --i >= 0;) { 938 Object key = stream.readObject(); 939 int hash = key.hashCode(); 940 int index = (hash & 0x7FFFFFFF) % length; 941 if (index < firstSlot) { 942 firstSlot = index; 943 } 944 if (index > lastSlot) { 945 lastSlot = index; 946 } 947 Entry<K, V> entry = newEntry((K) key, (V) stream.readObject(), hash); 948 entry.next = elementData[index]; 949 elementData[index] = entry; 950 } 951 } 952} 953