| GNU Classpath (0.95) | |
| Frames | No Frames |
1: /* Hashtable.java -- a class providing a basic hashtable data structure, 2: mapping Object --> Object 3: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 4: Free Software Foundation, Inc. 5: 6: This file is part of GNU Classpath. 7: 8: GNU Classpath is free software; you can redistribute it and/or modify 9: it under the terms of the GNU General Public License as published by 10: the Free Software Foundation; either version 2, or (at your option) 11: any later version. 12: 13: GNU Classpath is distributed in the hope that it will be useful, but 14: WITHOUT ANY WARRANTY; without even the implied warranty of 15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16: General Public License for more details. 17: 18: You should have received a copy of the GNU General Public License 19: along with GNU Classpath; see the file COPYING. If not, write to the 20: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 21: 02110-1301 USA. 22: 23: Linking this library statically or dynamically with other modules is 24: making a combined work based on this library. Thus, the terms and 25: conditions of the GNU General Public License cover the whole 26: combination. 27: 28: As a special exception, the copyright holders of this library give you 29: permission to link this library with independent modules to produce an 30: executable, regardless of the license terms of these independent 31: modules, and to copy and distribute the resulting executable under 32: terms of your choice, provided that you also meet, for each linked 33: independent module, the terms and conditions of the license of that 34: module. An independent module is a module which is not derived from 35: or based on this library. If you modify this library, you may extend 36: this exception to your version of the library, but you are not 37: obligated to do so. If you do not wish to do so, delete this 38: exception statement from your version. */ 39: 40: package java.util; 41: 42: import java.io.IOException; 43: import java.io.ObjectInputStream; 44: import java.io.ObjectOutputStream; 45: import java.io.Serializable; 46: 47: // NOTE: This implementation is very similar to that of HashMap. If you fix 48: // a bug in here, chances are you should make a similar change to the HashMap 49: // code. 50: 51: /** 52: * A class which implements a hashtable data structure. 53: * <p> 54: * 55: * This implementation of Hashtable uses a hash-bucket approach. That is: 56: * linear probing and rehashing is avoided; instead, each hashed value maps 57: * to a simple linked-list which, in the best case, only has one node. 58: * Assuming a large enough table, low enough load factor, and / or well 59: * implemented hashCode() methods, Hashtable should provide O(1) 60: * insertion, deletion, and searching of keys. Hashtable is O(n) in 61: * the worst case for all of these (if all keys hash to the same bucket). 62: * <p> 63: * 64: * This is a JDK-1.2 compliant implementation of Hashtable. As such, it 65: * belongs, partially, to the Collections framework (in that it implements 66: * Map). For backwards compatibility, it inherits from the obsolete and 67: * utterly useless Dictionary class. 68: * <p> 69: * 70: * Being a hybrid of old and new, Hashtable has methods which provide redundant 71: * capability, but with subtle and even crucial differences. 72: * For example, one can iterate over various aspects of a Hashtable with 73: * either an Iterator (which is the JDK-1.2 way of doing things) or with an 74: * Enumeration. The latter can end up in an undefined state if the Hashtable 75: * changes while the Enumeration is open. 76: * <p> 77: * 78: * Unlike HashMap, Hashtable does not accept `null' as a key value. Also, 79: * all accesses are synchronized: in a single thread environment, this is 80: * expensive, but in a multi-thread environment, this saves you the effort 81: * of extra synchronization. However, the old-style enumerators are not 82: * synchronized, because they can lead to unspecified behavior even if 83: * they were synchronized. You have been warned. 84: * <p> 85: * 86: * The iterators are <i>fail-fast</i>, meaning that any structural 87: * modification, except for <code>remove()</code> called on the iterator 88: * itself, cause the iterator to throw a 89: * <code>ConcurrentModificationException</code> rather than exhibit 90: * non-deterministic behavior. 91: * 92: * @author Jon Zeppieri 93: * @author Warren Levy 94: * @author Bryce McKinlay 95: * @author Eric Blake (ebb9@email.byu.edu) 96: * @see HashMap 97: * @see TreeMap 98: * @see IdentityHashMap 99: * @see LinkedHashMap 100: * @since 1.0 101: * @status updated to 1.4 102: */ 103: public class Hashtable<K, V> extends Dictionary<K, V> 104: implements Map<K, V>, Cloneable, Serializable 105: { 106: // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the 107: // comments in vm/reference/java/lang/Runtime for implications of this fact. 108: 109: /** Default number of buckets. This is the value the JDK 1.3 uses. Some 110: * early documentation specified this value as 101. That is incorrect. 111: */ 112: private static final int DEFAULT_CAPACITY = 11; 113: 114: /** 115: * The default load factor; this is explicitly specified by the spec. 116: */ 117: private static final float DEFAULT_LOAD_FACTOR = 0.75f; 118: 119: /** 120: * Compatible with JDK 1.0+. 121: */ 122: private static final long serialVersionUID = 1421746759512286392L; 123: 124: /** 125: * The rounded product of the capacity and the load factor; when the number 126: * of elements exceeds the threshold, the Hashtable calls 127: * <code>rehash()</code>. 128: * @serial 129: */ 130: private int threshold; 131: 132: /** 133: * Load factor of this Hashtable: used in computing the threshold. 134: * @serial 135: */ 136: private final float loadFactor; 137: 138: /** 139: * Array containing the actual key-value mappings. 140: */ 141: // Package visible for use by nested classes. 142: transient HashEntry<K, V>[] buckets; 143: 144: /** 145: * Counts the number of modifications this Hashtable has undergone, used 146: * by Iterators to know when to throw ConcurrentModificationExceptions. 147: */ 148: // Package visible for use by nested classes. 149: transient int modCount; 150: 151: /** 152: * The size of this Hashtable: denotes the number of key-value pairs. 153: */ 154: // Package visible for use by nested classes. 155: transient int size; 156: 157: /** 158: * The cache for {@link #keySet()}. 159: */ 160: private transient Set<K> keys; 161: 162: /** 163: * The cache for {@link #values()}. 164: */ 165: private transient Collection<V> values; 166: 167: /** 168: * The cache for {@link #entrySet()}. 169: */ 170: private transient Set<Map.Entry<K, V>> entries; 171: 172: /** 173: * Class to represent an entry in the hash table. Holds a single key-value 174: * pair. A Hashtable Entry is identical to a HashMap Entry, except that 175: * `null' is not allowed for keys and values. 176: */ 177: private static final class HashEntry<K, V> 178: extends AbstractMap.SimpleEntry<K, V> 179: { 180: /** The next entry in the linked list. */ 181: HashEntry<K, V> next; 182: 183: /** 184: * Simple constructor. 185: * @param key the key, already guaranteed non-null 186: * @param value the value, already guaranteed non-null 187: */ 188: HashEntry(K key, V value) 189: { 190: super(key, value); 191: } 192: 193: /** 194: * Resets the value. 195: * @param newVal the new value 196: * @return the prior value 197: * @throws NullPointerException if <code>newVal</code> is null 198: */ 199: public V setValue(V newVal) 200: { 201: if (newVal == null) 202: throw new NullPointerException(); 203: return super.setValue(newVal); 204: } 205: } 206: 207: /** 208: * Construct a new Hashtable with the default capacity (11) and the default 209: * load factor (0.75). 210: */ 211: public Hashtable() 212: { 213: this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); 214: } 215: 216: /** 217: * Construct a new Hashtable from the given Map, with initial capacity 218: * the greater of the size of <code>m</code> or the default of 11. 219: * <p> 220: * 221: * Every element in Map m will be put into this new Hashtable. 222: * 223: * @param m a Map whose key / value pairs will be put into 224: * the new Hashtable. <b>NOTE: key / value pairs 225: * are not cloned in this constructor.</b> 226: * @throws NullPointerException if m is null, or if m contains a mapping 227: * to or from `null'. 228: * @since 1.2 229: */ 230: public Hashtable(Map<? extends K, ? extends V> m) 231: { 232: this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); 233: putAll(m); 234: } 235: 236: /** 237: * Construct a new Hashtable with a specific inital capacity and 238: * default load factor of 0.75. 239: * 240: * @param initialCapacity the initial capacity of this Hashtable (>= 0) 241: * @throws IllegalArgumentException if (initialCapacity < 0) 242: */ 243: public Hashtable(int initialCapacity) 244: { 245: this(initialCapacity, DEFAULT_LOAD_FACTOR); 246: } 247: 248: /** 249: * Construct a new Hashtable with a specific initial capacity and 250: * load factor. 251: * 252: * @param initialCapacity the initial capacity (>= 0) 253: * @param loadFactor the load factor (> 0, not NaN) 254: * @throws IllegalArgumentException if (initialCapacity < 0) || 255: * ! (loadFactor > 0.0) 256: */ 257: public Hashtable(int initialCapacity, float loadFactor) 258: { 259: if (initialCapacity < 0) 260: throw new IllegalArgumentException("Illegal Capacity: " 261: + initialCapacity); 262: if (! (loadFactor > 0)) // check for NaN too 263: throw new IllegalArgumentException("Illegal Load: " + loadFactor); 264: 265: if (initialCapacity == 0) 266: initialCapacity = 1; 267: buckets = (HashEntry<K, V>[]) new HashEntry[initialCapacity]; 268: this.loadFactor = loadFactor; 269: threshold = (int) (initialCapacity * loadFactor); 270: } 271: 272: /** 273: * Returns the number of key-value mappings currently in this hashtable. 274: * @return the size 275: */ 276: public synchronized int size() 277: { 278: return size; 279: } 280: 281: /** 282: * Returns true if there are no key-value mappings currently in this table. 283: * @return <code>size() == 0</code> 284: */ 285: public synchronized boolean isEmpty() 286: { 287: return size == 0; 288: } 289: 290: /** 291: * Return an enumeration of the keys of this table. There's no point 292: * in synchronizing this, as you have already been warned that the 293: * enumeration is not specified to be thread-safe. 294: * 295: * @return the keys 296: * @see #elements() 297: * @see #keySet() 298: */ 299: public Enumeration<K> keys() 300: { 301: return new KeyEnumerator(); 302: } 303: 304: /** 305: * Return an enumeration of the values of this table. There's no point 306: * in synchronizing this, as you have already been warned that the 307: * enumeration is not specified to be thread-safe. 308: * 309: * @return the values 310: * @see #keys() 311: * @see #values() 312: */ 313: public Enumeration<V> elements() 314: { 315: return new ValueEnumerator(); 316: } 317: 318: /** 319: * Returns true if this Hashtable contains a value <code>o</code>, 320: * such that <code>o.equals(value)</code>. This is the same as 321: * <code>containsValue()</code>, and is O(n). 322: * <p> 323: * 324: * @param value the value to search for in this Hashtable 325: * @return true if at least one key maps to the value 326: * @throws NullPointerException if <code>value</code> is null 327: * @see #containsValue(Object) 328: * @see #containsKey(Object) 329: */ 330: public synchronized boolean contains(Object value) 331: { 332: if (value == null) 333: throw new NullPointerException(); 334: 335: for (int i = buckets.length - 1; i >= 0; i--) 336: { 337: HashEntry<K, V> e = buckets[i]; 338: while (e != null) 339: { 340: if (e.value.equals(value)) 341: return true; 342: e = e.next; 343: } 344: } 345: 346: return false; 347: } 348: 349: /** 350: * Returns true if this Hashtable contains a value <code>o</code>, such that 351: * <code>o.equals(value)</code>. This is the new API for the old 352: * <code>contains()</code>. 353: * 354: * @param value the value to search for in this Hashtable 355: * @return true if at least one key maps to the value 356: * @see #contains(Object) 357: * @see #containsKey(Object) 358: * @throws NullPointerException if <code>value</code> is null 359: * @since 1.2 360: */ 361: public boolean containsValue(Object value) 362: { 363: // Delegate to older method to make sure code overriding it continues 364: // to work. 365: return contains(value); 366: } 367: 368: /** 369: * Returns true if the supplied object <code>equals()</code> a key 370: * in this Hashtable. 371: * 372: * @param key the key to search for in this Hashtable 373: * @return true if the key is in the table 374: * @throws NullPointerException if key is null 375: * @see #containsValue(Object) 376: */ 377: public synchronized boolean containsKey(Object key) 378: { 379: int idx = hash(key); 380: HashEntry<K, V> e = buckets[idx]; 381: while (e != null) 382: { 383: if (e.key.equals(key)) 384: return true; 385: e = e.next; 386: } 387: return false; 388: } 389: 390: /** 391: * Return the value in this Hashtable associated with the supplied key, 392: * or <code>null</code> if the key maps to nothing. 393: * 394: * @param key the key for which to fetch an associated value 395: * @return what the key maps to, if present 396: * @throws NullPointerException if key is null 397: * @see #put(Object, Object) 398: * @see #containsKey(Object) 399: */ 400: public synchronized V get(Object key) 401: { 402: int idx = hash(key); 403: HashEntry<K, V> e = buckets[idx]; 404: while (e != null) 405: { 406: if (e.key.equals(key)) 407: return e.value; 408: e = e.next; 409: } 410: return null; 411: } 412: 413: /** 414: * Puts the supplied value into the Map, mapped by the supplied key. 415: * Neither parameter may be null. The value may be retrieved by any 416: * object which <code>equals()</code> this key. 417: * 418: * @param key the key used to locate the value 419: * @param value the value to be stored in the table 420: * @return the prior mapping of the key, or null if there was none 421: * @throws NullPointerException if key or value is null 422: * @see #get(Object) 423: * @see Object#equals(Object) 424: */ 425: public synchronized V put(K key, V value) 426: { 427: int idx = hash(key); 428: HashEntry<K, V> e = buckets[idx]; 429: 430: // Check if value is null since it is not permitted. 431: if (value == null) 432: throw new NullPointerException(); 433: 434: while (e != null) 435: { 436: if (e.key.equals(key)) 437: { 438: // Bypass e.setValue, since we already know value is non-null. 439: V r = e.value; 440: e.value = value; 441: return r; 442: } 443: else 444: { 445: e = e.next; 446: } 447: } 448: 449: // At this point, we know we need to add a new entry. 450: modCount++; 451: if (++size > threshold) 452: { 453: rehash(); 454: // Need a new hash value to suit the bigger table. 455: idx = hash(key); 456: } 457: 458: e = new HashEntry<K, V>(key, value); 459: 460: e.next = buckets[idx]; 461: buckets[idx] = e; 462: 463: return null; 464: } 465: 466: /** 467: * Removes from the table and returns the value which is mapped by the 468: * supplied key. If the key maps to nothing, then the table remains 469: * unchanged, and <code>null</code> is returned. 470: * 471: * @param key the key used to locate the value to remove 472: * @return whatever the key mapped to, if present 473: */ 474: public synchronized V remove(Object key) 475: { 476: int idx = hash(key); 477: HashEntry<K, V> e = buckets[idx]; 478: HashEntry<K, V> last = null; 479: 480: while (e != null) 481: { 482: if (e.key.equals(key)) 483: { 484: modCount++; 485: if (last == null) 486: buckets[idx] = e.next; 487: else 488: last.next = e.next; 489: size--; 490: return e.value; 491: } 492: last = e; 493: e = e.next; 494: } 495: return null; 496: } 497: 498: /** 499: * Copies all elements of the given map into this hashtable. However, no 500: * mapping can contain null as key or value. If this table already has 501: * a mapping for a key, the new mapping replaces the current one. 502: * 503: * @param m the map to be hashed into this 504: * @throws NullPointerException if m is null, or contains null keys or values 505: */ 506: public synchronized void putAll(Map<? extends K, ? extends V> m) 507: { 508: final Map<K,V> addMap = (Map<K,V>) m; 509: final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); 510: while (it.hasNext()) 511: { 512: final Map.Entry<K,V> e = it.next(); 513: // Optimize in case the Entry is one of our own. 514: if (e instanceof AbstractMap.SimpleEntry) 515: { 516: AbstractMap.SimpleEntry<? extends K, ? extends V> entry 517: = (AbstractMap.SimpleEntry<? extends K, ? extends V>) e; 518: put(entry.key, entry.value); 519: } 520: else 521: { 522: put(e.getKey(), e.getValue()); 523: } 524: } 525: } 526: 527: /** 528: * Clears the hashtable so it has no keys. This is O(1). 529: */ 530: public synchronized void clear() 531: { 532: if (size > 0) 533: { 534: modCount++; 535: Arrays.fill(buckets, null); 536: size = 0; 537: } 538: } 539: 540: /** 541: * Returns a shallow clone of this Hashtable. The Map itself is cloned, 542: * but its contents are not. This is O(n). 543: * 544: * @return the clone 545: */ 546: public synchronized Object clone() 547: { 548: Hashtable<K, V> copy = null; 549: try 550: { 551: copy = (Hashtable<K, V>) super.clone(); 552: } 553: catch (CloneNotSupportedException x) 554: { 555: // This is impossible. 556: } 557: copy.buckets = (HashEntry<K, V>[]) new HashEntry[buckets.length]; 558: copy.putAllInternal(this); 559: // Clear the caches. 560: copy.keys = null; 561: copy.values = null; 562: copy.entries = null; 563: return copy; 564: } 565: 566: /** 567: * Converts this Hashtable to a String, surrounded by braces, and with 568: * key/value pairs listed with an equals sign between, separated by a 569: * comma and space. For example, <code>"{a=1, b=2}"</code>.<p> 570: * 571: * NOTE: if the <code>toString()</code> method of any key or value 572: * throws an exception, this will fail for the same reason. 573: * 574: * @return the string representation 575: */ 576: public synchronized String toString() 577: { 578: // Since we are already synchronized, and entrySet().iterator() 579: // would repeatedly re-lock/release the monitor, we directly use the 580: // unsynchronized EntryIterator instead. 581: Iterator<Map.Entry<K, V>> entries = new EntryIterator(); 582: StringBuffer r = new StringBuffer("{"); 583: for (int pos = size; pos > 0; pos--) 584: { 585: r.append(entries.next()); 586: if (pos > 1) 587: r.append(", "); 588: } 589: r.append("}"); 590: return r.toString(); 591: } 592: 593: /** 594: * Returns a "set view" of this Hashtable's keys. The set is backed by 595: * the hashtable, so changes in one show up in the other. The set supports 596: * element removal, but not element addition. The set is properly 597: * synchronized on the original hashtable. Sun has not documented the 598: * proper interaction of null with this set, but has inconsistent behavior 599: * in the JDK. Therefore, in this implementation, contains, remove, 600: * containsAll, retainAll, removeAll, and equals just ignore a null key 601: * rather than throwing a {@link NullPointerException}. 602: * 603: * @return a set view of the keys 604: * @see #values() 605: * @see #entrySet() 606: * @since 1.2 607: */ 608: public Set<K> keySet() 609: { 610: if (keys == null) 611: { 612: // Create a synchronized AbstractSet with custom implementations of 613: // those methods that can be overridden easily and efficiently. 614: Set<K> r = new AbstractSet<K>() 615: { 616: public int size() 617: { 618: return size; 619: } 620: 621: public Iterator<K> iterator() 622: { 623: return new KeyIterator(); 624: } 625: 626: public void clear() 627: { 628: Hashtable.this.clear(); 629: } 630: 631: public boolean contains(Object o) 632: { 633: if (o == null) 634: return false; 635: return containsKey(o); 636: } 637: 638: public boolean remove(Object o) 639: { 640: return Hashtable.this.remove(o) != null; 641: } 642: }; 643: // We must specify the correct object to synchronize upon, hence the 644: // use of a non-public API 645: keys = new Collections.SynchronizedSet<K>(this, r); 646: } 647: return keys; 648: } 649: 650: /** 651: * Returns a "collection view" (or "bag view") of this Hashtable's values. 652: * The collection is backed by the hashtable, so changes in one show up 653: * in the other. The collection supports element removal, but not element 654: * addition. The collection is properly synchronized on the original 655: * hashtable. Sun has not documented the proper interaction of null with 656: * this set, but has inconsistent behavior in the JDK. Therefore, in this 657: * implementation, contains, remove, containsAll, retainAll, removeAll, and 658: * equals just ignore a null value rather than throwing a 659: * {@link NullPointerException}. 660: * 661: * @return a bag view of the values 662: * @see #keySet() 663: * @see #entrySet() 664: * @since 1.2 665: */ 666: public Collection<V> values() 667: { 668: if (values == null) 669: { 670: // We don't bother overriding many of the optional methods, as doing so 671: // wouldn't provide any significant performance advantage. 672: Collection<V> r = new AbstractCollection<V>() 673: { 674: public int size() 675: { 676: return size; 677: } 678: 679: public Iterator<V> iterator() 680: { 681: return new ValueIterator(); 682: } 683: 684: public void clear() 685: { 686: Hashtable.this.clear(); 687: } 688: }; 689: // We must specify the correct object to synchronize upon, hence the 690: // use of a non-public API 691: values = new Collections.SynchronizedCollection<V>(this, r); 692: } 693: return values; 694: } 695: 696: /** 697: * Returns a "set view" of this Hashtable's entries. The set is backed by 698: * the hashtable, so changes in one show up in the other. The set supports 699: * element removal, but not element addition. The set is properly 700: * synchronized on the original hashtable. Sun has not documented the 701: * proper interaction of null with this set, but has inconsistent behavior 702: * in the JDK. Therefore, in this implementation, contains, remove, 703: * containsAll, retainAll, removeAll, and equals just ignore a null entry, 704: * or an entry with a null key or value, rather than throwing a 705: * {@link NullPointerException}. However, calling entry.setValue(null) 706: * will fail. 707: * <p> 708: * 709: * Note that the iterators for all three views, from keySet(), entrySet(), 710: * and values(), traverse the hashtable in the same sequence. 711: * 712: * @return a set view of the entries 713: * @see #keySet() 714: * @see #values() 715: * @see Map.Entry 716: * @since 1.2 717: */ 718: public Set<Map.Entry<K, V>> entrySet() 719: { 720: if (entries == null) 721: { 722: // Create an AbstractSet with custom implementations of those methods 723: // that can be overridden easily and efficiently. 724: Set<Map.Entry<K, V>> r = new AbstractSet<Map.Entry<K, V>>() 725: { 726: public int size() 727: { 728: return size; 729: } 730: 731: public Iterator<Map.Entry<K, V>> iterator() 732: { 733: return new EntryIterator(); 734: } 735: 736: public void clear() 737: { 738: Hashtable.this.clear(); 739: } 740: 741: public boolean contains(Object o) 742: { 743: return getEntry(o) != null; 744: } 745: 746: public boolean remove(Object o) 747: { 748: HashEntry<K, V> e = getEntry(o); 749: if (e != null) 750: { 751: Hashtable.this.remove(e.key); 752: return true; 753: } 754: return false; 755: } 756: }; 757: // We must specify the correct object to synchronize upon, hence the 758: // use of a non-public API 759: entries = new Collections.SynchronizedSet<Map.Entry<K, V>>(this, r); 760: } 761: return entries; 762: } 763: 764: /** 765: * Returns true if this Hashtable equals the supplied Object <code>o</code>. 766: * As specified by Map, this is: 767: * <code> 768: * (o instanceof Map) && entrySet().equals(((Map) o).entrySet()); 769: * </code> 770: * 771: * @param o the object to compare to 772: * @return true if o is an equal map 773: * @since 1.2 774: */ 775: public boolean equals(Object o) 776: { 777: // no need to synchronize, entrySet().equals() does that. 778: if (o == this) 779: return true; 780: if (!(o instanceof Map)) 781: return false; 782: 783: return entrySet().equals(((Map) o).entrySet()); 784: } 785: 786: /** 787: * Returns the hashCode for this Hashtable. As specified by Map, this is 788: * the sum of the hashCodes of all of its Map.Entry objects 789: * 790: * @return the sum of the hashcodes of the entries 791: * @since 1.2 792: */ 793: public synchronized int hashCode() 794: { 795: // Since we are already synchronized, and entrySet().iterator() 796: // would repeatedly re-lock/release the monitor, we directly use the 797: // unsynchronized EntryIterator instead. 798: Iterator<Map.Entry<K, V>> itr = new EntryIterator(); 799: int hashcode = 0; 800: for (int pos = size; pos > 0; pos--) 801: hashcode += itr.next().hashCode(); 802: 803: return hashcode; 804: } 805: 806: /** 807: * Helper method that returns an index in the buckets array for `key' 808: * based on its hashCode(). 809: * 810: * @param key the key 811: * @return the bucket number 812: * @throws NullPointerException if key is null 813: */ 814: private int hash(Object key) 815: { 816: // Note: Inline Math.abs here, for less method overhead, and to avoid 817: // a bootstrap dependency, since Math relies on native methods. 818: int hash = key.hashCode() % buckets.length; 819: return hash < 0 ? -hash : hash; 820: } 821: 822: /** 823: * Helper method for entrySet(), which matches both key and value 824: * simultaneously. Ignores null, as mentioned in entrySet(). 825: * 826: * @param o the entry to match 827: * @return the matching entry, if found, or null 828: * @see #entrySet() 829: */ 830: // Package visible, for use in nested classes. 831: HashEntry<K, V> getEntry(Object o) 832: { 833: if (! (o instanceof Map.Entry)) 834: return null; 835: K key = ((Map.Entry<K, V>) o).getKey(); 836: if (key == null) 837: return null; 838: 839: int idx = hash(key); 840: HashEntry<K, V> e = buckets[idx]; 841: while (e != null) 842: { 843: if (e.equals(o)) 844: return e; 845: e = e.next; 846: } 847: return null; 848: } 849: 850: /** 851: * A simplified, more efficient internal implementation of putAll(). clone() 852: * should not call putAll or put, in order to be compatible with the JDK 853: * implementation with respect to subclasses. 854: * 855: * @param m the map to initialize this from 856: */ 857: void putAllInternal(Map<? extends K, ? extends V> m) 858: { 859: final Map<K,V> addMap = (Map<K,V>) m; 860: final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); 861: size = 0; 862: while (it.hasNext()) 863: { 864: final Map.Entry<K,V> e = it.next(); 865: size++; 866: K key = e.getKey(); 867: int idx = hash(key); 868: HashEntry<K, V> he = new HashEntry<K, V>(key, e.getValue()); 869: he.next = buckets[idx]; 870: buckets[idx] = he; 871: } 872: } 873: 874: /** 875: * Increases the size of the Hashtable and rehashes all keys to new array 876: * indices; this is called when the addition of a new value would cause 877: * size() > threshold. Note that the existing Entry objects are reused in 878: * the new hash table. 879: * <p> 880: * 881: * This is not specified, but the new size is twice the current size plus 882: * one; this number is not always prime, unfortunately. This implementation 883: * is not synchronized, as it is only invoked from synchronized methods. 884: */ 885: protected void rehash() 886: { 887: HashEntry<K, V>[] oldBuckets = buckets; 888: 889: int newcapacity = (buckets.length * 2) + 1; 890: threshold = (int) (newcapacity * loadFactor); 891: buckets = (HashEntry<K, V>[]) new HashEntry[newcapacity]; 892: 893: for (int i = oldBuckets.length - 1; i >= 0; i--) 894: { 895: HashEntry<K, V> e =