001/* HashMap.java -- a class providing a basic hashtable data structure, 002 mapping Object --> Object 003 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 004 005This file is part of GNU Classpath. 006 007GNU Classpath is free software; you can redistribute it and/or modify 008it under the terms of the GNU General Public License as published by 009the Free Software Foundation; either version 2, or (at your option) 010any later version. 011 012GNU Classpath is distributed in the hope that it will be useful, but 013WITHOUT ANY WARRANTY; without even the implied warranty of 014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015General Public License for more details. 016 017You should have received a copy of the GNU General Public License 018along with GNU Classpath; see the file COPYING. If not, write to the 019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02002110-1301 USA. 021 022Linking this library statically or dynamically with other modules is 023making a combined work based on this library. Thus, the terms and 024conditions of the GNU General Public License cover the whole 025combination. 026 027As a special exception, the copyright holders of this library give you 028permission to link this library with independent modules to produce an 029executable, regardless of the license terms of these independent 030modules, and to copy and distribute the resulting executable under 031terms of your choice, provided that you also meet, for each linked 032independent module, the terms and conditions of the license of that 033module. An independent module is a module which is not derived from 034or based on this library. If you modify this library, you may extend 035this exception to your version of the library, but you are not 036obligated to do so. If you do not wish to do so, delete this 037exception statement from your version. */ 038 039 040package java.util; 041 042import java.io.IOException; 043import java.io.ObjectInputStream; 044import java.io.ObjectOutputStream; 045import java.io.Serializable; 046 047// NOTE: This implementation is very similar to that of Hashtable. If you fix 048// a bug in here, chances are you should make a similar change to the Hashtable 049// code. 050 051// NOTE: This implementation has some nasty coding style in order to 052// support LinkedHashMap, which extends this. 053 054/** 055 * This class provides a hashtable-backed implementation of the 056 * Map interface. 057 * <p> 058 * 059 * It uses a hash-bucket approach; that is, hash collisions are handled 060 * by linking the new node off of the pre-existing node (or list of 061 * nodes). In this manner, techniques such as linear probing (which 062 * can cause primary clustering) and rehashing (which does not fit very 063 * well with Java's method of precomputing hash codes) are avoided. 064 * <p> 065 * 066 * Under ideal circumstances (no collisions), HashMap offers O(1) 067 * performance on most operations (<code>containsValue()</code> is, 068 * of course, O(n)). In the worst case (all keys map to the same 069 * hash code -- very unlikely), most operations are O(n). 070 * <p> 071 * 072 * HashMap is part of the JDK1.2 Collections API. It differs from 073 * Hashtable in that it accepts the null key and null values, and it 074 * does not support "Enumeration views." Also, it is not synchronized; 075 * if you plan to use it in multiple threads, consider using:<br> 076 * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code> 077 * <p> 078 * 079 * The iterators are <i>fail-fast</i>, meaning that any structural 080 * modification, except for <code>remove()</code> called on the iterator 081 * itself, cause the iterator to throw a 082 * <code>ConcurrentModificationException</code> rather than exhibit 083 * non-deterministic behavior. 084 * 085 * @author Jon Zeppieri 086 * @author Jochen Hoenicke 087 * @author Bryce McKinlay 088 * @author Eric Blake (ebb9@email.byu.edu) 089 * @see Object#hashCode() 090 * @see Collection 091 * @see Map 092 * @see TreeMap 093 * @see LinkedHashMap 094 * @see IdentityHashMap 095 * @see Hashtable 096 * @since 1.2 097 * @status updated to 1.4 098 */ 099public 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}