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