GNU Classpath (0.20) | |
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 extends AbstractMap 100: implements Map, 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[] 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 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 extends AbstractMap.BasicMapEntry 166: { 167: /** 168: * The next entry in the linked list. Package visible for use by subclass. 169: */ 170: HashEntry next; 171: 172: /** 173: * Simple constructor. 174: * @param key the key 175: * @param value the value 176: */ 177: HashEntry(Object key, Object 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: Object 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 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 = 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 Object get(Object key) 296: { 297: int idx = hash(key); 298: HashEntry 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 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 Object put(Object key, Object value) 343: { 344: int idx = hash(key); 345: HashEntry 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: Object 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 m) 382: { 383: Iterator itr = m.entrySet().iterator(); 384: while (itr.hasNext()) 385: { 386: Map.Entry e = (Map.Entry) itr.next(); 387: // Optimize in case the Entry is one of our own. 388: if (e instanceof AbstractMap.BasicMapEntry) 389: { 390: AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e; 391: put(entry.key, entry.value); 392: } 393: else 394: put(e.getKey(), e.getValue()); 395: } 396: } 397: 398: /** 399: * Removes from the HashMap and returns the value which is mapped by the 400: * supplied key. If the key maps to nothing, then the HashMap remains 401: * unchanged, and <code>null</code> is returned. NOTE: Since the value 402: * could also be null, you must use containsKey to see if you are 403: * actually removing a mapping. 404: * 405: * @param key the key used to locate the value to remove 406: * @return whatever the key mapped to, if present 407: */ 408: public Object remove(Object key) 409: { 410: int idx = hash(key); 411: HashEntry e = buckets[idx]; 412: HashEntry last = null; 413: 414: while (e != null) 415: { 416: if (equals(key, e.key)) 417: { 418: modCount++; 419: if (last == null) 420: buckets[idx] = e.next; 421: else 422: last.next = e.next; 423: size--; 424: // Method call necessary for LinkedHashMap to work correctly. 425: return e.cleanup(); 426: } 427: last = e; 428: e = e.next; 429: } 430: return null; 431: } 432: 433: /** 434: * Clears the Map so it has no keys. This is O(1). 435: */ 436: public void clear() 437: { 438: if (size != 0) 439: { 440: modCount++; 441: Arrays.fill(buckets, null); 442: size = 0; 443: } 444: } 445: 446: /** 447: * Returns true if this HashMap contains a value <code>o</code>, such that 448: * <code>o.equals(value)</code>. 449: * 450: * @param value the value to search for in this HashMap 451: * @return true if at least one key maps to the value 452: * @see #containsKey(Object) 453: */ 454: public boolean containsValue(Object value) 455: { 456: for (int i = buckets.length - 1; i >= 0; i--) 457: { 458: HashEntry e = buckets[i]; 459: while (e != null) 460: { 461: if (equals(value, e.value)) 462: return true; 463: e = e.next; 464: } 465: } 466: return false; 467: } 468: 469: /** 470: * Returns a shallow clone of this HashMap. The Map itself is cloned, 471: * but its contents are not. This is O(n). 472: * 473: * @return the clone 474: */ 475: public Object clone() 476: { 477: HashMap copy = null; 478: try 479: { 480: copy = (HashMap) super.clone(); 481: } 482: catch (CloneNotSupportedException x) 483: { 484: // This is impossible. 485: } 486: copy.buckets = new HashEntry[buckets.length]; 487: copy.putAllInternal(this); 488: // Clear the entry cache. AbstractMap.clone() does the others. 489: copy.entries = null; 490: return copy; 491: } 492: 493: /** 494: * Returns a "set view" of this HashMap's keys. The set is backed by the 495: * HashMap, so changes in one show up in the other. The set supports 496: * element removal, but not element addition. 497: * 498: * @return a set view of the keys 499: * @see #values() 500: * @see #entrySet() 501: */ 502: public Set keySet() 503: { 504: if (keys == null) 505: // Create an AbstractSet with custom implementations of those methods 506: // that can be overridden easily and efficiently. 507: keys = new AbstractSet() 508: { 509: public int size() 510: { 511: return size; 512: } 513: 514: public Iterator iterator() 515: { 516: // Cannot create the iterator directly, because of LinkedHashMap. 517: return HashMap.this.iterator(KEYS); 518: } 519: 520: public void clear() 521: { 522: HashMap.this.clear(); 523: } 524: 525: public boolean contains(Object o) 526: { 527: return containsKey(o); 528: } 529: 530: public boolean remove(Object o) 531: { 532: // Test against the size of the HashMap to determine if anything 533: // really got removed. This is necessary because the return value 534: // of HashMap.remove() is ambiguous in the null case. 535: int oldsize = size; 536: HashMap.this.remove(o); 537: return oldsize != size; 538: } 539: }; 540: return keys; 541: } 542: 543: /** 544: * Returns a "collection view" (or "bag view") of this HashMap's values. 545: * The collection is backed by the HashMap, so changes in one show up 546: * in the other. The collection supports element removal, but not element 547: * addition. 548: * 549: * @return a bag view of the values 550: * @see #keySet() 551: * @see #entrySet() 552: */ 553: public Collection values() 554: { 555: if (values == null) 556: // We don't bother overriding many of the optional methods, as doing so 557: // wouldn't provide any significant performance advantage. 558: values = new AbstractCollection() 559: { 560: public int size() 561: { 562: return size; 563: } 564: 565: public Iterator iterator() 566: { 567: // Cannot create the iterator directly, because of LinkedHashMap. 568: return HashMap.this.iterator(VALUES); 569: } 570: 571: public void clear() 572: { 573: HashMap.this.clear(); 574: } 575: }; 576: return values; 577: } 578: 579: /** 580: * Returns a "set view" of this HashMap's entries. The set is backed by 581: * the HashMap, so changes in one show up in the other. The set supports 582: * element removal, but not element addition.<p> 583: * 584: * Note that the iterators for all three views, from keySet(), entrySet(), 585: * and values(), traverse the HashMap in the same sequence. 586: * 587: * @return a set view of the entries 588: * @see #keySet() 589: * @see #values() 590: * @see Map.Entry 591: */ 592: public Set entrySet() 593: { 594: if (entries == null) 595: // Create an AbstractSet with custom implementations of those methods 596: // that can be overridden easily and efficiently. 597: entries = new AbstractSet() 598: { 599: public int size() 600: { 601: return size; 602: } 603: 604: public Iterator iterator() 605: { 606: // Cannot create the iterator directly, because of LinkedHashMap. 607: return HashMap.this.iterator(ENTRIES); 608: } 609: 610: public void clear() 611: { 612: HashMap.this.clear(); 613: } 614: 615: public boolean contains(Object o) 616: { 617: return getEntry(o) != null; 618: } 619: 620: public boolean remove(Object o) 621: { 622: HashEntry e = getEntry(o); 623: if (e != null) 624: { 625: HashMap.this.remove(e.key); 626: return true; 627: } 628: return false; 629: } 630: }; 631: return entries; 632: } 633: 634: /** 635: * Helper method for put, that creates and adds a new Entry. This is 636: * overridden in LinkedHashMap for bookkeeping purposes. 637: * 638: * @param key the key of the new Entry 639: * @param value the value 640: * @param idx the index in buckets where the new Entry belongs 641: * @param callRemove whether to call the removeEldestEntry method 642: * @see #put(Object, Object) 643: */ 644: void addEntry(Object key, Object value, int idx, boolean callRemove) 645: { 646: HashEntry e = new HashEntry(key, value); 647: e.next = buckets[idx]; 648: buckets[idx] = e; 649: } 650: 651: /** 652: * Helper method for entrySet(), which matches both key and value 653: * simultaneously. 654: * 655: * @param o the entry to match 656: * @return the matching entry, if found, or null 657: * @see #entrySet() 658: */ 659: // Package visible, for use in nested classes. 660: final HashEntry getEntry(Object o) 661: { 662: if (! (o instanceof Map.Entry)) 663: return null; 664: Map.Entry me = (Map.Entry) o; 665: Object key = me.getKey(); 666: int idx = hash(key); 667: HashEntry e = buckets[idx]; 668: while (e != null) 669: { 670: if (equals(e.key, key)) 671: return equals(e.value, me.getValue()) ? e : null; 672: e = e.next; 673: } 674: return null; 675: } 676: 677: /** 678: * Helper method that returns an index in the buckets array for `key' 679: * based on its hashCode(). Package visible for use by subclasses. 680: * 681: * @param key the key 682: * @return the bucket number 683: */ 684: final int hash(Object key) 685: { 686: return key == null ? 0 : Math.abs(key.hashCode() % buckets.length); 687: } 688: 689: /** 690: * Generates a parameterized iterator. Must be overrideable, since 691: * LinkedHashMap iterates in a different order. 692: * 693: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 694: * @return the appropriate iterator 695: */ 696: Iterator iterator(int type) 697: { 698: return new HashIterator(type); 699: } 700: 701: /** 702: * A simplified, more efficient internal implementation of putAll(). clone() 703: * should not call putAll or put, in order to be compatible with the JDK 704: * implementation with respect to subclasses. 705: * 706: * @param m the map to initialize this from 707: */ 708: void putAllInternal(Map m) 709: { 710: Iterator itr = m.entrySet().iterator(); 711: size = 0; 712: while (itr.hasNext()) 713: { 714: size++; 715: Map.Entry e = (Map.Entry) itr.next(); 716: Object key = e.getKey(); 717: int idx = hash(key); 718: addEntry(key, e.getValue(), idx, false); 719: } 720: } 721: 722: /** 723: * Increases the size of the HashMap and rehashes all keys to new 724: * array indices; this is called when the addition of a new value 725: * would cause size() > threshold. Note that the existing Entry 726: * objects are reused in the new hash table. 727: * 728: * <p>This is not specified, but the new size is twice the current size 729: * plus one; this number is not always prime, unfortunately. 730: */ 731: private void rehash() 732: { 733: HashEntry[] oldBuckets = buckets; 734: 735: int newcapacity = (buckets.length * 2) + 1; 736: threshold = (int) (newcapacity * loadFactor); 737: buckets = new HashEntry[newcapacity]; 738: 739: for (int i = oldBuckets.length - 1; i >= 0; i--) 740: { 741: HashEntry e = oldBuckets[i]; 742: while (e != null) 743: { 744: int idx = hash(e.key); 745: HashEntry dest = buckets[idx]; 746: HashEntry next = e.next; 747: e.next = buckets[idx]; 748: buckets[idx] = e; 749: e = next; 750: } 751: } 752: } 753: 754: /** 755: * Serializes this object to the given stream. 756: * 757: * @param s the stream to write to 758: * @throws IOException if the underlying stream fails 759: * @serialData the <i>capacity</i>(int) that is the length of the 760: * bucket array, the <i>size</i>(int) of the hash map 761: * are emitted first. They are followed by size entries, 762: * each consisting of a key (Object) and a value (Object). 763: */ 764: private void writeObject(ObjectOutputStream s) throws IOException 765: { 766: // Write the threshold and loadFactor fields. 767: s.defaultWriteObject(); 768: 769: s.writeInt(buckets.length); 770: s.writeInt(size); 771: // Avoid creating a wasted Set by creating the iterator directly. 772: Iterator it = iterator(ENTRIES); 773: while (it.hasNext()) 774: { 775: HashEntry entry = (HashEntry) it.next(); 776: s.writeObject(entry.key); 777: s.writeObject(entry.value); 778: } 779: } 780: 781: /** 782: * Deserializes this object from the given stream. 783: * 784: * @param s the stream to read from 785: * @throws ClassNotFoundException if the underlying stream fails 786: * @throws IOException if the underlying stream fails 787: * @serialData the <i>capacity</i>(int) that is the length of the 788: * bucket array, the <i>size</i>(int) of the hash map 789: * are emitted first. They are followed by size entries, 790: * each consisting of a key (Object) and a value (Object). 791: */ 792: private void readObject(ObjectInputStream s) 793: throws IOException, ClassNotFoundException 794: { 795: // Read the threshold and loadFactor fields. 796: s.defaultReadObject(); 797: 798: // Read and use capacity, followed by key/value pairs. 799: buckets = new HashEntry[s.readInt()]; 800: int len = s.readInt(); 801: size = len; 802: while (len-- > 0) 803: { 804: Object key = s.readObject(); 805: addEntry(key, s.readObject(), hash(key), false); 806: } 807: } 808: 809: /** 810: * Iterate over HashMap's entries. 811: * This implementation is parameterized to give a sequential view of 812: * keys, values, or entries. 813: * 814: * @author Jon Zeppieri 815: */ 816: private final class HashIterator implements Iterator 817: { 818: /** 819: * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 820: * or {@link #ENTRIES}. 821: */ 822: private final int type; 823: /** 824: * The number of modifications to the backing HashMap that we know about. 825: */ 826: private int knownMod = modCount; 827: /** The number of elements remaining to be returned by next(). */ 828: private int count = size; 829: /** Current index in the physical hash table. */ 830: private int idx = buckets.length; 831: /** The last Entry returned by a next() call. */ 832: private HashEntry last; 833: /** 834: * The next entry that should be returned by next(). It is set to something 835: * if we're iterating through a bucket that contains multiple linked 836: * entries. It is null if next() needs to find a new bucket. 837: */ 838: private HashEntry next; 839: 840: /** 841: * Construct a new HashIterator with the supplied type. 842: * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 843: */ 844: HashIterator(int type) 845: { 846: this.type = type; 847: } 848: 849: /** 850: * Returns true if the Iterator has more elements. 851: * @return true if there are more elements 852: * @throws ConcurrentModificationException if the HashMap was modified 853: */ 854: public boolean hasNext() 855: { 856: if (knownMod != modCount) 857: throw new ConcurrentModificationException(); 858: return count > 0; 859: } 860: 861: /** 862: * Returns the next element in the Iterator's sequential view. 863: * @return the next element 864: * @throws ConcurrentModificationException if the HashMap was modified 865: * @throws NoSuchElementException if there is none 866: */ 867: public Object next() 868: { 869: if (knownMod != modCount) 870: throw new ConcurrentModificationException(); 871: if (count == 0) 872: throw new NoSuchElementException(); 873: count--; 874: HashEntry e = next; 875: 876: while (e == null) 877: e = buckets[--idx]; 878: 879: next = e.next; 880: last = e; 881: if (type == VALUES) 882: return e.value; 883: if (type == KEYS) 884: return e.key; 885: return e; 886: } 887: 888: /** 889: * Removes from the backing HashMap the last element which was fetched 890: * with the <code>next()</code> method. 891: * @throws ConcurrentModificationException if the HashMap was modified 892: * @throws IllegalStateException if called when there is no last element 893: */ 894: public void remove() 895: { 896: if (knownMod != modCount) 897: throw new ConcurrentModificationException(); 898: if (last == null) 899: throw new IllegalStateException(); 900: 901: HashMap.this.remove(last.key); 902: last = null; 903: knownMod++; 904: } 905: } 906: }
GNU Classpath (0.20) |