| Frames | No Frames |
1: /* Hashtable.java -- a class providing a basic hashtable data structure, 2: mapping Object --> Object 3: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 4: Free Software Foundation, Inc. 5: 6: This file is part of GNU Classpath. 7: 8: GNU Classpath is free software; you can redistribute it and/or modify 9: it under the terms of the GNU General Public License as published by 10: the Free Software Foundation; either version 2, or (at your option) 11: any later version. 12: 13: GNU Classpath is distributed in the hope that it will be useful, but 14: WITHOUT ANY WARRANTY; without even the implied warranty of 15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16: General Public License for more details. 17: 18: You should have received a copy of the GNU General Public License 19: along with GNU Classpath; see the file COPYING. If not, write to the 20: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 21: 02110-1301 USA. 22: 23: Linking this library statically or dynamically with other modules is 24: making a combined work based on this library. Thus, the terms and 25: conditions of the GNU General Public License cover the whole 26: combination. 27: 28: As a special exception, the copyright holders of this library give you 29: permission to link this library with independent modules to produce an 30: executable, regardless of the license terms of these independent 31: modules, and to copy and distribute the resulting executable under 32: terms of your choice, provided that you also meet, for each linked 33: independent module, the terms and conditions of the license of that 34: module. An independent module is a module which is not derived from 35: or based on this library. If you modify this library, you may extend 36: this exception to your version of the library, but you are not 37: obligated to do so. If you do not wish to do so, delete this 38: exception statement from your version. */ 39: 40: package java.util; 41: 42: import gnu.java.lang.CPStringBuilder; 43: 44: import java.io.IOException; 45: import java.io.ObjectInputStream; 46: import java.io.ObjectOutputStream; 47: import java.io.Serializable; 48: 49: // NOTE: This implementation is very similar to that of HashMap. If you fix 50: // a bug in here, chances are you should make a similar change to the HashMap 51: // code. 52: 53: /** 54: * A class which implements a hashtable data structure. 55: * <p> 56: * 57: * This implementation of Hashtable uses a hash-bucket approach. That is: 58: * linear probing and rehashing is avoided; instead, each hashed value maps 59: * to a simple linked-list which, in the best case, only has one node. 60: * Assuming a large enough table, low enough load factor, and / or well 61: * implemented hashCode() methods, Hashtable should provide O(1) 62: * insertion, deletion, and searching of keys. Hashtable is O(n) in 63: * the worst case for all of these (if all keys hash to the same bucket). 64: * <p> 65: * 66: * This is a JDK-1.2 compliant implementation of Hashtable. As such, it 67: * belongs, partially, to the Collections framework (in that it implements 68: * Map). For backwards compatibility, it inherits from the obsolete and 69: * utterly useless Dictionary class. 70: * <p> 71: * 72: * Being a hybrid of old and new, Hashtable has methods which provide redundant 73: * capability, but with subtle and even crucial differences. 74: * For example, one can iterate over various aspects of a Hashtable with 75: * either an Iterator (which is the JDK-1.2 way of doing things) or with an 76: * Enumeration. The latter can end up in an undefined state if the Hashtable 77: * changes while the Enumeration is open. 78: * <p> 79: * 80: * Unlike HashMap, Hashtable does not accept `null' as a key value. Also, 81: * all accesses are synchronized: in a single thread environment, this is 82: * expensive, but in a multi-thread environment, this saves you the effort 83: * of extra synchronization. However, the old-style enumerators are not 84: * synchronized, because they can lead to unspecified behavior even if 85: * they were synchronized. You have been warned. 86: * <p> 87: * 88: * The iterators are <i>fail-fast</i>, meaning that any structural 89: * modification, except for <code>remove()</code> called on the iterator 90: * itself, cause the iterator to throw a 91: * <code>ConcurrentModificationException</code> rather than exhibit 92: * non-deterministic behavior. 93: * 94: * @author Jon Zeppieri 95: * @author Warren Levy 96: * @author Bryce McKinlay 97: * @author Eric Blake (ebb9@email.byu.edu) 98: * @see HashMap 99: * @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