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 005 This file is part of GNU Classpath. 006 007 GNU Classpath is free software; you can redistribute it and/or modify 008 it under the terms of the GNU General Public License as published by 009 the Free Software Foundation; either version 2, or (at your option) 010 any later version. 011 012 GNU Classpath is distributed in the hope that it will be useful, but 013 WITHOUT ANY WARRANTY; without even the implied warranty of 014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015 General Public License for more details. 016 017 You should have received a copy of the GNU General Public License 018 along with GNU Classpath; see the file COPYING. If not, write to the 019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 020 02110-1301 USA. 021 022 Linking this library statically or dynamically with other modules is 023 making a combined work based on this library. Thus, the terms and 024 conditions of the GNU General Public License cover the whole 025 combination. 026 027 As a special exception, the copyright holders of this library give you 028 permission to link this library with independent modules to produce an 029 executable, regardless of the license terms of these independent 030 modules, and to copy and distribute the resulting executable under 031 terms of your choice, provided that you also meet, for each linked 032 independent module, the terms and conditions of the license of that 033 module. An independent module is a module which is not derived from 034 or based on this library. If you modify this library, you may extend 035 this exception to your version of the library, but you are not 036 obligated to do so. If you do not wish to do so, delete this 037 exception statement from your version. */ 038 039 040 package java.util; 041 042 import java.io.IOException; 043 import java.io.ObjectInputStream; 044 import java.io.ObjectOutputStream; 045 import 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 */ 099 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 }