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 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 (&gt;=0)
234   * @throws IllegalArgumentException if (initialCapacity &lt; 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 (&gt;=0)
245   * @param loadFactor the load factor (&gt; 0, not NaN)
246   * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
247   *                                     ! (loadFactor &gt; 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() &gt; 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}