1 /* HashMap.java -- a class providing a basic hashtable data structure, 2 mapping Object --> Object 3 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 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., 59 Temple Place, Suite 330, Boston, MA 20 02111-1307 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.Serializable; 44 import java.io.ObjectInputStream; 45 import java.io.ObjectOutputStream; 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 */ HashEntry(Object key, Object value)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 */ access()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 */ cleanup()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 */ HashMap()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 */ HashMap(Map m)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 */ HashMap(int initialCapacity)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 */ HashMap(int initialCapacity, float loadFactor)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 */ size()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 */ isEmpty()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 */ get(Object key)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 */ containsKey(Object key)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 */ put(Object key, Object value)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 */ putAll(Map m)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 */ remove(Object key)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 */ clear()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 */ containsValue(Object value)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 */ clone()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 */ keySet()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 */ values()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 */ entrySet()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 */ addEntry(Object key, Object value, int idx, boolean callRemove)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. getEntry(Object o)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 */ hash(Object key)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 */ iterator(int type)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 */ putAllInternal(Map m)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 */ rehash()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 747 if (dest != null) 748 { 749 while (dest.next != null) 750 dest = dest.next; 751 dest.next = e; 752 } 753 else 754 buckets[idx] = e; 755 756 HashEntry next = e.next; 757 e.next = null; 758 e = next; 759 } 760 } 761 } 762 763 /** 764 * Serializes this object to the given stream. 765 * 766 * @param s the stream to write to 767 * @throws IOException if the underlying stream fails 768 * @serialData the <i>capacity</i>(int) that is the length of the 769 * bucket array, the <i>size</i>(int) of the hash map 770 * are emitted first. They are followed by size entries, 771 * each consisting of a key (Object) and a value (Object). 772 */ writeObject(ObjectOutputStream s)773 private void writeObject(ObjectOutputStream s) throws IOException 774 { 775 // Write the threshold and loadFactor fields. 776 s.defaultWriteObject(); 777 778 s.writeInt(buckets.length); 779 s.writeInt(size); 780 // Avoid creating a wasted Set by creating the iterator directly. 781 Iterator it = iterator(ENTRIES); 782 while (it.hasNext()) 783 { 784 HashEntry entry = (HashEntry) it.next(); 785 s.writeObject(entry.key); 786 s.writeObject(entry.value); 787 } 788 } 789 790 /** 791 * Deserializes this object from the given stream. 792 * 793 * @param s the stream to read from 794 * @throws ClassNotFoundException if the underlying stream fails 795 * @throws IOException if the underlying stream fails 796 * @serialData the <i>capacity</i>(int) that is the length of the 797 * bucket array, the <i>size</i>(int) of the hash map 798 * are emitted first. They are followed by size entries, 799 * each consisting of a key (Object) and a value (Object). 800 */ readObject(ObjectInputStream s)801 private void readObject(ObjectInputStream s) 802 throws IOException, ClassNotFoundException 803 { 804 // Read the threshold and loadFactor fields. 805 s.defaultReadObject(); 806 807 // Read and use capacity, followed by key/value pairs. 808 buckets = new HashEntry[s.readInt()]; 809 int len = s.readInt(); 810 size = len; 811 while (len-- > 0) 812 { 813 Object key = s.readObject(); 814 addEntry(key, s.readObject(), hash(key), false); 815 } 816 } 817 818 /** 819 * Iterate over HashMap's entries. 820 * This implementation is parameterized to give a sequential view of 821 * keys, values, or entries. 822 * 823 * @author Jon Zeppieri 824 */ 825 private final class HashIterator implements Iterator 826 { 827 /** 828 * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 829 * or {@link #ENTRIES}. 830 */ 831 private final int type; 832 /** 833 * The number of modifications to the backing HashMap that we know about. 834 */ 835 private int knownMod = modCount; 836 /** The number of elements remaining to be returned by next(). */ 837 private int count = size; 838 /** Current index in the physical hash table. */ 839 private int idx = buckets.length; 840 /** The last Entry returned by a next() call. */ 841 private HashEntry last; 842 /** 843 * The next entry that should be returned by next(). It is set to something 844 * if we're iterating through a bucket that contains multiple linked 845 * entries. It is null if next() needs to find a new bucket. 846 */ 847 private HashEntry next; 848 849 /** 850 * Construct a new HashIterator with the supplied type. 851 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 852 */ HashIterator(int type)853 HashIterator(int type) 854 { 855 this.type = type; 856 } 857 858 /** 859 * Returns true if the Iterator has more elements. 860 * @return true if there are more elements 861 * @throws ConcurrentModificationException if the HashMap was modified 862 */ hasNext()863 public boolean hasNext() 864 { 865 if (knownMod != modCount) 866 throw new ConcurrentModificationException(); 867 return count > 0; 868 } 869 870 /** 871 * Returns the next element in the Iterator's sequential view. 872 * @return the next element 873 * @throws ConcurrentModificationException if the HashMap was modified 874 * @throws NoSuchElementException if there is none 875 */ next()876 public Object next() 877 { 878 if (knownMod != modCount) 879 throw new ConcurrentModificationException(); 880 if (count == 0) 881 throw new NoSuchElementException(); 882 count--; 883 HashEntry e = next; 884 885 while (e == null) 886 e = buckets[--idx]; 887 888 next = e.next; 889 last = e; 890 if (type == VALUES) 891 return e.value; 892 if (type == KEYS) 893 return e.key; 894 return e; 895 } 896 897 /** 898 * Removes from the backing HashMap the last element which was fetched 899 * with the <code>next()</code> method. 900 * @throws ConcurrentModificationException if the HashMap was modified 901 * @throws IllegalStateException if called when there is no last element 902 */ remove()903 public void remove() 904 { 905 if (knownMod != modCount) 906 throw new ConcurrentModificationException(); 907 if (last == null) 908 throw new IllegalStateException(); 909 910 HashMap.this.remove(last.key); 911 last = null; 912 knownMod++; 913 } 914 } 915 } 916