| GNU Classpath (0.95) | |
| 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 java.io.IOException; 43: import java.io.ObjectInputStream; 44: import java.io.ObjectOutputStream; 45: import java.io.Serializable; 46: 47: // NOTE: This implementation is very similar to that of HashMap. If you fix 48: // a bug in here, chances are you should make a similar change to the HashMap 49: // code. 50: 51: /** 52: * A class which implements a hashtable data structure. 53: * <p> 54: * 55: * This implementation of Hashtable uses a hash-bucket approach. That is: 56: * linear probing and rehashing is avoided; instead, each hashed value maps 57: * to a simple linked-list which, in the best case, only has one node. 58: * Assuming a large enough table, low enough load factor, and / or well 59: * implemented hashCode() methods, Hashtable should provide O(1) 60: * insertion, deletion, and searching of keys. Hashtable is O(n) in 61: * the worst case for all of these (if all keys hash to the same bucket). 62: * <p> 63: * 64: * This is a JDK-1.2 compliant implementation of Hashtable. As such, it 65: * belongs, partially, to the Collections framework (in that it implements 66: * Map). For backwards compatibility, it inherits from the obsolete and 67: * utterly useless Dictionary class. 68: * <p> 69: * 70: * Being a hybrid of old and new, Hashtable has methods which provide redundant 71: * capability, but with subtle and even crucial differences. 72: * For example, one can iterate over various aspects of a Hashtable with 73: * either an Iterator (which is the JDK-1.2 way of doing things) or with an 74: * Enumeration. The latter can end up in an undefined state if the Hashtable 75: * changes while the Enumeration is open. 76: * <p> 77: * 78: * Unlike HashMap, Hashtable does not accept `null' as a key value. Also, 79: * all accesses are synchronized: in a single thread environment, this is 80: * expensive, but in a multi-thread environment, this saves you the effort 81: * of extra synchronization. However, the old-style enumerators are not 82: * synchronized, because they can lead to unspecified behavior even if 83: * they were synchronized. You have been warned. 84: * <p> 85: * 86: * The iterators are <i>fail-fast</i>, meaning that any structural 87: * modification, except for <code>remove()</code> called on the iterator 88: * itself, cause the iterator to throw a 89: * <code>ConcurrentModificationException</code> rather than exhibit 90: * non-deterministic behavior. 91: * 92: * @author Jon Zeppieri 93: * @author Warren Levy 94: * @author Bryce McKinlay 95: * @author Eric Blake (ebb9@email.byu.edu) 96: * @see HashMap 97: * @see TreeMap 98: * @see IdentityHashMap 99: * @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
| GNU Classpath (0.95) |