toolchain/gcc/libjava/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 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., 59 Temple Place, Suite 330, Boston, MA
  20 02111-1307 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.Serializable;
  44 import java.io.ObjectInputStream;
  45 import java.io.ObjectOutputStream;
  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 extends AbstractMap
 100   implements Map, 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[] 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 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 extends AbstractMap.BasicMapEntry
 166   {
 167     /**
 168      * The next entry in the linked list. Package visible for use by subclass.
 169      */
 170     HashEntry next;
 171
 172     /**
 173      * Simple constructor.
 174      * @param key the key
 175      * @param value the value
 176      */
 177     HashEntry(Object key, Object 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     Object 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 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 = 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 Object get(Object key)
 296   {
 297     int idx = hash(key);
 298     HashEntry 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 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 Object put(Object key, Object value)
 343   {
 344     int idx = hash(key);
 345     HashEntry 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             Object 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 m)
 382   {
 383     Iterator itr = m.entrySet().iterator();
 384     while (itr.hasNext())
 385       {
 386         Map.Entry e = (Map.Entry) itr.next();
 387         // Optimize in case the Entry is one of our own.
 388         if (e instanceof AbstractMap.BasicMapEntry)
 389           {
 390             AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e;
 391             put(entry.key, entry.value);
 392           }
 393         else
 394           put(e.getKey(), e.getValue());
 395       }
 396   }
 397
 398   /**
 399    * Removes from the HashMap and returns the value which is mapped by the
 400    * supplied key. If the key maps to nothing, then the HashMap remains
 401    * unchanged, and <code>null</code> is returned. NOTE: Since the value
 402    * could also be null, you must use containsKey to see if you are
 403    * actually removing a mapping.
 404    *
 405    * @param key the key used to locate the value to remove
 406    * @return whatever the key mapped to, if present
 407    */
 408   public Object remove(Object key)
 409   {
 410     int idx = hash(key);
 411     HashEntry e = buckets[idx];
 412     HashEntry last = null;
 413
 414     while (e != null)
 415       {
 416         if (equals(key, e.key))
 417           {
 418             modCount++;
 419             if (last == null)
 420               buckets[idx] = e.next;
 421             else
 422               last.next = e.next;
 423             size--;
 424             // Method call necessary for LinkedHashMap to work correctly.
 425             return e.cleanup();
 426           }
 427         last = e;
 428         e = e.next;
 429       }
 430     return null;
 431   }
 432
 433   /**
 434    * Clears the Map so it has no keys. This is O(1).
 435    */
 436   public void clear()
 437   {
 438     if (size != 0)
 439       {
 440         modCount++;
 441         Arrays.fill(buckets, null);
 442         size = 0;
 443       }
 444   }
 445
 446   /**
 447    * Returns true if this HashMap contains a value <code>o</code>, such that
 448    * <code>o.equals(value)</code>.
 449    *
 450    * @param value the value to search for in this HashMap
 451    * @return true if at least one key maps to the value
 452    * @see containsKey(Object)
 453    */
 454   public boolean containsValue(Object value)
 455   {
 456     for (int i = buckets.length - 1; i >= 0; i--)
 457       {
 458         HashEntry e = buckets[i];
 459         while (e != null)
 460           {
 461             if (equals(value, e.value))
 462               return true;
 463             e = e.next;
 464           }
 465       }
 466     return false;
 467   }
 468
 469   /**
 470    * Returns a shallow clone of this HashMap. The Map itself is cloned,
 471    * but its contents are not.  This is O(n).
 472    *
 473    * @return the clone
 474    */
 475   public Object clone()
 476   {
 477     HashMap copy = null;
 478     try
 479       {
 480         copy = (HashMap) super.clone();
 481       }
 482     catch (CloneNotSupportedException x)
 483       {
 484         // This is impossible.
 485       }
 486     copy.buckets = new HashEntry[buckets.length];
 487     copy.putAllInternal(this);
 488     // Clear the entry cache. AbstractMap.clone() does the others.
 489     copy.entries = null;
 490     return copy;
 491   }
 492
 493   /**
 494    * Returns a "set view" of this HashMap's keys. The set is backed by the
 495    * HashMap, so changes in one show up in the other.  The set supports
 496    * element removal, but not element addition.
 497    *
 498    * @return a set view of the keys
 499    * @see #values()
 500    * @see #entrySet()
 501    */
 502   public Set keySet()
 503   {
 504     if (keys == null)
 505       // Create an AbstractSet with custom implementations of those methods
 506       // that can be overridden easily and efficiently.
 507       keys = new AbstractSet()
 508       {
 509         public int size()
 510         {
 511           return size;
 512         }
 513
 514         public Iterator iterator()
 515         {
 516           // Cannot create the iterator directly, because of LinkedHashMap.
 517           return HashMap.this.iterator(KEYS);
 518         }
 519
 520         public void clear()
 521         {
 522           HashMap.this.clear();
 523         }
 524
 525         public boolean contains(Object o)
 526         {
 527           return containsKey(o);
 528         }
 529
 530         public boolean remove(Object o)
 531         {
 532           // Test against the size of the HashMap to determine if anything
 533           // really got removed. This is necessary because the return value
 534           // of HashMap.remove() is ambiguous in the null case.
 535           int oldsize = size;
 536           HashMap.this.remove(o);
 537           return oldsize != size;
 538         }
 539       };
 540     return keys;
 541   }
 542
 543   /**
 544    * Returns a "collection view" (or "bag view") of this HashMap's values.
 545    * The collection is backed by the HashMap, so changes in one show up
 546    * in the other.  The collection supports element removal, but not element
 547    * addition.
 548    *
 549    * @return a bag view of the values
 550    * @see #keySet()
 551    * @see #entrySet()
 552    */
 553   public Collection values()
 554   {
 555     if (values == null)
 556       // We don't bother overriding many of the optional methods, as doing so
 557       // wouldn't provide any significant performance advantage.
 558       values = new AbstractCollection()
 559       {
 560         public int size()
 561         {
 562           return size;
 563         }
 564
 565         public Iterator iterator()
 566         {
 567           // Cannot create the iterator directly, because of LinkedHashMap.
 568           return HashMap.this.iterator(VALUES);
 569         }
 570
 571         public void clear()
 572         {
 573           HashMap.this.clear();
 574         }
 575       };
 576     return values;
 577   }
 578
 579   /**
 580    * Returns a "set view" of this HashMap's entries. The set is backed by
 581    * the HashMap, so changes in one show up in the other.  The set supports
 582    * element removal, but not element addition.<p>
 583    *
 584    * Note that the iterators for all three views, from keySet(), entrySet(),
 585    * and values(), traverse the HashMap in the same sequence.
 586    *
 587    * @return a set view of the entries
 588    * @see #keySet()
 589    * @see #values()
 590    * @see Map.Entry
 591    */
 592   public Set entrySet()
 593   {
 594     if (entries == null)
 595       // Create an AbstractSet with custom implementations of those methods
 596       // that can be overridden easily and efficiently.
 597       entries = new AbstractSet()
 598       {
 599         public int size()
 600         {
 601           return size;
 602         }
 603
 604         public Iterator iterator()
 605         {
 606           // Cannot create the iterator directly, because of LinkedHashMap.
 607           return HashMap.this.iterator(ENTRIES);
 608         }
 609
 610         public void clear()
 611         {
 612           HashMap.this.clear();
 613         }
 614
 615         public boolean contains(Object o)
 616         {
 617           return getEntry(o) != null;
 618         }
 619
 620         public boolean remove(Object o)
 621         {
 622           HashEntry e = getEntry(o);
 623           if (e != null)
 624             {
 625               HashMap.this.remove(e.key);
 626               return true;
 627             }
 628           return false;
 629         }
 630       };
 631     return entries;
 632   }
 633
 634   /**
 635    * Helper method for put, that creates and adds a new Entry.  This is
 636    * overridden in LinkedHashMap for bookkeeping purposes.
 637    *
 638    * @param key the key of the new Entry
 639    * @param value the value
 640    * @param idx the index in buckets where the new Entry belongs
 641    * @param callRemove whether to call the removeEldestEntry method
 642    * @see #put(Object, Object)
 643    */
 644   void addEntry(Object key, Object value, int idx, boolean callRemove)
 645   {
 646     HashEntry e = new HashEntry(key, value);
 647     e.next = buckets[idx];
 648     buckets[idx] = e;
 649   }
 650
 651   /**
 652    * Helper method for entrySet(), which matches both key and value
 653    * simultaneously.
 654    *
 655    * @param o the entry to match
 656    * @return the matching entry, if found, or null
 657    * @see #entrySet()
 658    */
 659   // Package visible, for use in nested classes.
 660   final HashEntry getEntry(Object o)
 661   {
 662     if (! (o instanceof Map.Entry))
 663       return null;
 664     Map.Entry me = (Map.Entry) o;
 665     Object key = me.getKey();
 666     int idx = hash(key);
 667     HashEntry e = buckets[idx];
 668     while (e != null)
 669       {
 670         if (equals(e.key, key))
 671           return equals(e.value, me.getValue()) ? e : null;
 672         e = e.next;
 673       }
 674     return null;
 675   }
 676
 677   /**
 678    * Helper method that returns an index in the buckets array for `key'
 679    * based on its hashCode().  Package visible for use by subclasses.
 680    *
 681    * @param key the key
 682    * @return the bucket number
 683    */
 684   final int hash(Object key)
 685   {
 686     return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
 687   }
 688
 689   /**
 690    * Generates a parameterized iterator.  Must be overrideable, since
 691    * LinkedHashMap iterates in a different order.
 692    *
 693    * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
 694    * @return the appropriate iterator
 695    */
 696   Iterator iterator(int type)
 697   {
 698     return new HashIterator(type);
 699   }
 700
 701   /**
 702    * A simplified, more efficient internal implementation of putAll(). clone()
 703    * should not call putAll or put, in order to be compatible with the JDK
 704    * implementation with respect to subclasses.
 705    *
 706    * @param m the map to initialize this from
 707    */
 708   void putAllInternal(Map m)
 709   {
 710     Iterator itr = m.entrySet().iterator();
 711     size = 0;
 712     while (itr.hasNext())
 713       {
 714         size++;
 715         Map.Entry e = (Map.Entry) itr.next();
 716         Object key = e.getKey();
 717         int idx = hash(key);
 718         addEntry(key, e.getValue(), idx, false);
 719       }
 720   }
 721
 722   /**
 723    * Increases the size of the HashMap and rehashes all keys to new
 724    * array indices; this is called when the addition of a new value
 725    * would cause size() &gt; threshold. Note that the existing Entry
 726    * objects are reused in the new hash table.
 727    *
 728    * <p>This is not specified, but the new size is twice the current size
 729    * plus one; this number is not always prime, unfortunately.
 730    */
 731   private void rehash()
 732   {
 733     HashEntry[] oldBuckets = buckets;
 734
 735     int newcapacity = (buckets.length * 2) + 1;
 736     threshold = (int) (newcapacity * loadFactor);
 737     buckets = new HashEntry[newcapacity];
 738
 739     for (int i = oldBuckets.length - 1; i >= 0; i--)
 740       {
 741         HashEntry e = oldBuckets[i];
 742         while (e != null)
 743           {
 744             int idx = hash(e.key);
 745             HashEntry dest = buckets[idx];
 746
 747             if (dest != null)
 748               {
 749                 while (dest.next != null)
 750                   dest = dest.next;
 751                 dest.next = e;
 752               }
 753             else
 754               buckets[idx] = e;
 755
 756             HashEntry next = e.next;
 757             e.next = null;
 758             e = next;
 759           }
 760       }
 761   }
 762
 763   /**
 764    * Serializes this object to the given stream.
 765    *
 766    * @param s the stream to write to
 767    * @throws IOException if the underlying stream fails
 768    * @serialData the <i>capacity</i>(int) that is the length of the
 769    *             bucket array, the <i>size</i>(int) of the hash map
 770    *             are emitted first.  They are followed by size entries,
 771    *             each consisting of a key (Object) and a value (Object).
 772    */
 773   private void writeObject(ObjectOutputStream s) throws IOException
 774   {
 775     // Write the threshold and loadFactor fields.
 776     s.defaultWriteObject();
 777
 778     s.writeInt(buckets.length);
 779     s.writeInt(size);
 780     // Avoid creating a wasted Set by creating the iterator directly.
 781     Iterator it = iterator(ENTRIES);
 782     while (it.hasNext())
 783       {
 784         HashEntry entry = (HashEntry) it.next();
 785         s.writeObject(entry.key);
 786         s.writeObject(entry.value);
 787       }
 788   }
 789
 790   /**
 791    * Deserializes this object from the given stream.
 792    *
 793    * @param s the stream to read from
 794    * @throws ClassNotFoundException if the underlying stream fails
 795    * @throws IOException if the underlying stream fails
 796    * @serialData the <i>capacity</i>(int) that is the length of the
 797    *             bucket array, the <i>size</i>(int) of the hash map
 798    *             are emitted first.  They are followed by size entries,
 799    *             each consisting of a key (Object) and a value (Object).
 800    */
 801   private void readObject(ObjectInputStream s)
 802     throws IOException, ClassNotFoundException
 803   {
 804     // Read the threshold and loadFactor fields.
 805     s.defaultReadObject();
 806
 807     // Read and use capacity, followed by key/value pairs.
 808     buckets = new HashEntry[s.readInt()];
 809     int len = s.readInt();
 810     size = len;
 811     while (len-- > 0)
 812       {
 813         Object key = s.readObject();
 814         addEntry(key, s.readObject(), hash(key), false);
 815       }
 816   }
 817
 818   /**
 819    * Iterate over HashMap's entries.
 820    * This implementation is parameterized to give a sequential view of
 821    * keys, values, or entries.
 822    *
 823    * @author Jon Zeppieri
 824    */
 825   private final class HashIterator implements Iterator
 826   {
 827     /**
 828      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
 829      * or {@link #ENTRIES}.
 830      */
 831     private final int type;
 832     /**
 833      * The number of modifications to the backing HashMap that we know about.
 834      */
 835     private int knownMod = modCount;
 836     /** The number of elements remaining to be returned by next(). */
 837     private int count = size;
 838     /** Current index in the physical hash table. */
 839     private int idx = buckets.length;
 840     /** The last Entry returned by a next() call. */
 841     private HashEntry last;
 842     /**
 843      * The next entry that should be returned by next(). It is set to something
 844      * if we're iterating through a bucket that contains multiple linked
 845      * entries. It is null if next() needs to find a new bucket.
 846      */
 847     private HashEntry next;
 848
 849     /**
 850      * Construct a new HashIterator with the supplied type.
 851      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
 852      */
 853     HashIterator(int type)
 854     {
 855       this.type = type;
 856     }
 857
 858     /**
 859      * Returns true if the Iterator has more elements.
 860      * @return true if there are more elements
 861      * @throws ConcurrentModificationException if the HashMap was modified
 862      */
 863     public boolean hasNext()
 864     {
 865       if (knownMod != modCount)
 866         throw new ConcurrentModificationException();
 867       return count > 0;
 868     }
 869
 870     /**
 871      * Returns the next element in the Iterator's sequential view.
 872      * @return the next element
 873      * @throws ConcurrentModificationException if the HashMap was modified
 874      * @throws NoSuchElementException if there is none
 875      */
 876     public Object next()
 877     {
 878       if (knownMod != modCount)
 879         throw new ConcurrentModificationException();
 880       if (count == 0)
 881         throw new NoSuchElementException();
 882       count--;
 883       HashEntry e = next;
 884
 885       while (e == null)
 886         e = buckets[--idx];
 887
 888       next = e.next;
 889       last = e;
 890       if (type == VALUES)
 891         return e.value;
 892       if (type == KEYS)
 893         return e.key;
 894       return e;
 895     }
 896
 897     /**
 898      * Removes from the backing HashMap the last element which was fetched
 899      * with the <code>next()</code> method.
 900      * @throws ConcurrentModificationException if the HashMap was modified
 901      * @throws IllegalStateException if called when there is no last element
 902      */
 903     public void remove()
 904     {
 905       if (knownMod != modCount)
 906         throw new ConcurrentModificationException();
 907       if (last == null)
 908         throw new IllegalStateException();
 909
 910       HashMap.this.remove(last.key);
 911       last = null;
 912       knownMod++;
 913     }
 914   }
 915 }