libjava/java/util/HashMap.java

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