| Frames | No Frames |
1: /* HashMap.java -- a class providing a basic hashtable data structure, 2: mapping Object --> Object 3: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 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: 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 Hashtable. If you fix 48: // a bug in here, chances are you should make a similar change to the Hashtable 49: // code. 50: 51: // NOTE: This implementation has some nasty coding style in order to 52: // support LinkedHashMap, which extends this. 53: 54: /** 55: * This class provides a hashtable-backed implementation of the 56: * Map interface. 57: * <p> 58: * 59: * It uses a hash-bucket approach; that is, hash collisions are handled 60: * by linking the new node off of the pre-existing node (or list of 61: * nodes). In this manner, techniques such as linear probing (which 62: * can cause primary clustering) and rehashing (which does not fit very 63: * well with Java's method of precomputing hash codes) are avoided. 64: * <p> 65: * 66: * Under ideal circumstances (no collisions), HashMap offers O(1) 67: * performance on most operations (<code>containsValue()</code> is, 68: * of course, O(n)). In the worst case (all keys map to the same 69: * hash code -- very unlikely), most operations are O(n). 70: * <p> 71: * 72: * HashMap is part of the JDK1.2 Collections API. It differs from 73: * Hashtable in that it accepts the null key and null values, and it 74: * does not support "Enumeration views." Also, it is not synchronized; 75: * if you plan to use it in multiple threads, consider using:<br> 76: * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code> 77: * <p> 78: * 79: * The iterators are <i>fail-fast</i>, meaning that any structural 80: * modification, except for <code>remove()</code> called on the iterator 81: * itself, cause the iterator to throw a 82: * <code>ConcurrentModificationException</code> rather than exhibit 83: * non-deterministic behavior. 84: * 85: * @author Jon Zeppieri 86: * @author Jochen Hoenicke 87: * @author Bryce McKinlay 88: * @author Eric Blake (ebb9@email.byu.edu) 89: * @see Object#hashCode() 90: * @see Collection 91: * @see Map 92: * @see TreeMap 93: * @see LinkedHashMap 94: * @see IdentityHashMap 95: * @see Hashtable 96: * @since 1.2 97: * @status updated to 1.4 98: */ 99: public class HashMap<K, V> extends AbstractMap<K, V> 100: implements Map<K, V>, Cloneable, Serializable 101: { 102: /** 103: * Default number of buckets; this is currently set to 16. 104: * Package visible for use by HashSet. 105: */ 106: static final int DEFAULT_CAPACITY = 16; 107: 108: /** 109: * The default load factor; this is explicitly specified by the spec. 110: * Package visible for use by HashSet. 111: */ 112: static final float DEFAULT_LOAD_FACTOR = 0.75f; 113: 114: /** 115: * Compatible with JDK 1.2. 116: */ 117: private static final long serialVersionUID = 362498820763181265L; 118: 119: /** 120: * The rounded product of the capacity and the load factor; when the number 121: * of elements exceeds the threshold, the HashMap calls 122: * <code>rehash()</code>. 123: * @serial the threshold for rehashing 124: */ 125: private int threshold; 126: 127: /** 128: * Load factor of this HashMap: used in computing the threshold. 129: * Package visible for use by HashSet. 130: * @serial the load factor 131: */ 132: final float loadFactor; 133: 134: /** 135: * Array containing the actual key-value mappings. 136: * Package visible for use by nested and subclasses. 137: */ 138: transient HashEntry<K, V>[] buckets; 139: 140: /** 141: * Counts the number of modifications this HashMap has undergone, used 142: * by Iterators to know when to throw ConcurrentModificationExceptions. 143: * Package visible for use by nested and subclasses. 144: */ 145: transient int modCount; 146: 147: /** 148: * The size of this HashMap: denotes the number of key-value pairs. 149: * Package visible for use by nested and subclasses. 150: */ 151: transient int size; 152: 153: /** 154: * The cache for {@link #entrySet()}. 155: */ 156: private transient Set<Map.Entry<K, V>> entries; 157: 158: /** 159: * Class to represent an entry in the hash table. Holds a single key-value 160: * pair. Package visible for use by subclass. 161: * 162: * @author Eric Blake (ebb9@email.byu.edu) 163: */ 164: static class HashEntry<K, V> extends AbstractMap.SimpleEntry<K, V> 165: { 166: /** 167: * The next entry in the linked list. Package visible for use by subclass. 168: */ 169: HashEntry<K, V> next; 170: 171: /** 172: * Simple constructor. 173: * @param key the key 174: * @param value the value 175: */ 176: HashEntry(K key, V value) 177: { 178: super(key, value); 179: } 180: 181: /** 182: * Called when this entry is accessed via {@link #put(Object, Object)}. 183: * This version does nothing, but in LinkedHashMap, it must do some 184: * bookkeeping for access-traversal mode. 185: */ 186: void access() 187: { 188: } 189: 190: /** 191: * Called when this entry is removed from the map. This version simply 192: * returns the value, but in LinkedHashMap, it must also do bookkeeping. 193: * 194: * @return the value of this key as it is removed 195: */ 196: V cleanup() 197: { 198: return value; 199: } 200: } 201: 202: /** 203: * Construct a new HashMap with the default capacity (11) and the default 204: * load factor (0.75). 205: */ 206: public HashMap() 207: { 208: this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); 209: } 210: 211: /** 212: * Construct a new HashMap from the given Map, with initial capacity 213: * the greater of the size of <code>m</code> or the default of 11. 214: * <p> 215: * 216: * Every element in Map m will be put into this new HashMap. 217: * 218: * @param m a Map whose key / value pairs will be put into the new HashMap. 219: * <b>NOTE: key / value pairs are not cloned in this constructor.</b> 220: * @throws NullPointerException if m is null 221: */ 222: public HashMap(Map<? extends K, ? extends V> m) 223: { 224: this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); 225: putAll(m); 226: } 227: 228: /** 229: * Construct a new HashMap with a specific inital capacity and 230: * default load factor of 0.75. 231: * 232: * @param initialCapacity the initial capacity of this HashMap (>=0) 233: * @throws IllegalArgumentException if (initialCapacity < 0) 234: */ 235: public HashMap(int initialCapacity) 236: { 237: this(initialCapacity, DEFAULT_LOAD_FACTOR); 238: } 239: 240: /** 241: * Construct a new HashMap with a specific inital capacity and load factor. 242: * 243: * @param initialCapacity the initial capacity (>=0) 244: * @param loadFactor the load factor (> 0, not NaN) 245: * @throws IllegalArgumentException if (initialCapacity < 0) || 246: * ! (loadFactor > 0.0) 247: */ 248: public HashMap(int initialCapacity, float loadFactor) 249: { 250: if (initialCapacity < 0) 251: throw new IllegalArgumentException("Illegal Capacity: " 252: + initialCapacity); 253: if (! (loadFactor > 0)) // check for NaN too 254: throw new IllegalArgumentException("Illegal Load: " + loadFactor); 255: 256: if (initialCapacity == 0) 257: initialCapacity = 1; 258: buckets = (HashEntry<K, V>[]) new HashEntry[initialCapacity]; 259: this.loadFactor = loadFactor; 260: threshold = (int) (initialCapacity * loadFactor); 261: } 262: 263: /** 264: * Returns the number of kay-value mappings currently in this Map. 265: * 266: * @return the size 267: */ 268: public int size() 269: { 270: return size; 271: } 272: 273: /** 274: * Returns true if there are no key-value mappings currently in this Map. 275: * 276: * @return <code>size() == 0</code> 277: */ 278: public boolean isEmpty() 279: { 280: return size == 0; 281: } 282: 283: /** 284: * Return the value in this HashMap associated with the supplied key, 285: * or <code>null</code> if the key maps to nothing. NOTE: Since the value 286: * could also be null, you must use containsKey to see if this key 287: * actually maps to something. 288: * 289: * @param key the key for which to fetch an associated value 290: * @return what the key maps to, if present 291: * @see #put(Object, Object) 292: * @see #containsKey(Object) 293: */ 294: public V get(Object key) 295: { 296: int idx = hash(key); 297: HashEntry<K, V> e = buckets[idx]; 298: while (e != null) 299: { 300: if (equals(key, e.key)) 301: return e.value; 302: e = e.next; 303: } 304: return null; 305: } 306: 307: /** 308: * Returns true if the supplied object <code>equals()</code> a key 309: * in this HashMap. 310: * 311: * @param key the key to search for in this HashMap 312: * @return true if the key is in the table 313: * @see #containsValue(Object) 314: */ 315: public boolean containsKey(Object key) 316: { 317: int idx = hash(key); 318: HashEntry<K, V> e = buckets[idx]; 319: while (e != null) 320: { 321: if (equals(key, e.key)) 322: return true; 323: e = e.next; 324: } 325: return false; 326: } 327: 328: /** 329: * Puts the supplied value into the Map, mapped by the supplied key. 330: * The value may be retrieved by any object which <code>equals()</code> 331: * this key. NOTE: Since the prior value could also be null, you must 332: * first use containsKey if you want to see if you are replacing the 333: * key's mapping. 334: * 335: * @param key the key used to locate the value 336: * @param value the value to be stored in the HashMap 337: * @return the prior mapping of the key, or null if there was none 338: * @see #get(Object) 339: * @see Object#equals(Object) 340: */ 341: public V put(K key, V value) 342: { 343: int idx = hash(key); 344: HashEntry<K, V> e = buckets[idx]; 345: 346: int hash1 = key == null ? 0 : key.hashCode(); 347: while (e != null) 348: { 349: int hash2 = e.key == null ? 0 : e.key.hashCode(); 350: 351: if ((hash1 == hash2) && equals(key, e.key)) 352: { 353: e.access(); // Must call this for bookkeeping in LinkedHashMap. 354: V r = e.value; 355: e.value = value; 356: return r; 357: } 358: else 359: e = e.next; 360: } 361: 362: // At this point, we know we need to add a new entry. 363: modCount++; 364: if (++size > threshold) 365: { 366: rehash(); 367: // Need a new hash value to suit the bigger table. 368: idx = hash(key); 369: } 370: 371: // LinkedHashMap cannot override put(), hence this call. 372: addEntry(key, value, idx, true); 373: return null; 374: } 375: 376: /** 377: * Copies all elements of the given map into this hashtable. If this table 378: * already has a mapping for a key, the new mapping replaces the current 379: * one. 380: * 381: * @param m the map to be hashed into this 382: */ 383: public void putAll(Map<? extends K, ? extends V> m) 384: { 385: final Map<K,V> addMap = (Map<K,V>) m; 386: final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); 387: while (it.hasNext()) 388: { 389: final Map.Entry<K,V> e = it.next(); 390: // Optimize in case the Entry is one of our own. 391: if (e instanceof AbstractMap.SimpleEntry) 392: { 393: AbstractMap.SimpleEntry<? extends K, ? extends V> entry 394: = (AbstractMap.SimpleEntry<? extends K, ? extends V>) e; 395: put(entry.key, entry.value); 396: } 397: else 398: put(e.getKey(), e.getValue()); 399: } 400: } 401: 402: /** 403: * Removes from the HashMap and returns the value which is mapped by the 404: * supplied key. If the key maps to nothing, then the HashMap remains 405: * unchanged, and <code>null</code> is returned. NOTE: Since the value 406: * could also be null, you must use containsKey to see if you are 407: * actually removing a mapping. 408: * 409: * @param key the key used to locate the value to remove 410: * @return whatever the key mapped to, if present 411: */ 412: public V remove(Object key) 413: { 414: int idx = hash(key); 415: HashEntry<K, V> e = buckets[idx]; 416: HashEntry<K, V> last = null; 417: 418: while (e != null) 419: { 420: if (equals(key, e.key)) 421: { 422: modCount++; 423: if (last == null) 424: buckets[idx] = e.next; 425: else 426: last.next = e.next; 427: size--; 428: // Method call necessary for LinkedHashMap to work correctly. 429: return e.cleanup(); 430: } 431: last = e; 432: e = e.next; 433: } 434: return null; 435: } 436: 437: /** 438: * Clears the Map so it has no keys. This is O(1). 439: */ 440: public void clear() 441: { 442: if (size != 0) 443: { 444: modCount++; 445: Arrays.fill(buckets, null); 446: size = 0; 447: } 448: } 449: 450: /** 451: * Returns true if this HashMap contains a value <code>o</code>, such that 452: * <code>o.equals(value)</code>. 453: * 454: * @param value the value to search for in this HashMap 455: * @return true if at least one key maps to the value 456: * @see #containsKey(Object) 457: */ 458: public boolean containsValue(Object value) 459: { 460: for (int i = buckets.length - 1; i >= 0; i--) 461: { 462: HashEntry<K, V> e = buckets[i]; 463: while (e != null) 464: { 465: if (equals(value, e.value)) 466: return true; 467: e = e.next; 468: } 469: } 470: return false; 471: } 472: 473: /** 474: * Returns a shallow clone of this HashMap. The Map itself is cloned, 475: * but its contents are not. This is O(n). 476: * 477: * @return the clone 478: */ 479: public Object clone() 480: { 481: HashMap<K, V> copy = null; 482: try 483: { 484: copy = (HashMap<K, V>) super.clone(); 485: } 486: catch (CloneNotSupportedException x) 487: { 488: // This is impossible. 489: } 490: copy.buckets = (HashEntry<K, V>[]) new HashEntry[buckets.length]; 491: copy.putAllInternal(this); 492: // Clear the entry cache. AbstractMap.clone() does the others. 493: copy.entries = null; 494: return copy; 495: } 496: 497: /** 498: * Returns a "set view" of this HashMap's keys. The set is backed by the 499: * HashMap, so changes in one show up in the other. The set supports 500: * element removal, but not element addition. 501: * 502: * @return a set view of the keys 503: * @see #values() 504: * @see #entrySet() 505: */ 506: public Set<K> keySet() 507: { 508: if (keys == null) 509: // Create an AbstractSet with custom implementations of those methods 510: // that can be overridden easily and efficiently. 511: keys = new AbstractSet<K>() 512: { 513: public int size() 514: { 515: return size; 516: } 517: 518: public Iterator<K> iterator() 519: { 520: // Cannot create the iterator directly, because of LinkedHashMap. 521: return HashMap.this.iterator(KEYS); 522: } 523: 524: public void clear() 525: { 526: HashMap.this.clear(); 527: } 528: 529: public boolean contains(Object o) 530: { 531: return containsKey(o); 532: } 533: 534: public boolean remove(Object o) 535: { 536: // Test against the size of the HashMap to determine if anything 537: // really got removed. This is necessary because the return value 538: // of HashMap.remove() is ambiguous in the null case. 539: int oldsize = size; 540: HashMap.this.remove(o); 541: return oldsize != size; 542: } 543: }; 544: return keys; 545: } 546: 547: /** 548: * Returns a "collection view" (or "bag view") of this HashMap's values. 549: * The collection is backed by the HashMap, so changes in one show up 550: * in the other. The collection supports element removal, but not element 551: * addition. 552: * 553: * @return a bag view of the values 554: * @see #keySet() 555: * @see #entrySet() 556: */ 557: public Collection<V> values() 558: { 559: if (values == null) 560: // We don't bother overriding many of the optional methods, as doing so 561: // wouldn't provide any significant performance advantage. 562: values = new AbstractCollection<V>() 563: { 564: public int size() 565: { 566: return size; 567: } 568: 569: public Iterator<V> iterator() 570: { 571: // Cannot create the iterator directly, because of LinkedHashMap. 572: return HashMap.this.iterator(VALUES); 573: } 574: 575: public void clear() 576: { 577: HashMap.this.clear(); 578: } 579: }; 580: return values; 581: } 582: 583: /** 584: * Returns a "set view" of this HashMap's entries. The set is backed by 585: * the HashMap, so changes in one show up in the other. The set supports 586: * element removal, but not element addition.<p> 587: * 588: * Note that the iterators for all three views, from keySet(), entrySet(), 589: * and values(), traverse the HashMap in the same sequence. 590: * 591: * @return a set view of the entries 592: * @see #keySet() 593: * @see #values() 594: * @see Map.Entry 595: */ 596: public Set<Map.Entry<K, V>> entrySet() 597: { 598: if (entries == null) 599: // Create an AbstractSet with custom implementations of those methods 600: // that can be overridden easily and efficiently. 601: entries = new AbstractSet<Map.Entry<K, V>>() 602: { 603: public int size() 604: { 605: return size; 606: } 607: 608: public Iterator<Map.Entry<K, V>> iterator() 609: { 610: // Cannot create the iterator directly, because of LinkedHashMap. 611: return HashMap.this.iterator(ENTRIES); 612: } 613: 614: public void clear() 615: { 616: HashMap.this.clear(); 617: } 618: 619: public boolean contains(Object o) 620: { 621: return getEntry(o) != null; 622: } 623: 624: public boolean remove(Object o) 625: { 626: HashEntry<K, V> e = getEntry(o); 627: if (e != null) 628: { 629: HashMap.this.remove(e.key); 630: return true; 631: } 632: return false; 633: } 634: }; 635: return entries; 636: } 637: 638: /** 639: * Helper method for put, that creates and adds a new Entry. This is 640: * overridden in LinkedHashMap for bookkeeping purposes. 641: * 642: * @param key the key of the new Entry 643: * @param value the value 644: * @param idx the index in buckets where the new Entry belongs 645: * @param callRemove whether to call the removeEldestEntry method 646: * @see #put(Object, Object) 647: */ 648: void addEntry(K key, V value, int idx, boolean callRemove) 649: { 650: HashEntry<K, V> e = new HashEntry<K, V>(key, value); 651: e.next = buckets[idx]; 652: buckets[idx] = e; 653: } 654: 655: /** 656: * Helper method for entrySet(), which matches both key and value 657: * simultaneously. 658: * 659: * @param o the entry to match 660: * @return the matching entry, if found, or null 661: * @see #entrySet() 662: */ 663: // Package visible, for use in nested classes. 664: final HashEntry<K, V> getEntry(Object o) 665: { 666: if (! (o instanceof Map.Entry)) 667: return null; 668: Map.Entry<K, V> me = (Map.Entry<K, V>) o; 669: K key = me.getKey(); 670: int idx = hash(key); 671: HashEntry<K, V> e = buckets[idx]; 672: while (e != null) 673: { 674: if (equals(e.key, key)) 675: return equals(e.value, me.getValue()) ? e : null; 676: e = e.next; 677: } 678: return null; 679: } 680: 681: /** 682: * Helper method that returns an index in the buckets array for `key' 683: * based on its hashCode(). Package visible for use by subclasses. 684: * 685: * @param key the key 686: * @return the bucket number 687: */ 688: final int hash(Object key) 689: { 690: return key == null ? 0 : Math.abs(key.hashCode() % buckets.length); 691: } 692: 693: /** 694: * Generates a parameterized iterator. Must be overrideable, since 695: * LinkedHashMap iterates in a different order. 696: * 697: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 698: * @return the appropriate iterator 699: */ 700: <T> Iterator<T> iterator(int type) 701: { 702: // FIXME: bogus cast here. 703: return new HashIterator<T>(type); 704: } 705: 706: /** 707: * A simplified, more efficient internal implementation of putAll(). clone() 708: * should not call putAll or put, in order to be compatible with the JDK 709: * implementation with respect to subclasses. 710: * 711: * @param m the map to initialize this from 712: */ 713: void putAllInternal(Map<? extends K, ? extends V> m) 714: { 715: final Map<K,V> addMap = (Map<K,V>) m; 716: final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); 717: size = 0; 718: while (it.hasNext()) 719: { 720: final Map.Entry<K,V> e = it.next(); 721: size++; 722: K key = e.getKey(); 723: int idx = hash(key); 724: addEntry(key, e.getValue(), idx, false); 725: } 726: } 727: 728: /** 729: * Increases the size of the HashMap and rehashes all keys to new 730: * array indices; this is called when the addition of a new value 731: * would cause size() > threshold. Note that the existing Entry 732: * objects are reused in the new hash table. 733: * 734: * <p>This is not specified, but the new size is twice the current size 735: * plus one; this number is not always prime, unfortunately. 736: */ 737: private void rehash() 738: { 739: HashEntry<K, V>[] oldBuckets = buckets; 740: 741: int newcapacity = (buckets.length * 2) + 1; 742: threshold = (int) (newcapacity * loadFactor); 743: buckets = (HashEntry<K, V>[]) new HashEntry[newcapacity]; 744: 745: for (int i = oldBuckets.length - 1; i >= 0; i--) 746: { 747: HashEntry<K, V> e = oldBuckets[i]; 748: while (e != null) 749: { 750: int idx = hash(e.key); 751: HashEntry<K, V> dest = buckets[idx]; 752: HashEntry<K, V> next = e.next; 753: e.next = buckets[idx]; 754: buckets[idx] = e; 755: e = next; 756: } 757: } 758: } 759: 760: /** 761: * Serializes this object to the given stream. 762: * 763: * @param s the stream to write to 764: * @throws IOException if the underlying stream fails 765: * @serialData the <i>capacity</i>(int) that is the length of the 766: * bucket array, the <i>size</i>(int) of the hash map 767: * are emitted first. They are followed by size entries, 768: * each consisting of a key (Object) and a value (Object). 769: */ 770: private void writeObject(ObjectOutputStream s) throws IOException 771: { 772: // Write the threshold and loadFactor fields. 773: s.defaultWriteObject(); 774: 775: s.writeInt(buckets.length); 776: s.writeInt(size); 777: // Avoid creating a wasted Set by creating the iterator directly. 778: Iterator<HashEntry<K, V>> it = iterator(ENTRIES); 779: while (it.hasNext()) 780: { 781: HashEntry<K, V> entry = it.next(); 782: s.writeObject(entry.key); 783: s.writeObject(entry.value); 784: } 785: } 786: 787: /** 788: * Deserializes this object from the given stream. 789: * 790: * @param s the stream to read from 791: * @throws ClassNotFoundException if the underlying stream fails 792: * @throws IOException if the underlying stream fails 793: * @serialData the <i>capacity</i>(int) that is the length of the 794: * bucket array, the <i>size</i>(int) of the hash map 795: * are emitted first. They are followed by size entries, 796: * each consisting of a key (Object) and a value (Object). 797: */ 798: private void readObject(ObjectInputStream s) 799: throws IOException, ClassNotFoundException 800: { 801: // Read the threshold and loadFactor fields. 802: s.defaultReadObject(); 803: 804: // Read and use capacity, followed by key/value pairs. 805: buckets = (HashEntry<K, V>[]) new HashEntry[s.readInt()]; 806: int len = s.readInt(); 807: size = len; 808: while (len-- > 0) 809: { 810: Object key = s.readObject(); 811: addEntry((K) key, (V) s.readObject(), hash(key), false); 812: } 813: } 814: 815: /** 816: * Iterate over HashMap's entries. 817: * This implementation is parameterized to give a sequential view of 818: * keys, values, or entries. 819: * 820: * @author Jon Zeppieri 821: */ 822: private final class HashIterator<T> implements Iterator<T> 823: { 824: /** 825: * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 826: * or {@link #ENTRIES}. 827: */ 828: private final int type; 829: /** 830: * The number of modifications to the backing HashMap that we know about. 831: */ 832: private int knownMod = modCount; 833: /** The number of elements remaining to be returned by next(). */ 834: private int count = size; 835: /** Current index in the physical hash table. */ 836: private int idx = buckets.length; 837: /** The last Entry returned by a next() call. */ 838: private HashEntry last; 839: /** 840: * The next entry that should be returned by next(). It is set to something 841: * if we're iterating through a bucket that contains multiple linked 842: * entries. It is null if next() needs to find a new bucket. 843: */ 844: private HashEntry next; 845: 846: /** 847: * Construct a new HashIterator with the supplied type. 848: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 849: */ 850: HashIterator(int type) 851: { 852: this.type = type; 853: } 854: 855: /** 856: * Returns true if the Iterator has more elements. 857: * @return true if there are more elements 858: */ 859: public boolean hasNext() 860: { 861: return count > 0; 862: } 863: 864: /** 865: * Returns the next element in the Iterator's sequential view. 866: * @return the next element 867: * @throws ConcurrentModificationException if the HashMap was modified 868: * @throws NoSuchElementException if there is none 869: */ 870: public T next() 871: { 872: if (knownMod != modCount) 873: throw new ConcurrentModificationException(); 874: if (count == 0) 875: throw new NoSuchElementException(); 876: count--; 877: HashEntry e = next; 878: 879: while (e == null) 880: e = buckets[--idx]; 881: 882: next = e.next; 883: last = e; 884: if (type == VALUES) 885: return (T) e.value; 886: if (type == KEYS) 887: return (T) e.key; 888: return (T) e; 889: } 890: 891: /** 892: * Removes from the backing HashMap the last element which was fetched 893: * with the <code>next()</code> method. 894: * @throws ConcurrentModificationException if the HashMap was modified 895: * @throws IllegalStateException if called when there is no last element 896: */ 897: public void remove() 898: { 899: if (knownMod != modCount) 900: throw new ConcurrentModificationException(); 901: if (last == null) 902: throw new IllegalStateException(); 903: 904: HashMap.this.remove(last.key); 905: last = null; 906: knownMod++; 907: } 908: } 909: }