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