Source for java.util.HashMap

   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 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:             HashEntry next = e.next;
 747:             e.next = buckets[idx];
 748:             buckets[idx] = e;
 749:             e = next;
 750:           }
 751:       }
 752:   }
 753: 
 754:   /**
 755:    * Serializes this object to the given stream.
 756:    *
 757:    * @param s the stream to write to
 758:    * @throws IOException if the underlying stream fails
 759:    * @serialData the <i>capacity</i>(int) that is the length of the
 760:    *             bucket array, the <i>size</i>(int) of the hash map
 761:    *             are emitted first.  They are followed by size entries,
 762:    *             each consisting of a key (Object) and a value (Object).
 763:    */
 764:   private void writeObject(ObjectOutputStream s) throws IOException
 765:   {
 766:     // Write the threshold and loadFactor fields.
 767:     s.defaultWriteObject();
 768: 
 769:     s.writeInt(buckets.length);
 770:     s.writeInt(size);
 771:     // Avoid creating a wasted Set by creating the iterator directly.
 772:     Iterator it = iterator(ENTRIES);
 773:     while (it.hasNext())
 774:       {
 775:         HashEntry entry = (HashEntry) it.next();
 776:         s.writeObject(entry.key);
 777:         s.writeObject(entry.value);
 778:       }
 779:   }
 780: 
 781:   /**
 782:    * Deserializes this object from the given stream.
 783:    *
 784:    * @param s the stream to read from
 785:    * @throws ClassNotFoundException if the underlying stream fails
 786:    * @throws IOException if the underlying stream fails
 787:    * @serialData the <i>capacity</i>(int) that is the length of the
 788:    *             bucket array, the <i>size</i>(int) of the hash map
 789:    *             are emitted first.  They are followed by size entries,
 790:    *             each consisting of a key (Object) and a value (Object).
 791:    */
 792:   private void readObject(ObjectInputStream s)
 793:     throws IOException, ClassNotFoundException
 794:   {
 795:     // Read the threshold and loadFactor fields.
 796:     s.defaultReadObject();
 797: 
 798:     // Read and use capacity, followed by key/value pairs.
 799:     buckets = new HashEntry[s.readInt()];
 800:     int len = s.readInt();
 801:     size = len;
 802:     while (len-- > 0)
 803:       {
 804:         Object key = s.readObject();
 805:         addEntry(key, s.readObject(), hash(key), false);
 806:       }
 807:   }
 808: 
 809:   /**
 810:    * Iterate over HashMap's entries.
 811:    * This implementation is parameterized to give a sequential view of
 812:    * keys, values, or entries.
 813:    *
 814:    * @author Jon Zeppieri
 815:    */
 816:   private final class HashIterator implements Iterator
 817:   {
 818:     /**
 819:      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
 820:      * or {@link #ENTRIES}.
 821:      */
 822:     private final int type;
 823:     /**
 824:      * The number of modifications to the backing HashMap that we know about.
 825:      */
 826:     private int knownMod = modCount;
 827:     /** The number of elements remaining to be returned by next(). */
 828:     private int count = size;
 829:     /** Current index in the physical hash table. */
 830:     private int idx = buckets.length;
 831:     /** The last Entry returned by a next() call. */
 832:     private HashEntry last;
 833:     /**
 834:      * The next entry that should be returned by next(). It is set to something
 835:      * if we're iterating through a bucket that contains multiple linked
 836:      * entries. It is null if next() needs to find a new bucket.
 837:      */
 838:     private HashEntry next;
 839: 
 840:     /**
 841:      * Construct a new HashIterator with the supplied type.
 842:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
 843:      */
 844:     HashIterator(int type)
 845:     {
 846:       this.type = type;
 847:     }
 848: 
 849:     /**
 850:      * Returns true if the Iterator has more elements.
 851:      * @return true if there are more elements
 852:      * @throws ConcurrentModificationException if the HashMap was modified
 853:      */
 854:     public boolean hasNext()
 855:     {
 856:       if (knownMod != modCount)
 857:         throw new ConcurrentModificationException();
 858:       return count > 0;
 859:     }
 860: 
 861:     /**
 862:      * Returns the next element in the Iterator's sequential view.
 863:      * @return the next element
 864:      * @throws ConcurrentModificationException if the HashMap was modified
 865:      * @throws NoSuchElementException if there is none
 866:      */
 867:     public Object next()
 868:     {
 869:       if (knownMod != modCount)
 870:         throw new ConcurrentModificationException();
 871:       if (count == 0)
 872:         throw new NoSuchElementException();
 873:       count--;
 874:       HashEntry e = next;
 875: 
 876:       while (e == null)
 877:         e = buckets[--idx];
 878: 
 879:       next = e.next;
 880:       last = e;
 881:       if (type == VALUES)
 882:         return e.value;
 883:       if (type == KEYS)
 884:         return e.key;
 885:       return e;
 886:     }
 887: 
 888:     /**
 889:      * Removes from the backing HashMap the last element which was fetched
 890:      * with the <code>next()</code> method.
 891:      * @throws ConcurrentModificationException if the HashMap was modified
 892:      * @throws IllegalStateException if called when there is no last element
 893:      */
 894:     public void remove()
 895:     {
 896:       if (knownMod != modCount)
 897:         throw new ConcurrentModificationException();
 898:       if (last == null)
 899:         throw new IllegalStateException();
 900: 
 901:       HashMap.this.remove(last.key);
 902:       last = null;
 903:       knownMod++;
 904:     }
 905:   }
 906: }