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