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 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 }