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