001 /* Hashtable.java -- a class providing a basic hashtable data structure, 002 mapping Object --> Object 003 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 004 Free Software Foundation, Inc. 005 006 This file is part of GNU Classpath. 007 008 GNU Classpath is free software; you can redistribute it and/or modify 009 it under the terms of the GNU General Public License as published by 010 the Free Software Foundation; either version 2, or (at your option) 011 any later version. 012 013 GNU Classpath is distributed in the hope that it will be useful, but 014 WITHOUT ANY WARRANTY; without even the implied warranty of 015 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 016 General Public License for more details. 017 018 You should have received a copy of the GNU General Public License 019 along with GNU Classpath; see the file COPYING. If not, write to the 020 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021 02110-1301 USA. 022 023 Linking this library statically or dynamically with other modules is 024 making a combined work based on this library. Thus, the terms and 025 conditions of the GNU General Public License cover the whole 026 combination. 027 028 As a special exception, the copyright holders of this library give you 029 permission to link this library with independent modules to produce an 030 executable, regardless of the license terms of these independent 031 modules, and to copy and distribute the resulting executable under 032 terms of your choice, provided that you also meet, for each linked 033 independent module, the terms and conditions of the license of that 034 module. An independent module is a module which is not derived from 035 or based on this library. If you modify this library, you may extend 036 this exception to your version of the library, but you are not 037 obligated to do so. If you do not wish to do so, delete this 038 exception statement from your version. */ 039 040 package java.util; 041 042 import java.io.IOException; 043 import java.io.ObjectInputStream; 044 import java.io.ObjectOutputStream; 045 import java.io.Serializable; 046 047 // NOTE: This implementation is very similar to that of HashMap. If you fix 048 // a bug in here, chances are you should make a similar change to the HashMap 049 // code. 050 051 /** 052 * A class which implements a hashtable data structure. 053 * <p> 054 * 055 * This implementation of Hashtable uses a hash-bucket approach. That is: 056 * linear probing and rehashing is avoided; instead, each hashed value maps 057 * to a simple linked-list which, in the best case, only has one node. 058 * Assuming a large enough table, low enough load factor, and / or well 059 * implemented hashCode() methods, Hashtable should provide O(1) 060 * insertion, deletion, and searching of keys. Hashtable is O(n) in 061 * the worst case for all of these (if all keys hash to the same bucket). 062 * <p> 063 * 064 * This is a JDK-1.2 compliant implementation of Hashtable. As such, it 065 * belongs, partially, to the Collections framework (in that it implements 066 * Map). For backwards compatibility, it inherits from the obsolete and 067 * utterly useless Dictionary class. 068 * <p> 069 * 070 * Being a hybrid of old and new, Hashtable has methods which provide redundant 071 * capability, but with subtle and even crucial differences. 072 * For example, one can iterate over various aspects of a Hashtable with 073 * either an Iterator (which is the JDK-1.2 way of doing things) or with an 074 * Enumeration. The latter can end up in an undefined state if the Hashtable 075 * changes while the Enumeration is open. 076 * <p> 077 * 078 * Unlike HashMap, Hashtable does not accept `null' as a key value. Also, 079 * all accesses are synchronized: in a single thread environment, this is 080 * expensive, but in a multi-thread environment, this saves you the effort 081 * of extra synchronization. However, the old-style enumerators are not 082 * synchronized, because they can lead to unspecified behavior even if 083 * they were synchronized. You have been warned. 084 * <p> 085 * 086 * The iterators are <i>fail-fast</i>, meaning that any structural 087 * modification, except for <code>remove()</code> called on the iterator 088 * itself, cause the iterator to throw a 089 * <code>ConcurrentModificationException</code> rather than exhibit 090 * non-deterministic behavior. 091 * 092 * @author Jon Zeppieri 093 * @author Warren Levy 094 * @author Bryce McKinlay 095 * @author Eric Blake (ebb9@email.byu.edu) 096 * @see HashMap 097 * @see TreeMap 098 * @see IdentityHashMap 099 * @see LinkedHashMap 100 * @since 1.0 101 * @status updated to 1.4 102 */ 103 public class Hashtable<K, V> extends Dictionary<K, V> 104 implements Map<K, V>, Cloneable, Serializable 105 { 106 // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the 107 // comments in vm/reference/java/lang/Runtime for implications of this fact. 108 109 /** Default number of buckets. This is the value the JDK 1.3 uses. Some 110 * early documentation specified this value as 101. That is incorrect. 111 */ 112 private static final int DEFAULT_CAPACITY = 11; 113 114 /** 115 * The default load factor; this is explicitly specified by the spec. 116 */ 117 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 118 119 /** 120 * Compatible with JDK 1.0+. 121 */ 122 private static final long serialVersionUID = 1421746759512286392L; 123 124 /** 125 * The rounded product of the capacity and the load factor; when the number 126 * of elements exceeds the threshold, the Hashtable calls 127 * <code>rehash()</code>. 128 * @serial 129 */ 130 private int threshold; 131 132 /** 133 * Load factor of this Hashtable: used in computing the threshold. 134 * @serial 135 */ 136 private final float loadFactor; 137 138 /** 139 * Array containing the actual key-value mappings. 140 */ 141 // Package visible for use by nested classes. 142 transient HashEntry<K, V>[] buckets; 143 144 /** 145 * Counts the number of modifications this Hashtable has undergone, used 146 * by Iterators to know when to throw ConcurrentModificationExceptions. 147 */ 148 // Package visible for use by nested classes. 149 transient int modCount; 150 151 /** 152 * The size of this Hashtable: denotes the number of key-value pairs. 153 */ 154 // Package visible for use by nested classes. 155 transient int size; 156 157 /** 158 * The cache for {@link #keySet()}. 159 */ 160 private transient Set<K> keys; 161 162 /** 163 * The cache for {@link #values()}. 164 */ 165 private transient Collection<V> values; 166 167 /** 168 * The cache for {@link #entrySet()}. 169 */ 170 private transient Set<Map.Entry<K, V>> entries; 171 172 /** 173 * Class to represent an entry in the hash table. Holds a single key-value 174 * pair. A Hashtable Entry is identical to a HashMap Entry, except that 175 * `null' is not allowed for keys and values. 176 */ 177 private static final class HashEntry<K, V> 178 extends AbstractMap.SimpleEntry<K, V> 179 { 180 /** The next entry in the linked list. */ 181 HashEntry<K, V> next; 182 183 /** 184 * Simple constructor. 185 * @param key the key, already guaranteed non-null 186 * @param value the value, already guaranteed non-null 187 */ 188 HashEntry(K key, V value) 189 { 190 super(key, value); 191 } 192 193 /** 194 * Resets the value. 195 * @param newVal the new value 196 * @return the prior value 197 * @throws NullPointerException if <code>newVal</code> is null 198 */ 199 public V setValue(V newVal) 200 { 201 if (newVal == null) 202 throw new NullPointerException(); 203 return super.setValue(newVal); 204 } 205 } 206 207 /** 208 * Construct a new Hashtable with the default capacity (11) and the default 209 * load factor (0.75). 210 */ 211 public Hashtable() 212 { 213 this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); 214 } 215 216 /** 217 * Construct a new Hashtable from the given Map, with initial capacity 218 * the greater of the size of <code>m</code> or the default of 11. 219 * <p> 220 * 221 * Every element in Map m will be put into this new Hashtable. 222 * 223 * @param m a Map whose key / value pairs will be put into 224 * the new Hashtable. <b>NOTE: key / value pairs 225 * are not cloned in this constructor.</b> 226 * @throws NullPointerException if m is null, or if m contains a mapping 227 * to or from `null'. 228 * @since 1.2 229 */ 230 public Hashtable(Map<? extends K, ? extends V> m) 231 { 232 this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); 233 putAll(m); 234 } 235 236 /** 237 * Construct a new Hashtable with a specific inital capacity and 238 * default load factor of 0.75. 239 * 240 * @param initialCapacity the initial capacity of this Hashtable (>= 0) 241 * @throws IllegalArgumentException if (initialCapacity < 0) 242 */ 243 public Hashtable(int initialCapacity) 244 { 245 this(initialCapacity, DEFAULT_LOAD_FACTOR); 246 } 247 248 /** 249 * Construct a new Hashtable with a specific initial capacity and 250 * load factor. 251 * 252 * @param initialCapacity the initial capacity (>= 0) 253 * @param loadFactor the load factor (> 0, not NaN) 254 * @throws IllegalArgumentException if (initialCapacity < 0) || 255 * ! (loadFactor > 0.0) 256 */ 257 public Hashtable(int initialCapacity, float loadFactor) 258 { 259 if (initialCapacity < 0) 260 throw new IllegalArgumentException("Illegal Capacity: " 261 + initialCapacity); 262 if (! (loadFactor > 0)) // check for NaN too 263 throw new IllegalArgumentException("Illegal Load: " + loadFactor); 264 265 if (initialCapacity == 0) 266 initialCapacity = 1; 267 buckets = (HashEntry<K, V>[]) new HashEntry[initialCapacity]; 268 this.loadFactor = loadFactor; 269 threshold = (int) (initialCapacity * loadFactor); 270 } 271 272 /** 273 * Returns the number of key-value mappings currently in this hashtable. 274 * @return the size 275 */ 276 public synchronized int size() 277 { 278 return size; 279 } 280 281 /** 282 * Returns true if there are no key-value mappings currently in this table. 283 * @return <code>size() == 0</code> 284 */ 285 public synchronized boolean isEmpty() 286 { 287 return size == 0; 288 } 289 290 /** 291 * Return an enumeration of the keys of this table. There's no point 292 * in synchronizing this, as you have already been warned that the 293 * enumeration is not specified to be thread-safe. 294 * 295 * @return the keys 296 * @see #elements() 297 * @see #keySet() 298 */ 299 public Enumeration<K> keys() 300 { 301 return new KeyEnumerator(); 302 } 303 304 /** 305 * Return an enumeration of the values of this table. There's no point 306 * in synchronizing this, as you have already been warned that the 307 * enumeration is not specified to be thread-safe. 308 * 309 * @return the values 310 * @see #keys() 311 * @see #values() 312 */ 313 public Enumeration<V> elements() 314 { 315 return new ValueEnumerator(); 316 } 317 318 /** 319 * Returns true if this Hashtable contains a value <code>o</code>, 320 * such that <code>o.equals(value)</code>. This is the same as 321 * <code>containsValue()</code>, and is O(n). 322 * <p> 323 * 324 * @param value the value to search for in this Hashtable 325 * @return true if at least one key maps to the value 326 * @throws NullPointerException if <code>value</code> is null 327 * @see #containsValue(Object) 328 * @see #containsKey(Object) 329 */ 330 public synchronized boolean contains(Object value) 331 { 332 if (value == null) 333 throw new NullPointerException(); 334 335 for (int i = buckets.length - 1; i >= 0; i--) 336 { 337 HashEntry<K, V> e = buckets[i]; 338 while (e != null) 339 { 340 if (e.value.equals(value)) 341 return true; 342 e = e.next; 343 } 344 } 345 346 return false; 347 } 348 349 /** 350 * Returns true if this Hashtable contains a value <code>o</code>, such that 351 * <code>o.equals(value)</code>. This is the new API for the old 352 * <code>contains()</code>. 353 * 354 * @param value the value to search for in this Hashtable 355 * @return true if at least one key maps to the value 356 * @see #contains(Object) 357 * @see #containsKey(Object) 358 * @throws NullPointerException if <code>value</code> is null 359 * @since 1.2 360 */ 361 public boolean containsValue(Object value) 362 { 363 // Delegate to older method to make sure code overriding it continues 364 // to work. 365 return contains(value); 366 } 367 368 /** 369 * Returns true if the supplied object <code>equals()</code> a key 370 * in this Hashtable. 371 * 372 * @param key the key to search for in this Hashtable 373 * @return true if the key is in the table 374 * @throws NullPointerException if key is null 375 * @see #containsValue(Object) 376 */ 377 public synchronized boolean containsKey(Object key) 378 { 379 int idx = hash(key); 380 HashEntry<K, V> e = buckets[idx]; 381 while (e != null) 382 { 383 if (e.key.equals(key)) 384 return true; 385 e = e.next; 386 } 387 return false; 388 } 389 390 /** 391 * Return the value in this Hashtable associated with the supplied key, 392 * or <code>null</code> if the key maps to nothing. 393 * 394 * @param key the key for which to fetch an associated value 395 * @return what the key maps to, if present 396 * @throws NullPointerException if key is null 397 * @see #put(Object, Object) 398 * @see #containsKey(Object) 399 */ 400 public synchronized V get(Object key) 401 { 402 int idx = hash(key); 403 HashEntry<K, V> e = buckets[idx]; 404 while (e != null) 405 { 406 if (e.key.equals(key)) 407 return e.value; 408 e = e.next; 409 } 410 return null; 411 } 412 413 /** 414 * Puts the supplied value into the Map, mapped by the supplied key. 415 * Neither parameter may be null. The value may be retrieved by any 416 * object which <code>equals()</code> this key. 417 * 418 * @param key the key used to locate the value 419 * @param value the value to be stored in the table 420 * @return the prior mapping of the key, or null if there was none 421 * @throws NullPointerException if key or value is null 422 * @see #get(Object) 423 * @see Object#equals(Object) 424 */ 425 public synchronized V put(K key, V value) 426 { 427 int idx = hash(key); 428 HashEntry<K, V> e = buckets[idx]; 429 430 // Check if value is null since it is not permitted. 431 if (value == null) 432 throw new NullPointerException(); 433 434 while (e != null) 435 { 436 if (e.key.equals(key)) 437 { 438 // Bypass e.setValue, since we already know value is non-null. 439 V r = e.value; 440 e.value = value; 441 return r; 442 } 443 else 444 { 445 e = e.next; 446 } 447 } 448 449 // At this point, we know we need to add a new entry. 450 modCount++; 451 if (++size > threshold) 452 { 453 rehash(); 454 // Need a new hash value to suit the bigger table. 455 idx = hash(key); 456 } 457 458 e = new HashEntry<K, V>(key, value); 459 460 e.next = buckets[idx]; 461 buckets[idx] = e; 462 463 return null; 464 } 465 466 /** 467 * Removes from the table and returns the value which is mapped by the 468 * supplied key. If the key maps to nothing, then the table remains 469 * unchanged, and <code>null</code> is returned. 470 * 471 * @param key the key used to locate the value to remove 472 * @return whatever the key mapped to, if present 473 */ 474 public synchronized V remove(Object key) 475 { 476 int idx = hash(key); 477 HashEntry<K, V> e = buckets[idx]; 478 HashEntry<K, V> last = null; 479 480 while (e != null) 481 { 482 if (e.key.equals(key)) 483 { 484 modCount++; 485 if (last == null) 486 buckets[idx] = e.next; 487 else 488 last.next = e.next; 489 size--; 490 return e.value; 491 } 492 last = e; 493 e = e.next; 494 } 495 return null; 496 } 497 498 /** 499 * Copies all elements of the given map into this hashtable. However, no 500 * mapping can contain null as key or value. If this table already has 501 * a mapping for a key, the new mapping replaces the current one. 502 * 503 * @param m the map to be hashed into this 504 * @throws NullPointerException if m is null, or contains null keys or values 505 */ 506 public synchronized void putAll(Map<? extends K, ? extends V> m) 507 { 508 final Map<K,V> addMap = (Map<K,V>) m; 509 final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); 510 while (it.hasNext()) 511 { 512 final Map.Entry<K,V> e = it.next(); 513 // Optimize in case the Entry is one of our own. 514 if (e instanceof AbstractMap.SimpleEntry) 515 { 516 AbstractMap.SimpleEntry<? extends K, ? extends V> entry 517 = (AbstractMap.SimpleEntry<? extends K, ? extends V>) e; 518 put(entry.key, entry.value); 519 } 520 else 521 { 522 put(e.getKey(), e.getValue()); 523 } 524 } 525 } 526 527 /** 528 * Clears the hashtable so it has no keys. This is O(1). 529 */ 530 public synchronized void clear() 531 { 532 if (size > 0) 533 { 534 modCount++; 535 Arrays.fill(buckets, null); 536 size = 0; 537 } 538 } 539 540 /** 541 * Returns a shallow clone of this Hashtable. The Map itself is cloned, 542 * but its contents are not. This is O(n). 543 * 544 * @return the clone 545 */ 546 public synchronized Object clone() 547 { 548 Hashtable<K, V> copy = null; 549 try 550 { 551 copy = (Hashtable<K, V>) super.clone(); 552 } 553 catch (CloneNotSupportedException x) 554 { 555 // This is impossible. 556 } 557 copy.buckets = (HashEntry<K, V>[]) new HashEntry[buckets.length]; 558 copy.putAllInternal(this); 559 // Clear the caches. 560 copy.keys = null; 561 copy.values = null; 562 copy.entries = null; 563 return copy; 564 } 565 566 /** 567 * Converts this Hashtable to a String, surrounded by braces, and with 568 * key/value pairs listed with an equals sign between, separated by a 569 * comma and space. For example, <code>"{a=1, b=2}"</code>.<p> 570 * 571 * NOTE: if the <code>toString()</code> method of any key or value 572 * throws an exception, this will fail for the same reason. 573 * 574 * @return the string representation 575 */ 576 public synchronized String toString() 577 { 578 // Since we are already synchronized, and entrySet().iterator() 579 // would repeatedly re-lock/release the monitor, we directly use the 580 // unsynchronized EntryIterator instead. 581 Iterator<Map.Entry<K, V>> entries = new EntryIterator(); 582 StringBuffer r = new StringBuffer("{"); 583 for (int pos = size; pos > 0; pos--) 584 { 585 r.append(entries.next()); 586 if (pos > 1) 587 r.append(", "); 588 } 589 r.append("}"); 590 return r.toString(); 591 } 592 593 /** 594 * Returns a "set view" of this Hashtable's keys. The set is backed by 595 * the hashtable, so changes in one show up in the other. The set supports 596 * element removal, but not element addition. The set is properly 597 * synchronized on the original hashtable. Sun has not documented the 598 * proper interaction of null with this set, but has inconsistent behavior 599 * in the JDK. Therefore, in this implementation, contains, remove, 600 * containsAll, retainAll, removeAll, and equals just ignore a null key 601 * rather than throwing a {@link NullPointerException}. 602 * 603 * @return a set view of the keys 604 * @see #values() 605 * @see #entrySet() 606 * @since 1.2 607 */ 608 public Set<K> keySet() 609 { 610 if (keys == null) 611 { 612 // Create a synchronized AbstractSet with custom implementations of 613 // those methods that can be overridden easily and efficiently. 614 Set<K> r = new AbstractSet<K>() 615 { 616 public int size() 617 { 618 return size; 619 } 620 621 public Iterator<K> iterator() 622 { 623 return new KeyIterator(); 624 } 625 626 public void clear() 627 { 628 Hashtable.this.clear(); 629 } 630 631 public boolean contains(Object o) 632 { 633 if (o == null) 634 return false; 635 return containsKey(o); 636 } 637 638 public boolean remove(Object o) 639 { 640 return Hashtable.this.remove(o) != null; 641 } 642 }; 643 // We must specify the correct object to synchronize upon, hence the 644 // use of a non-public API 645 keys = new Collections.SynchronizedSet<K>(this, r); 646 } 647 return keys; 648 } 649 650 /** 651 * Returns a "collection view" (or "bag view") of this Hashtable's values. 652 * The collection is backed by the hashtable, so changes in one show up 653 * in the other. The collection supports element removal, but not element 654 * addition. The collection is properly synchronized on the original 655 * hashtable. Sun has not documented the proper interaction of null with 656 * this set, but has inconsistent behavior in the JDK. Therefore, in this 657 * implementation, contains, remove, containsAll, retainAll, removeAll, and 658 * equals just ignore a null value rather than throwing a 659 * {@link NullPointerException}. 660 * 661 * @return a bag view of the values 662 * @see #keySet() 663 * @see #entrySet() 664 * @since 1.2 665 */ 666 public Collection<V> values() 667 { 668 if (values == null) 669 { 670 // We don't bother overriding many of the optional methods, as doing so 671 // wouldn't provide any significant performance advantage. 672 Collection<V> r = new AbstractCollection<V>() 673 { 674 public int size() 675 { 676 return size; 677 } 678 679 public Iterator<V> iterator() 680 { 681 return new ValueIterator(); 682 } 683 684 public void clear() 685 { 686 Hashtable.this.clear(); 687 } 688 }; 689 // We must specify the correct object to synchronize upon, hence the 690 // use of a non-public API 691 values = new Collections.SynchronizedCollection<V>(this, r); 692 } 693 return values; 694 } 695 696 /** 697 * Returns a "set view" of this Hashtable's entries. The set is backed by 698 * the hashtable, so changes in one show up in the other. The set supports 699 * element removal, but not element addition. The set is properly 700 * synchronized on the original hashtable. Sun has not documented the 701 * proper interaction of null with this set, but has inconsistent behavior 702 * in the JDK. Therefore, in this implementation, contains, remove, 703 * containsAll, retainAll, removeAll, and equals just ignore a null entry, 704 * or an entry with a null key or value, rather than throwing a 705 * {@link NullPointerException}. However, calling entry.setValue(null) 706 * will fail. 707 * <p> 708 * 709 * Note that the iterators for all three views, from keySet(), entrySet(), 710 * and values(), traverse the hashtable in the same sequence. 711 * 712 * @return a set view of the entries 713 * @see #keySet() 714 * @see #values() 715 * @see Map.Entry 716 * @since 1.2 717 */ 718 public Set<Map.Entry<K, V>> entrySet() 719 { 720 if (entries == null) 721 { 722 // Create an AbstractSet with custom implementations of those methods 723 // that can be overridden easily and efficiently. 724 Set<Map.Entry<K, V>> r = new AbstractSet<Map.Entry<K, V>>() 725 { 726 public int size() 727 { 728 return size; 729 } 730 731 public Iterator<Map.Entry<K, V>> iterator() 732 { 733 return new EntryIterator(); 734 } 735 736 public void clear() 737 { 738 Hashtable.this.clear(); 739 } 740 741 public boolean contains(Object o) 742 { 743 return getEntry(o) != null; 744 } 745 746 public boolean remove(Object o) 747 { 748 HashEntry<K, V> e = getEntry(o); 749 if (e != null) 750 { 751 Hashtable.this.remove(e.key); 752 return true; 753 } 754 return false; 755 } 756 }; 757 // We must specify the correct object to synchronize upon, hence the 758 // use of a non-public API 759 entries = new Collections.SynchronizedSet<Map.Entry<K, V>>(this, r); 760 } 761 return entries; 762 } 763 764 /** 765 * Returns true if this Hashtable equals the supplied Object <code>o</code>. 766 * As specified by Map, this is: 767 * <code> 768 * (o instanceof Map) && entrySet().equals(((Map) o).entrySet()); 769 * </code> 770 * 771 * @param o the object to compare to 772 * @return true if o is an equal map 773 * @since 1.2 774 */ 775 public boolean equals(Object o) 776 { 777 // no need to synchronize, entrySet().equals() does that. 778 if (o == this) 779 return true; 780 if (!(o instanceof Map)) 781 return false; 782 783 return entrySet().equals(((Map) o).entrySet()); 784 } 785 786 /** 787 * Returns the hashCode for this Hashtable. As specified by Map, this is 788 * the sum of the hashCodes of all of its Map.Entry objects 789 * 790 * @return the sum of the hashcodes of the entries 791 * @since 1.2 792 */ 793 public synchronized int hashCode() 794 { 795 // Since we are already synchronized, and entrySet().iterator() 796 // would repeatedly re-lock/release the monitor, we directly use the 797 // unsynchronized EntryIterator instead. 798 Iterator<Map.Entry<K, V>> itr = new EntryIterator(); 799 int hashcode = 0; 800 for (int pos = size; pos > 0; pos--) 801 hashcode += itr.next().hashCode(); 802 803 return hashcode; 804 } 805 806 /** 807 * Helper method that returns an index in the buckets array for `key' 808 * based on its hashCode(). 809 * 810 * @param key the key 811 * @return the bucket number 812 * @throws NullPointerException if key is null 813 */ 814 private int hash(Object key) 815 { 816 // Note: Inline Math.abs here, for less method overhead, and to avoid 817 // a bootstrap dependency, since Math relies on native methods. 818 int hash = key.hashCode() % buckets.length; 819 return hash < 0 ? -hash : hash; 820 } 821 822 /** 823 * Helper method for entrySet(), which matches both key and value 824 * simultaneously. Ignores null, as mentioned in entrySet(). 825 * 826 * @param o the entry to match 827 * @return the matching entry, if found, or null 828 * @see #entrySet() 829 */ 830 // Package visible, for use in nested classes. 831 HashEntry<K, V> getEntry(Object o) 832 { 833 if (! (o instanceof Map.Entry)) 834 return null; 835 K key = ((Map.Entry<K, V>) o).getKey(); 836 if (key == null) 837 return null; 838 839 int idx = hash(key); 840 HashEntry<K, V> e = buckets[idx]; 841 while (e != null) 842 { 843 if (e.equals(o)) 844 return e; 845 e = e.next; 846 } 847 return null; 848 } 849 850 /** 851 * A simplified, more efficient internal implementation of putAll(). clone() 852 * should not call putAll or put, in order to be compatible with the JDK 853 * implementation with respect to subclasses. 854 * 855 * @param m the map to initialize this from 856 */ 857 void putAllInternal(Map<? extends K, ? extends V> m) 858 { 859 final Map<K,V> addMap = (Map<K,V>) m; 860 final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); 861 size = 0; 862 while (it.hasNext()) 863 { 864 final Map.Entry<K,V> e = it.next(); 865 size++; 866 K key = e.getKey(); 867 int idx = hash(key); 868 HashEntry<K, V> he = new HashEntry<K, V>(key, e.getValue()); 869 he.next = buckets[idx]; 870 buckets[idx] = he; 871 } 872 } 873 874 /** 875 * Increases the size of the Hashtable and rehashes all keys to new array 876 * indices; this is called when the addition of a new value would cause 877 * size() > threshold. Note that the existing Entry objects are reused in 878 * the new hash table. 879 * <p> 880 * 881 * This is not specified, but the new size is twice the current size plus 882 * one; this number is not always prime, unfortunately. This implementation 883 * is not synchronized, as it is only invoked from synchronized methods. 884 */ 885 protected void rehash() 886 { 887 HashEntry<K, V>[] oldBuckets = buckets; 888 889 int newcapacity = (buckets.length * 2) + 1; 890 threshold = (int) (newcapacity * loadFactor); 891 buckets = (HashEntry<K, V>[]) new HashEntry[newcapacity]; 892 893 for (int i = oldBuckets.length - 1; i >= 0; i--) 894 { 895 HashEntry<K, V> e = oldBuckets[i]; 896 while (e != null) 897 { 898 int idx = hash(e.key); 899 HashEntry<K, V> dest = buckets[idx]; 900 901 if (dest != null) 902 { 903 HashEntry next = dest.next; 904 while (next != null) 905 { 906 dest = next; 907 next = dest.next; 908 } 909 dest.next = e; 910 } 911 else 912 { 913 buckets[idx] = e; 914 } 915 916 HashEntry<K, V> next = e.next; 917 e.next = null; 918 e = next; 919 } 920 } 921 } 922 923 /** 924 * Serializes this object to the given stream. 925 * 926 * @param s the stream to write to 927 * @throws IOException if the underlying stream fails 928 * @serialData the <i>capacity</i> (int) that is the length of the 929 * bucket array, the <i>size</i> (int) of the hash map 930 * are emitted first. They are followed by size entries, 931 * each consisting of a key (Object) and a value (Object). 932 */ 933 private synchronized void writeObject(ObjectOutputStream s) 934 throws IOException 935 { 936 // Write the threshold and loadFactor fields. 937 s.defaultWriteObject(); 938 939 s.writeInt(buckets.length); 940 s.writeInt(size); 941 // Since we are already synchronized, and entrySet().iterator() 942 // would repeatedly re-lock/release the monitor, we directly use the 943 // unsynchronized EntryIterator instead. 944 Iterator<Map.Entry<K, V>> it = new EntryIterator(); 945 while (it.hasNext()) 946 { 947 HashEntry<K, V> entry = (HashEntry<K, V>) it.next(); 948 s.writeObject(entry.key); 949 s.writeObject(entry.value); 950 } 951 } 952 953 /** 954 * Deserializes this object from the given stream. 955 * 956 * @param s the stream to read from 957 * @throws ClassNotFoundException if the underlying stream fails 958 * @throws IOException if the underlying stream fails 959 * @serialData the <i>capacity</i> (int) that is the length of the 960 * bucket array, the <i>size</i> (int) of the hash map 961 * are emitted first. They are followed by size entries, 962 * each consisting of a key (Object) and a value (Object). 963 */ 964 private void readObject(ObjectInputStream s) 965 throws IOException, ClassNotFoundException 966 { 967 // Read the threshold and loadFactor fields. 968 s.defaultReadObject(); 969 970 // Read and use capacity. 971 buckets = (HashEntry<K, V>[]) new HashEntry[s.readInt()]; 972 int len = s.readInt(); 973 974 // Read and use key/value pairs. 975 // TODO: should we be defensive programmers, and check for illegal nulls? 976 while (--len >= 0) 977 put((K) s.readObject(), (V) s.readObject()); 978 } 979 980 /** 981 * A class which implements the Iterator interface and is used for 982 * iterating over Hashtables. 983 * This implementation iterates entries. Subclasses are used to 984 * iterate key and values. It also allows the removal of elements, 985 * as per the Javasoft spec. Note that it is not synchronized; this 986 * is a performance enhancer since it is never exposed externally 987 * and is only used within synchronized blocks above. 988 * 989 * @author Jon Zeppieri 990 * @author Fridjof Siebert 991 */ 992 private class EntryIterator 993 implements Iterator<Entry<K,V>> 994 { 995 /** 996 * The number of modifications to the backing Hashtable that we know about. 997 */ 998 int knownMod = modCount; 999 /** The number of elements remaining to be returned by next(). */ 1000 int count = size; 1001 /** Current index in the physical hash table. */ 1002 int idx = buckets.length; 1003 /** The last Entry returned by a next() call. */ 1004 HashEntry<K, V> last; 1005 /** 1006 * The next entry that should be returned by next(). It is set to something 1007 * if we're iterating through a bucket that contains multiple linked 1008 * entries. It is null if next() needs to find a new bucket. 1009 */ 1010 HashEntry<K, V> next; 1011 1012 /** 1013 * Construct a new EntryIterator 1014 */ 1015 EntryIterator() 1016 { 1017 } 1018 1019 1020 /** 1021 * Returns true if the Iterator has more elements. 1022 * @return true if there are more elements 1023 */ 1024 public boolean hasNext() 1025 { 1026 return count > 0; 1027 } 1028 1029 /** 1030 * Returns the next element in the Iterator's sequential view. 1031 * @return the next element 1032 * @throws ConcurrentModificationException if the hashtable was modified 1033 * @throws NoSuchElementException if there is none 1034 */ 1035 public Map.Entry<K,V> next() 1036 { 1037 if (knownMod != modCount) 1038 throw new ConcurrentModificationException(); 1039 if (count == 0) 1040 throw new NoSuchElementException(); 1041 count--; 1042 HashEntry<K, V> e = next; 1043 1044 while (e == null) 1045 if (idx <= 0) 1046 return null; 1047 else 1048 e = buckets[--idx]; 1049 1050 next = e.next; 1051 last = e; 1052 return e; 1053 } 1054 1055 /** 1056 * Removes from the backing Hashtable the last element which was fetched 1057 * with the <code>next()</code> method. 1058 * @throws ConcurrentModificationException if the hashtable was modified 1059 * @throws IllegalStateException if called when there is no last element 1060 */ 1061 public void remove() 1062 { 1063 if (knownMod != modCount) 1064 throw new ConcurrentModificationException(); 1065 if (last == null) 1066 throw new IllegalStateException(); 1067 1068 Hashtable.this.remove(last.key); 1069 last = null; 1070 knownMod++; 1071 } 1072 } // class EntryIterator 1073 1074 /** 1075 * A class which implements the Iterator interface and is used for 1076 * iterating over keys in Hashtables. This class uses an 1077 * <code>EntryIterator</code> to obtain the keys of each entry. 1078 * 1079 * @author Fridtjof Siebert 1080 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 1081 */ 1082 private class KeyIterator 1083 implements Iterator<K> 1084 { 1085 1086 /** 1087 * This entry iterator is used for most operations. Only 1088 * <code>next()</code> gives a different result, by returning just 1089 * the key rather than the whole element. 1090 */ 1091 private EntryIterator iterator; 1092 1093 /** 1094 * Construct a new KeyIterator 1095 */ 1096 KeyIterator() 1097 { 1098 iterator = new EntryIterator(); 1099 } 1100 1101 1102 /** 1103 * Returns true if the entry iterator has more elements. 1104 * 1105 * @return true if there are more elements 1106 * @throws ConcurrentModificationException if the hashtable was modified 1107 */ 1108 public boolean hasNext() 1109 { 1110 return iterator.hasNext(); 1111 } 1112 1113 /** 1114 * Returns the next element in the Iterator's sequential view. 1115 * 1116 * @return the next element 1117 * 1118 * @throws ConcurrentModificationException if the hashtable was modified 1119 * @throws NoSuchElementException if there is none 1120 */ 1121 public K next() 1122 { 1123 return ((HashEntry<K,V>) iterator.next()).key; 1124 } 1125 1126 /** 1127 * Removes the last element used by the <code>next()</code> method 1128 * using the entry iterator. 1129 * 1130 * @throws ConcurrentModificationException if the hashtable was modified 1131 * @throws IllegalStateException if called when there is no last element 1132 */ 1133 public void remove() 1134 { 1135 iterator.remove(); 1136 } 1137 } // class KeyIterator 1138 1139 /** 1140 * A class which implements the Iterator interface and is used for 1141 * iterating over values in Hashtables. This class uses an 1142 * <code>EntryIterator</code> to obtain the values of each entry. 1143 * 1144 * @author Fridtjof Siebert 1145 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 1146 */ 1147 private class ValueIterator 1148 implements Iterator<V> 1149 { 1150 1151 /** 1152 * This entry iterator is used for most operations. Only 1153 * <code>next()</code> gives a different result, by returning just 1154 * the value rather than the whole element. 1155 */ 1156 private EntryIterator iterator; 1157 1158 /** 1159 * Construct a new KeyIterator 1160 */ 1161 ValueIterator() 1162 { 1163 iterator = new EntryIterator(); 1164 } 1165 1166 1167 /** 1168 * Returns true if the entry iterator has more elements. 1169 * 1170 * @return true if there are more elements 1171 * @throws ConcurrentModificationException if the hashtable was modified 1172 */ 1173 public boolean hasNext() 1174 { 1175 return iterator.hasNext(); 1176 } 1177 1178 /** 1179 * Returns the value of the next element in the iterator's sequential view. 1180 * 1181 * @return the next value 1182 * 1183 * @throws ConcurrentModificationException if the hashtable was modified 1184 * @throws NoSuchElementException if there is none 1185 */ 1186 public V next() 1187 { 1188 return ((HashEntry<K,V>) iterator.next()).value; 1189 } 1190 1191 /** 1192 * Removes the last element used by the <code>next()</code> method 1193 * using the entry iterator. 1194 * 1195 * @throws ConcurrentModificationException if the hashtable was modified 1196 * @throws IllegalStateException if called when there is no last element 1197 */ 1198 public void remove() 1199 { 1200 iterator.remove(); 1201 } 1202 1203 } // class ValueIterator 1204 1205 /** 1206 * Enumeration view of the entries in this Hashtable, providing 1207 * sequential access to its elements. 1208 * 1209 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table 1210 * as this could cause a rehash and we'd completely lose our place. Even 1211 * without a rehash, it is undetermined if a new element added would 1212 * appear in the enumeration. The spec says nothing about this, but 1213 * the "Java Class Libraries" book implies that modifications to the 1214 * hashtable during enumeration causes indeterminate results. Don't do it! 1215 * 1216 * @author Jon Zeppieri 1217 * @author Fridjof Siebert 1218 */ 1219 private class EntryEnumerator 1220 implements Enumeration<Entry<K,V>> 1221 { 1222 /** The number of elements remaining to be returned by next(). */ 1223 int count = size; 1224 /** Current index in the physical hash table. */ 1225 int idx = buckets.length; 1226 /** 1227 * Entry which will be returned by the next nextElement() call. It is 1228 * set if we are iterating through a bucket with multiple entries, or null 1229 * if we must look in the next bucket. 1230 */ 1231 HashEntry<K, V> next; 1232 1233 /** 1234 * Construct the enumeration. 1235 */ 1236 EntryEnumerator() 1237 { 1238 // Nothing to do here. 1239 } 1240 1241 /** 1242 * Checks whether more elements remain in the enumeration. 1243 * @return true if nextElement() will not fail. 1244 */ 1245 public boolean hasMoreElements() 1246 { 1247 return count > 0; 1248 } 1249 1250 /** 1251 * Returns the next element. 1252 * @return the next element 1253 * @throws NoSuchElementException if there is none. 1254 */ 1255 public Map.Entry<K,V> nextElement() 1256 { 1257 if (count == 0) 1258 throw new NoSuchElementException("Hashtable Enumerator"); 1259 count--; 1260 HashEntry<K, V> e = next; 1261 1262 while (e == null) 1263 if (idx <= 0) 1264 return null; 1265 else 1266 e = buckets[--idx]; 1267 1268 next = e.next; 1269 return e; 1270 } 1271 } // class EntryEnumerator 1272 1273 1274 /** 1275 * Enumeration view of this Hashtable, providing sequential access to its 1276 * elements. 1277 * 1278 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table 1279 * as this could cause a rehash and we'd completely lose our place. Even 1280 * without a rehash, it is undetermined if a new element added would 1281 * appear in the enumeration. The spec says nothing about this, but 1282 * the "Java Class Libraries" book implies that modifications to the 1283 * hashtable during enumeration causes indeterminate results. Don't do it! 1284 * 1285 * @author Jon Zeppieri 1286 * @author Fridjof Siebert 1287 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 1288 */ 1289 private final class KeyEnumerator 1290 implements Enumeration<K> 1291 { 1292 /** 1293 * This entry enumerator is used for most operations. Only 1294 * <code>nextElement()</code> gives a different result, by returning just 1295 * the key rather than the whole element. 1296 */ 1297 private EntryEnumerator enumerator; 1298 1299 /** 1300 * Construct a new KeyEnumerator 1301 */ 1302 KeyEnumerator() 1303 { 1304 enumerator = new EntryEnumerator(); 1305 } 1306 1307 1308 /** 1309 * Returns true if the entry enumerator has more elements. 1310 * 1311 * @return true if there are more elements 1312 * @throws ConcurrentModificationException if the hashtable was modified 1313 */ 1314 public boolean hasMoreElements() 1315 { 1316 return enumerator.hasMoreElements(); 1317 } 1318 1319 /** 1320 * Returns the next element. 1321 * @return the next element 1322 * @throws NoSuchElementException if there is none. 1323 */ 1324 public K nextElement() 1325 { 1326 HashEntry<K,V> entry = (HashEntry<K,V>) enumerator.nextElement(); 1327 K retVal = null; 1328 if (entry != null) 1329 retVal = entry.key; 1330 return retVal; 1331 } 1332 } // class KeyEnumerator 1333 1334 1335 /** 1336 * Enumeration view of this Hashtable, providing sequential access to its 1337 * values. 1338 * 1339 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table 1340 * as this could cause a rehash and we'd completely lose our place. Even 1341 * without a rehash, it is undetermined if a new element added would 1342 * appear in the enumeration. The spec says nothing about this, but 1343 * the "Java Class Libraries" book implies that modifications to the 1344 * hashtable during enumeration causes indeterminate results. Don't do it! 1345 * 1346 * @author Jon Zeppieri 1347 * @author Fridjof Siebert 1348 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 1349 */ 1350 private final class ValueEnumerator 1351 implements Enumeration<V> 1352 { 1353 /** 1354 * This entry enumerator is used for most operations. Only 1355 * <code>nextElement()</code> gives a different result, by returning just 1356 * the value rather than the whole element. 1357 */ 1358 private EntryEnumerator enumerator; 1359 1360 /** 1361 * Construct a new ValueEnumerator 1362 */ 1363 ValueEnumerator() 1364 { 1365 enumerator = new EntryEnumerator(); 1366 } 1367 1368 1369 /** 1370 * Returns true if the entry enumerator has more elements. 1371 * 1372 * @return true if there are more elements 1373 * @throws ConcurrentModificationException if the hashtable was modified 1374 */ 1375 public boolean hasMoreElements() 1376 { 1377 return enumerator.hasMoreElements(); 1378 } 1379 1380 /** 1381 * Returns the next element. 1382 * @return the next element 1383 * @throws NoSuchElementException if there is none. 1384 */ 1385 public V nextElement() 1386 { 1387 HashEntry<K,V> entry = (HashEntry<K,V>) enumerator.nextElement(); 1388 V retVal = null; 1389 if (entry != null) 1390 retVal = entry.value; 1391 return retVal; 1392 } 1393 } // class ValueEnumerator 1394 1395 } // class Hashtable