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