Source for java.util.Hashtable

   1: /* Hashtable.java -- a class providing a basic hashtable data structure,
   2:    mapping Object --> Object
   3:    Copyright (C) 1998, 1999, 2000, 2001, 2002, 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: package java.util;
  40: 
  41: import java.io.IOException;
  42: import java.io.ObjectInputStream;
  43: import java.io.ObjectOutputStream;
  44: import java.io.Serializable;
  45: 
  46: // NOTE: This implementation is very similar to that of HashMap. If you fix
  47: // a bug in here, chances are you should make a similar change to the HashMap
  48: // code.
  49: 
  50: /**
  51:  * A class which implements a hashtable data structure.
  52:  * <p>
  53:  *
  54:  * This implementation of Hashtable uses a hash-bucket approach. That is:
  55:  * linear probing and rehashing is avoided; instead, each hashed value maps
  56:  * to a simple linked-list which, in the best case, only has one node.
  57:  * Assuming a large enough table, low enough load factor, and / or well
  58:  * implemented hashCode() methods, Hashtable should provide O(1)
  59:  * insertion, deletion, and searching of keys.  Hashtable is O(n) in
  60:  * the worst case for all of these (if all keys hash to the same bucket).
  61:  * <p>
  62:  *
  63:  * This is a JDK-1.2 compliant implementation of Hashtable.  As such, it
  64:  * belongs, partially, to the Collections framework (in that it implements
  65:  * Map).  For backwards compatibility, it inherits from the obsolete and
  66:  * utterly useless Dictionary class.
  67:  * <p>
  68:  *
  69:  * Being a hybrid of old and new, Hashtable has methods which provide redundant
  70:  * capability, but with subtle and even crucial differences.
  71:  * For example, one can iterate over various aspects of a Hashtable with
  72:  * either an Iterator (which is the JDK-1.2 way of doing things) or with an
  73:  * Enumeration.  The latter can end up in an undefined state if the Hashtable
  74:  * changes while the Enumeration is open.
  75:  * <p>
  76:  *
  77:  * Unlike HashMap, Hashtable does not accept `null' as a key value. Also,
  78:  * all accesses are synchronized: in a single thread environment, this is
  79:  * expensive, but in a multi-thread environment, this saves you the effort
  80:  * of extra synchronization. However, the old-style enumerators are not
  81:  * synchronized, because they can lead to unspecified behavior even if
  82:  * they were synchronized. You have been warned.
  83:  * <p>
  84:  *
  85:  * The iterators are <i>fail-fast</i>, meaning that any structural
  86:  * modification, except for <code>remove()</code> called on the iterator
  87:  * itself, cause the iterator to throw a
  88:  * <code>ConcurrentModificationException</code> rather than exhibit
  89:  * non-deterministic behavior.
  90:  *
  91:  * @author Jon Zeppieri
  92:  * @author Warren Levy
  93:  * @author Bryce McKinlay
  94:  * @author Eric Blake (ebb9@email.byu.edu)
  95:  * @see HashMap
  96:  * @see TreeMap
  97:  * @see IdentityHashMap
  98:  * @see LinkedHashMap
  99:  * @since 1.0
 100:  * @status updated to 1.4
 101:  */
 102: public class Hashtable extends Dictionary
 103:   implements Map, Cloneable, Serializable
 104: {
 105:   // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the
 106:   // comments in vm/reference/java/lang/Runtime for implications of this fact.
 107: 
 108:   /** Default number of buckets. This is the value the JDK 1.3 uses. Some
 109:    * early documentation specified this value as 101. That is incorrect.
 110:    */
 111:   private static final int DEFAULT_CAPACITY = 11;
 112: 
 113:   /** An "enum" of iterator types. */
 114:   // Package visible for use by nested classes.
 115:   static final int KEYS = 0,
 116:                    VALUES = 1,
 117:                    ENTRIES = 2;
 118: 
 119:   /**
 120:    * The default load factor; this is explicitly specified by the spec.
 121:    */
 122:   private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 123: 
 124:   /**
 125:    * Compatible with JDK 1.0+.
 126:    */
 127:   private static final long serialVersionUID = 1421746759512286392L;
 128: 
 129:   /**
 130:    * The rounded product of the capacity and the load factor; when the number
 131:    * of elements exceeds the threshold, the Hashtable calls
 132:    * <code>rehash()</code>.
 133:    * @serial
 134:    */
 135:   private int threshold;
 136: 
 137:   /**
 138:    * Load factor of this Hashtable:  used in computing the threshold.
 139:    * @serial
 140:    */
 141:   private final float loadFactor;
 142: 
 143:   /**
 144:    * Array containing the actual key-value mappings.
 145:    */
 146:   // Package visible for use by nested classes.
 147:   transient HashEntry[] buckets;
 148: 
 149:   /**
 150:    * Counts the number of modifications this Hashtable has undergone, used
 151:    * by Iterators to know when to throw ConcurrentModificationExceptions.
 152:    */
 153:   // Package visible for use by nested classes.
 154:   transient int modCount;
 155: 
 156:   /**
 157:    * The size of this Hashtable:  denotes the number of key-value pairs.
 158:    */
 159:   // Package visible for use by nested classes.
 160:   transient int size;
 161: 
 162:   /**
 163:    * The cache for {@link #keySet()}.
 164:    */
 165:   private transient Set keys;
 166: 
 167:   /**
 168:    * The cache for {@link #values()}.
 169:    */
 170:   private transient Collection values;
 171: 
 172:   /**
 173:    * The cache for {@link #entrySet()}.
 174:    */
 175:   private transient Set entries;
 176: 
 177:   /**
 178:    * Class to represent an entry in the hash table. Holds a single key-value
 179:    * pair. A Hashtable Entry is identical to a HashMap Entry, except that
 180:    * `null' is not allowed for keys and values.
 181:    */
 182:   private static final class HashEntry extends AbstractMap.BasicMapEntry
 183:   {
 184:     /** The next entry in the linked list. */
 185:     HashEntry next;
 186: 
 187:     /**
 188:      * Simple constructor.
 189:      * @param key the key, already guaranteed non-null
 190:      * @param value the value, already guaranteed non-null
 191:      */
 192:     HashEntry(Object key, Object value)
 193:     {
 194:       super(key, value);
 195:     }
 196: 
 197:     /**
 198:      * Resets the value.
 199:      * @param newVal the new value
 200:      * @return the prior value
 201:      * @throws NullPointerException if <code>newVal</code> is null
 202:      */
 203:     public Object setValue(Object newVal)
 204:     {
 205:       if (newVal == null)
 206:         throw new NullPointerException();
 207:       return super.setValue(newVal);
 208:     }
 209:   }
 210: 
 211:   /**
 212:    * Construct a new Hashtable with the default capacity (11) and the default
 213:    * load factor (0.75).
 214:    */
 215:   public Hashtable()
 216:   {
 217:     this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
 218:   }
 219: 
 220:   /**
 221:    * Construct a new Hashtable from the given Map, with initial capacity
 222:    * the greater of the size of <code>m</code> or the default of 11.
 223:    * <p>
 224:    *
 225:    * Every element in Map m will be put into this new Hashtable.
 226:    *
 227:    * @param m a Map whose key / value pairs will be put into
 228:    *          the new Hashtable.  <b>NOTE: key / value pairs
 229:    *          are not cloned in this constructor.</b>
 230:    * @throws NullPointerException if m is null, or if m contains a mapping
 231:    *         to or from `null'.
 232:    * @since 1.2
 233:    */
 234:   public Hashtable(Map m)
 235:   {
 236:     this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
 237:     putAll(m);
 238:   }
 239: 
 240:   /**
 241:    * Construct a new Hashtable with a specific inital capacity and
 242:    * default load factor of 0.75.
 243:    *
 244:    * @param initialCapacity the initial capacity of this Hashtable (&gt;= 0)
 245:    * @throws IllegalArgumentException if (initialCapacity &lt; 0)
 246:    */
 247:   public Hashtable(int initialCapacity)
 248:   {
 249:     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 250:   }
 251: 
 252:   /**
 253:    * Construct a new Hashtable with a specific initial capacity and
 254:    * load factor.
 255:    *
 256:    * @param initialCapacity the initial capacity (&gt;= 0)
 257:    * @param loadFactor the load factor (&gt; 0, not NaN)
 258:    * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
 259:    *                                     ! (loadFactor &gt; 0.0)
 260:    */
 261:   public Hashtable(int initialCapacity, float loadFactor)
 262:   {
 263:     if (initialCapacity < 0)
 264:       throw new IllegalArgumentException("Illegal Capacity: "
 265:                                          + initialCapacity);
 266:     if (! (loadFactor > 0)) // check for NaN too
 267:       throw new IllegalArgumentException("Illegal Load: " + loadFactor);
 268: 
 269:     if (initialCapacity == 0)
 270:       initialCapacity = 1;
 271:     buckets = new HashEntry[initialCapacity];
 272:     this.loadFactor = loadFactor;
 273:     threshold = (int) (initialCapacity * loadFactor);
 274:   }
 275: 
 276:   /**
 277:    * Returns the number of key-value mappings currently in this hashtable.
 278:    * @return the size
 279:    */
 280:   public synchronized int size()
 281:   {
 282:     return size;
 283:   }
 284: 
 285:   /**
 286:    * Returns true if there are no key-value mappings currently in this table.
 287:    * @return <code>size() == 0</code>
 288:    */
 289:   public synchronized boolean isEmpty()
 290:   {
 291:     return size == 0;
 292:   }
 293: 
 294:   /**
 295:    * Return an enumeration of the keys of this table. There's no point
 296:    * in synchronizing this, as you have already been warned that the
 297:    * enumeration is not specified to be thread-safe.
 298:    *
 299:    * @return the keys
 300:    * @see #elements()
 301:    * @see #keySet()
 302:    */
 303:   public Enumeration keys()
 304:   {
 305:     return new Enumerator(KEYS);
 306:   }
 307: 
 308:   /**
 309:    * Return an enumeration of the values of this table. There's no point
 310:    * in synchronizing this, as you have already been warned that the
 311:    * enumeration is not specified to be thread-safe.
 312:    *
 313:    * @return the values
 314:    * @see #keys()
 315:    * @see #values()
 316:    */
 317:   public Enumeration elements()
 318:   {
 319:     return new Enumerator(VALUES);
 320:   }
 321: 
 322:   /**
 323:    * Returns true if this Hashtable contains a value <code>o</code>,
 324:    * such that <code>o.equals(value)</code>.  This is the same as
 325:    * <code>containsValue()</code>, and is O(n).
 326:    * <p>
 327:    *
 328:    * @param value the value to search for in this Hashtable
 329:    * @return true if at least one key maps to the value
 330:    * @throws NullPointerException if <code>value</code> is null
 331:    * @see #containsValue(Object)
 332:    * @see #containsKey(Object)
 333:    */
 334:   public synchronized boolean contains(Object value)
 335:   {
 336:     for (int i = buckets.length - 1; i >= 0; i--)
 337:       {
 338:         HashEntry e = buckets[i];
 339:         while (e != null)
 340:           {
 341:             if (value.equals(e.value))
 342:               return true;
 343:             e = e.next;
 344:           }
 345:       }
 346: 
 347:     // Must throw on null argument even if the table is empty
 348:     if (value == null)
 349:       throw new NullPointerException();
 350:  
 351:     return false;  
 352:   }
 353: 
 354:   /**
 355:    * Returns true if this Hashtable contains a value <code>o</code>, such that
 356:    * <code>o.equals(value)</code>. This is the new API for the old
 357:    * <code>contains()</code>.
 358:    *
 359:    * @param value the value to search for in this Hashtable
 360:    * @return true if at least one key maps to the value
 361:    * @see #contains(Object)
 362:    * @see #containsKey(Object)
 363:    * @throws NullPointerException if <code>value</code> is null
 364:    * @since 1.2
 365:    */
 366:   public boolean containsValue(Object value)
 367:   {
 368:     // Delegate to older method to make sure code overriding it continues 
 369:     // to work.
 370:     return contains(value);
 371:   }
 372: 
 373:   /**
 374:    * Returns true if the supplied object <code>equals()</code> a key
 375:    * in this Hashtable.
 376:    *
 377:    * @param key the key to search for in this Hashtable
 378:    * @return true if the key is in the table
 379:    * @throws NullPointerException if key is null
 380:    * @see #containsValue(Object)
 381:    */
 382:   public synchronized boolean containsKey(Object key)
 383:   {
 384:     int idx = hash(key);
 385:     HashEntry e = buckets[idx];
 386:     while (e != null)
 387:       {
 388:         if (key.equals(e.key))
 389:           return true;
 390:         e = e.next;
 391:       }
 392:     return false;
 393:   }
 394: 
 395:   /**
 396:    * Return the value in this Hashtable associated with the supplied key,
 397:    * or <code>null</code> if the key maps to nothing.
 398:    *
 399:    * @param key the key for which to fetch an associated value
 400:    * @return what the key maps to, if present
 401:    * @throws NullPointerException if key is null
 402:    * @see #put(Object, Object)
 403:    * @see #containsKey(Object)
 404:    */
 405:   public synchronized Object get(Object key)
 406:   {
 407:     int idx = hash(key);
 408:     HashEntry e = buckets[idx];
 409:     while (e != null)
 410:       {
 411:         if (key.equals(e.key))
 412:           return e.value;
 413:         e = e.next;
 414:       }
 415:     return null;
 416:   }
 417: 
 418:   /**
 419:    * Puts the supplied value into the Map, mapped by the supplied key.
 420:    * Neither parameter may be null.  The value may be retrieved by any
 421:    * object which <code>equals()</code> this key.
 422:    *
 423:    * @param key the key used to locate the value
 424:    * @param value the value to be stored in the table
 425:    * @return the prior mapping of the key, or null if there was none
 426:    * @throws NullPointerException if key or value is null
 427:    * @see #get(Object)
 428:    * @see Object#equals(Object)
 429:    */
 430:   public synchronized Object put(Object key, Object value)
 431:   {
 432:     int idx = hash(key);
 433:     HashEntry e = buckets[idx];
 434: 
 435:     // Check if value is null since it is not permitted.
 436:     if (value == null)
 437:       throw new NullPointerException();
 438: 
 439:     while (e != null)
 440:       {
 441:         if (key.equals(e.key))
 442:           {
 443:             // Bypass e.setValue, since we already know value is non-null.
 444:             Object r = e.value;
 445:             e.value = value;
 446:             return r;
 447:           }
 448:         else
 449:           {
 450:             e = e.next;
 451:           }
 452:       }
 453: 
 454:     // At this point, we know we need to add a new entry.
 455:     modCount++;
 456:     if (++size > threshold)
 457:       {
 458:         rehash();
 459:         // Need a new hash value to suit the bigger table.
 460:         idx = hash(key);
 461:       }
 462: 
 463:     e = new HashEntry(key, value);
 464: 
 465:     e.next = buckets[idx];
 466:     buckets[idx] = e;
 467: 
 468:     return null;
 469:   }
 470: 
 471:   /**
 472:    * Removes from the table and returns the value which is mapped by the
 473:    * supplied key. If the key maps to nothing, then the table remains
 474:    * unchanged, and <code>null</code> is returned.
 475:    *
 476:    * @param key the key used to locate the value to remove
 477:    * @return whatever the key mapped to, if present
 478:    */
 479:   public synchronized Object remove(Object key)
 480:   {
 481:     int idx = hash(key);
 482:     HashEntry e = buckets[idx];
 483:     HashEntry last = null;
 484: 
 485:     while (e != null)
 486:       {
 487:         if (key.equals(e.key))
 488:           {
 489:             modCount++;
 490:             if (last == null)
 491:               buckets[idx] = e.next;
 492:             else
 493:               last.next = e.next;
 494:             size--;
 495:             return e.value;
 496:           }
 497:         last = e;
 498:         e = e.next;
 499:       }
 500:     return null;
 501:   }
 502: 
 503:   /**
 504:    * Copies all elements of the given map into this hashtable.  However, no
 505:    * mapping can contain null as key or value.  If this table already has
 506:    * a mapping for a key, the new mapping replaces the current one.
 507:    *
 508:    * @param m the map to be hashed into this
 509:    * @throws NullPointerException if m is null, or contains null keys or values
 510:    */
 511:   public synchronized void putAll(Map m)
 512:   {
 513:     Iterator itr = m.entrySet().iterator();
 514: 
 515:     while (itr.hasNext())
 516:       {
 517:         Map.Entry e = (Map.Entry) itr.next();
 518:         // Optimize in case the Entry is one of our own.
 519:         if (e instanceof AbstractMap.BasicMapEntry)
 520:           {
 521:             AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e;
 522:             put(entry.key, entry.value);
 523:           }
 524:         else
 525:           {
 526:             put(e.getKey(), e.getValue());
 527:           }
 528:       }
 529:   }
 530: 
 531:   /**
 532:    * Clears the hashtable so it has no keys.  This is O(1).
 533:    */
 534:   public synchronized void clear()
 535:   {
 536:     if (size > 0)
 537:       {
 538:         modCount++;
 539:         Arrays.fill(buckets, null);
 540:         size = 0;
 541:       }
 542:   }
 543: 
 544:   /**
 545:    * Returns a shallow clone of this Hashtable. The Map itself is cloned,
 546:    * but its contents are not.  This is O(n).
 547:    *
 548:    * @return the clone
 549:    */
 550:   public synchronized Object clone()
 551:   {
 552:     Hashtable copy = null;
 553:     try
 554:       {
 555:         copy = (Hashtable) super.clone();
 556:       }
 557:     catch (CloneNotSupportedException x)
 558:       {
 559:         // This is impossible.
 560:       }
 561:     copy.buckets = new HashEntry[buckets.length];
 562:     copy.putAllInternal(this);
 563:     // Clear the caches.
 564:     copy.keys = null;
 565:     copy.values = null;
 566:     copy.entries = null;
 567:     return copy;
 568:   }
 569: 
 570:   /**
 571:    * Converts this Hashtable to a String, surrounded by braces, and with
 572:    * key/value pairs listed with an equals sign between, separated by a
 573:    * comma and space. For example, <code>"{a=1, b=2}"</code>.<p>
 574:    *
 575:    * NOTE: if the <code>toString()</code> method of any key or value
 576:    * throws an exception, this will fail for the same reason.
 577:    *
 578:    * @return the string representation
 579:    */
 580:   public synchronized String toString()
 581:   {
 582:     // Since we are already synchronized, and entrySet().iterator()
 583:     // would repeatedly re-lock/release the monitor, we directly use the
 584:     // unsynchronized HashIterator instead.
 585:     Iterator entries = new HashIterator(ENTRIES);
 586:     StringBuffer r = new StringBuffer("{");
 587:     for (int pos = size; pos > 0; pos--)
 588:       {
 589:         r.append(entries.next());
 590:         if (pos > 1)
 591:           r.append(", ");
 592:       }
 593:     r.append("}");
 594:     return r.toString();
 595:   }
 596: 
 597:   /**
 598:    * Returns a "set view" of this Hashtable's keys. The set is backed by
 599:    * the hashtable, so changes in one show up in the other.  The set supports
 600:    * element removal, but not element addition.  The set is properly
 601:    * synchronized on the original hashtable.  Sun has not documented the
 602:    * proper interaction of null with this set, but has inconsistent behavior
 603:    * in the JDK. Therefore, in this implementation, contains, remove,
 604:    * containsAll, retainAll, removeAll, and equals just ignore a null key
 605:    * rather than throwing a {@link NullPointerException}.
 606:    *
 607:    * @return a set view of the keys
 608:    * @see #values()
 609:    * @see #entrySet()
 610:    * @since 1.2
 611:    */
 612:   public Set keySet()
 613:   {
 614:     if (keys == null)
 615:       {
 616:         // Create a synchronized AbstractSet with custom implementations of
 617:         // those methods that can be overridden easily and efficiently.
 618:         Set r = new AbstractSet()
 619:         {
 620:           public int size()
 621:           {
 622:             return size;
 623:           }
 624: 
 625:           public Iterator iterator()
 626:           {
 627:             return new HashIterator(KEYS);
 628:           }
 629: 
 630:           public void clear()
 631:           {
 632:             Hashtable.this.clear();
 633:           }
 634: 
 635:           public boolean contains(Object o)
 636:           {
 637:             if (o == null)
 638:               return false;
 639:             return containsKey(o);
 640:           }
 641: 
 642:           public boolean remove(Object o)
 643:           {
 644:             return Hashtable.this.remove(o) != null;
 645:           }
 646:         };
 647:         // We must specify the correct object to synchronize upon, hence the
 648:         // use of a non-public API
 649:         keys = new Collections.SynchronizedSet(this, r);
 650:       }
 651:     return keys;
 652:   }
 653: 
 654:   /**
 655:    * Returns a "collection view" (or "bag view") of this Hashtable's values.
 656:    * The collection is backed by the hashtable, so changes in one show up
 657:    * in the other.  The collection supports element removal, but not element
 658:    * addition.  The collection is properly synchronized on the original
 659:    * hashtable.  Sun has not documented the proper interaction of null with
 660:    * this set, but has inconsistent behavior in the JDK. Therefore, in this
 661:    * implementation, contains, remove, containsAll, retainAll, removeAll, and
 662:    * equals just ignore a null value rather than throwing a
 663:    * {@link NullPointerException}.
 664:    *
 665:    * @return a bag view of the values
 666:    * @see #keySet()
 667:    * @see #entrySet()
 668:    * @since 1.2
 669:    */
 670:   public Collection values()
 671:   {
 672:     if (values == null)
 673:       {
 674:         // We don't bother overriding many of the optional methods, as doing so
 675:         // wouldn't provide any significant performance advantage.
 676:         Collection r = new AbstractCollection()
 677:         {
 678:           public int size()
 679:           {
 680:             return size;
 681:           }
 682: 
 683:           public Iterator iterator()
 684:           {
 685:             return new HashIterator(VALUES);
 686:           }
 687: 
 688:           public void clear()
 689:           {
 690:             Hashtable.this.clear();
 691:           }
 692:         };
 693:         // We must specify the correct object to synchronize upon, hence the
 694:         // use of a non-public API
 695:         values = new Collections.SynchronizedCollection(this, r);
 696:       }
 697:     return values;
 698:   }
 699: 
 700:   /**
 701:    * Returns a "set view" of this Hashtable's entries. The set is backed by
 702:    * the hashtable, so changes in one show up in the other.  The set supports
 703:    * element removal, but not element addition.  The set is properly
 704:    * synchronized on the original hashtable.  Sun has not documented the
 705:    * proper interaction of null with this set, but has inconsistent behavior
 706:    * in the JDK. Therefore, in this implementation, contains, remove,
 707:    * containsAll, retainAll, removeAll, and equals just ignore a null entry,
 708:    * or an entry with a null key or value, rather than throwing a
 709:    * {@link NullPointerException}. However, calling entry.setValue(null)
 710:    * will fail.
 711:    * <p>
 712:    *
 713:    * Note that the iterators for all three views, from keySet(), entrySet(),
 714:    * and values(), traverse the hashtable in the same sequence.
 715:    *
 716:    * @return a set view of the entries
 717:    * @see #keySet()
 718:    * @see #values()
 719:    * @see Map.Entry
 720:    * @since 1.2
 721:    */
 722:   public Set entrySet()
 723:   {
 724:     if (entries == null)
 725:       {
 726:         // Create an AbstractSet with custom implementations of those methods
 727:         // that can be overridden easily and efficiently.
 728:         Set r = new AbstractSet()
 729:         {
 730:           public int size()
 731:           {
 732:             return size;
 733:           }
 734: 
 735:           public Iterator iterator()
 736:           {
 737:             return new HashIterator(ENTRIES);
 738:           }
 739: 
 740:           public void clear()
 741:           {
 742:             Hashtable.this.clear();
 743:           }
 744: 
 745:           public boolean contains(Object o)
 746:           {
 747:             return getEntry(o) != null;
 748:           }
 749: 
 750:           public boolean remove(Object o)
 751:           {
 752:             HashEntry e = getEntry(o);
 753:             if (e != null)
 754:               {
 755:                 Hashtable.this.remove(e.key);
 756:                 return true;
 757:               }
 758:             return false;
 759:           }
 760:         };
 761:         // We must specify the correct object to synchronize upon, hence the
 762:         // use of a non-public API
 763:         entries = new Collections.SynchronizedSet(this, r);
 764:       }
 765:     return entries;
 766:   }
 767: 
 768:   /**
 769:    * Returns true if this Hashtable equals the supplied Object <code>o</code>.
 770:    * As specified by Map, this is:
 771:    * <code>
 772:    * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
 773:    * </code>
 774:    *
 775:    * @param o the object to compare to
 776:    * @return true if o is an equal map
 777:    * @since 1.2
 778:    */
 779:   public boolean equals(Object o)
 780:   {
 781:     // no need to synchronize, entrySet().equals() does that
 782:     if (o == this)
 783:       return true;
 784:     if (!(o instanceof Map))
 785:       return false;
 786: 
 787:     return entrySet().equals(((Map) o).entrySet());
 788:   }
 789: 
 790:   /**
 791:    * Returns the hashCode for this Hashtable.  As specified by Map, this is
 792:    * the sum of the hashCodes of all of its Map.Entry objects
 793:    *
 794:    * @return the sum of the hashcodes of the entries
 795:    * @since 1.2
 796:    */
 797:   public synchronized int hashCode()
 798:   {
 799:     // Since we are already synchronized, and entrySet().iterator()
 800:     // would repeatedly re-lock/release the monitor, we directly use the
 801:     // unsynchronized HashIterator instead.
 802:     Iterator itr = new HashIterator(ENTRIES);
 803:     int hashcode = 0;
 804:     for (int pos = size; pos > 0; pos--)
 805:       hashcode += itr.next().hashCode();
 806: 
 807:     return hashcode;
 808:   }
 809: 
 810:   /**
 811:    * Helper method that returns an index in the buckets array for `key'
 812:    * based on its hashCode().
 813:    *
 814:    * @param key the key
 815:    * @return the bucket number
 816:    * @throws NullPointerException if key is null
 817:    */
 818:   private int hash(Object key)
 819:   {
 820:     // Note: Inline Math.abs here, for less method overhead, and to avoid
 821:     // a bootstrap dependency, since Math relies on native methods.
 822:     int hash = key.hashCode() % buckets.length;
 823:     return hash < 0 ? -hash : hash;
 824:   }
 825: 
 826:   /**
 827:    * Helper method for entrySet(), which matches both key and value
 828:    * simultaneously. Ignores null, as mentioned in entrySet().
 829:    *
 830:    * @param o the entry to match
 831:    * @return the matching entry, if found, or null
 832:    * @see #entrySet()
 833:    */
 834:   // Package visible, for use in nested classes.
 835:   HashEntry getEntry(Object o)
 836:   {
 837:     if (! (o instanceof Map.Entry))
 838:       return null;
 839:     Object key = ((Map.Entry) o).getKey();
 840:     if (key == null)
 841:       return null;
 842: 
 843:     int idx = hash(key);
 844:     HashEntry e = buckets[idx];
 845:     while (e != null)
 846:       {
 847:         if (o.equals(e))
 848:           return e;
 849:         e = e.next;
 850:       }
 851:     return null;
 852:   }
 853: 
 854:   /**
 855:    * A simplified, more efficient internal implementation of putAll(). clone() 
 856:    * should not call putAll or put, in order to be compatible with the JDK 
 857:    * implementation with respect to subclasses.
 858:    *
 859:    * @param m the map to initialize this from
 860:    */
 861:   void putAllInternal(Map m)
 862:   {
 863:     Iterator itr = m.entrySet().iterator();
 864:     size = 0;
 865: 
 866:     while (itr.hasNext())
 867:       {
 868:         size++;
 869:     Map.Entry e = (Map.Entry) itr.next();
 870:     Object key = e.getKey();
 871:     int idx = hash(key);
 872:     HashEntry he = new HashEntry(key, e.getValue());
 873:     he.next = buckets[idx];
 874:     buckets[idx] = he;
 875:       }
 876:   }
 877: 
 878:   /**
 879:    * Increases the size of the Hashtable and rehashes all keys to new array
 880:    * indices; this is called when the addition of a new value would cause
 881:    * size() &gt; threshold. Note that the existing Entry objects are reused in
 882:    * the new hash table.
 883:    * <p>
 884:    *
 885:    * This is not specified, but the new size is twice the current size plus
 886:    * one; this number is not always prime, unfortunately. This implementation
 887:    * is not synchronized, as it is only invoked from synchronized methods.
 888:    */
 889:   protected void rehash()
 890:   {
 891:     HashEntry[] oldBuckets = buckets;
 892: 
 893:     int newcapacity = (buckets.length * 2) + 1;
 894:     threshold = (int) (newcapacity * loadFactor);
 895:     buckets = new HashEntry[newcapacity];
 896: 
 897:     for (int i = oldBuckets.length - 1; i >= 0; i--)
 898:       {
 899:         HashEntry e = oldBuckets[i];
 900:         while (e != null)
 901:           {
 902:             int idx = hash(e.key);
 903:             HashEntry dest = buckets[idx];
 904: 
 905:             if (dest != null)
 906:               {
 907:                 while (dest.next != null)
 908:                   dest = dest.next;
 909:                 dest.next = e;
 910:               }
 911:             else
 912:               {
 913:                 buckets[idx] = e;
 914:               }
 915: 
 916:             HashEntry next = e.next;
 917:             e.next = null;
 918:             e = next;
 919:           }
 920:       }
 921:   }
 922: 
 923:   /**
 924:    * Serializes this object to the given stream.
 925:    *
 926:    * @param s the stream to write to
 927:    * @throws IOException if the underlying stream fails
 928:    * @serialData the <i>capacity</i> (int) that is the length of the
 929:    *             bucket array, the <i>size</i> (int) of the hash map
 930:    *             are emitted first.  They are followed by size entries,
 931:    *             each consisting of a key (Object) and a value (Object).
 932:    */
 933:   private synchronized void writeObject(ObjectOutputStream s)
 934:     throws IOException
 935:   {
 936:     // Write the threshold and loadFactor fields.
 937:     s.defaultWriteObject();
 938: 
 939:     s.writeInt(buckets.length);
 940:     s.writeInt(size);
 941:     // Since we are already synchronized, and entrySet().iterator()
 942:     // would repeatedly re-lock/release the monitor, we directly use the
 943:     // unsynchronized HashIterator instead.
 944:     Iterator it = new HashIterator(ENTRIES);
 945:     while (it.hasNext())
 946:       {
 947:         HashEntry entry = (HashEntry) it.next();
 948:         s.writeObject(entry.key);
 949:         s.writeObject(entry.value);
 950:       }
 951:   }
 952: 
 953:   /**
 954:    * Deserializes this object from the given stream.
 955:    *
 956:    * @param s the stream to read from
 957:    * @throws ClassNotFoundException if the underlying stream fails
 958:    * @throws IOException if the underlying stream fails
 959:    * @serialData the <i>capacity</i> (int) that is the length of the
 960:    *             bucket array, the <i>size</i> (int) of the hash map
 961:    *             are emitted first.  They are followed by size entries,
 962:    *             each consisting of a key (Object) and a value (Object).
 963:    */
 964:   private void readObject(ObjectInputStream s)
 965:     throws IOException, ClassNotFoundException
 966:   {
 967:     // Read the threshold and loadFactor fields.
 968:     s.defaultReadObject();
 969: 
 970:     // Read and use capacity.
 971:     buckets = new HashEntry[s.readInt()];
 972:     int len = s.readInt();
 973: 
 974:     // Read and use key/value pairs.
 975:     // TODO: should we be defensive programmers, and check for illegal nulls?
 976:     while (--len >= 0)
 977:       put(s.readObject(), s.readObject());
 978:   }
 979: 
 980:   /**
 981:    * A class which implements the Iterator interface and is used for
 982:    * iterating over Hashtables.
 983:    * This implementation is parameterized to give a sequential view of
 984:    * keys, values, or entries; it also allows the removal of elements,
 985:    * as per the Javasoft spec.  Note that it is not synchronized; this is
 986:    * a performance enhancer since it is never exposed externally and is
 987:    * only used within synchronized blocks above.
 988:    *
 989:    * @author Jon Zeppieri
 990:    */
 991:   private final class HashIterator implements Iterator
 992:   {
 993:     /**
 994:      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
 995:      * or {@link #ENTRIES}.
 996:      */
 997:     final int type;
 998:     /**
 999:      * The number of modifications to the backing Hashtable that we know about.
1000:      */
1001:     int knownMod = modCount;
1002:     /** The number of elements remaining to be returned by next(). */
1003:     int count = size;
1004:     /** Current index in the physical hash table. */
1005:     int idx = buckets.length;
1006:     /** The last Entry returned by a next() call. */
1007:     HashEntry last;
1008:     /**
1009:      * The next entry that should be returned by next(). It is set to something
1010:      * if we're iterating through a bucket that contains multiple linked
1011:      * entries. It is null if next() needs to find a new bucket.
1012:      */
1013:     HashEntry next;
1014: 
1015:     /**
1016:      * Construct a new HashIterator with the supplied type.
1017:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1018:      */
1019:     HashIterator(int type)
1020:     {
1021:       this.type = type;
1022:     }
1023: 
1024:     /**
1025:      * Returns true if the Iterator has more elements.
1026:      * @return true if there are more elements
1027:      * @throws ConcurrentModificationException if the hashtable was modified
1028:      */
1029:     public boolean hasNext()
1030:     {
1031:       if (knownMod != modCount)
1032:         throw new ConcurrentModificationException();
1033:       return count > 0;
1034:     }
1035: 
1036:     /**
1037:      * Returns the next element in the Iterator's sequential view.
1038:      * @return the next element
1039:      * @throws ConcurrentModificationException if the hashtable was modified
1040:      * @throws NoSuchElementException if there is none
1041:      */
1042:     public Object next()
1043:     {
1044:       if (knownMod != modCount)
1045:         throw new ConcurrentModificationException();
1046:       if (count == 0)
1047:         throw new NoSuchElementException();
1048:       count--;
1049:       HashEntry e = next;
1050: 
1051:       while (e == null)
1052:         e = buckets[--idx];
1053: 
1054:       next = e.next;
1055:       last = e;
1056:       if (type == VALUES)
1057:         return e.value;
1058:       if (type == KEYS)
1059:         return e.key;
1060:       return e;
1061:     }
1062: 
1063:     /**
1064:      * Removes from the backing Hashtable the last element which was fetched
1065:      * with the <code>next()</code> method.
1066:      * @throws ConcurrentModificationException if the hashtable was modified
1067:      * @throws IllegalStateException if called when there is no last element
1068:      */
1069:     public void remove()
1070:     {
1071:       if (knownMod != modCount)
1072:         throw new ConcurrentModificationException();
1073:       if (last == null)
1074:         throw new IllegalStateException();
1075: 
1076:       Hashtable.this.remove(last.key);
1077:       last = null;
1078:       knownMod++;
1079:     }
1080:   } // class HashIterator
1081: 
1082: 
1083:   /**
1084:    * Enumeration view of this Hashtable, providing sequential access to its
1085:    * elements; this implementation is parameterized to provide access either
1086:    * to the keys or to the values in the Hashtable.
1087:    *
1088:    * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1089:    * as this could cause a rehash and we'd completely lose our place.  Even
1090:    * without a rehash, it is undetermined if a new element added would
1091:    * appear in the enumeration.  The spec says nothing about this, but
1092:    * the "Java Class Libraries" book infers that modifications to the
1093:    * hashtable during enumeration causes indeterminate results.  Don't do it!
1094:    *
1095:    * @author Jon Zeppieri
1096:    */
1097:   private final class Enumerator implements Enumeration
1098:   {
1099:     /**
1100:      * The type of this Iterator: {@link #KEYS} or {@link #VALUES}.
1101:      */
1102:     final int type;
1103:     /** The number of elements remaining to be returned by next(). */
1104:     int count = size;
1105:     /** Current index in the physical hash table. */
1106:     int idx = buckets.length;
1107:     /**
1108:      * Entry which will be returned by the next nextElement() call. It is
1109:      * set if we are iterating through a bucket with multiple entries, or null
1110:      * if we must look in the next bucket.
1111:      */
1112:     HashEntry next;
1113: 
1114:     /**
1115:      * Construct the enumeration.
1116:      * @param type either {@link #KEYS} or {@link #VALUES}.
1117:      */
1118:     Enumerator(int type)
1119:     {
1120:       this.type = type;
1121:     }
1122: 
1123:     /**
1124:      * Checks whether more elements remain in the enumeration.
1125:      * @return true if nextElement() will not fail.
1126:      */
1127:     public boolean hasMoreElements()
1128:     {
1129:       return count > 0;
1130:     }
1131: 
1132:     /**
1133:      * Returns the next element.
1134:      * @return the next element
1135:      * @throws NoSuchElementException if there is none.
1136:      */
1137:     public Object nextElement()
1138:     {
1139:       if (count == 0)
1140:         throw new NoSuchElementException("Hashtable Enumerator");
1141:       count--;
1142:       HashEntry e = next;
1143: 
1144:       while (e == null)
1145:         e = buckets[--idx];
1146: 
1147:       next = e.next;
1148:       return type == VALUES ? e.value : e.key;
1149:     }
1150:   } // class Enumerator
1151: } // class Hashtable