001    /* HashMap.java -- a class providing a basic hashtable data structure,
002       mapping Object --> Object
003       Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.
004    
005    This file is part of GNU Classpath.
006    
007    GNU Classpath is free software; you can redistribute it and/or modify
008    it under the terms of the GNU General Public License as published by
009    the Free Software Foundation; either version 2, or (at your option)
010    any later version.
011    
012    GNU Classpath is distributed in the hope that it will be useful, but
013    WITHOUT ANY WARRANTY; without even the implied warranty of
014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015    General Public License for more details.
016    
017    You should have received a copy of the GNU General Public License
018    along with GNU Classpath; see the file COPYING.  If not, write to the
019    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020    02110-1301 USA.
021    
022    Linking this library statically or dynamically with other modules is
023    making a combined work based on this library.  Thus, the terms and
024    conditions of the GNU General Public License cover the whole
025    combination.
026    
027    As a special exception, the copyright holders of this library give you
028    permission to link this library with independent modules to produce an
029    executable, regardless of the license terms of these independent
030    modules, and to copy and distribute the resulting executable under
031    terms of your choice, provided that you also meet, for each linked
032    independent module, the terms and conditions of the license of that
033    module.  An independent module is a module which is not derived from
034    or based on this library.  If you modify this library, you may extend
035    this exception to your version of the library, but you are not
036    obligated to do so.  If you do not wish to do so, delete this
037    exception statement from your version. */
038    
039    
040    package java.util;
041    
042    import java.io.IOException;
043    import java.io.ObjectInputStream;
044    import java.io.ObjectOutputStream;
045    import java.io.Serializable;
046    
047    // NOTE: This implementation is very similar to that of Hashtable. If you fix
048    // a bug in here, chances are you should make a similar change to the Hashtable
049    // code.
050    
051    // NOTE: This implementation has some nasty coding style in order to
052    // support LinkedHashMap, which extends this.
053    
054    /**
055     * This class provides a hashtable-backed implementation of the
056     * Map interface.
057     * <p>
058     *
059     * It uses a hash-bucket approach; that is, hash collisions are handled
060     * by linking the new node off of the pre-existing node (or list of
061     * nodes).  In this manner, techniques such as linear probing (which
062     * can cause primary clustering) and rehashing (which does not fit very
063     * well with Java's method of precomputing hash codes) are avoided.
064     * <p>
065     *
066     * Under ideal circumstances (no collisions), HashMap offers O(1)
067     * performance on most operations (<code>containsValue()</code> is,
068     * of course, O(n)).  In the worst case (all keys map to the same
069     * hash code -- very unlikely), most operations are O(n).
070     * <p>
071     *
072     * HashMap is part of the JDK1.2 Collections API.  It differs from
073     * Hashtable in that it accepts the null key and null values, and it
074     * does not support "Enumeration views." Also, it is not synchronized;
075     * if you plan to use it in multiple threads, consider using:<br>
076     * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code>
077     * <p>
078     *
079     * The iterators are <i>fail-fast</i>, meaning that any structural
080     * modification, except for <code>remove()</code> called on the iterator
081     * itself, cause the iterator to throw a
082     * <code>ConcurrentModificationException</code> rather than exhibit
083     * non-deterministic behavior.
084     *
085     * @author Jon Zeppieri
086     * @author Jochen Hoenicke
087     * @author Bryce McKinlay
088     * @author Eric Blake (ebb9@email.byu.edu)
089     * @see Object#hashCode()
090     * @see Collection
091     * @see Map
092     * @see TreeMap
093     * @see LinkedHashMap
094     * @see IdentityHashMap
095     * @see Hashtable
096     * @since 1.2
097     * @status updated to 1.4
098     */
099    public class HashMap<K, V> extends AbstractMap<K, V>
100      implements Map<K, V>, Cloneable, Serializable
101    {
102      /**
103       * Default number of buckets. This is the value the JDK 1.3 uses. Some
104       * early documentation specified this value as 101. That is incorrect.
105       * Package visible for use by HashSet.
106       */
107      static final int DEFAULT_CAPACITY = 11;
108    
109      /**
110       * The default load factor; this is explicitly specified by the spec.
111       * Package visible for use by HashSet.
112       */
113      static final float DEFAULT_LOAD_FACTOR = 0.75f;
114    
115      /**
116       * Compatible with JDK 1.2.
117       */
118      private static final long serialVersionUID = 362498820763181265L;
119    
120      /**
121       * The rounded product of the capacity and the load factor; when the number
122       * of elements exceeds the threshold, the HashMap calls
123       * <code>rehash()</code>.
124       * @serial the threshold for rehashing
125       */
126      private int threshold;
127    
128      /**
129       * Load factor of this HashMap:  used in computing the threshold.
130       * Package visible for use by HashSet.
131       * @serial the load factor
132       */
133      final float loadFactor;
134    
135      /**
136       * Array containing the actual key-value mappings.
137       * Package visible for use by nested and subclasses.
138       */
139      transient HashEntry<K, V>[] buckets;
140    
141      /**
142       * Counts the number of modifications this HashMap has undergone, used
143       * by Iterators to know when to throw ConcurrentModificationExceptions.
144       * Package visible for use by nested and subclasses.
145       */
146      transient int modCount;
147    
148      /**
149       * The size of this HashMap:  denotes the number of key-value pairs.
150       * Package visible for use by nested and subclasses.
151       */
152      transient int size;
153    
154      /**
155       * The cache for {@link #entrySet()}.
156       */
157      private transient Set<Map.Entry<K, V>> entries;
158    
159      /**
160       * Class to represent an entry in the hash table. Holds a single key-value
161       * pair. Package visible for use by subclass.
162       *
163       * @author Eric Blake (ebb9@email.byu.edu)
164       */
165      static class HashEntry<K, V> extends AbstractMap.SimpleEntry<K, V>
166      {
167        /**
168         * The next entry in the linked list. Package visible for use by subclass.
169         */
170        HashEntry<K, V> next;
171    
172        /**
173         * Simple constructor.
174         * @param key the key
175         * @param value the value
176         */
177        HashEntry(K key, V value)
178        {
179          super(key, value);
180        }
181    
182        /**
183         * Called when this entry is accessed via {@link #put(Object, Object)}.
184         * This version does nothing, but in LinkedHashMap, it must do some
185         * bookkeeping for access-traversal mode.
186         */
187        void access()
188        {
189        }
190    
191        /**
192         * Called when this entry is removed from the map. This version simply
193         * returns the value, but in LinkedHashMap, it must also do bookkeeping.
194         *
195         * @return the value of this key as it is removed
196         */
197        V cleanup()
198        {
199          return value;
200        }
201      }
202    
203      /**
204       * Construct a new HashMap with the default capacity (11) and the default
205       * load factor (0.75).
206       */
207      public HashMap()
208      {
209        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
210      }
211    
212      /**
213       * Construct a new HashMap from the given Map, with initial capacity
214       * the greater of the size of <code>m</code> or the default of 11.
215       * <p>
216       *
217       * Every element in Map m will be put into this new HashMap.
218       *
219       * @param m a Map whose key / value pairs will be put into the new HashMap.
220       *        <b>NOTE: key / value pairs are not cloned in this constructor.</b>
221       * @throws NullPointerException if m is null
222       */
223      public HashMap(Map<? extends K, ? extends V> m)
224      {
225        this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
226        putAll(m);
227      }
228    
229      /**
230       * Construct a new HashMap with a specific inital capacity and
231       * default load factor of 0.75.
232       *
233       * @param initialCapacity the initial capacity of this HashMap (&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    }