Collections drop from Classpath:

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of
	the bitset.
	(andNot): Likewise.
	(xor): Likewise.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/LinkedList.java (LinkedListItr.add): Don't skip the next
	entry.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/TreeMap.java (removeNode): Fix bug in node removal.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractCollection.java (containsAll): Use size of the
	correct collection for loop bound.
	* java/util/AbstractList.java (iterator.next): Increment pos after
	calling get on backing list.
	(listIterator.next): Likewise.
	* java/util/LinkedList.java (addLastEntry): Don't increment size before
	checking for size == 0.
	(addFirstEntry): Rearrange to match addLastEntry.
	(add): Do not increment size before inserting the new entry.

	* java/util/AbstractCollection.java (addAll): Use size of the
	correct collection for loop bound.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractSet.java (removeAll): Fix scoping thinko.
	* java/util/HashMap.java (putAllInternal): Set size here.
	* java/util/Hashtable.java (putAllInternal): New method. Copy contents
	of a map efficiently without calling put() or putAll().
	(Hashtable (map)): Use putAllInternal.
	(clone): Likewise.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/Collections.java:
	* java/util/Vector.java:
	* java/util/WeakHashMap.java: Fix spelling errors.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java (removeAllInternal),
	(retainAllInternal): Add hooks for use by ArrayList.
	* java/util/AbstractList.java: Minor code updates. Fix some
	scoping.
	* java/util/AbstractMap.java: ditto
	* java/util/ArrayList.java (readObject, writeObject): ditto
	(removeAllInternal, retainAllInternal): Optimize.
	* java/util/Arrays.java: ditto
	* java/util/Collections.java: ditto. Change order of parameters
	to equals(Object, Object) to match specs.
	* java/util/Dictionary.java: Improve javadoc.
	(Dictionary): Add explicit constructor.
	* java/util/HashMap.java: Improve javadoc. Rearrange methods to
	follow order in JDK. Cleanups related to recent code migration to
	AbstractMap. Fix some scoping.
	(entrySet): Cache the result.
	(modCount): Ensure that this is updated correctly.
	* java/util/HashSet.java: Improve javadoc. Fix some scoping.
	(init): Add hooks for LinkedHashSet.
	(map): Use "" instead of Boolean.TRUE in backing map. Use
	package-private API where possible for less overhead.
	(readObject, writeObject): Fix serialization.
	* java/util/Hashtable.java: Improve javadoc. Fix some scoping.
	(entrySet, keySet, values): Cache the result.
	(modCount): Ensure that this is updated correctly.
	(contains, remove): Fix NullPointer checking to match specs.
	(class Enumeration): Make more like HashIterator.
	* java/util/IdentityHashMap.java: Minor code updates.
	(modCount): Ensure that this is updated correctly.
	(readObject, writeObject): Fix serialization.
	* java/util/LinkedHashMap.java: Minor code updates. Cleanups
	related to recent code migration to AbstractMap.
	* java/util/LinkedHashSet.java: New file.
	* java/util/LinkedList.java:
	(readObject, writeObject): Fix serialization.
	* java/util/Makefile.am: List recently added files.
	* java/util/Stack.java: Minor code updates.
	* java/util/TreeMap.java: Improve javadoc. Overhaul the class to
	be more efficient. Fix some scoping. Rearrange the methods.
	(nil): Ensure that this can be thread-safe, and make it a static
	final. Initialize it to be more useful as a sentinal node.
	(Node): Specify color in constructor.
	(deleteFixup, insertFixup): Improve comments and algorithm.
	(fabricateTree): Redesign with less overhead.
	(lowestGreaterThan): Add parameter first to make SubMap easier.
	(removeNode): Patch hole where nil was being modified. Choose
	predecessor instead of successor so in-place swap works.
	(class VerifyResult, verifyTree, verifySub, verifyError): Remove
	this dead code after verifying the class works.
	(class SubMap): Rewrite several algorithms to avoid problems with
	comparing nil.
	* java/util/TreeSet.java: Improve javadoc. Fix some scoping.
	(clone): Fix ClassCastException when cloning subSet().
	(readObject, writeObject): Fix serialization.
	* java/util/WeakHashMap.java: Improve javadoc. Fix some scoping.
	(NULL_KEY): Make it compare as null, for ease elsewhere.
	(Class WeakEntry): Rename from Entry, to avoid shadowing
	Map.Entry. Add missing toString.
	(modCount): Ensure that this is updated correctly.
	(clear, containsValue, keySet, putAll, values, WeakHashMap(Map)):
	Add missing methods and constructor.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/ArrayList.java (checkBoundExclusive),
	(checkBoundInclusive): Rename from range??clusive, to match
	AbstractList.
	* java/util/LinkedList.java (checkBoundsExclusive),
	(checkBoundsInclusive): ditto
	* java/util/Vector.java (checkBoundExclusive),
	(checkBoundInclusive): Move bounds checking into common methods.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractList.java:
	(modCount): Make sure it is updated in all needed places.
	* java/util/ArrayList.java: Improve javadoc. Implements
	RandomAccess. Add serialVersionUID. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	(isEmpty): Add missing method.
	* java/util/Collections.java: (class SynchronizedList): Make
	package visible.
	* java/util/ConcurrentModificationException.java: Improve
	javadoc.
	* java/util/EmptyStackException.java: Improve javadoc.
	* java/util/LinkedList.java: Improve javadoc.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	* java/util/NoSuchElementException.java: Improve javadoc.
	* java/util/Stack.java: Improve javadoc. Fix synchronization
	issues.
	(modCount): Make sure it is updated in all needed places.
	* java/util/Vector.java: Improve javadoc. Fix synchronization
	issues. Implements RandomAccess. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(setSize): Fix according to specifications: this does not dictate
	the backing array size.
	(removeAll, retainAll): Faster implementations.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/BitSet.java: Improve javadoc.
	(cardinality(), clear(), clear(int, int), flip(int)),
	(flip(int, int), get(int, int), intersects(BitSet), isEmpty()),
	(nextClearBit(int), nextSetBit(int), set(int, boolean)),
	(set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods.
	(clone): Fix so subclasses clone correctly.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java: Improve javadoc.
	(AbstractCollection()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	* java/util/AbstractList.java: Improve javadoc.
	(AbstractList()): Make constructor protected.
	(indexOf(Object)): Call listIterator(), not listIterator(int).
	(iterator()): Follow Sun's requirement to not use listIterator(0).
	(listIterator(int)): Make AbstractListItr anonymous.
	(subList(int, int)): Add support for RandomAccess.
	(SubList.add(int, Object), SubList.remove(Object)): Fix bug with
	modCount tracking.
	(SubList.addAll(Collection)): Add missing method.
	(SubList.listIterator(int)): Fix bugs in indexing, modCount
	tracking.
	(class RandomAccessSubList): Add new class.
	* java/util/AbstractMap.java: Improve javadoc.
	(keys, values, KEYS, VALUES, ENTRIES): Consolidate common map
	fields.
	(AbstractMap()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	(equals(Object)): Change algorithm to
	entrySet().equals(m.entrySet()), as documented by Sun.
	(keySet(), values()): Cache the collections.
	* java/util/AbstractSequentialList.java: Improve javadoc.
	(AbstractSequentialList()): Make constructor protected.
	* java/util/AbstractSet.java: Improve javadoc.
	(AbstractSet()): Make constructor protected.
	(removeAll(Collection)): Add missing method.
	* java/util/Arrays.java: Improve javadoc, rearrange method orders.
	(defaultComparator): Remove, in favor of
	Collections.compare(Object, Object, Comparator).
	(binarySearch, equals, sort): Fix natural order comparison of
	floats and doubles. Also improve Object comparison - when
	comparator is null, use natural order.
	(fill, sort): Add missing checks for IllegalArgumentException.
	(sort, qsort): Fix sorting bugs, rework the code for more
	legibility.
	(mergeSort): Inline into sort(Object[], int, int, Comparator).
	(class ArrayList): Rename from ListImpl, and make compatible with
	JDK serialization. Add methods which more efficiently override
	those of AbstractList.
	* java/util/Collections: Improve javadoc.
	(isSequential(List)): Add and use a method for deciding between
	RandomAccess and sequential algorithms on lists.
	(class Empty*, class Synchronized*, class Unmodifiable*): Make
	compliant with JDK serializability.
	(class Singleton*, class CopiesList, class RevereseComparator),
	(class UnmodifiableMap.UnmodifiableEntrySet),
	(class *RandomAccessList): New classes for serial compatibility.
	(class Empty*, class Singleton*, class CopiesList): Add methods
	which more efficiently override those of Abstract*.
	(search): Inline into binarySearch(List, Object, Comparator).
	(binarySearch): Make sequential search only do log(n) comparisons,
	instead of n.
	(copy(List, List)): Do bounds checking before starting.
	(indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate),
	(swap):	Add new JDK 1.4 methods.
	(binarySearch, max, min, sort): Allow null comparator to represent
	natural ordering.
	(reverse(List)): Avoid unnecessary swap.
	(shuffle(List, Random)): Do shuffle in-place for RandomAccess
	lists.
	(SingletonList.get): Fix logic bug.
	(SingletonMap.entrySet): Make the entry immutable, and cache the
	returned set.
	(SynchronizedCollection, SynchronizedMap, UnmodifiableCollection),
	(UnmodifiableMap): Detect null pointer in construction.
	(SynchronizedMap, UnmodifiableMap): Cache collection views.
	* java/util/BasicMapEntry: Improve javadoc.

From-SVN: r48035

1 files changed, 277 insertions, 248 deletions

diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java
index 3b35105..dcf7e7e 100644
--- a/libjava/java/util/HashMap.java
+++ b/libjava/java/util/HashMap.java
@@ -53,14 +53,16 @@ import java.io.ObjectOutputStream;
  * <p>
  *
  * Under ideal circumstances (no collisions), HashMap offers O(1)
- * performance on most operations (<pre>containsValue()</pre> is,
+ * performance on most operations (<code>containsValue()</code> is,
  * of course, O(n)).  In the worst case (all keys map to the same
  * hash code -- very unlikely), most operations are O(n).
  * <p>
  *
  * HashMap is part of the JDK1.2 Collections API.  It differs from
  * Hashtable in that it accepts the null key and null values, and it
- * does not support "Enumeration views."
+ * does not support "Enumeration views." Also, it is not synchronized;
+ * if you plan to use it in multiple threads, consider using:<br>
+ * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code>
  * <p>
  *
  * The iterators are <i>fail-fast</i>, meaning that any structural
@@ -81,6 +83,7 @@ import java.io.ObjectOutputStream;
  * @see IdentityHashMap
  * @see Hashtable
  * @since 1.2
+ * @status updated to 1.4
  */
 public class HashMap extends AbstractMap
   implements Map, Cloneable, Serializable
@@ -88,19 +91,16 @@ public class HashMap extends AbstractMap
   /**
    * Default number of buckets. This is the value the JDK 1.3 uses. Some
    * early documentation specified this value as 101. That is incorrect.
+   * Package visible for use by HashSet.
    */
   static final int DEFAULT_CAPACITY = 11;
 
   /**
    * The default load factor; this is explicitly specified by the spec.
+   * Package visible for use by HashSet.
    */
   static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
-  /** "enum" of iterator types. */
-  static final int KEYS = 0,
-                   VALUES = 1,
-                   ENTRIES = 2;
-
   /**
    * Compatible with JDK 1.2.
    */
@@ -108,41 +108,54 @@ public class HashMap extends AbstractMap
 
   /**
    * The rounded product of the capacity and the load factor; when the number
-   * of elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>.
-   * @serial
+   * of elements exceeds the threshold, the HashMap calls
+   * <code>rehash()</code>.
+   * @serial the threshold for rehashing
    */
-  int threshold;
+  private int threshold;
 
   /**
    * Load factor of this HashMap:  used in computing the threshold.
-   * @serial
+   * Package visible for use by HashSet.
+   * @serial the load factor
    */
   final float loadFactor;
 
   /**
    * Array containing the actual key-value mappings.
+   * Package visible for use by nested and subclasses.
    */
   transient HashEntry[] buckets;
 
   /**
    * Counts the number of modifications this HashMap has undergone, used
    * by Iterators to know when to throw ConcurrentModificationExceptions.
+   * Package visible for use by nested and subclasses.
    */
   transient int modCount;
 
   /**
    * The size of this HashMap:  denotes the number of key-value pairs.
+   * Package visible for use by nested and subclasses.
    */
   transient int size;
 
   /**
+   * The cache for {@link #entrySet()}.
+   */
+  private transient Set entries;
+
+  /**
    * Class to represent an entry in the hash table. Holds a single key-value
-   * pair.  This is extended again in LinkedHashMap.  See {@link clone()}
-   * for why this must be Cloneable.
+   * pair. Package visible for use by subclass.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
    */
-  static class HashEntry extends BasicMapEntry implements Cloneable
+  static class HashEntry extends BasicMapEntry
   {
-    /** The next entry in the linked list. */
+    /**
+     * The next entry in the linked list. Package visible for use by subclass.
+     */
     HashEntry next;
 
     /**
@@ -158,7 +171,8 @@ public class HashMap extends AbstractMap
     /**
      * Called when this entry is removed from the map. This version simply
      * returns the value, but in LinkedHashMap, it must also do bookkeeping.
-     * @return the value of this key as it is removed.
+     *
+     * @return the value of this key as it is removed
      */
     Object cleanup()
     {
@@ -182,9 +196,8 @@ public class HashMap extends AbstractMap
    *
    * Every element in Map m will be put into this new HashMap.
    *
-   * @param m a Map whose key / value pairs will be put into
-   *          the new HashMap.  <b>NOTE: key / value pairs
-   *          are not cloned in this constructor.</b>
+   * @param m a Map whose key / value pairs will be put into the new HashMap.
+   *        <b>NOTE: key / value pairs are not cloned in this constructor.</b>
    * @throws NullPointerException if m is null
    */
   public HashMap(Map m)
@@ -197,8 +210,8 @@ public class HashMap extends AbstractMap
    * Construct a new HashMap with a specific inital capacity and
    * default load factor of 0.75.
    *
-   * @param initialCapacity the initial capacity of this HashMap (>=0)
-   * @throws IllegalArgumentException if (initialCapacity < 0)
+   * @param initialCapacity the initial capacity of this HashMap (&gt;=0)
+   * @throws IllegalArgumentException if (initialCapacity &lt; 0)
    */
   public HashMap(int initialCapacity)
   {
@@ -208,10 +221,10 @@ public class HashMap extends AbstractMap
   /**
    * Construct a new HashMap with a specific inital capacity and load factor.
    *
-   * @param initialCapacity the initial capacity (>=0)
-   * @param loadFactor the load factor (>0, not NaN)
-   * @throws IllegalArgumentException if (initialCapacity < 0) ||
-   *                                     ! (loadFactor > 0.0)
+   * @param initialCapacity the initial capacity (&gt;=0)
+   * @param loadFactor the load factor (&gt; 0, not NaN)
+   * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
+   *                                     ! (loadFactor &gt; 0.0)
    */
   public HashMap(int initialCapacity, float loadFactor)
   {
@@ -229,7 +242,8 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Returns the number of kay-value mappings currently in this Map
+   * Returns the number of kay-value mappings currently in this Map.
+   *
    * @return the size
    */
   public int size()
@@ -238,7 +252,8 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Returns true if there are no key-value mappings currently in this Map
+   * Returns true if there are no key-value mappings currently in this Map.
+   *
    * @return <code>size() == 0</code>
    */
   public boolean isEmpty()
@@ -247,29 +262,31 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Returns true if this HashMap contains a value <pre>o</pre>, such that
-   * <pre>o.equals(value)</pre>.
+   * Return the value in this HashMap associated with the supplied key,
+   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
+   * could also be null, you must use containsKey to see if this key
+   * actually maps to something.
    *
-   * @param value the value to search for in this HashMap
-   * @return true if at least one key maps to the value
+   * @param key the key for which to fetch an associated value
+   * @return what the key maps to, if present
+   * @see #put(Object, Object)
+   * @see #containsKey(Object)
    */
-  public boolean containsValue(Object value)
+  public Object get(Object key)
   {
-    for (int i = buckets.length - 1; i >= 0; i--)
+    int idx = hash(key);
+    HashEntry e = buckets[idx];
+    while (e != null)
       {
-        HashEntry e = buckets[i];
-        while (e != null)
-          {
-            if (value == null ? e.value == null : value.equals(e.value))
-              return true;
-            e = e.next;
-          }
+        if (equals(key, e.key))
+          return e.value;
+        e = e.next;
       }
-    return false;
+    return null;
   }
 
   /**
-   * Returns true if the supplied object <pre>equals()</pre> a key
+   * Returns true if the supplied object <code>equals()</code> a key
    * in this HashMap.
    *
    * @param key the key to search for in this HashMap
@@ -282,7 +299,7 @@ public class HashMap extends AbstractMap
     HashEntry e = buckets[idx];
     while (e != null)
       {
-        if (key == null ? e.key == null : key.equals(e.key))
+        if (equals(key, e.key))
           return true;
         e = e.next;
       }
@@ -290,30 +307,6 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Return the value in this HashMap associated with the supplied key,
-   * or <pre>null</pre> if the key maps to nothing.  NOTE: Since the value
-   * could also be null, you must use containsKey to see if this key
-   * actually maps to something.
-   *
-   * @param key the key for which to fetch an associated value
-   * @return what the key maps to, if present
-   * @see #put(Object, Object)
-   * @see #containsKey(Object)
-   */
-  public Object get(Object key)
-  {
-    int idx = hash(key);
-    HashEntry e = buckets[idx];
-    while (e != null)
-      {
-        if (key == null ? e.key == null : key.equals(e.key))
-          return e.value;
-        e = e.next;
-      }
-    return null;
-  }
-
-  /**
    * Puts the supplied value into the Map, mapped by the supplied key.
    * The value may be retrieved by any object which <code>equals()</code>
    * this key. NOTE: Since the prior value could also be null, you must
@@ -328,13 +321,12 @@ public class HashMap extends AbstractMap
    */
   public Object put(Object key, Object value)
   {
-    modCount++;
     int idx = hash(key);
     HashEntry e = buckets[idx];
 
     while (e != null)
       {
-        if (key == null ? e.key == null : key.equals(e.key))
+        if (equals(key, e.key))
           // Must use this method for necessary bookkeeping in LinkedHashMap.
           return e.setValue(value);
         else
@@ -342,6 +334,7 @@ public class HashMap extends AbstractMap
       }
 
     // At this point, we know we need to add a new entry.
+    modCount++;
     if (++size > threshold)
       {
         rehash();
@@ -355,27 +348,36 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Helper method for put, that creates and adds a new Entry.  This is
-   * overridden in LinkedHashMap for bookkeeping purposes.
+   * Copies all elements of the given map into this hashtable.  If this table
+   * already has a mapping for a key, the new mapping replaces the current
+   * one.
    *
-   * @param key the key of the new Entry
-   * @param value the value
-   * @param idx the index in buckets where the new Entry belongs
-   * @param callRemove Whether to call the removeEldestEntry method.
-   * @see #put(Object, Object)
+   * @param m the map to be hashed into this
    */
-  void addEntry(Object key, Object value, int idx, boolean callRemove)
+  public void putAll(Map m)
   {
-    HashEntry e = new HashEntry(key, value);
+    Iterator itr = m.entrySet().iterator();
 
-    e.next = buckets[idx];
-    buckets[idx] = e;
+    for (int msize = m.size(); msize > 0; msize--)
+      {
+        Map.Entry e = (Map.Entry) itr.next();
+        // Optimize in case the Entry is one of our own.
+        if (e instanceof BasicMapEntry)
+          {
+            BasicMapEntry entry = (BasicMapEntry) e;
+            put(entry.key, entry.value);
+          }
+        else
+          {
+            put(e.getKey(), e.getValue());
+          }
+      }
   }
-
+  
   /**
    * Removes from the HashMap and returns the value which is mapped by the
    * supplied key. If the key maps to nothing, then the HashMap remains
-   * unchanged, and <pre>null</pre> is returned. NOTE: Since the value
+   * unchanged, and <code>null</code> is returned. NOTE: Since the value
    * could also be null, you must use containsKey to see if you are
    * actually removing a mapping.
    *
@@ -384,15 +386,15 @@ public class HashMap extends AbstractMap
    */
   public Object remove(Object key)
   {
-    modCount++;
     int idx = hash(key);
     HashEntry e = buckets[idx];
     HashEntry last = null;
 
     while (e != null)
       {
-        if (key == null ? e.key == null : key.equals(e.key))
+        if (equals(key, e.key))
           {
+            modCount++;
             if (last == null)
               buckets[idx] = e.next;
             else
@@ -408,40 +410,39 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Copies all elements of the given map into this hashtable.  If this table
-   * already has a mapping for a key, the new mapping replaces the current
-   * one.
-   *
-   * @param m the map to be hashed into this
+   * Clears the Map so it has no keys. This is O(1).
    */
-  public void putAll(Map m)
+  public void clear()
   {
-    Iterator itr = m.entrySet().iterator();
-
-    for (int msize = m.size(); msize > 0; msize--)
+    if (size != 0)
       {
-        Map.Entry e = (Map.Entry) itr.next();
-        // Optimize in case the Entry is one of our own.
-        if (e instanceof BasicMapEntry)
-          {
-            BasicMapEntry entry = (BasicMapEntry) e;
-            put(entry.key, entry.value);
-          }
-        else
-          {
-            put(e.getKey(), e.getValue());
-          }
+        modCount++;
+        Arrays.fill(buckets, null);
+        size = 0;
       }
   }
-  
+
   /**
-   * Clears the Map so it has no keys. This is O(1).
+   * Returns true if this HashMap contains a value <code>o</code>, such that
+   * <code>o.equals(value)</code>.
+   *
+   * @param value the value to search for in this HashMap
+   * @return true if at least one key maps to the value
+   * @see containsKey(Object)
    */
-  public void clear()
+  public boolean containsValue(Object value)
   {
-    modCount++;
-    Arrays.fill(buckets, null);
-    size = 0;
+    for (int i = buckets.length - 1; i >= 0; i--)
+      {
+        HashEntry e = buckets[i];
+        while (e != null)
+          {
+            if (equals(value, e.value))
+              return true;
+            e = e.next;
+          }
+      }
+    return false;
   }
 
   /**
@@ -463,6 +464,8 @@ public class HashMap extends AbstractMap
       }
     copy.buckets = new HashEntry[buckets.length];
     copy.putAllInternal(this);
+    // Clear the entry cache. AbstractMap.clone() does the others.
+    copy.entries = null;
     return copy;
   }
 
@@ -477,41 +480,43 @@ public class HashMap extends AbstractMap
    */
   public Set keySet()
   {
-    // Create an AbstractSet with custom implementations of those methods that
-    // can be overridden easily and efficiently.
-    return new AbstractSet()
-    {
-      public int size()
-      {
-        return size;
-      }
-
-      public Iterator iterator()
-      {
-        // Cannot create the iterator directly, because of LinkedHashMap.
-        return HashMap.this.iterator(KEYS);
-      }
-
-      public void clear()
-      {
-        HashMap.this.clear();
-      }
-
-      public boolean contains(Object o)
-      {
-        return HashMap.this.containsKey(o);
-      }
-
-      public boolean remove(Object o)
+    if (keys == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overridden easily and efficiently.
+      keys = new AbstractSet()
       {
-        // Test against the size of the HashMap to determine if anything
-        // really got removed. This is necessary because the return value of
-        // HashMap.remove() is ambiguous in the null case.
-        int oldsize = size;
-        HashMap.this.remove(o);
-        return (oldsize != size);
-      }
-    };
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator iterator()
+        {
+          // Cannot create the iterator directly, because of LinkedHashMap.
+          return HashMap.this.iterator(KEYS);
+        }
+
+        public void clear()
+        {
+          HashMap.this.clear();
+        }
+
+        public boolean contains(Object o)
+        {
+          return containsKey(o);
+        }
+
+        public boolean remove(Object o)
+        {
+          // Test against the size of the HashMap to determine if anything
+          // really got removed. This is neccessary because the return value
+          // of HashMap.remove() is ambiguous in the null case.
+          int oldsize = size;
+          HashMap.this.remove(o);
+          return oldsize != size;
+        }
+      };
+    return keys;
   }
 
   /**
@@ -526,33 +531,34 @@ public class HashMap extends AbstractMap
    */
   public Collection values()
   {
-    // We don't bother overriding many of the optional methods, as doing so
-    // wouldn't provide any significant performance advantage.
-    return new AbstractCollection()
-    {
-      public int size()
-      {
-        return size;
-      }
-
-      public Iterator iterator()
-      {
-        // Cannot create the iterator directly, because of LinkedHashMap.
-        return HashMap.this.iterator(VALUES);
-      }
-
-      public void clear()
+    if (values == null)
+      // We don't bother overriding many of the optional methods, as doing so
+      // wouldn't provide any significant performance advantage.
+      values = new AbstractCollection()
       {
-        HashMap.this.clear();
-      }
-    };
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator iterator()
+        {
+          // Cannot create the iterator directly, because of LinkedHashMap.
+          return HashMap.this.iterator(VALUES);
+        }
+
+        public void clear()
+        {
+          HashMap.this.clear();
+        }
+      };
+    return values;
   }
 
   /**
    * Returns a "set view" of this HashMap's entries. The set is backed by
    * the HashMap, so changes in one show up in the other.  The set supports
-   * element removal, but not element addition.
-   * <p>
+   * element removal, but not element addition.<p>
    *
    * Note that the iterators for all three views, from keySet(), entrySet(),
    * and values(), traverse the HashMap in the same sequence.
@@ -564,53 +570,62 @@ public class HashMap extends AbstractMap
    */
   public Set entrySet()
   {
-    // Create an AbstractSet with custom implementations of those methods that
-    // can be overridden easily and efficiently.
-    return new AbstractSet()
-    {
-      public int size()
-      {
-        return size;
-      }
-
-      public Iterator iterator()
-      {
-        // Cannot create the iterator directly, because of LinkedHashMap.
-        return HashMap.this.iterator(ENTRIES);
-      }
-
-      public void clear()
-      {
-        HashMap.this.clear();
-      }
-
-      public boolean contains(Object o)
-      {
-        return getEntry(o) != null;
-      }
-
-      public boolean remove(Object o)
+    if (entries == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overridden easily and efficiently.
+      entries = new AbstractSet()
       {
-        HashEntry e = getEntry(o);
-        if (e != null)
-          {
-            HashMap.this.remove(e.key);
-            return true;
-          }
-        return false;
-      }
-    };
+        public int size()
+        {
+          return size;
+        }
+
+        public Iterator iterator()
+        {
+          // Cannot create the iterator directly, because of LinkedHashMap.
+          return HashMap.this.iterator(ENTRIES);
+        }
+
+        public void clear()
+        {
+          HashMap.this.clear();
+        }
+
+        public boolean contains(Object o)
+        {
+          return getEntry(o) != null;
+        }
+
+        public boolean remove(Object o)
+        {
+          HashEntry e = getEntry(o);
+          if (e != null)
+            {
+              HashMap.this.remove(e.key);
+              return true;
+            }
+          return false;
+        }
+      };
+    return entries;
   }
 
-  /** Helper method that returns an index in the buckets array for `key;
-   * based on its hashCode().
+  /**
+   * Helper method for put, that creates and adds a new Entry.  This is
+   * overridden in LinkedHashMap for bookkeeping purposes.
    *
-   * @param key the key
-   * @return the bucket number
+   * @param key the key of the new Entry
+   * @param value the value
+   * @param idx the index in buckets where the new Entry belongs
+   * @param callRemove whether to call the removeEldestEntry method
+   * @see #put(Object, Object)
    */
-  int hash(Object key)
+  void addEntry(Object key, Object value, int idx, boolean callRemove)
   {
-    return (key == null) ? 0 : Math.abs(key.hashCode() % buckets.length);
+    HashEntry e = new HashEntry(key, value);
+
+    e.next = buckets[idx];
+    buckets[idx] = e;
   }
 
   /**
@@ -638,6 +653,52 @@ public class HashMap extends AbstractMap
   }
 
   /**
+   * Helper method that returns an index in the buckets array for `key'
+   * based on its hashCode().  Package visible for use by subclasses.
+   *
+   * @param key the key
+   * @return the bucket number
+   */
+  final int hash(Object key)
+  {
+    return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
+  }
+
+  /**
+   * Generates a parameterized iterator.  Must be overrideable, since
+   * LinkedHashMap iterates in a different order.
+   *
+   * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
+   * @return the appropriate iterator
+   */
+  Iterator iterator(int type)
+  {
+    return new HashIterator(type);
+  }
+
+  /**
+   * A simplified, more efficient internal implementation of putAll(). The 
+   * Map constructor and clone() should not call putAll or put, in order to 
+   * be compatible with the JDK implementation with respect to subclasses.
+   *
+   * @param m the map to initialize this from
+   */
+  void putAllInternal(Map m)
+  {
+    Iterator itr = m.entrySet().iterator();
+    int msize = m.size();
+    this.size = msize;
+
+    for (; msize > 0; msize--)
+      {
+	Map.Entry e = (Map.Entry) itr.next();
+	Object key = e.getKey();
+	int idx = hash(key);
+	addEntry(key, e.getValue(), idx, false);
+      }
+  }
+
+  /**
    * Increases the size of the HashMap and rehashes all keys to new array
    * indices; this is called when the addition of a new value would cause
    * size() > threshold. Note that the existing Entry objects are reused in
@@ -682,35 +743,6 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * Generates a parameterized iterator.  Must be overrideable, since
-   * LinkedHashMap iterates in a different order.
-   * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
-   * @return the appropriate iterator
-   */
-  Iterator iterator(int type)
-  {
-    return new HashIterator(type);
-  }
-
-  /**
-   * A simplified, more efficient internal implementation of putAll(). The 
-   * Map constructor and clone() should not call putAll or put, in order to 
-   * be compatible with the JDK implementation with respect to subclasses.
-   */
-  void putAllInternal(Map m)
-  {
-    Iterator itr = m.entrySet().iterator();
-
-    for (int msize = m.size(); msize > 0; msize--)
-      {
-	Map.Entry e = (Map.Entry) itr.next();
-	Object key = e.getKey();
-	int idx = hash(key);
-	addEntry(key, e.getValue(), idx, false);
-      }
-  }
-
-  /**
    * Serializes this object to the given stream.
    *
    * @param s the stream to write to
@@ -757,9 +789,6 @@ public class HashMap extends AbstractMap
     // Read and use capacity.
     buckets = new HashEntry[s.readInt()];
     int len = s.readInt();
-    // Already happens automatically.
-    // size = 0;
-    // modCount = 0;
 
     // Read and use key/value pairs.
     for ( ; len > 0; len--)
@@ -773,29 +802,29 @@ public class HashMap extends AbstractMap
    *
    * @author Jon Zeppieri
    */
-  class HashIterator implements Iterator
+  private final class HashIterator implements Iterator
   {
     /**
      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
      * or {@link #ENTRIES}.
      */
-    final int type;
+    private final int type;
     /**
      * The number of modifications to the backing HashMap that we know about.
      */
-    int knownMod = modCount;
+    private int knownMod = modCount;
     /** The number of elements remaining to be returned by next(). */
-    int count = size;
+    private int count = size;
     /** Current index in the physical hash table. */
-    int idx = buckets.length;
+    private int idx = buckets.length;
     /** The last Entry returned by a next() call. */
-    HashEntry last;
+    private HashEntry last;
     /**
      * The next entry that should be returned by next(). It is set to something
      * if we're iterating through a bucket that contains multiple linked
      * entries. It is null if next() needs to find a new bucket.
      */
-    HashEntry next;
+    private HashEntry next;
 
     /**
      * Construct a new HashIterator with the supplied type.
@@ -840,14 +869,14 @@ public class HashMap extends AbstractMap
       last = e;
       if (type == VALUES)
         return e.value;
-      else if (type == KEYS)
+      if (type == KEYS)
         return e.key;
       return e;
     }
 
     /**
      * Removes from the backing HashMap the last element which was fetched
-     * with the <pre>next()</pre> method.
+     * with the <code>next()</code> method.
      * @throws ConcurrentModificationException if the HashMap was modified
      * @throws IllegalStateException if called when there is no last element
      */
@@ -859,8 +888,8 @@ public class HashMap extends AbstractMap
         throw new IllegalStateException();
 
       HashMap.this.remove(last.key);
-      knownMod++;
       last = null;
+      knownMod++;
     }
   }
 }