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