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 extends Dictionary 104: implements Map, 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: /** An "enum" of iterator types. */ 115: // Package visible for use by nested classes. 116: static final int KEYS = 0, 117: VALUES = 1, 118: ENTRIES = 2; 119: 120: /** 121: * The default load factor; this is explicitly specified by the spec. 122: */ 123: private static final float DEFAULT_LOAD_FACTOR = 0.75f; 124: 125: /** 126: * Compatible with JDK 1.0+. 127: */ 128: private static final long serialVersionUID = 1421746759512286392L; 129: 130: /** 131: * The rounded product of the capacity and the load factor; when the number 132: * of elements exceeds the threshold, the Hashtable calls 133: * <code>rehash()</code>. 134: * @serial 135: */ 136: private int threshold; 137: 138: /** 139: * Load factor of this Hashtable: used in computing the threshold. 140: * @serial 141: */ 142: private final float loadFactor; 143: 144: /** 145: * Array containing the actual key-value mappings. 146: */ 147: // Package visible for use by nested classes. 148: transient HashEntry[] buckets; 149: 150: /** 151: * Counts the number of modifications this Hashtable has undergone, used 152: * by Iterators to know when to throw ConcurrentModificationExceptions. 153: */ 154: // Package visible for use by nested classes. 155: transient int modCount; 156: 157: /** 158: * The size of this Hashtable: denotes the number of key-value pairs. 159: */ 160: // Package visible for use by nested classes. 161: transient int size; 162: 163: /** 164: * The cache for {@link #keySet()}. 165: */ 166: private transient Set keys; 167: 168: /** 169: * The cache for {@link #values()}. 170: */ 171: private transient Collection values; 172: 173: /** 174: * The cache for {@link #entrySet()}. 175: */ 176: private transient Set entries; 177: 178: /** 179: * Class to represent an entry in the hash table. Holds a single key-value 180: * pair. A Hashtable Entry is identical to a HashMap Entry, except that 181: * `null' is not allowed for keys and values. 182: */ 183: private static final class HashEntry extends AbstractMap.BasicMapEntry 184: { 185: /** The next entry in the linked list. */ 186: HashEntry next; 187: 188: /** 189: * Simple constructor. 190: * @param key the key, already guaranteed non-null 191: * @param value the value, already guaranteed non-null 192: */ 193: HashEntry(Object key, Object value) 194: { 195: super(key, value); 196: } 197: 198: /** 199: * Resets the value. 200: * @param newVal the new value 201: * @return the prior value 202: * @throws NullPointerException if <code>newVal</code> is null 203: */ 204: public Object setValue(Object newVal) 205: { 206: if (newVal == null) 207: throw new NullPointerException(); 208: return super.setValue(newVal); 209: } 210: } 211: 212: /** 213: * Construct a new Hashtable with the default capacity (11) and the default 214: * load factor (0.75). 215: */ 216: public Hashtable() 217: { 218: this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); 219: } 220: 221: /** 222: * Construct a new Hashtable from the given Map, with initial capacity 223: * the greater of the size of <code>m</code> or the default of 11. 224: * <p> 225: * 226: * Every element in Map m will be put into this new Hashtable. 227: * 228: * @param m a Map whose key / value pairs will be put into 229: * the new Hashtable. <b>NOTE: key / value pairs 230: * are not cloned in this constructor.</b> 231: * @throws NullPointerException if m is null, or if m contains a mapping 232: * to or from `null'. 233: * @since 1.2 234: */ 235: public Hashtable(Map m) 236: { 237: this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); 238: putAll(m); 239: } 240: 241: /** 242: * Construct a new Hashtable with a specific inital capacity and 243: * default load factor of 0.75. 244: * 245: * @param initialCapacity the initial capacity of this Hashtable (>= 0) 246: * @throws IllegalArgumentException if (initialCapacity < 0) 247: */ 248: public Hashtable(int initialCapacity) 249: { 250: this(initialCapacity, DEFAULT_LOAD_FACTOR); 251: } 252: 253: /** 254: * Construct a new Hashtable with a specific initial capacity and 255: * load factor. 256: * 257: * @param initialCapacity the initial capacity (>= 0) 258: * @param loadFactor the load factor (> 0, not NaN) 259: * @throws IllegalArgumentException if (initialCapacity < 0) || 260: * ! (loadFactor > 0.0) 261: */ 262: public Hashtable(int initialCapacity, float loadFactor) 263: { 264: if (initialCapacity < 0) 265: throw new IllegalArgumentException("Illegal Capacity: " 266: + initialCapacity); 267: if (! (loadFactor > 0)) // check for NaN too 268: throw new IllegalArgumentException("Illegal Load: " + loadFactor); 269: 270: if (initialCapacity == 0) 271: initialCapacity = 1; 272: buckets = new HashEntry[initialCapacity]; 273: this.loadFactor = loadFactor; 274: threshold = (int) (initialCapacity * loadFactor); 275: } 276: 277: /** 278: * Returns the number of key-value mappings currently in this hashtable. 279: * @return the size 280: */ 281: public synchronized int size() 282: { 283: return size; 284: } 285: 286: /** 287: * Returns true if there are no key-value mappings currently in this table. 288: * @return <code>size() == 0</code> 289: */ 290: public synchronized boolean isEmpty() 291: { 292: return size == 0; 293: } 294: 295: /** 296: * Return an enumeration of the keys of this table. There's no point 297: * in synchronizing this, as you have already been warned that the 298: * enumeration is not specified to be thread-safe. 299: * 300: * @return the keys 301: * @see #elements() 302: * @see #keySet() 303: */ 304: public Enumeration keys() 305: { 306: return new Enumerator(KEYS); 307: } 308: 309: /** 310: * Return an enumeration of the values of this table. There's no point 311: * in synchronizing this, as you have already been warned that the 312: * enumeration is not specified to be thread-safe. 313: * 314: * @return the values 315: * @see #keys() 316: * @see #values() 317: */ 318: public Enumeration elements() 319: { 320: return new Enumerator(VALUES); 321: } 322: 323: /** 324: * Returns true if this Hashtable contains a value <code>o</code>, 325: * such that <code>o.equals(value)</code>. This is the same as 326: * <code>containsValue()</code>, and is O(n). 327: * <p> 328: * 329: * @param value the value to search for in this Hashtable 330: * @return true if at least one key maps to the value 331: * @throws NullPointerException if <code>value</code> is null 332: * @see #containsValue(Object) 333: * @see #containsKey(Object) 334: */ 335: public synchronized boolean contains(Object value) 336: { 337: if (value == null) 338: throw new NullPointerException(); 339: 340: for (int i = buckets.length - 1; i >= 0; i--) 341: { 342: HashEntry e = buckets[i]; 343: while (e != null) 344: { 345: if (e.value.equals(value)) 346: return true; 347: e = e.next; 348: } 349: } 350: 351: return false; 352: } 353: 354: /** 355: * Returns true if this Hashtable contains a value <code>o</code>, such that 356: * <code>o.equals(value)</code>. This is the new API for the old 357: * <code>contains()</code>. 358: * 359: * @param value the value to search for in this Hashtable 360: * @return true if at least one key maps to the value 361: * @see #contains(Object) 362: * @see #containsKey(Object) 363: * @throws NullPointerException if <code>value</code> is null 364: * @since 1.2 365: */ 366: public boolean containsValue(Object value) 367: { 368: // Delegate to older method to make sure code overriding it continues 369: // to work. 370: return contains(value); 371: } 372: 373: /** 374: * Returns true if the supplied object <code>equals()</code> a key 375: * in this Hashtable. 376: * 377: * @param key the key to search for in this Hashtable 378: * @return true if the key is in the table 379: * @throws NullPointerException if key is null 380: * @see #containsValue(Object) 381: */ 382: public synchronized boolean containsKey(Object key) 383: { 384: int idx = hash(key); 385: HashEntry e = buckets[idx]; 386: while (e != null) 387: { 388: if (e.key.equals(key)) 389: return true; 390: e = e.next; 391: } 392: return false; 393: } 394: 395: /** 396: * Return the value in this Hashtable associated with the supplied key, 397: * or <code>null</code> if the key maps to nothing. 398: * 399: * @param key the key for which to fetch an associated value 400: * @return what the key maps to, if present 401: * @throws NullPointerException if key is null 402: * @see #put(Object, Object) 403: * @see #containsKey(Object) 404: */ 405: public synchronized Object get(Object key) 406: { 407: int idx = hash(key); 408: HashEntry e = buckets[idx]; 409: while (e != null) 410: { 411: if (e.key.equals(key)) 412: return e.value; 413: e = e.next; 414: } 415: return null; 416: } 417: 418: /** 419: * Puts the supplied value into the Map, mapped by the supplied key. 420: * Neither parameter may be null. The value may be retrieved by any 421: * object which <code>equals()</code> this key. 422: * 423: * @param key the key used to locate the value 424: * @param value the value to be stored in the table 425: * @return the prior mapping of the key, or null if there was none 426: * @throws NullPointerException if key or value is null 427: * @see #get(Object) 428: * @see Object#equals(Object) 429: */ 430: public synchronized Object put(Object key, Object value) 431: { 432: int idx = hash(key); 433: HashEntry e = buckets[idx]; 434: 435: // Check if value is null since it is not permitted. 436: if (value == null) 437: throw new NullPointerException(); 438: 439: while (e != null) 440: { 441: if (e.key.equals(key)) 442: { 443: // Bypass e.setValue, since we already know value is non-null. 444: Object r = e.value; 445: e.value = value; 446: return r; 447: } 448: else 449: { 450: e = e.next; 451: } 452: } 453: 454: // At this point, we know we need to add a new entry. 455: modCount++; 456: if (++size > threshold) 457: { 458: rehash(); 459: // Need a new hash value to suit the bigger table. 460: idx = hash(key); 461: } 462: 463: e = new HashEntry(key, value); 464: 465: e.next = buckets[idx]; 466: buckets[idx] = e; 467: 468: return null; 469: } 470: 471: /** 472: * Removes from the table and returns the value which is mapped by the 473: * supplied key. If the key maps to nothing, then the table remains 474: * unchanged, and <code>null</code> is returned. 475: * 476: * @param key the key used to locate the value to remove 477: * @return whatever the key mapped to, if present 478: */ 479: public synchronized Object remove(Object key) 480: { 481: int idx = hash(key); 482: HashEntry e = buckets[idx]; 483: HashEntry last = null; 484: 485: while (e != null) 486: { 487: if (e.key.equals(key)) 488: { 489: modCount++; 490: if (last == null) 491: buckets[idx] = e.next; 492: else 493: last.next = e.next; 494: size--; 495: return e.value; 496: } 497: last = e; 498: e = e.next; 499: } 500: return null; 501: } 502: 503: /** 504: * Copies all elements of the given map into this hashtable. However, no 505: * mapping can contain null as key or value. If this table already has 506: * a mapping for a key, the new mapping replaces the current one. 507: * 508: * @param m the map to be hashed into this 509: * @throws NullPointerException if m is null, or contains null keys or values 510: */ 511: public synchronized void putAll(Map m) 512: { 513: Iterator itr = m.entrySet().iterator(); 514: 515: while (itr.hasNext()) 516: { 517: Map.Entry e = (Map.Entry) itr.next(); 518: // Optimize in case the Entry is one of our own. 519: if (e instanceof AbstractMap.BasicMapEntry) 520: { 521: AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e; 522: put(entry.key, entry.value); 523: } 524: else 525: { 526: put(e.getKey(), e.getValue()); 527: } 528: } 529: } 530: 531: /** 532: * Clears the hashtable so it has no keys. This is O(1). 533: */ 534: public synchronized void clear() 535: { 536: if (size > 0) 537: { 538: modCount++; 539: Arrays.fill(buckets, null); 540: size = 0; 541: } 542: } 543: 544: /** 545: * Returns a shallow clone of this Hashtable. The Map itself is cloned, 546: * but its contents are not. This is O(n). 547: * 548: * @return the clone 549: */ 550: public synchronized Object clone() 551: { 552: Hashtable copy = null; 553: try 554: { 555: copy = (Hashtable) super.clone(); 556: } 557: catch (CloneNotSupportedException x) 558: { 559: // This is impossible. 560: } 561: copy.buckets = new HashEntry[buckets.length]; 562: copy.putAllInternal(this); 563: // Clear the caches. 564: copy.keys = null; 565: copy.values = null; 566: copy.entries = null; 567: return copy; 568: } 569: 570: /** 571: * Converts this Hashtable to a String, surrounded by braces, and with 572: * key/value pairs listed with an equals sign between, separated by a 573: * comma and space. For example, <code>"{a=1, b=2}"</code>.<p> 574: * 575: * NOTE: if the <code>toString()</code> method of any key or value 576: * throws an exception, this will fail for the same reason. 577: * 578: * @return the string representation 579: */ 580: public synchronized String toString() 581: { 582: // Since we are already synchronized, and entrySet().iterator() 583: // would repeatedly re-lock/release the monitor, we directly use the 584: // unsynchronized HashIterator instead. 585: Iterator entries = new HashIterator(ENTRIES); 586: StringBuffer r = new StringBuffer("{"); 587: for (int pos = size; pos > 0; pos--) 588: { 589: r.append(entries.next()); 590: if (pos > 1) 591: r.append(", "); 592: } 593: r.append("}"); 594: return r.toString(); 595: } 596: 597: /** 598: * Returns a "set view" of this Hashtable's keys. The set is backed by 599: * the hashtable, so changes in one show up in the other. The set supports 600: * element removal, but not element addition. The set is properly 601: * synchronized on the original hashtable. Sun has not documented the 602: * proper interaction of null with this set, but has inconsistent behavior 603: * in the JDK. Therefore, in this implementation, contains, remove, 604: * containsAll, retainAll, removeAll, and equals just ignore a null key 605: * rather than throwing a {@link NullPointerException}. 606: * 607: * @return a set view of the keys 608: * @see #values() 609: * @see #entrySet() 610: * @since 1.2 611: */ 612: public Set keySet() 613: { 614: if (keys == null) 615: { 616: // Create a synchronized AbstractSet with custom implementations of 617: // those methods that can be overridden easily and efficiently. 618: Set r = new AbstractSet() 619: { 620: public int size() 621: { 622: return size; 623: } 624: 625: public Iterator iterator() 626: { 627: return new HashIterator(KEYS); 628: } 629: 630: public void clear() 631: { 632: Hashtable.this.clear(); 633: } 634: 635: public boolean contains(Object o) 636: { 637: if (o == null) 638: return false; 639: return containsKey(o); 640: } 641: 642: public boolean remove(Object o) 643: { 644: return Hashtable.this.remove(o) != null; 645: } 646: }; 647: // We must specify the correct object to synchronize upon, hence the 648: // use of a non-public API 649: keys = new Collections.SynchronizedSet(this, r); 650: } 651: return keys; 652: } 653: 654: /** 655: * Returns a "collection view" (or "bag view") of this Hashtable's values. 656: * The collection is backed by the hashtable, so changes in one show up 657: * in the other. The collection supports element removal, but not element 658: * addition. The collection is properly synchronized on the original 659: * hashtable. Sun has not documented the proper interaction of null with 660: * this set, but has inconsistent behavior in the JDK. Therefore, in this 661: * implementation, contains, remove, containsAll, retainAll, removeAll, and 662: * equals just ignore a null value rather than throwing a 663: * {@link NullPointerException}. 664: * 665: * @return a bag view of the values 666: * @see #keySet() 667: * @see #entrySet() 668: * @since 1.2 669: */ 670: public Collection values() 671: { 672: if (values == null) 673: { 674: // We don't bother overriding many of the optional methods, as doing so 675: // wouldn't provide any significant performance advantage. 676: Collection r = new AbstractCollection() 677: { 678: public int size() 679: { 680: return size; 681: } 682: 683: public Iterator iterator() 684: { 685: return new HashIterator(VALUES); 686: } 687: 688: public void clear() 689: { 690: Hashtable.this.clear(); 691: } 692: }; 693: // We must specify the correct object to synchronize upon, hence the 694: // use of a non-public API 695: values = new Collections.SynchronizedCollection(this, r); 696: } 697: return values; 698: } 699: 700: /** 701: * Returns a "set view" of this Hashtable's entries. The set is backed by 702: * the hashtable, so changes in one show up in the other. The set supports 703: * element removal, but not element addition. The set is properly 704: * synchronized on the original hashtable. Sun has not documented the 705: * proper interaction of null with this set, but has inconsistent behavior 706: * in the JDK. Therefore, in this implementation, contains, remove, 707: * containsAll, retainAll, removeAll, and equals just ignore a null entry, 708: * or an entry with a null key or value, rather than throwing a 709: * {@link NullPointerException}. However, calling entry.setValue(null) 710: * will fail. 711: * <p> 712: * 713: * Note that the iterators for all three views, from keySet(), entrySet(), 714: * and values(), traverse the hashtable in the same sequence. 715: * 716: * @return a set view of the entries 717: * @see #keySet() 718: * @see #values() 719: * @see Map.Entry 720: * @since 1.2 721: */ 722: public Set entrySet() 723: { 724: if (entries == null) 725: { 726: // Create an AbstractSet with custom implementations of those methods 727: // that can be overridden easily and efficiently. 728: Set r = new AbstractSet() 729: { 730: public int size() 731: { 732: return size; 733: } 734: 735: public Iterator iterator() 736: { 737: return new HashIterator(ENTRIES); 738: } 739: 740: public void clear() 741: { 742: Hashtable.this.clear(); 743: } 744: 745: public boolean contains(Object o) 746: { 747: return getEntry(o) != null; 748: } 749: 750: public boolean remove(Object o) 751: { 752: HashEntry e = getEntry(o); 753: if (e != null) 754: { 755: Hashtable.this.remove(e.key); 756: return true; 757: } 758: return false; 759: } 760: }; 761: // We must specify the correct object to synchronize upon, hence the 762: // use of a non-public API 763: entries = new Collections.SynchronizedSet(this, r); 764: } 765: return entries; 766: } 767: 768: /** 769: * Returns true if this Hashtable equals the supplied Object <code>o</code>. 770: * As specified by Map, this is: 771: * <code> 772: * (o instanceof Map) && entrySet().equals(((Map) o).entrySet()); 773: * </code> 774: * 775: * @param o the object to compare to 776: * @return true if o is an equal map 777: * @since 1.2 778: */ 779: public boolean equals(Object o) 780: { 781: // no need to synchronize, entrySet().equals() does that 782: if (o == this) 783: return true; 784: if (!(o instanceof Map)) 785: return false; 786: 787: return entrySet().equals(((Map) o).entrySet()); 788: } 789: 790: /** 791: * Returns the hashCode for this Hashtable. As specified by Map, this is 792: * the sum of the hashCodes of all of its Map.Entry objects 793: * 794: * @return the sum of the hashcodes of the entries 795: * @since 1.2 796: */ 797: public synchronized int hashCode() 798: { 799: // Since we are already synchronized, and entrySet().iterator() 800: // would repeatedly re-lock/release the monitor, we directly use the 801: // unsynchronized HashIterator instead. 802: Iterator itr = new HashIterator(ENTRIES); 803: int hashcode = 0; 804: for (int pos = size; pos > 0; pos--) 805: hashcode += itr.next().hashCode(); 806: 807: return hashcode; 808: } 809: 810: /** 811: * Helper method that returns an index in the buckets array for `key' 812: * based on its hashCode(). 813: * 814: * @param key the key 815: * @return the bucket number 816: * @throws NullPointerException if key is null 817: */ 818: private int hash(Object key) 819: { 820: // Note: Inline Math.abs here, for less method overhead, and to avoid 821: // a bootstrap dependency, since Math relies on native methods. 822: int hash = key.hashCode() % buckets.length; 823: return hash < 0 ? -hash : hash; 824: } 825: 826: /** 827: * Helper method for entrySet(), which matches both key and value 828: * simultaneously. Ignores null, as mentioned in entrySet(). 829: * 830: * @param o the entry to match 831: * @return the matching entry, if found, or null 832: * @see #entrySet() 833: */ 834: // Package visible, for use in nested classes. 835: HashEntry getEntry(Object o) 836: { 837: if (! (o instanceof Map.Entry)) 838: return null; 839: Object key = ((Map.Entry) o).getKey(); 840: if (key == null) 841: return null; 842: 843: int idx = hash(key); 844: HashEntry e = buckets[idx]; 845: while (e != null) 846: { 847: if (e.equals(o)) 848: return e; 849: e = e.next; 850: } 851: return null; 852: } 853: 854: /** 855: * A simplified, more efficient internal implementation of putAll(). clone() 856: * should not call putAll or put, in order to be compatible with the JDK 857: * implementation with respect to subclasses. 858: * 859: * @param m the map to initialize this from 860: */ 861: void putAllInternal(Map m) 862: { 863: Iterator itr = m.entrySet().iterator(); 864: size = 0; 865: 866: while (itr.hasNext()) 867: { 868: size++; 869: Map.Entry e = (Map.Entry) itr.next(); 870: Object key = e.getKey(); 871: int idx = hash(key); 872: HashEntry he = new HashEntry(key, e.getValue()); 873: he.next = buckets[idx]; 874: buckets[idx] = he; 875: } 876: } 877: 878: /** 879: * Increases the size of the Hashtable and rehashes all keys to new array 880: * indices; this is called when the addition of a new value would cause 881: * size() > threshold. Note that the existing Entry objects are reused in 882: * the new hash table. 883: * <p> 884: * 885: * This is not specified, but the new size is twice the current size plus 886: * one; this number is not always prime, unfortunately. This implementation 887: * is not synchronized, as it is only invoked from synchronized methods. 888: */ 889: protected void rehash() 890: { 891: HashEntry[] oldBuckets = buckets; 892: 893: int newcapacity = (buckets.length * 2) + 1; 894: threshold = (int) (newcapacity * loadFactor); 895: buckets = new HashEntry[newcapacity]; 896: 897: for (int i = oldBuckets.length - 1; i >= 0; i--) 898: { 899: HashEntry e = oldBuckets[i]; 900: while (e != null) 901: { 902: int idx = hash(e.key); 903: HashEntry dest = buckets[idx]; 904: 905: if (dest != null) 906: { 907: while (dest.next != null) 908: dest = dest.next; 909: dest.next = e; 910: } 911: else 912: { 913: buckets[idx] = e; 914: } 915: 916: HashEntry 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 HashIterator instead. 944: Iterator it = new HashIterator(ENTRIES); 945: while (it.hasNext()) 946: { 947: HashEntry entry = (HashEntry) 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 = 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(s.readObject(), s.readObject()); 978: } 979: 980: /** 981: * A class which implements the Iterator interface and is used for 982: * iterating over Hashtables. 983: * This implementation is parameterized to give a sequential view of 984: * keys, values, or entries; it also allows the removal of elements, 985: * as per the Javasoft spec. Note that it is not synchronized; this is 986: * a performance enhancer since it is never exposed externally and is 987: * only used within synchronized blocks above. 988: * 989: * @author Jon Zeppieri 990: */ 991: private final class HashIterator implements Iterator 992: { 993: /** 994: * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 995: * or {@link #ENTRIES}. 996: */ 997: final int type; 998: /** 999: * The number of modifications to the backing Hashtable that we know about. 1000: */ 1001: int knownMod = modCount; 1002: /** The number of elements remaining to be returned by next(). */ 1003: int count = size; 1004: /** Current index in the physical hash table. */ 1005: int idx = buckets.length; 1006: /** The last Entry returned by a next() call. */ 1007: HashEntry last; 1008: /** 1009: * The next entry that should be returned by next(). It is set to something 1010: * if we're iterating through a bucket that contains multiple linked 1011: * entries. It is null if next() needs to find a new bucket. 1012: */ 1013: HashEntry next; 1014: 1015: /** 1016: * Construct a new HashIterator with the supplied type. 1017: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 1018: */ 1019: HashIterator(int type) 1020: { 1021: this.type = type; 1022: } 1023: 1024: /** 1025: * Returns true if the Iterator has more elements. 1026: * @return true if there are more elements 1027: * @throws ConcurrentModificationException if the hashtable was modified 1028: */ 1029: public boolean hasNext() 1030: { 1031: if (knownMod != modCount) 1032: throw new ConcurrentModificationException(); 1033: return count > 0; 1034: } 1035: 1036: /** 1037: * Returns the next element in the Iterator's sequential view. 1038: * @return the next element 1039: * @throws ConcurrentModificationException if the hashtable was modified 1040: * @throws NoSuchElementException if there is none 1041: */ 1042: public Object next() 1043: { 1044: if (knownMod != modCount) 1045: throw new ConcurrentModificationException(); 1046: if (count == 0) 1047: throw new NoSuchElementException(); 1048: count--; 1049: HashEntry e = next; 1050: 1051: while (e == null) 1052: e = buckets[--idx]; 1053: 1054: next = e.next; 1055: last = e; 1056: if (type == VALUES) 1057: return e.value; 1058: if (type == KEYS) 1059: return e.key; 1060: return e; 1061: } 1062: 1063: /** 1064: * Removes from the backing Hashtable the last element which was fetched 1065: * with the <code>next()</code> method. 1066: * @throws ConcurrentModificationException if the hashtable was modified 1067: * @throws IllegalStateException if called when there is no last element 1068: */ 1069: public void remove() 1070: { 1071: if (knownMod != modCount) 1072: throw new ConcurrentModificationException(); 1073: if (last == null) 1074: throw new IllegalStateException(); 1075: 1076: Hashtable.this.remove(last.key); 1077: last = null; 1078: knownMod++; 1079: } 1080: } // class HashIterator 1081: 1082: 1083: /** 1084: * Enumeration view of this Hashtable, providing sequential access to its 1085: * elements; this implementation is parameterized to provide access either 1086: * to the keys or to the values in the Hashtable. 1087: * 1088: * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table 1089: * as this could cause a rehash and we'd completely lose our place. Even 1090: * without a rehash, it is undetermined if a new element added would 1091: * appear in the enumeration. The spec says nothing about this, but 1092: * the "Java Class Libraries" book infers that modifications to the 1093: * hashtable during enumeration causes indeterminate results. Don't do it! 1094: * 1095: * @author Jon Zeppieri 1096: */ 1097: private final class Enumerator implements Enumeration 1098: { 1099: /** 1100: * The type of this Iterator: {@link #KEYS} or {@link #VALUES}. 1101: */ 1102: final int type; 1103: /** The number of elements remaining to be returned by next(). */ 1104: int count = size; 1105: /** Current index in the physical hash table. */ 1106: int idx = buckets.length; 1107: /** 1108: * Entry which will be returned by the next nextElement() call. It is 1109: * set if we are iterating through a bucket with multiple entries, or null 1110: * if we must look in the next bucket. 1111: */ 1112: HashEntry next; 1113: 1114: /** 1115: * Construct the enumeration. 1116: * @param type either {@link #KEYS} or {@link #VALUES}. 1117: */ 1118: Enumerator(int type) 1119: { 1120: this.type = type; 1121: } 1122: 1123: /** 1124: * Checks whether more elements remain in the enumeration. 1125: * @return true if nextElement() will not fail. 1126: */ 1127: public boolean hasMoreElements() 1128: { 1129: return count > 0; 1130: } 1131: 1132: /** 1133: * Returns the next element. 1134: * @return the next element 1135: * @throws NoSuchElementException if there is none. 1136: */ 1137: public Object nextElement() 1138: { 1139: if (count == 0) 1140: throw new NoSuchElementException("Hashtable Enumerator"); 1141: count--; 1142: HashEntry e = next; 1143: 1144: while (e == null) 1145: e = buckets[--idx]; 1146: 1147: next = e.next; 1148: return type == VALUES ? e.value : e.key; 1149: } 1150: } // class Enumerator 1151: } // class Hashtable