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, 2006
   4:    Free Software Foundation, Inc.
   5: 
   6: This file is part of GNU Classpath.
   7: 
   8: GNU Classpath is free software; you can redistribute it and/or modify
   9: it under the terms of the GNU General Public License as published by
  10: the Free Software Foundation; either version 2, or (at your option)
  11: any later version.
  12: 
  13: GNU Classpath is distributed in the hope that it will be useful, but
  14: WITHOUT ANY WARRANTY; without even the implied warranty of
  15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16: General Public License for more details.
  17: 
  18: You should have received a copy of the GNU General Public License
  19: along with GNU Classpath; see the file COPYING.  If not, write to the
  20: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21: 02110-1301 USA.
  22: 
  23: Linking this library statically or dynamically with other modules is
  24: making a combined work based on this library.  Thus, the terms and
  25: conditions of the GNU General Public License cover the whole
  26: combination.
  27: 
  28: As a special exception, the copyright holders of this library give you
  29: permission to link this library with independent modules to produce an
  30: executable, regardless of the license terms of these independent
  31: modules, and to copy and distribute the resulting executable under
  32: terms of your choice, provided that you also meet, for each linked
  33: independent module, the terms and conditions of the license of that
  34: module.  An independent module is a module which is not derived from
  35: or based on this library.  If you modify this library, you may extend
  36: this exception to your version of the library, but you are not
  37: obligated to do so.  If you do not wish to do so, delete this
  38: exception statement from your version. */
  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 HashMap. If you fix
  48: // a bug in here, chances are you should make a similar change to the HashMap
  49: // code.
  50: 
  51: /**
  52:  * A class which implements a hashtable data structure.
  53:  * <p>
  54:  *
  55:  * This implementation of Hashtable uses a hash-bucket approach. That is:
  56:  * linear probing and rehashing is avoided; instead, each hashed value maps
  57:  * to a simple linked-list which, in the best case, only has one node.
  58:  * Assuming a large enough table, low enough load factor, and / or well
  59:  * implemented hashCode() methods, Hashtable should provide O(1)
  60:  * insertion, deletion, and searching of keys.  Hashtable is O(n) in
  61:  * the worst case for all of these (if all keys hash to the same bucket).
  62:  * <p>
  63:  *
  64:  * This is a JDK-1.2 compliant implementation of Hashtable.  As such, it
  65:  * belongs, partially, to the Collections framework (in that it implements
  66:  * Map).  For backwards compatibility, it inherits from the obsolete and
  67:  * utterly useless Dictionary class.
  68:  * <p>
  69:  *
  70:  * Being a hybrid of old and new, Hashtable has methods which provide redundant
  71:  * capability, but with subtle and even crucial differences.
  72:  * For example, one can iterate over various aspects of a Hashtable with
  73:  * either an Iterator (which is the JDK-1.2 way of doing things) or with an
  74:  * Enumeration.  The latter can end up in an undefined state if the Hashtable
  75:  * changes while the Enumeration is open.
  76:  * <p>
  77:  *
  78:  * Unlike HashMap, Hashtable does not accept `null' as a key value. Also,
  79:  * all accesses are synchronized: in a single thread environment, this is
  80:  * expensive, but in a multi-thread environment, this saves you the effort
  81:  * of extra synchronization. However, the old-style enumerators are not
  82:  * synchronized, because they can lead to unspecified behavior even if
  83:  * they were synchronized. You have been warned.
  84:  * <p>
  85:  *
  86:  * The iterators are <i>fail-fast</i>, meaning that any structural
  87:  * modification, except for <code>remove()</code> called on the iterator
  88:  * itself, cause the iterator to throw a
  89:  * <code>ConcurrentModificationException</code> rather than exhibit
  90:  * non-deterministic behavior.
  91:  *
  92:  * @author Jon Zeppieri
  93:  * @author Warren Levy
  94:  * @author Bryce McKinlay
  95:  * @author Eric Blake (ebb9@email.byu.edu)
  96:  * @see HashMap
  97:  * @see TreeMap
  98:  * @see IdentityHashMap
  99:  * @see LinkedHashMap
 100:  * @since 1.0
 101:  * @status updated to 1.4
 102:  */
 103: public class Hashtable extends Dictionary
 104:   implements Map, Cloneable, Serializable
 105: {
 106:   // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the
 107:   // comments in vm/reference/java/lang/Runtime for implications of this fact.
 108: 
 109:   /** Default number of buckets. This is the value the JDK 1.3 uses. Some
 110:    * early documentation specified this value as 101. That is incorrect.
 111:    */
 112:   private static final int DEFAULT_CAPACITY = 11;
 113: 
 114:   /** An "enum" of iterator types. */
 115:   // Package visible for use by nested classes.
 116:   static final int KEYS = 0,
 117:                    VALUES = 1,
 118:                    ENTRIES = 2;
 119: 
 120:   /**
 121:    * The default load factor; this is explicitly specified by the spec.
 122:    */
 123:   private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 124: 
 125:   /**
 126:    * Compatible with JDK 1.0+.
 127:    */
 128:   private static final long serialVersionUID = 1421746759512286392L;
 129: 
 130:   /**
 131:    * The rounded product of the capacity and the load factor; when the number
 132:    * of elements exceeds the threshold, the Hashtable calls
 133:    * <code>rehash()</code>.
 134:    * @serial
 135:    */
 136:   private int threshold;
 137: 
 138:   /**
 139:    * Load factor of this Hashtable:  used in computing the threshold.
 140:    * @serial
 141:    */
 142:   private final float loadFactor;
 143: 
 144:   /**
 145:    * Array containing the actual key-value mappings.
 146:    */
 147:   // Package visible for use by nested classes.
 148:   transient HashEntry[] buckets;
 149: 
 150:   /**
 151:    * Counts the number of modifications this Hashtable has undergone, used
 152:    * by Iterators to know when to throw ConcurrentModificationExceptions.
 153:    */
 154:   // Package visible for use by nested classes.
 155:   transient int modCount;
 156: 
 157:   /**
 158:    * The size of this Hashtable:  denotes the number of key-value pairs.
 159:    */
 160:   // Package visible for use by nested classes.
 161:   transient int size;
 162: 
 163:   /**
 164:    * The cache for {@link #keySet()}.
 165:    */
 166:   private transient Set keys;
 167: 
 168:   /**
 169:    * The cache for {@link #values()}.
 170:    */
 171:   private transient Collection values;
 172: 
 173:   /**
 174:    * The cache for {@link #entrySet()}.
 175:    */
 176:   private transient Set entries;
 177: 
 178:   /**
 179:    * Class to represent an entry in the hash table. Holds a single key-value
 180:    * pair. A Hashtable Entry is identical to a HashMap Entry, except that
 181:    * `null' is not allowed for keys and values.
 182:    */
 183:   private static final class HashEntry extends AbstractMap.BasicMapEntry
 184:   {
 185:     /** The next entry in the linked list. */
 186:     HashEntry next;
 187: 
 188:     /**
 189:      * Simple constructor.
 190:      * @param key the key, already guaranteed non-null
 191:      * @param value the value, already guaranteed non-null
 192:      */
 193:     HashEntry(Object key, Object value)
 194:     {
 195:       super(key, value);
 196:     }
 197: 
 198:     /**
 199:      * Resets the value.
 200:      * @param newVal the new value
 201:      * @return the prior value
 202:      * @throws NullPointerException if <code>newVal</code> is null
 203:      */
 204:     public Object setValue(Object newVal)
 205:     {
 206:       if (newVal == null)
 207:         throw new NullPointerException();
 208:       return super.setValue(newVal);
 209:     }
 210:   }
 211: 
 212:   /**
 213:    * Construct a new Hashtable with the default capacity (11) and the default
 214:    * load factor (0.75).
 215:    */
 216:   public Hashtable()
 217:   {
 218:     this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
 219:   }
 220: 
 221:   /**
 222:    * Construct a new Hashtable from the given Map, with initial capacity
 223:    * the greater of the size of <code>m</code> or the default of 11.
 224:    * <p>
 225:    *
 226:    * Every element in Map m will be put into this new Hashtable.
 227:    *
 228:    * @param m a Map whose key / value pairs will be put into
 229:    *          the new Hashtable.  <b>NOTE: key / value pairs
 230:    *          are not cloned in this constructor.</b>
 231:    * @throws NullPointerException if m is null, or if m contains a mapping
 232:    *         to or from `null'.
 233:    * @since 1.2
 234:    */
 235:   public Hashtable(Map m)
 236:   {
 237:     this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
 238:     putAll(m);
 239:   }
 240: 
 241:   /**
 242:    * Construct a new Hashtable with a specific inital capacity and
 243:    * default load factor of 0.75.
 244:    *
 245:    * @param initialCapacity the initial capacity of this Hashtable (&gt;= 0)
 246:    * @throws IllegalArgumentException if (initialCapacity &lt; 0)
 247:    */
 248:   public Hashtable(int initialCapacity)
 249:   {
 250:     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 251:   }
 252: 
 253:   /**
 254:    * Construct a new Hashtable with a specific initial capacity and
 255:    * load factor.
 256:    *
 257:    * @param initialCapacity the initial capacity (&gt;= 0)
 258:    * @param loadFactor the load factor (&gt; 0, not NaN)
 259:    * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
 260:    *                                     ! (loadFactor &gt; 0.0)
 261:    */
 262:   public Hashtable(int initialCapacity, float loadFactor)
 263:   {
 264:     if (initialCapacity < 0)
 265:       throw new IllegalArgumentException("Illegal Capacity: "
 266:                                          + initialCapacity);
 267:     if (! (loadFactor > 0)) // check for NaN too
 268:       throw new IllegalArgumentException("Illegal Load: " + loadFactor);
 269: 
 270:     if (initialCapacity == 0)
 271:       initialCapacity = 1;
 272:     buckets = new HashEntry[initialCapacity];
 273:     this.loadFactor = loadFactor;
 274:     threshold = (int) (initialCapacity * loadFactor);
 275:   }
 276: 
 277:   /**
 278:    * Returns the number of key-value mappings currently in this hashtable.
 279:    * @return the size
 280:    */
 281:   public synchronized int size()
 282:   {
 283:     return size;
 284:   }
 285: 
 286:   /**
 287:    * Returns true if there are no key-value mappings currently in this table.
 288:    * @return <code>size() == 0</code>
 289:    */
 290:   public synchronized boolean isEmpty()
 291:   {
 292:     return size == 0;
 293:   }
 294: 
 295:   /**
 296:    * Return an enumeration of the keys of this table. There's no point
 297:    * in synchronizing this, as you have already been warned that the
 298:    * enumeration is not specified to be thread-safe.
 299:    *
 300:    * @return the keys
 301:    * @see #elements()
 302:    * @see #keySet()
 303:    */
 304:   public Enumeration keys()
 305:   {
 306:     return new Enumerator(KEYS);
 307:   }
 308: 
 309:   /**
 310:    * Return an enumeration of the values of this table. There's no point
 311:    * in synchronizing this, as you have already been warned that the
 312:    * enumeration is not specified to be thread-safe.
 313:    *
 314:    * @return the values
 315:    * @see #keys()
 316:    * @see #values()
 317:    */
 318:   public Enumeration elements()
 319:   {
 320:     return new Enumerator(VALUES);
 321:   }
 322: 
 323:   /**
 324:    * Returns true if this Hashtable contains a value <code>o</code>,
 325:    * such that <code>o.equals(value)</code>.  This is the same as
 326:    * <code>containsValue()</code>, and is O(n).
 327:    * <p>
 328:    *
 329:    * @param value the value to search for in this Hashtable
 330:    * @return true if at least one key maps to the value
 331:    * @throws NullPointerException if <code>value</code> is null
 332:    * @see #containsValue(Object)
 333:    * @see #containsKey(Object)
 334:    */
 335:   public synchronized boolean contains(Object value)
 336:   {
 337:     if (value == null)
 338:       throw new NullPointerException();
 339: 
 340:     for (int i = buckets.length - 1; i >= 0; i--)
 341:       {
 342:         HashEntry e = buckets[i];
 343:         while (e != null)
 344:           {
 345:             if (e.value.equals(value))
 346:               return true;
 347:             e = e.next;
 348:           }
 349:       }
 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 (e.key.equals(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 (e.key.equals(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 (e.key.equals(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 (e.key.equals(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 (e.equals(o))
 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:      */
1028:     public boolean hasNext()
1029:     {
1030:       return count > 0;
1031:     }
1032: 
1033:     /**
1034:      * Returns the next element in the Iterator's sequential view.
1035:      * @return the next element
1036:      * @throws ConcurrentModificationException if the hashtable was modified
1037:      * @throws NoSuchElementException if there is none
1038:      */
1039:     public Object next()
1040:     {
1041:       if (knownMod != modCount)
1042:         throw new ConcurrentModificationException();
1043:       if (count == 0)
1044:         throw new NoSuchElementException();
1045:       count--;
1046:       HashEntry e = next;
1047: 
1048:       while (e == null)
1049:         e = buckets[--idx];
1050: 
1051:       next = e.next;
1052:       last = e;
1053:       if (type == VALUES)
1054:         return e.value;
1055:       if (type == KEYS)
1056:         return e.key;
1057:       return e;
1058:     }
1059: 
1060:     /**
1061:      * Removes from the backing Hashtable the last element which was fetched
1062:      * with the <code>next()</code> method.
1063:      * @throws ConcurrentModificationException if the hashtable was modified
1064:      * @throws IllegalStateException if called when there is no last element
1065:      */
1066:     public void remove()
1067:     {
1068:       if (knownMod != modCount)
1069:         throw new ConcurrentModificationException();
1070:       if (last == null)
1071:         throw new IllegalStateException();
1072: 
1073:       Hashtable.this.remove(last.key);
1074:       last = null;
1075:       knownMod++;
1076:     }
1077:   } // class HashIterator
1078: 
1079: 
1080:   /**
1081:    * Enumeration view of this Hashtable, providing sequential access to its
1082:    * elements; this implementation is parameterized to provide access either
1083:    * to the keys or to the values in the Hashtable.
1084:    *
1085:    * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1086:    * as this could cause a rehash and we'd completely lose our place.  Even
1087:    * without a rehash, it is undetermined if a new element added would
1088:    * appear in the enumeration.  The spec says nothing about this, but
1089:    * the "Java Class Libraries" book infers that modifications to the
1090:    * hashtable during enumeration causes indeterminate results.  Don't do it!
1091:    *
1092:    * @author Jon Zeppieri
1093:    */
1094:   private final class Enumerator implements Enumeration
1095:   {
1096:     /**
1097:      * The type of this Iterator: {@link #KEYS} or {@link #VALUES}.
1098:      */
1099:     final int type;
1100:     /** The number of elements remaining to be returned by next(). */
1101:     int count = size;
1102:     /** Current index in the physical hash table. */
1103:     int idx = buckets.length;
1104:     /**
1105:      * Entry which will be returned by the next nextElement() call. It is
1106:      * set if we are iterating through a bucket with multiple entries, or null
1107:      * if we must look in the next bucket.
1108:      */
1109:     HashEntry next;
1110: 
1111:     /**
1112:      * Construct the enumeration.
1113:      * @param type either {@link #KEYS} or {@link #VALUES}.
1114:      */
1115:     Enumerator(int type)
1116:     {
1117:       this.type = type;
1118:     }
1119: 
1120:     /**
1121:      * Checks whether more elements remain in the enumeration.
1122:      * @return true if nextElement() will not fail.
1123:      */
1124:     public boolean hasMoreElements()
1125:     {
1126:       return count > 0;
1127:     }
1128: 
1129:     /**
1130:      * Returns the next element.
1131:      * @return the next element
1132:      * @throws NoSuchElementException if there is none.
1133:      */
1134:     public Object nextElement()
1135:     {
1136:       if (count == 0)
1137:         throw new NoSuchElementException("Hashtable Enumerator");
1138:       count--;
1139:       HashEntry e = next;
1140: 
1141:       while (e == null)
1142:         e = buckets[--idx];
1143: 
1144:       next = e.next;
1145:       return type == VALUES ? e.value : e.key;
1146:     }
1147:   } // class Enumerator
1148: } // class Hashtable