libjava/classpath/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, 2002, 2003, 2004, 2005  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., 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301 USA.
  21
  22 Linking this library statically or dynamically with other modules is
  23 making a combined work based on this library.  Thus, the terms and
  24 conditions of the GNU General Public License cover the whole
  25 combination.
  26
  27 As a special exception, the copyright holders of this library give you
  28 permission to link this library with independent modules to produce an
  29 executable, regardless of the license terms of these independent
  30 modules, and to copy and distribute the resulting executable under
  31 terms of your choice, provided that you also meet, for each linked
  32 independent module, the terms and conditions of the license of that
  33 module.  An independent module is a module which is not derived from
  34 or based on this library.  If you modify this library, you may extend
  35 this exception to your version of the library, but you are not
  36 obligated to do so.  If you do not wish to do so, delete this
  37 exception statement from your version. */
  38
  39
  40 package java.util;
  41
  42 import java.io.IOException;
  43 import java.io.ObjectInputStream;
  44 import java.io.ObjectOutputStream;
  45 import java.io.Serializable;
  46
  47 // NOTE: This implementation is very similar to that of Hashtable. If you fix
  48 // a bug in here, chances are you should make a similar change to the Hashtable
  49 // code.
  50
  51 // NOTE: This implementation has some nasty coding style in order to
  52 // support LinkedHashMap, which extends this.
  53
  54 /**
  55  * This class provides a hashtable-backed implementation of the
  56  * Map interface.
  57  * <p>
  58  *
  59  * It uses a hash-bucket approach; that is, hash collisions are handled
  60  * by linking the new node off of the pre-existing node (or list of
  61  * nodes).  In this manner, techniques such as linear probing (which
  62  * can cause primary clustering) and rehashing (which does not fit very
  63  * well with Java's method of precomputing hash codes) are avoided.
  64  * <p>
  65  *
  66  * Under ideal circumstances (no collisions), HashMap offers O(1)
  67  * performance on most operations (<code>containsValue()</code> is,
  68  * of course, O(n)).  In the worst case (all keys map to the same
  69  * hash code -- very unlikely), most operations are O(n).
  70  * <p>
  71  *
  72  * HashMap is part of the JDK1.2 Collections API.  It differs from
  73  * Hashtable in that it accepts the null key and null values, and it
  74  * does not support "Enumeration views." Also, it is not synchronized;
  75  * if you plan to use it in multiple threads, consider using:<br>
  76  * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code>
  77  * <p>
  78  *
  79  * The iterators are <i>fail-fast</i>, meaning that any structural
  80  * modification, except for <code>remove()</code> called on the iterator
  81  * itself, cause the iterator to throw a
  82  * <code>ConcurrentModificationException</code> rather than exhibit
  83  * non-deterministic behavior.
  84  *
  85  * @author Jon Zeppieri
  86  * @author Jochen Hoenicke
  87  * @author Bryce McKinlay
  88  * @author Eric Blake (ebb9@email.byu.edu)
  89  * @see Object#hashCode()
  90  * @see Collection
  91  * @see Map
  92  * @see TreeMap
  93  * @see LinkedHashMap
  94  * @see IdentityHashMap
  95  * @see Hashtable
  96  * @since 1.2
  97  * @status updated to 1.4
  98  */
  99 public class HashMap<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 }