GNU Classpath (0.19) | ||
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 Free Software Foundation, Inc. 4: 5: This file is part of GNU Classpath. 6: 7: GNU Classpath is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU Classpath is distributed in the hope that it will be useful, but 13: WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15: General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU Classpath; see the file COPYING. If not, write to the 19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20: 02110-1301 USA. 21: 22: Linking this library statically or dynamically with other modules is 23: making a combined work based on this library. Thus, the terms and 24: conditions of the GNU General Public License cover the whole 25: combination. 26: 27: As a special exception, the copyright holders of this library give you 28: permission to link this library with independent modules to produce an 29: executable, regardless of the license terms of these independent 30: modules, and to copy and distribute the resulting executable under 31: terms of your choice, provided that you also meet, for each linked 32: independent module, the terms and conditions of the license of that 33: module. An independent module is a module which is not derived from 34: or based on this library. If you modify this library, you may extend 35: this exception to your version of the library, but you are not 36: obligated to do so. If you do not wish to do so, delete this 37: exception statement from your version. */ 38: 39: package java.util; 40: 41: import java.io.IOException; 42: import java.io.ObjectInputStream; 43: import java.io.ObjectOutputStream; 44: import java.io.Serializable; 45: 46: // NOTE: This implementation is very similar to that of HashMap. If you fix 47: // a bug in here, chances are you should make a similar change to the HashMap 48: // code. 49: 50: /** 51: * A class which implements a hashtable data structure. 52: * <p> 53: * 54: * This implementation of Hashtable uses a hash-bucket approach. That is: 55: * linear probing and rehashing is avoided; instead, each hashed value maps 56: * to a simple linked-list which, in the best case, only has one node. 57: * Assuming a large enough table, low enough load factor, and / or well 58: * implemented hashCode() methods, Hashtable should provide O(1) 59: * insertion, deletion, and searching of keys. Hashtable is O(n) in 60: * the worst case for all of these (if all keys hash to the same bucket). 61: * <p> 62: * 63: * This is a JDK-1.2 compliant implementation of Hashtable. As such, it 64: * belongs, partially, to the Collections framework (in that it implements 65: * Map). For backwards compatibility, it inherits from the obsolete and 66: * utterly useless Dictionary class. 67: * <p> 68: * 69: * Being a hybrid of old and new, Hashtable has methods which provide redundant 70: * capability, but with subtle and even crucial differences. 71: * For example, one can iterate over various aspects of a Hashtable with 72: * either an Iterator (which is the JDK-1.2 way of doing things) or with an 73: * Enumeration. The latter can end up in an undefined state if the Hashtable 74: * changes while the Enumeration is open. 75: * <p> 76: * 77: * Unlike HashMap, Hashtable does not accept `null' as a key value. Also, 78: * all accesses are synchronized: in a single thread environment, this is 79: * expensive, but in a multi-thread environment, this saves you the effort 80: * of extra synchronization. However, the old-style enumerators are not 81: * synchronized, because they can lead to unspecified behavior even if 82: * they were synchronized. You have been warned. 83: * <p> 84: * 85: * The iterators are <i>fail-fast</i>, meaning that any structural 86: * modification, except for <code>remove()</code> called on the iterator 87: * itself, cause the iterator to throw a 88: * <code>ConcurrentModificationException</code> rather than exhibit 89: * non-deterministic behavior. 90: * 91: * @author Jon Zeppieri 92: * @author Warren Levy 93: * @author Bryce McKinlay 94: * @author Eric Blake (ebb9@email.byu.edu) 95: * @see HashMap 96: * @see TreeMap 97: * @see IdentityHashMap 98: * @see LinkedHashMap 99: * @since 1.0 100: * @status updated to 1.4 101: */ 102: public class Hashtable extends Dictionary 103: implements Map, Cloneable, Serializable 104: { 105: // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the 106: // comments in vm/reference/java/lang/Runtime for implications of this fact. 107: 108: /** Default number of buckets. This is the value the JDK 1.3 uses. Some 109: * early documentation specified this value as 101. That is incorrect. 110: */ 111: private static final int DEFAULT_CAPACITY = 11; 112: 113: /** An "enum" of iterator types. */ 114: // Package visible for use by nested classes. 115: static final int KEYS = 0, 116: VALUES = 1, 117: ENTRIES = 2; 118: 119: /** 120: * The default load factor; this is explicitly specified by the spec. 121: */ 122: private static final float DEFAULT_LOAD_FACTOR = 0.75f; 123: 124: /** 125: * Compatible with JDK 1.0+. 126: */ 127: private static final long serialVersionUID = 1421746759512286392L; 128: 129: /** 130: * The rounded product of the capacity and the load factor; when the number 131: * of elements exceeds the threshold, the Hashtable calls 132: * <code>rehash()</code>. 133: * @serial 134: */ 135: private int threshold; 136: 137: /** 138: * Load factor of this Hashtable: used in computing the threshold. 139: * @serial 140: */ 141: private final float loadFactor; 142: 143: /** 144: * Array containing the actual key-value mappings. 145: */ 146: // Package visible for use by nested classes. 147: transient HashEntry[] buckets; 148: 149: /** 150: * Counts the number of modifications this Hashtable has undergone, used 151: * by Iterators to know when to throw ConcurrentModificationExceptions. 152: */ 153: // Package visible for use by nested classes. 154: transient int modCount; 155: 156: /** 157: * The size of this Hashtable: denotes the number of key-value pairs. 158: */ 159: // Package visible for use by nested classes. 160: transient int size; 161: 162: /** 163: * The cache for {@link #keySet()}. 164: */ 165: private transient Set keys; 166: 167: /** 168: * The cache for {@link #values()}. 169: */ 170: private transient Collection values; 171: 172: /** 173: * The cache for {@link #entrySet()}. 174: */ 175: private transient Set entries; 176: 177: /** 178: * Class to represent an entry in the hash table. Holds a single key-value 179: * pair. A Hashtable Entry is identical to a HashMap Entry, except that 180: * `null' is not allowed for keys and values. 181: */ 182: private static final class HashEntry extends AbstractMap.BasicMapEntry 183: { 184: /** The next entry in the linked list. */ 185: HashEntry next; 186: 187: /** 188: * Simple constructor. 189: * @param key the key, already guaranteed non-null 190: * @param value the value, already guaranteed non-null 191: */ 192: HashEntry(Object key, Object value) 193: { 194: super(key, value); 195: } 196: 197: /** 198: * Resets the value. 199: * @param newVal the new value 200: * @return the prior value 201: * @throws NullPointerException if <code>newVal</code> is null 202: */ 203: public Object setValue(Object newVal) 204: { 205: if (newVal == null) 206: throw new NullPointerException(); 207: return super.setValue(newVal); 208: } 209: } 210: 211: /** 212: * Construct a new Hashtable with the default capacity (11) and the default 213: * load factor (0.75). 214: */ 215: public Hashtable() 216: { 217: this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); 218: } 219: 220: /** 221: * Construct a new Hashtable from the given Map, with initial capacity 222: * the greater of the size of <code>m</code> or the default of 11. 223: * <p> 224: * 225: * Every element in Map m will be put into this new Hashtable. 226: * 227: * @param m a Map whose key / value pairs will be put into 228: * the new Hashtable. <b>NOTE: key / value pairs 229: * are not cloned in this constructor.</b> 230: * @throws NullPointerException if m is null, or if m contains a mapping 231: * to or from `null'. 232: * @since 1.2 233: */ 234: public Hashtable(Map m) 235: { 236: this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); 237: putAll(m); 238: } 239: 240: /** 241: * Construct a new Hashtable with a specific inital capacity and 242: * default load factor of 0.75. 243: * 244: * @param initialCapacity the initial capacity of this Hashtable (>= 0) 245: * @throws IllegalArgumentException if (initialCapacity < 0) 246: */ 247: public Hashtable(int initialCapacity) 248: { 249: this(initialCapacity, DEFAULT_LOAD_FACTOR); 250: } 251: 252: /** 253: * Construct a new Hashtable with a specific initial capacity and 254: * load factor. 255: * 256: * @param initialCapacity the initial capacity (>= 0) 257: * @param loadFactor the load factor (> 0, not NaN) 258: * @throws IllegalArgumentException if (initialCapacity < 0) || 259: * ! (loadFactor > 0.0) 260: */ 261: public Hashtable(int initialCapacity, float loadFactor) 262: { 263: if (initialCapacity < 0) 264: throw new IllegalArgumentException("Illegal Capacity: " 265: + initialCapacity); 266: if (! (loadFactor > 0)) // check for NaN too 267: throw new IllegalArgumentException("Illegal Load: " + loadFactor); 268: 269: if (initialCapacity == 0) 270: initialCapacity = 1; 271: buckets = new HashEntry[initialCapacity]; 272: this.loadFactor = loadFactor; 273: threshold = (int) (initialCapacity * loadFactor); 274: } 275: 276: /** 277: * Returns the number of key-value mappings currently in this hashtable. 278: * @return the size 279: */ 280: public synchronized int size() 281: { 282: return size; 283: } 284: 285: /** 286: * Returns true if there are no key-value mappings currently in this table. 287: * @return <code>size() == 0</code> 288: */ 289: public synchronized boolean isEmpty() 290: { 291: return size == 0; 292: } 293: 294: /** 295: * Return an enumeration of the keys of this table. There's no point 296: * in synchronizing this, as you have already been warned that the 297: * enumeration is not specified to be thread-safe. 298: * 299: * @return the keys 300: * @see #elements() 301: * @see #keySet() 302: */ 303: public Enumeration keys() 304: { 305: return new Enumerator(KEYS); 306: } 307: 308: /** 309: * Return an enumeration of the values of this table. There's no point 310: * in synchronizing this, as you have already been warned that the 311: * enumeration is not specified to be thread-safe. 312: * 313: * @return the values 314: * @see #keys() 315: * @see #values() 316: */ 317: public Enumeration elements() 318: { 319: return new Enumerator(VALUES); 320: } 321: 322: /** 323: * Returns true if this Hashtable contains a value <code>o</code>, 324: * such that <code>o.equals(value)</code>. This is the same as 325: * <code>containsValue()</code>, and is O(n). 326: * <p> 327: * 328: * @param value the value to search for in this Hashtable 329: * @return true if at least one key maps to the value 330: * @throws NullPointerException if <code>value</code> is null 331: * @see #containsValue(Object) 332: * @see #containsKey(Object) 333: */ 334: public synchronized boolean contains(Object value) 335: { 336: for (int i = buckets.length - 1; i >= 0; i--) 337: { 338: HashEntry e = buckets[i]; 339: while (e != null) 340: { 341: if (value.equals(e.value)) 342: return true; 343: e = e.next; 344: } 345: } 346: 347: // Must throw on null argument even if the table is empty 348: if (value == null) 349: throw new NullPointerException(); 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 (key.equals(e.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 (key.equals(e.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 (key.equals(e.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 (key.equals(e.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 (o.equals(e)) 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
GNU Classpath (0.19) |