001    /* Hashtable.java -- a class providing a basic hashtable data structure,
002       mapping Object --> Object
003       Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
004       Free Software Foundation, Inc.
005    
006    This file is part of GNU Classpath.
007    
008    GNU Classpath is free software; you can redistribute it and/or modify
009    it under the terms of the GNU General Public License as published by
010    the Free Software Foundation; either version 2, or (at your option)
011    any later version.
012    
013    GNU Classpath is distributed in the hope that it will be useful, but
014    WITHOUT ANY WARRANTY; without even the implied warranty of
015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
016    General Public License for more details.
017    
018    You should have received a copy of the GNU General Public License
019    along with GNU Classpath; see the file COPYING.  If not, write to the
020    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
021    02110-1301 USA.
022    
023    Linking this library statically or dynamically with other modules is
024    making a combined work based on this library.  Thus, the terms and
025    conditions of the GNU General Public License cover the whole
026    combination.
027    
028    As a special exception, the copyright holders of this library give you
029    permission to link this library with independent modules to produce an
030    executable, regardless of the license terms of these independent
031    modules, and to copy and distribute the resulting executable under
032    terms of your choice, provided that you also meet, for each linked
033    independent module, the terms and conditions of the license of that
034    module.  An independent module is a module which is not derived from
035    or based on this library.  If you modify this library, you may extend
036    this exception to your version of the library, but you are not
037    obligated to do so.  If you do not wish to do so, delete this
038    exception statement from your version. */
039    
040    package java.util;
041    
042    import java.io.IOException;
043    import java.io.ObjectInputStream;
044    import java.io.ObjectOutputStream;
045    import java.io.Serializable;
046    
047    // NOTE: This implementation is very similar to that of HashMap. If you fix
048    // a bug in here, chances are you should make a similar change to the HashMap
049    // code.
050    
051    /**
052     * A class which implements a hashtable data structure.
053     * <p>
054     *
055     * This implementation of Hashtable uses a hash-bucket approach. That is:
056     * linear probing and rehashing is avoided; instead, each hashed value maps
057     * to a simple linked-list which, in the best case, only has one node.
058     * Assuming a large enough table, low enough load factor, and / or well
059     * implemented hashCode() methods, Hashtable should provide O(1)
060     * insertion, deletion, and searching of keys.  Hashtable is O(n) in
061     * the worst case for all of these (if all keys hash to the same bucket).
062     * <p>
063     *
064     * This is a JDK-1.2 compliant implementation of Hashtable.  As such, it
065     * belongs, partially, to the Collections framework (in that it implements
066     * Map).  For backwards compatibility, it inherits from the obsolete and
067     * utterly useless Dictionary class.
068     * <p>
069     *
070     * Being a hybrid of old and new, Hashtable has methods which provide redundant
071     * capability, but with subtle and even crucial differences.
072     * For example, one can iterate over various aspects of a Hashtable with
073     * either an Iterator (which is the JDK-1.2 way of doing things) or with an
074     * Enumeration.  The latter can end up in an undefined state if the Hashtable
075     * changes while the Enumeration is open.
076     * <p>
077     *
078     * Unlike HashMap, Hashtable does not accept `null' as a key value. Also,
079     * all accesses are synchronized: in a single thread environment, this is
080     * expensive, but in a multi-thread environment, this saves you the effort
081     * of extra synchronization. However, the old-style enumerators are not
082     * synchronized, because they can lead to unspecified behavior even if
083     * they were synchronized. You have been warned.
084     * <p>
085     *
086     * The iterators are <i>fail-fast</i>, meaning that any structural
087     * modification, except for <code>remove()</code> called on the iterator
088     * itself, cause the iterator to throw a
089     * <code>ConcurrentModificationException</code> rather than exhibit
090     * non-deterministic behavior.
091     *
092     * @author Jon Zeppieri
093     * @author Warren Levy
094     * @author Bryce McKinlay
095     * @author Eric Blake (ebb9@email.byu.edu)
096     * @see HashMap
097     * @see TreeMap
098     * @see IdentityHashMap
099     * @see LinkedHashMap
100     * @since 1.0
101     * @status updated to 1.4
102     */
103    public class Hashtable<K, V> extends Dictionary<K, V>
104      implements Map<K, V>, 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<K, V>[] 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<K> keys;
161    
162      /**
163       * The cache for {@link #values()}.
164       */
165      private transient Collection<V> values;
166    
167      /**
168       * The cache for {@link #entrySet()}.
169       */
170      private transient Set<Map.Entry<K, V>> 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<K, V>
178        extends AbstractMap.SimpleEntry<K, V>
179      {
180        /** The next entry in the linked list. */
181        HashEntry<K, V> next;
182    
183        /**
184         * Simple constructor.
185         * @param key the key, already guaranteed non-null
186         * @param value the value, already guaranteed non-null
187         */
188        HashEntry(K key, V value)
189        {
190          super(key, value);
191        }
192    
193        /**
194         * Resets the value.
195         * @param newVal the new value
196         * @return the prior value
197         * @throws NullPointerException if <code>newVal</code> is null
198         */
199        public V setValue(V newVal)
200        {
201          if (newVal == null)
202            throw new NullPointerException();
203          return super.setValue(newVal);
204        }
205      }
206    
207      /**
208       * Construct a new Hashtable with the default capacity (11) and the default
209       * load factor (0.75).
210       */
211      public Hashtable()
212      {
213        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
214      }
215    
216      /**
217       * Construct a new Hashtable from the given Map, with initial capacity
218       * the greater of the size of <code>m</code> or the default of 11.
219       * <p>
220       *
221       * Every element in Map m will be put into this new Hashtable.
222       *
223       * @param m a Map whose key / value pairs will be put into
224       *          the new Hashtable.  <b>NOTE: key / value pairs
225       *          are not cloned in this constructor.</b>
226       * @throws NullPointerException if m is null, or if m contains a mapping
227       *         to or from `null'.
228       * @since 1.2
229       */
230      public Hashtable(Map<? extends K, ? extends V> m)
231      {
232        this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
233        putAll(m);
234      }
235    
236      /**
237       * Construct a new Hashtable with a specific inital capacity and
238       * default load factor of 0.75.
239       *
240       * @param initialCapacity the initial capacity of this Hashtable (&gt;= 0)
241       * @throws IllegalArgumentException if (initialCapacity &lt; 0)
242       */
243      public Hashtable(int initialCapacity)
244      {
245        this(initialCapacity, DEFAULT_LOAD_FACTOR);
246      }
247    
248      /**
249       * Construct a new Hashtable with a specific initial capacity and
250       * load factor.
251       *
252       * @param initialCapacity the initial capacity (&gt;= 0)
253       * @param loadFactor the load factor (&gt; 0, not NaN)
254       * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
255       *                                     ! (loadFactor &gt; 0.0)
256       */
257      public Hashtable(int initialCapacity, float loadFactor)
258      {
259        if (initialCapacity < 0)
260          throw new IllegalArgumentException("Illegal Capacity: "
261                                             + initialCapacity);
262        if (! (loadFactor > 0)) // check for NaN too
263          throw new IllegalArgumentException("Illegal Load: " + loadFactor);
264    
265        if (initialCapacity == 0)
266          initialCapacity = 1;
267        buckets = (HashEntry<K, V>[]) new HashEntry[initialCapacity];
268        this.loadFactor = loadFactor;
269        threshold = (int) (initialCapacity * loadFactor);
270      }
271    
272      /**
273       * Returns the number of key-value mappings currently in this hashtable.
274       * @return the size
275       */
276      public synchronized int size()
277      {
278        return size;
279      }
280    
281      /**
282       * Returns true if there are no key-value mappings currently in this table.
283       * @return <code>size() == 0</code>
284       */
285      public synchronized boolean isEmpty()
286      {
287        return size == 0;
288      }
289    
290      /**
291       * Return an enumeration of the keys of this table. There's no point
292       * in synchronizing this, as you have already been warned that the
293       * enumeration is not specified to be thread-safe.
294       *
295       * @return the keys
296       * @see #elements()
297       * @see #keySet()
298       */
299      public Enumeration<K> keys()
300      {
301        return new KeyEnumerator();
302      }
303    
304      /**
305       * Return an enumeration of the values of this table. There's no point
306       * in synchronizing this, as you have already been warned that the
307       * enumeration is not specified to be thread-safe.
308       *
309       * @return the values
310       * @see #keys()
311       * @see #values()
312       */
313      public Enumeration<V> elements()
314      {
315        return new ValueEnumerator();
316      }
317    
318      /**
319       * Returns true if this Hashtable contains a value <code>o</code>,
320       * such that <code>o.equals(value)</code>.  This is the same as
321       * <code>containsValue()</code>, and is O(n).
322       * <p>
323       *
324       * @param value the value to search for in this Hashtable
325       * @return true if at least one key maps to the value
326       * @throws NullPointerException if <code>value</code> is null
327       * @see #containsValue(Object)
328       * @see #containsKey(Object)
329       */
330      public synchronized boolean contains(Object value)
331      {
332        if (value == null)
333          throw new NullPointerException();
334    
335        for (int i = buckets.length - 1; i >= 0; i--)
336          {
337            HashEntry<K, V> e = buckets[i];
338            while (e != null)
339              {
340                if (e.value.equals(value))
341                  return true;
342                e = e.next;
343              }
344          }
345    
346        return false;  
347      }
348    
349      /**
350       * Returns true if this Hashtable contains a value <code>o</code>, such that
351       * <code>o.equals(value)</code>. This is the new API for the old
352       * <code>contains()</code>.
353       *
354       * @param value the value to search for in this Hashtable
355       * @return true if at least one key maps to the value
356       * @see #contains(Object)
357       * @see #containsKey(Object)
358       * @throws NullPointerException if <code>value</code> is null
359       * @since 1.2
360       */
361      public boolean containsValue(Object value)
362      {
363        // Delegate to older method to make sure code overriding it continues 
364        // to work.
365        return contains(value);
366      }
367    
368      /**
369       * Returns true if the supplied object <code>equals()</code> a key
370       * in this Hashtable.
371       *
372       * @param key the key to search for in this Hashtable
373       * @return true if the key is in the table
374       * @throws NullPointerException if key is null
375       * @see #containsValue(Object)
376       */
377      public synchronized boolean containsKey(Object key)
378      {
379        int idx = hash(key);
380        HashEntry<K, V> e = buckets[idx];
381        while (e != null)
382          {
383            if (e.key.equals(key))
384              return true;
385            e = e.next;
386          }
387        return false;
388      }
389    
390      /**
391       * Return the value in this Hashtable associated with the supplied key,
392       * or <code>null</code> if the key maps to nothing.
393       *
394       * @param key the key for which to fetch an associated value
395       * @return what the key maps to, if present
396       * @throws NullPointerException if key is null
397       * @see #put(Object, Object)
398       * @see #containsKey(Object)
399       */
400      public synchronized V get(Object key)
401      {
402        int idx = hash(key);
403        HashEntry<K, V> e = buckets[idx];
404        while (e != null)
405          {
406            if (e.key.equals(key))
407              return e.value;
408            e = e.next;
409          }
410        return null;
411      }
412    
413      /**
414       * Puts the supplied value into the Map, mapped by the supplied key.
415       * Neither parameter may be null.  The value may be retrieved by any
416       * object which <code>equals()</code> this key.
417       *
418       * @param key the key used to locate the value
419       * @param value the value to be stored in the table
420       * @return the prior mapping of the key, or null if there was none
421       * @throws NullPointerException if key or value is null
422       * @see #get(Object)
423       * @see Object#equals(Object)
424       */
425      public synchronized V put(K key, V value)
426      {
427        int idx = hash(key);
428        HashEntry<K, V> e = buckets[idx];
429    
430        // Check if value is null since it is not permitted.
431        if (value == null)
432          throw new NullPointerException();
433    
434        while (e != null)
435          {
436            if (e.key.equals(key))
437              {
438                // Bypass e.setValue, since we already know value is non-null.
439                V r = e.value;
440                e.value = value;
441                return r;
442              }
443            else
444              {
445                e = e.next;
446              }
447          }
448    
449        // At this point, we know we need to add a new entry.
450        modCount++;
451        if (++size > threshold)
452          {
453            rehash();
454            // Need a new hash value to suit the bigger table.
455            idx = hash(key);
456          }
457    
458        e = new HashEntry<K, V>(key, value);
459    
460        e.next = buckets[idx];
461        buckets[idx] = e;
462    
463        return null;
464      }
465    
466      /**
467       * Removes from the table and returns the value which is mapped by the
468       * supplied key. If the key maps to nothing, then the table remains
469       * unchanged, and <code>null</code> is returned.
470       *
471       * @param key the key used to locate the value to remove
472       * @return whatever the key mapped to, if present
473       */
474      public synchronized V remove(Object key)
475      {
476        int idx = hash(key);
477        HashEntry<K, V> e = buckets[idx];
478        HashEntry<K, V> last = null;
479    
480        while (e != null)
481          {
482            if (e.key.equals(key))
483              {
484                modCount++;
485                if (last == null)
486                  buckets[idx] = e.next;
487                else
488                  last.next = e.next;
489                size--;
490                return e.value;
491              }
492            last = e;
493            e = e.next;
494          }
495        return null;
496      }
497    
498      /**
499       * Copies all elements of the given map into this hashtable.  However, no
500       * mapping can contain null as key or value.  If this table already has
501       * a mapping for a key, the new mapping replaces the current one.
502       *
503       * @param m the map to be hashed into this
504       * @throws NullPointerException if m is null, or contains null keys or values
505       */
506      public synchronized void putAll(Map<? extends K, ? extends V> m)
507      {
508        final Map<K,V> addMap = (Map<K,V>) m;
509        final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator();
510        while (it.hasNext())
511          {
512            final Map.Entry<K,V> e = it.next();
513            // Optimize in case the Entry is one of our own.
514            if (e instanceof AbstractMap.SimpleEntry)
515              {
516                AbstractMap.SimpleEntry<? extends K, ? extends V> entry
517                  = (AbstractMap.SimpleEntry<? extends K, ? extends V>) e;
518                put(entry.key, entry.value);
519              }
520            else
521              {
522                put(e.getKey(), e.getValue());
523              }
524          }
525      }
526    
527      /**
528       * Clears the hashtable so it has no keys.  This is O(1).
529       */
530      public synchronized void clear()
531      {
532        if (size > 0)
533          {
534            modCount++;
535            Arrays.fill(buckets, null);
536            size = 0;
537          }
538      }
539    
540      /**
541       * Returns a shallow clone of this Hashtable. The Map itself is cloned,
542       * but its contents are not.  This is O(n).
543       *
544       * @return the clone
545       */
546      public synchronized Object clone()
547      {
548        Hashtable<K, V> copy = null;
549        try
550          {
551            copy = (Hashtable<K, V>) super.clone();
552          }
553        catch (CloneNotSupportedException x)
554          {
555            // This is impossible.
556          }
557        copy.buckets = (HashEntry<K, V>[]) new HashEntry[buckets.length];
558        copy.putAllInternal(this);
559        // Clear the caches.
560        copy.keys = null;
561        copy.values = null;
562        copy.entries = null;
563        return copy;
564      }
565    
566      /**
567       * Converts this Hashtable to a String, surrounded by braces, and with
568       * key/value pairs listed with an equals sign between, separated by a
569       * comma and space. For example, <code>"{a=1, b=2}"</code>.<p>
570       *
571       * NOTE: if the <code>toString()</code> method of any key or value
572       * throws an exception, this will fail for the same reason.
573       *
574       * @return the string representation
575       */
576      public synchronized String toString()
577      {
578        // Since we are already synchronized, and entrySet().iterator()
579        // would repeatedly re-lock/release the monitor, we directly use the
580        // unsynchronized EntryIterator instead.
581        Iterator<Map.Entry<K, V>> entries = new EntryIterator();
582        StringBuffer r = new StringBuffer("{");
583        for (int pos = size; pos > 0; pos--)
584          {
585            r.append(entries.next());
586            if (pos > 1)
587              r.append(", ");
588          }
589        r.append("}");
590        return r.toString();
591      }
592    
593      /**
594       * Returns a "set view" of this Hashtable's keys. The set is backed by
595       * the hashtable, so changes in one show up in the other.  The set supports
596       * element removal, but not element addition.  The set is properly
597       * synchronized on the original hashtable.  Sun has not documented the
598       * proper interaction of null with this set, but has inconsistent behavior
599       * in the JDK. Therefore, in this implementation, contains, remove,
600       * containsAll, retainAll, removeAll, and equals just ignore a null key
601       * rather than throwing a {@link NullPointerException}.
602       *
603       * @return a set view of the keys
604       * @see #values()
605       * @see #entrySet()
606       * @since 1.2
607       */
608      public Set<K> keySet()
609      {
610        if (keys == null)
611          {
612            // Create a synchronized AbstractSet with custom implementations of
613            // those methods that can be overridden easily and efficiently.
614            Set<K> r = new AbstractSet<K>()
615            {
616              public int size()
617              {
618                return size;
619              }
620    
621              public Iterator<K> iterator()
622              {
623                return new KeyIterator();
624              }
625    
626              public void clear()
627              {
628                Hashtable.this.clear();
629              }
630    
631              public boolean contains(Object o)
632              {
633                if (o == null)
634                  return false;
635                return containsKey(o);
636              }
637    
638              public boolean remove(Object o)
639              {
640                return Hashtable.this.remove(o) != null;
641              }
642            };
643            // We must specify the correct object to synchronize upon, hence the
644            // use of a non-public API
645            keys = new Collections.SynchronizedSet<K>(this, r);
646          }
647        return keys;
648      }
649    
650      /**
651       * Returns a "collection view" (or "bag view") of this Hashtable's values.
652       * The collection is backed by the hashtable, so changes in one show up
653       * in the other.  The collection supports element removal, but not element
654       * addition.  The collection is properly synchronized on the original
655       * hashtable.  Sun has not documented the proper interaction of null with
656       * this set, but has inconsistent behavior in the JDK. Therefore, in this
657       * implementation, contains, remove, containsAll, retainAll, removeAll, and
658       * equals just ignore a null value rather than throwing a
659       * {@link NullPointerException}.
660       *
661       * @return a bag view of the values
662       * @see #keySet()
663       * @see #entrySet()
664       * @since 1.2
665       */
666      public Collection<V> values()
667      {
668        if (values == null)
669          {
670            // We don't bother overriding many of the optional methods, as doing so
671            // wouldn't provide any significant performance advantage.
672            Collection<V> r = new AbstractCollection<V>()
673            {
674              public int size()
675              {
676                return size;
677              }
678    
679              public Iterator<V> iterator()
680              {
681                return new ValueIterator();
682              }
683    
684              public void clear()
685              {
686                Hashtable.this.clear();
687              }
688            };
689            // We must specify the correct object to synchronize upon, hence the
690            // use of a non-public API
691            values = new Collections.SynchronizedCollection<V>(this, r);
692          }
693        return values;
694      }
695    
696      /**
697       * Returns a "set view" of this Hashtable's entries. The set is backed by
698       * the hashtable, so changes in one show up in the other.  The set supports
699       * element removal, but not element addition.  The set is properly
700       * synchronized on the original hashtable.  Sun has not documented the
701       * proper interaction of null with this set, but has inconsistent behavior
702       * in the JDK. Therefore, in this implementation, contains, remove,
703       * containsAll, retainAll, removeAll, and equals just ignore a null entry,
704       * or an entry with a null key or value, rather than throwing a
705       * {@link NullPointerException}. However, calling entry.setValue(null)
706       * will fail.
707       * <p>
708       *
709       * Note that the iterators for all three views, from keySet(), entrySet(),
710       * and values(), traverse the hashtable in the same sequence.
711       *
712       * @return a set view of the entries
713       * @see #keySet()
714       * @see #values()
715       * @see Map.Entry
716       * @since 1.2
717       */
718      public Set<Map.Entry<K, V>> entrySet()
719      {
720        if (entries == null)
721          {
722            // Create an AbstractSet with custom implementations of those methods
723            // that can be overridden easily and efficiently.
724            Set<Map.Entry<K, V>> r = new AbstractSet<Map.Entry<K, V>>()
725            {
726              public int size()
727              {
728                return size;
729              }
730    
731              public Iterator<Map.Entry<K, V>> iterator()
732              {
733                return new EntryIterator();
734              }
735    
736              public void clear()
737              {
738                Hashtable.this.clear();
739              }
740    
741              public boolean contains(Object o)
742              {
743                return getEntry(o) != null;
744              }
745    
746              public boolean remove(Object o)
747              {
748                HashEntry<K, V> e = getEntry(o);
749                if (e != null)
750                  {
751                    Hashtable.this.remove(e.key);
752                    return true;
753                  }
754                return false;
755              }
756            };
757            // We must specify the correct object to synchronize upon, hence the
758            // use of a non-public API
759            entries = new Collections.SynchronizedSet<Map.Entry<K, V>>(this, r);
760          }
761        return entries;
762      }
763    
764      /**
765       * Returns true if this Hashtable equals the supplied Object <code>o</code>.
766       * As specified by Map, this is:
767       * <code>
768       * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
769       * </code>
770       *
771       * @param o the object to compare to
772       * @return true if o is an equal map
773       * @since 1.2
774       */
775      public boolean equals(Object o)
776      {
777        // no need to synchronize, entrySet().equals() does that.
778        if (o == this)
779          return true;
780        if (!(o instanceof Map))
781          return false;
782    
783        return entrySet().equals(((Map) o).entrySet());
784      }
785    
786      /**
787       * Returns the hashCode for this Hashtable.  As specified by Map, this is
788       * the sum of the hashCodes of all of its Map.Entry objects
789       *
790       * @return the sum of the hashcodes of the entries
791       * @since 1.2
792       */
793      public synchronized int hashCode()
794      {
795        // Since we are already synchronized, and entrySet().iterator()
796        // would repeatedly re-lock/release the monitor, we directly use the
797        // unsynchronized EntryIterator instead.
798        Iterator<Map.Entry<K, V>> itr = new EntryIterator();
799        int hashcode = 0;
800        for (int pos = size; pos > 0; pos--)
801          hashcode += itr.next().hashCode();
802    
803        return hashcode;
804      }
805    
806      /**
807       * Helper method that returns an index in the buckets array for `key'
808       * based on its hashCode().
809       *
810       * @param key the key
811       * @return the bucket number
812       * @throws NullPointerException if key is null
813       */
814      private int hash(Object key)
815      {
816        // Note: Inline Math.abs here, for less method overhead, and to avoid
817        // a bootstrap dependency, since Math relies on native methods.
818        int hash = key.hashCode() % buckets.length;
819        return hash < 0 ? -hash : hash;
820      }
821    
822      /**
823       * Helper method for entrySet(), which matches both key and value
824       * simultaneously. Ignores null, as mentioned in entrySet().
825       *
826       * @param o the entry to match
827       * @return the matching entry, if found, or null
828       * @see #entrySet()
829       */
830      // Package visible, for use in nested classes.
831      HashEntry<K, V> getEntry(Object o)
832      {
833        if (! (o instanceof Map.Entry))
834          return null;
835        K key = ((Map.Entry<K, V>) o).getKey();
836        if (key == null)
837          return null;
838    
839        int idx = hash(key);
840        HashEntry<K, V> e = buckets[idx];
841        while (e != null)
842          {
843            if (e.equals(o))
844              return e;
845            e = e.next;
846          }
847        return null;
848      }
849    
850      /**
851       * A simplified, more efficient internal implementation of putAll(). clone() 
852       * should not call putAll or put, in order to be compatible with the JDK 
853       * implementation with respect to subclasses.
854       *
855       * @param m the map to initialize this from
856       */
857      void putAllInternal(Map<? extends K, ? extends V> m)
858      {
859        final Map<K,V> addMap = (Map<K,V>) m;
860        final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator();
861        size = 0;
862        while (it.hasNext())
863          {
864            final Map.Entry<K,V> e = it.next();
865            size++;
866            K key = e.getKey();
867            int idx = hash(key);
868            HashEntry<K, V> he = new HashEntry<K, V>(key, e.getValue());
869            he.next = buckets[idx];
870            buckets[idx] = he;
871          }
872      }
873    
874      /**
875       * Increases the size of the Hashtable and rehashes all keys to new array
876       * indices; this is called when the addition of a new value would cause
877       * size() &gt; threshold. Note that the existing Entry objects are reused in
878       * the new hash table.
879       * <p>
880       *
881       * This is not specified, but the new size is twice the current size plus
882       * one; this number is not always prime, unfortunately. This implementation
883       * is not synchronized, as it is only invoked from synchronized methods.
884       */
885      protected void rehash()
886      {
887        HashEntry<K, V>[] oldBuckets = buckets;
888    
889        int newcapacity = (buckets.length * 2) + 1;
890        threshold = (int) (newcapacity * loadFactor);
891        buckets = (HashEntry<K, V>[]) new HashEntry[newcapacity];
892    
893        for (int i = oldBuckets.length - 1; i >= 0; i--)
894          {
895            HashEntry<K, V> e = oldBuckets[i];
896            while (e != null)
897              {
898                int idx = hash(e.key);
899                HashEntry<K, V> dest = buckets[idx];
900    
901                if (dest != null)
902                  {
903                    HashEntry next = dest.next;
904                    while (next != null)
905                      {
906                        dest = next;
907                        next = dest.next;
908                      }
909                    dest.next = e;
910                  }
911                else
912                  {
913                    buckets[idx] = e;
914                  }
915    
916                HashEntry<K, V> 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 EntryIterator instead.
944        Iterator<Map.Entry<K, V>> it = new EntryIterator();
945        while (it.hasNext())
946          {
947            HashEntry<K, V> entry = (HashEntry<K, V>) 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 = (HashEntry<K, V>[]) 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((K) s.readObject(), (V) s.readObject());
978      }
979    
980      /**
981       * A class which implements the Iterator interface and is used for
982       * iterating over Hashtables.
983       * This implementation iterates entries. Subclasses are used to
984       * iterate key and values. It also allows the removal of elements,
985       * as per the Javasoft spec.  Note that it is not synchronized; this
986       * is a performance enhancer since it is never exposed externally
987       * and is only used within synchronized blocks above.
988       *
989       * @author Jon Zeppieri
990       * @author Fridjof Siebert
991       */
992      private class EntryIterator 
993          implements Iterator<Entry<K,V>>
994      {
995        /**
996         * The number of modifications to the backing Hashtable that we know about.
997         */
998        int knownMod = modCount;
999        /** The number of elements remaining to be returned by next(). */
1000        int count = size;
1001        /** Current index in the physical hash table. */
1002        int idx = buckets.length;
1003        /** The last Entry returned by a next() call. */
1004        HashEntry<K, V> last;
1005        /**
1006         * The next entry that should be returned by next(). It is set to something
1007         * if we're iterating through a bucket that contains multiple linked
1008         * entries. It is null if next() needs to find a new bucket.
1009         */
1010        HashEntry<K, V> next;
1011    
1012        /**
1013         * Construct a new EntryIterator
1014         */
1015        EntryIterator()
1016        {
1017        }
1018    
1019    
1020        /**
1021         * Returns true if the Iterator has more elements.
1022         * @return true if there are more elements
1023         */
1024        public boolean hasNext()
1025        {
1026          return count > 0;
1027        }
1028    
1029        /**
1030         * Returns the next element in the Iterator's sequential view.
1031         * @return the next element
1032         * @throws ConcurrentModificationException if the hashtable was modified
1033         * @throws NoSuchElementException if there is none
1034         */
1035        public Map.Entry<K,V> next()
1036        {
1037          if (knownMod != modCount)
1038            throw new ConcurrentModificationException();
1039          if (count == 0)
1040            throw new NoSuchElementException();
1041          count--;
1042          HashEntry<K, V> e = next;
1043    
1044          while (e == null)
1045            if (idx <= 0)
1046              return null;
1047            else
1048              e = buckets[--idx];
1049    
1050          next = e.next;
1051          last = e;
1052          return e;
1053        }
1054    
1055        /**
1056         * Removes from the backing Hashtable the last element which was fetched
1057         * with the <code>next()</code> method.
1058         * @throws ConcurrentModificationException if the hashtable was modified
1059         * @throws IllegalStateException if called when there is no last element
1060         */
1061        public void remove()
1062        {
1063          if (knownMod != modCount)
1064            throw new ConcurrentModificationException();
1065          if (last == null)
1066            throw new IllegalStateException();
1067    
1068          Hashtable.this.remove(last.key);
1069          last = null;
1070          knownMod++;
1071        }
1072      } // class EntryIterator
1073    
1074      /**
1075       * A class which implements the Iterator interface and is used for
1076       * iterating over keys in Hashtables.  This class uses an
1077       * <code>EntryIterator</code> to obtain the keys of each entry.
1078       *
1079       * @author Fridtjof Siebert
1080       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1081       */
1082      private class KeyIterator 
1083          implements Iterator<K>
1084      {
1085    
1086        /**
1087         * This entry iterator is used for most operations.  Only
1088         * <code>next()</code> gives a different result, by returning just
1089         * the key rather than the whole element.
1090         */
1091        private EntryIterator iterator;
1092    
1093        /**
1094         * Construct a new KeyIterator
1095         */
1096        KeyIterator()
1097        {
1098            iterator = new EntryIterator();
1099        }
1100    
1101    
1102        /**
1103         * Returns true if the entry iterator has more elements.
1104         *
1105         * @return true if there are more elements
1106         * @throws ConcurrentModificationException if the hashtable was modified
1107         */
1108        public boolean hasNext()
1109        {
1110            return iterator.hasNext();
1111        }
1112    
1113        /**
1114         * Returns the next element in the Iterator's sequential view.
1115         *
1116         * @return the next element
1117         *
1118         * @throws ConcurrentModificationException if the hashtable was modified
1119         * @throws NoSuchElementException if there is none
1120         */
1121        public K next()
1122        {
1123          return ((HashEntry<K,V>) iterator.next()).key;
1124        }
1125    
1126        /**
1127         * Removes the last element used by the <code>next()</code> method
1128         * using the entry iterator.
1129         *
1130         * @throws ConcurrentModificationException if the hashtable was modified
1131         * @throws IllegalStateException if called when there is no last element
1132         */
1133        public void remove()
1134        {
1135          iterator.remove();
1136        }
1137      } // class KeyIterator
1138     
1139      /**
1140       * A class which implements the Iterator interface and is used for
1141       * iterating over values in Hashtables.  This class uses an
1142       * <code>EntryIterator</code> to obtain the values of each entry.
1143       *
1144       * @author Fridtjof Siebert
1145       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1146       */
1147      private class ValueIterator
1148          implements Iterator<V>
1149      {
1150    
1151        /**
1152         * This entry iterator is used for most operations.  Only
1153         * <code>next()</code> gives a different result, by returning just
1154         * the value rather than the whole element.
1155         */
1156        private EntryIterator iterator;
1157    
1158        /**
1159         * Construct a new KeyIterator
1160         */
1161        ValueIterator()
1162        {
1163            iterator = new EntryIterator();
1164        }
1165    
1166    
1167        /**
1168         * Returns true if the entry iterator has more elements.
1169         *
1170         * @return true if there are more elements
1171         * @throws ConcurrentModificationException if the hashtable was modified
1172         */
1173        public boolean hasNext()
1174        {
1175            return iterator.hasNext();
1176        }
1177    
1178        /**
1179         * Returns the value of the next element in the iterator's sequential view.
1180         *
1181         * @return the next value
1182         *
1183         * @throws ConcurrentModificationException if the hashtable was modified
1184         * @throws NoSuchElementException if there is none
1185         */
1186        public V next()
1187        {
1188          return ((HashEntry<K,V>) iterator.next()).value;
1189        }
1190    
1191        /**
1192         * Removes the last element used by the <code>next()</code> method
1193         * using the entry iterator.
1194         *
1195         * @throws ConcurrentModificationException if the hashtable was modified
1196         * @throws IllegalStateException if called when there is no last element
1197         */
1198        public void remove()
1199        {
1200          iterator.remove();
1201        }
1202    
1203      } // class ValueIterator
1204    
1205      /**
1206       * Enumeration view of the entries in this Hashtable, providing
1207       * sequential access to its elements.
1208       *
1209       * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1210       * as this could cause a rehash and we'd completely lose our place.  Even
1211       * without a rehash, it is undetermined if a new element added would
1212       * appear in the enumeration.  The spec says nothing about this, but
1213       * the "Java Class Libraries" book implies that modifications to the
1214       * hashtable during enumeration causes indeterminate results.  Don't do it!
1215       *
1216       * @author Jon Zeppieri
1217       * @author Fridjof Siebert
1218       */
1219      private class EntryEnumerator 
1220          implements Enumeration<Entry<K,V>>
1221      {
1222        /** The number of elements remaining to be returned by next(). */
1223        int count = size;
1224        /** Current index in the physical hash table. */
1225        int idx = buckets.length;
1226        /**
1227         * Entry which will be returned by the next nextElement() call. It is
1228         * set if we are iterating through a bucket with multiple entries, or null
1229         * if we must look in the next bucket.
1230         */
1231        HashEntry<K, V> next;
1232    
1233        /**
1234         * Construct the enumeration.
1235         */
1236        EntryEnumerator()
1237        {
1238          // Nothing to do here.
1239        }
1240    
1241        /**
1242         * Checks whether more elements remain in the enumeration.
1243         * @return true if nextElement() will not fail.
1244         */
1245        public boolean hasMoreElements()
1246        {
1247          return count > 0;
1248        }
1249    
1250        /**
1251         * Returns the next element.
1252         * @return the next element
1253         * @throws NoSuchElementException if there is none.
1254         */
1255        public Map.Entry<K,V> nextElement()
1256        {
1257          if (count == 0)
1258            throw new NoSuchElementException("Hashtable Enumerator");
1259          count--;
1260          HashEntry<K, V> e = next;
1261    
1262          while (e == null)
1263            if (idx <= 0)
1264              return null;
1265            else
1266              e = buckets[--idx];
1267    
1268          next = e.next;
1269          return e;
1270        }
1271      } // class EntryEnumerator
1272    
1273    
1274      /**
1275       * Enumeration view of this Hashtable, providing sequential access to its
1276       * elements.
1277       *
1278       * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1279       * as this could cause a rehash and we'd completely lose our place.  Even
1280       * without a rehash, it is undetermined if a new element added would
1281       * appear in the enumeration.  The spec says nothing about this, but
1282       * the "Java Class Libraries" book implies that modifications to the
1283       * hashtable during enumeration causes indeterminate results.  Don't do it!
1284       *
1285       * @author Jon Zeppieri
1286       * @author Fridjof Siebert
1287       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1288       */
1289      private final class KeyEnumerator
1290          implements Enumeration<K>
1291      {
1292        /**
1293         * This entry enumerator is used for most operations.  Only
1294         * <code>nextElement()</code> gives a different result, by returning just
1295         * the key rather than the whole element.
1296         */
1297        private EntryEnumerator enumerator;
1298    
1299        /**
1300         * Construct a new KeyEnumerator
1301         */
1302        KeyEnumerator()
1303        {
1304          enumerator = new EntryEnumerator();
1305        }
1306    
1307    
1308        /**
1309         * Returns true if the entry enumerator has more elements.
1310         *
1311         * @return true if there are more elements
1312         * @throws ConcurrentModificationException if the hashtable was modified
1313         */
1314        public boolean hasMoreElements()
1315        {
1316            return enumerator.hasMoreElements();
1317        }
1318    
1319        /**
1320         * Returns the next element.
1321         * @return the next element
1322         * @throws NoSuchElementException if there is none.
1323         */
1324        public K nextElement()
1325        {
1326          HashEntry<K,V> entry = (HashEntry<K,V>) enumerator.nextElement();
1327          K retVal = null;
1328          if (entry != null)
1329            retVal = entry.key;
1330          return retVal;
1331        }
1332      } // class KeyEnumerator
1333    
1334    
1335      /**
1336       * Enumeration view of this Hashtable, providing sequential access to its
1337       * values.
1338       *
1339       * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1340       * as this could cause a rehash and we'd completely lose our place.  Even
1341       * without a rehash, it is undetermined if a new element added would
1342       * appear in the enumeration.  The spec says nothing about this, but
1343       * the "Java Class Libraries" book implies that modifications to the
1344       * hashtable during enumeration causes indeterminate results.  Don't do it!
1345       *
1346       * @author Jon Zeppieri
1347       * @author Fridjof Siebert
1348       * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1349       */
1350      private final class ValueEnumerator
1351          implements Enumeration<V>
1352      {
1353        /**
1354         * This entry enumerator is used for most operations.  Only
1355         * <code>nextElement()</code> gives a different result, by returning just
1356         * the value rather than the whole element.
1357         */
1358        private EntryEnumerator enumerator;
1359    
1360        /**
1361         * Construct a new ValueEnumerator
1362         */
1363        ValueEnumerator()
1364        {
1365          enumerator = new EntryEnumerator();
1366        }
1367    
1368    
1369        /**
1370         * Returns true if the entry enumerator has more elements.
1371         *
1372         * @return true if there are more elements
1373         * @throws ConcurrentModificationException if the hashtable was modified
1374         */
1375        public boolean hasMoreElements()
1376        {
1377            return enumerator.hasMoreElements();
1378        }
1379    
1380        /**
1381         * Returns the next element.
1382         * @return the next element
1383         * @throws NoSuchElementException if there is none.
1384         */
1385        public V nextElement()
1386        {
1387          HashEntry<K,V> entry = (HashEntry<K,V>) enumerator.nextElement();
1388          V retVal = null;
1389          if (entry != null)
1390            retVal = entry.value;
1391          return retVal;
1392        }
1393      } // class ValueEnumerator
1394    
1395    } // class Hashtable