Makefile.am: Add HashSet.java and java/lang/ref classes.

	* Makefile.am: Add HashSet.java and java/lang/ref classes.
	Remove BasicMapEntry.java and Bucket.java.
	* Makefile.in: Rebuilt.
	* java/util/HashMap.java: Rewritten.
	* java/util/HashSet.java: Imported from classpath.
	* java/util/WeakHashMap.java: Imported from classpath.
	* java/util/Hashtable.java: Rewritten based on new HashMap code.
	* java/util/Bucket.java: Deleted.
	* java/util/BasicMapEntry.java: Deleted.
	* java/util/Collections.java (search): Use a for-loop, not iterator
	hasNext().
	(copy): Use a for-loop. Throw an IndexOutOfBoundsException if run out
	of elements in source.
	(max): Use a for-loop.
	(min): Ditto.
	(reverse): Keep track of positions instead of using Iterator's
	nextIndex() and previousIndex().
	(shuffle(List)): Initialize defaultRandom if required using
	double-check thread safety idiom. Call two-argument shuffle method
	using defaultRandom.
	(defaultRandom): New field.
	(shuffle(List, Random)): Use a for-loop. Keep track of pos instead
	of using previousIndex() and nextIndex().
	(singletonMap(iterator)): Use a HashMap.Entry, not BasicMapEntry.
	* java/util/AbstractCollection.java (toString): Use a StringBuffer.
	* java/util/AbstractMap.java (toString): Use StringBuffer.
	* java/lang/ref/PhantomReference.java: Imported from classpath.
	* java/lang/ref/SoftReference.java: Ditto.
	* java/lang/ref/Reference.java: Ditto.
	* java/lang/ref/WeakReference.java: Ditto.
	* java/lang/ref/ReferenceQueue.java: Ditto.

From-SVN: r38183

18 files changed, 2916 insertions, 2036 deletions

diff --git a/libjava/ChangeLog b/libjava/ChangeLog
index c9a636a..9773112 100644
--- a/libjava/ChangeLog
+++ b/libjava/ChangeLog
@@ -1,3 +1,37 @@
+2000-12-11  Bryce McKinlay  <bryce@albatross.co.nz>
+
+	* Makefile.am: Add HashSet.java and java/lang/ref classes.
+	Remove BasicMapEntry.java and Bucket.java.
+	* Makefile.in: Rebuilt.
+	* java/util/HashMap.java: Rewritten.
+	* java/util/HashSet.java: Imported from classpath.
+	* java/util/WeakHashMap.java: Imported from classpath.
+	* java/util/Hashtable.java: Rewritten based on new HashMap code.
+	* java/util/Bucket.java: Deleted.
+	* java/util/BasicMapEntry.java: Deleted.
+	* java/util/Collections.java (search): Use a for-loop, not iterator
+	hasNext().
+	(copy): Use a for-loop. Throw an IndexOutOfBoundsException if run out 
+	of elements in source.
+	(max): Use a for-loop.
+	(min): Ditto.
+	(reverse): Keep track of positions instead of using Iterator's 
+	nextIndex() and previousIndex().
+	(shuffle(List)): Initialize defaultRandom if required using 
+	double-check thread safety idiom. Call two-argument shuffle method 
+	using defaultRandom.
+	(defaultRandom): New field.
+	(shuffle(List, Random)): Use a for-loop. Keep track of pos instead of
+	using previousIndex() and nextIndex().
+	(singletonMap(iterator)): Use a HashMap.Entry, not BasicMapEntry.
+	* java/util/AbstractCollection.java (toString): Use a StringBuffer.
+	* java/util/AbstractMap.java (toString): Use StringBuffer.
+	* java/lang/ref/PhantomReference.java: Imported from classpath.
+	* java/lang/ref/SoftReference.java: Ditto.
+	* java/lang/ref/Reference.java: Ditto.
+	* java/lang/ref/WeakReference.java: Ditto.
+	* java/lang/ref/ReferenceQueue.java: Ditto.
+
 2000-12-10  Richard Henderson <rth@redhat.com>
 	
 	* configure.host: Recognize alpha*-*, not alphaev6-*.
diff --git a/libjava/Makefile.am b/libjava/Makefile.am
index 1888118..4fff252 100644
--- a/libjava/Makefile.am
+++ b/libjava/Makefile.am
@@ -843,15 +843,6 @@ java/lang/UnsupportedOperationException.java \
 java/lang/VerifyError.java \
 java/lang/VirtualMachineError.java \
 java/lang/Void.java \
-java/lang/reflect/AccessibleObject.java	\
-java/lang/reflect/Array.java \
-java/lang/reflect/Constructor.java \
-java/lang/reflect/Field.java \
-java/lang/reflect/InvocationTargetException.java \
-java/lang/reflect/Member.java \
-java/lang/reflect/Method.java \
-java/lang/reflect/Modifier.java	\
-java/lang/reflect/ReflectPermission.java \
 java/io/BlockDataException.java	\
 java/io/BufferedInputStream.java \
 java/io/BufferedOutputStream.java \
@@ -934,9 +925,7 @@ java/util/AbstractSequentialList.java \
 java/util/AbstractSet.java \
 java/util/ArrayList.java \
 java/util/Arrays.java \
-java/util/BasicMapEntry.java \
 java/util/BitSet.java \
-java/util/Bucket.java \
 java/util/Calendar.java	\
 java/util/Collection.java \
 java/util/Collections.java \
@@ -950,6 +939,7 @@ java/util/EventListener.java \
 java/util/EventObject.java \
 java/util/GregorianCalendar.java \
 java/util/HashMap.java \
+java/util/HashSet.java \
 java/util/Hashtable.java \
 java/util/Iterator.java	\
 java/util/LinkedList.java \
@@ -978,6 +968,7 @@ java/util/Timer.java \
 java/util/TimerTask.java \
 java/util/TooManyListenersException.java \
 java/util/Vector.java
+#java/util/WeakHashmap.java
 
 
 ## List of all .java files to be compiled.  Please keep this list
@@ -1023,6 +1014,20 @@ gnu/java/locale/Calendar_nl.java \
 gnu/java/security/provider/Gnu.java \
 gnu/java/security/provider/SHA.java \
 gnu/java/security/provider/SHA1PRNG.java \
+java/lang/ref/PhantomReference.java \
+java/lang/ref/Reference.java \
+java/lang/ref/ReferenceQueue.java \
+java/lang/ref/SoftReference.java \
+java/lang/ref/WeakReference.java \
+java/lang/reflect/AccessibleObject.java	\
+java/lang/reflect/Array.java \
+java/lang/reflect/Constructor.java \
+java/lang/reflect/Field.java \
+java/lang/reflect/InvocationTargetException.java \
+java/lang/reflect/Member.java \
+java/lang/reflect/Method.java \
+java/lang/reflect/Modifier.java	\
+java/lang/reflect/ReflectPermission.java \
 java/math/BigDecimal.java \
 java/math/BigInteger.java \
 java/net/BindException.java \
diff --git a/libjava/Makefile.in b/libjava/Makefile.in
index 6bc235e..25b30a0 100644
--- a/libjava/Makefile.in
+++ b/libjava/Makefile.in
@@ -120,43 +120,29 @@ here = @here@
 libgcj_basedir = @libgcj_basedir@
 
 AUTOMAKE_OPTIONS = foreign no-installinfo
-@TESTSUBDIR_TRUE@SUBDIRS = \
-@TESTSUBDIR_TRUE@$(DIRLTDL) testsuite gcj include
-@TESTSUBDIR_FALSE@SUBDIRS = \
-@TESTSUBDIR_FALSE@$(DIRLTDL) gcj include
-@USE_LIBDIR_TRUE@toolexeclibdir = \
-@USE_LIBDIR_TRUE@$(libdir)$(MULTISUBDIR)
-@USE_LIBDIR_FALSE@toolexeclibdir = \
-@USE_LIBDIR_FALSE@$(toolexecdir)/lib$(MULTISUBDIR)
-@USE_LIBDIR_FALSE@toolexecdir = \
-@USE_LIBDIR_FALSE@$(exec_prefix)/$(target_alias)
-@NO_X_TRUE@cond_x_ltlibrary = \
-@NO_X_FALSE@cond_x_ltlibrary = \
-@NO_X_FALSE@libgcjx.la
+@TESTSUBDIR_TRUE@SUBDIRS = @TESTSUBDIR_TRUE@$(DIRLTDL) testsuite gcj include
+@TESTSUBDIR_FALSE@SUBDIRS = @TESTSUBDIR_FALSE@$(DIRLTDL) gcj include
+@USE_LIBDIR_TRUE@toolexeclibdir = @USE_LIBDIR_TRUE@$(libdir)$(MULTISUBDIR)
+@USE_LIBDIR_FALSE@toolexeclibdir = @USE_LIBDIR_FALSE@$(toolexecdir)/lib$(MULTISUBDIR)
+@USE_LIBDIR_FALSE@toolexecdir = @USE_LIBDIR_FALSE@$(exec_prefix)/$(target_alias)
+@NO_X_TRUE@cond_x_ltlibrary = 
+@NO_X_FALSE@cond_x_ltlibrary = @NO_X_FALSE@libgcjx.la
 
 toolexeclib_LTLIBRARIES = libgcj.la $(cond_x_ltlibrary)
 toolexeclib_DATA = libgcj.spec
 data_DATA = libgcj.jar
 
-@NEEDS_DATA_START_TRUE@toolexeclib_LIBRARIES = \
-@NEEDS_DATA_START_TRUE@libgcjdata.a
-@NEEDS_DATA_START_TRUE@libgcjdata_a_SOURCES = \
-@NEEDS_DATA_START_TRUE@libgcjdata.c
+@NEEDS_DATA_START_TRUE@toolexeclib_LIBRARIES = @NEEDS_DATA_START_TRUE@libgcjdata.a
+@NEEDS_DATA_START_TRUE@libgcjdata_a_SOURCES = @NEEDS_DATA_START_TRUE@libgcjdata.c
 
-@NATIVE_TRUE@bin_PROGRAMS = \
-@NATIVE_TRUE@jv-convert gij
+@NATIVE_TRUE@bin_PROGRAMS = @NATIVE_TRUE@jv-convert gij
 
 bin_SCRIPTS = addr2name.awk
-@CANADIAN_TRUE@@NULL_TARGET_TRUE@ZIP = \
-@CANADIAN_TRUE@@NULL_TARGET_TRUE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
-@CANADIAN_TRUE@@NULL_TARGET_FALSE@ZIP = \
-@CANADIAN_TRUE@@NULL_TARGET_FALSE@fastjar
-@CANADIAN_FALSE@ZIP = \
-@CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
-@CANADIAN_TRUE@GCJH = \
-@CANADIAN_TRUE@gcjh
-@CANADIAN_FALSE@GCJH = \
-@CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/gcc/gcjh$(EXEEXT)
+@CANADIAN_TRUE@@NULL_TARGET_TRUE@ZIP = @CANADIAN_TRUE@@NULL_TARGET_TRUE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
+@CANADIAN_TRUE@@NULL_TARGET_FALSE@ZIP = @CANADIAN_TRUE@@NULL_TARGET_FALSE@fastjar
+@CANADIAN_FALSE@ZIP = @CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/fastjar/fastjar$(EXEEXT)
+@CANADIAN_TRUE@GCJH = @CANADIAN_TRUE@gcjh
+@CANADIAN_FALSE@GCJH = @CANADIAN_FALSE@$(MULTIBUILDTOP)../$(COMPPATH)/gcc/gcjh$(EXEEXT)
 
 GCJCOMPILE = $(LIBTOOL) --tag=GCJ --mode=compile $(GCJ) -fassume-compiled -fclasspath=$(here) -L$(here) $(JC1FLAGS) -MD -MT $@ -MF $(@:.lo=.d) -c
 GCJLINK = $(LIBTOOL) --mode=link $(GCJ) -L$(here) $(JC1FLAGS) $(LDFLAGS) -o $@
@@ -171,10 +157,8 @@ AM_CXXFLAGS = -fno-rtti -fvtable-thunks -fasynchronous-exceptions \
 	-fdollars-in-identifiers \
 	@LIBGCJ_CXXFLAGS@ @EXCEPTIONSPEC@ @X_CFLAGS@ $(WARNINGS) -D_GNU_SOURCE
 
-@USING_GCC_TRUE@AM_CFLAGS = \
-@USING_GCC_TRUE@@LIBGCJ_CFLAGS@ $(WARNINGS)
-@USING_GCC_FALSE@AM_CFLAGS = \
-@USING_GCC_FALSE@@LIBGCJ_CFLAGS@
+@USING_GCC_TRUE@AM_CFLAGS = @USING_GCC_TRUE@@LIBGCJ_CFLAGS@ $(WARNINGS)
+@USING_GCC_FALSE@AM_CFLAGS = @USING_GCC_FALSE@@LIBGCJ_CFLAGS@
 
 JCFLAGS = -g
 JC1FLAGS = -g @LIBGCJ_JAVAFLAGS@
@@ -243,8 +227,7 @@ extra_headers = java/lang/Object.h java/lang/Class.h
 
 NM = nm
 
-@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@noinst_PROGRAMS = \
-@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@gen-from-JIS
+@NATIVE_TRUE@@MAINTAINER_MODE_TRUE@noinst_PROGRAMS = @NATIVE_TRUE@@MAINTAINER_MODE_TRUE@gen-from-JIS
 
 CONVERT_DIR = gnu/gcj/convert
 
@@ -611,15 +594,6 @@ java/lang/UnsupportedOperationException.java \
 java/lang/VerifyError.java \
 java/lang/VirtualMachineError.java \
 java/lang/Void.java \
-java/lang/reflect/AccessibleObject.java	\
-java/lang/reflect/Array.java \
-java/lang/reflect/Constructor.java \
-java/lang/reflect/Field.java \
-java/lang/reflect/InvocationTargetException.java \
-java/lang/reflect/Member.java \
-java/lang/reflect/Method.java \
-java/lang/reflect/Modifier.java	\
-java/lang/reflect/ReflectPermission.java \
 java/io/BlockDataException.java	\
 java/io/BufferedInputStream.java \
 java/io/BufferedOutputStream.java \
@@ -702,9 +676,7 @@ java/util/AbstractSequentialList.java \
 java/util/AbstractSet.java \
 java/util/ArrayList.java \
 java/util/Arrays.java \
-java/util/BasicMapEntry.java \
 java/util/BitSet.java \
-java/util/Bucket.java \
 java/util/Calendar.java	\
 java/util/Collection.java \
 java/util/Collections.java \
@@ -718,6 +690,7 @@ java/util/EventListener.java \
 java/util/EventObject.java \
 java/util/GregorianCalendar.java \
 java/util/HashMap.java \
+java/util/HashSet.java \
 java/util/Hashtable.java \
 java/util/Iterator.java	\
 java/util/LinkedList.java \
@@ -747,6 +720,7 @@ java/util/TimerTask.java \
 java/util/TooManyListenersException.java \
 java/util/Vector.java
 
+#java/util/WeakHashmap.java
 
 ordinary_java_source_files = $(core_java_source_files) \
 gnu/gcj/RawData.java \
@@ -785,6 +759,20 @@ gnu/java/locale/Calendar_nl.java \
 gnu/java/security/provider/Gnu.java \
 gnu/java/security/provider/SHA.java \
 gnu/java/security/provider/SHA1PRNG.java \
+java/lang/ref/PhantomReference.java \
+java/lang/ref/Reference.java \
+java/lang/ref/ReferenceQueue.java \
+java/lang/ref/SoftReference.java \
+java/lang/ref/WeakReference.java \
+java/lang/reflect/AccessibleObject.java	\
+java/lang/reflect/Array.java \
+java/lang/reflect/Constructor.java \
+java/lang/reflect/Field.java \
+java/lang/reflect/InvocationTargetException.java \
+java/lang/reflect/Member.java \
+java/lang/reflect/Method.java \
+java/lang/reflect/Modifier.java	\
+java/lang/reflect/ReflectPermission.java \
 java/math/BigDecimal.java \
 java/math/BigInteger.java \
 java/net/BindException.java \
@@ -1203,7 +1191,7 @@ libgcj-test.spec.in libgcj.spec.in
 
 DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
 
-TAR = tar
+TAR = gtar
 GZIP_ENV = --best
 DIST_SUBDIRS =  @DIRLTDL@ testsuite gcj include @DIRLTDL@ gcj include
 DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
@@ -1562,7 +1550,9 @@ DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
 .deps/java/lang/natMath.P .deps/java/lang/natObject.P \
 .deps/java/lang/natRuntime.P .deps/java/lang/natString.P \
 .deps/java/lang/natSystem.P .deps/java/lang/natThread.P \
-.deps/java/lang/natThrowable.P \
+.deps/java/lang/natThrowable.P .deps/java/lang/ref/PhantomReference.P \
+.deps/java/lang/ref/Reference.P .deps/java/lang/ref/ReferenceQueue.P \
+.deps/java/lang/ref/SoftReference.P .deps/java/lang/ref/WeakReference.P \
 .deps/java/lang/reflect/AccessibleObject.P \
 .deps/java/lang/reflect/Array.P .deps/java/lang/reflect/Constructor.P \
 .deps/java/lang/reflect/Field.P \
@@ -1682,8 +1672,7 @@ DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
 .deps/java/util/AbstractCollection.P .deps/java/util/AbstractList.P \
 .deps/java/util/AbstractMap.P .deps/java/util/AbstractSequentialList.P \
 .deps/java/util/AbstractSet.P .deps/java/util/ArrayList.P \
-.deps/java/util/Arrays.P .deps/java/util/BasicMapEntry.P \
-.deps/java/util/BitSet.P .deps/java/util/Bucket.P \
+.deps/java/util/Arrays.P .deps/java/util/BitSet.P \
 .deps/java/util/Calendar.P .deps/java/util/Collection.P \
 .deps/java/util/Collections.P .deps/java/util/Comparator.P \
 .deps/java/util/ConcurrentModificationException.P \
@@ -1691,11 +1680,11 @@ DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
 .deps/java/util/EmptyStackException.P .deps/java/util/Enumeration.P \
 .deps/java/util/EventListener.P .deps/java/util/EventObject.P \
 .deps/java/util/GregorianCalendar.P .deps/java/util/HashMap.P \
-.deps/java/util/Hashtable.P .deps/java/util/Iterator.P \
-.deps/java/util/LinkedList.P .deps/java/util/List.P \
-.deps/java/util/ListIterator.P .deps/java/util/ListResourceBundle.P \
-.deps/java/util/Locale.P .deps/java/util/Map.P \
-.deps/java/util/MissingResourceException.P \
+.deps/java/util/HashSet.P .deps/java/util/Hashtable.P \
+.deps/java/util/Iterator.P .deps/java/util/LinkedList.P \
+.deps/java/util/List.P .deps/java/util/ListIterator.P \
+.deps/java/util/ListResourceBundle.P .deps/java/util/Locale.P \
+.deps/java/util/Map.P .deps/java/util/MissingResourceException.P \
 .deps/java/util/NoSuchElementException.P .deps/java/util/Observable.P \
 .deps/java/util/Observer.P .deps/java/util/Properties.P \
 .deps/java/util/PropertyPermission.P \
@@ -2103,7 +2092,7 @@ distdir: $(DISTFILES)
 	@for file in $(DISTFILES); do \
 	  d=$(srcdir); \
 	  if test -d $$d/$$file; then \
-	    cp -pr $$/$$file $(distdir)/$$file; \
+	    cp -pr $$d/$$file $(distdir)/$$file; \
 	  else \
 	    test -f $(distdir)/$$file \
 	    || ln $$d/$$file $(distdir)/$$file 2> /dev/null \
diff --git a/libjava/java/lang/ref/PhantomReference.java b/libjava/java/lang/ref/PhantomReference.java
new file mode 100644
index 0000000..7c07b52e
--- /dev/null
+++ b/libjava/java/lang/ref/PhantomReference.java
@@ -0,0 +1,62 @@
+/* java.lang.ref.PhantomReference
+   Copyright (C) 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+ 
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * A phantom reference is useful, to get notified, when an object got
+ * finalized.  You can't access that object though, since it is
+ * finalized.  This is the reason, why <code>get()</code> always
+ * returns null.
+ *
+ * @author Jochen Hoenicke 
+ */
+public class PhantomReference 
+  extends Reference
+{
+  /**
+   * Creates a new phantom reference.
+   * @param referent the object that should be watched.
+   * @param q the queue that should be notified, if the referent was
+   * finalized.  This mustn't be <code>null</code>.
+   * @exception NullPointerException if q is null.
+   */
+  public PhantomReference(Object referent, ReferenceQueue q)
+  {
+    super(referent, q);
+  }
+  
+  /**
+   * Returns the object, this reference refers to.
+   * @return <code>null</code>, since the refered object may be
+   * finalized and thus not accessible.  
+   */
+  public Object get()
+  {
+    return null;
+  }
+}
diff --git a/libjava/java/lang/ref/Reference.java b/libjava/java/lang/ref/Reference.java
new file mode 100644
index 0000000..2349033
--- /dev/null
+++ b/libjava/java/lang/ref/Reference.java
@@ -0,0 +1,166 @@
+/* java.lang.ref.Reference
+   Copyright (C) 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+ 
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * This is the base class of all references.  A reference allows
+ * refering to an object without preventing the garbage collection to
+ * collect it.  The only way to get the referred object is via the
+ * <code>get()</code>-method.  This method will return
+ * <code>null</code> if the object was collected. <br>
+ *
+ * A reference may be registered with a queue.  When a referred
+ * element gets collected the reference will be put on the queue, so
+ * that you will be notified. <br>
+ *
+ * There are currently three types of references:  soft reference,
+ * weak reference and phantom reference. <br>
+ *
+ * Soft references will be cleared if the garbage collection is told
+ * to free some memory and there are no unreferenced or weakly referenced
+ * objects.  It is useful for caches. <br>
+ *
+ * Weak references will be cleared as soon as the garbage collection
+ * determines that the refered object is only weakly reachable.  They
+ * are useful as keys in hashtables (see <code>WeakHashtable</code>) as
+ * you get notified when nobody has the key anymore.
+ *
+ * Phantom references don't prevent finalization.  If an object is only
+ * phantom reachable, it will be finalized, and the reference will be
+ * enqueued, but not cleared.  Since you mustn't access an finalized
+ * object, the <code>get</code> method of a phantom reference will never
+ * work.  It is useful to keep track, when an object is finalized.
+ *
+ * @author Jochen Hoenicke
+ * @see java.util.WeakHashtable
+ */
+public abstract class Reference
+{
+  /**
+   * The underlying object.  This field is handled in a special way by
+   * the garbage collection.
+   */
+  Object referent;
+
+  /**
+   * The queue this reference is registered on. This is null, if this
+   * wasn't registered to any queue or reference was already enqueued.
+   */
+  ReferenceQueue queue;
+
+  /**
+   * Link to the next entry on the queue.  If this is null, this
+   * reference is not enqueued.  Otherwise it points to the next
+   * reference.  The last reference on a queue will point to itself
+   * (not to null, that value is used to mark a not enqueued
+   * reference).  
+   */
+  Reference nextOnQueue;
+
+  /**
+   * This lock should be taken by the garbage collection, before
+   * determining reachability.  It will prevent the get()-method to
+   * return the reference so that reachability doesn't change.
+   */
+  static Object lock = new Object();
+
+  /**
+   * Creates a new reference that is not registered to any queue.
+   * Since it is package private, it is not possible to overload this
+   * class in a different package.  
+   * @param referent the object we refer to.
+   */
+  Reference(Object ref)
+  {
+    referent = ref;
+  }
+
+  /**
+   * Creates a reference that is registered to a queue.  Since this is
+   * package private, it is not possible to overload this class in a
+   * different package.  
+   * @param referent the object we refer to.
+   * @param q the reference queue to register on.
+   * @exception NullPointerException if q is null.
+   */
+  Reference(Object ref, ReferenceQueue q)
+  {
+    if (q == null)
+      throw new NullPointerException();
+    referent = ref;
+    queue = q;
+  }
+
+  /**
+   * Returns the object, this reference refers to.
+   * @return the object, this reference refers to, or null if the 
+   * reference was cleared.
+   */
+  public Object get()
+  {
+    synchronized(lock)
+      {
+	return referent;
+      }
+  }
+
+  /**
+   * Clears the reference, so that it doesn't refer to its object
+   * anymore.  For soft and weak references this is called by the
+   * garbage collection.  For phantom references you should call 
+   * this when enqueuing the reference.
+   */
+  public void clear()
+  {
+    referent = null;
+  }
+
+  /**
+   * Tells if the object is enqueued on a reference queue.
+   * @return true if it is enqueued, false otherwise.
+   */
+  public boolean isEnqueued()
+  {
+    return nextOnQueue != null;
+  }
+
+  /**
+   * Enqueue an object on a reference queue.  This is normally executed
+   * by the garbage collection.
+   */
+  public boolean enqueue() 
+  {
+    if (queue != null)
+      {
+	queue.enqueue(this);
+	queue = null;
+	return true;
+      }
+    return false;
+  }
+}
diff --git a/libjava/java/lang/ref/ReferenceQueue.java b/libjava/java/lang/ref/ReferenceQueue.java
new file mode 100644
index 0000000..57ec4193
--- /dev/null
+++ b/libjava/java/lang/ref/ReferenceQueue.java
@@ -0,0 +1,134 @@
+/* java.lang.ref.ReferenceQueue
+   Copyright (C) 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+ 
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * This is the queue, where references can enqueue themselve on.  Each
+ * reference may be registered to a queue at initialization time and
+ * will be appended to the queue, when the enqueue method is called.
+ *
+ * The enqueue method may be automatically called by the garbage
+ * collector if it detects, that the object is only reachable through
+ * the Reference objects.
+ *
+ * @author Jochen Hoenicke
+ * @see Reference#enqueue()
+ */
+public class ReferenceQueue
+{
+  /**
+   * This is a linked list of references.  If this is null, the list is
+   * empty.  Otherwise this points to the first reference on the queue.
+   * The first reference will point to the next reference via the 
+   * <code>nextOnQueue</code> field.  The last reference will point to
+   * itself (not to null, since <code>nextOnQueue</code> is used to 
+   * determine if a reference is enqueued).
+   */
+  private Reference first;
+
+  /**
+   * Creates a new empty reference queue.
+   */
+  public ReferenceQueue()
+  {
+  }
+
+  /**
+   * Checks if there is a reference on the queue, returning it
+   * immediately.  The reference will be dequeued.
+   *
+   * @return a reference on the queue, if there is one,
+   * <code>null</code> otherwise.  
+   */
+  public synchronized Reference poll()
+  { 
+    return dequeue();
+  }
+
+  /**
+   * This is called by reference to enqueue itself on this queue.  
+   * @param ref the reference that should be enqueued.
+   */
+  synchronized void enqueue(Reference ref)
+  {
+    /* last reference will point to itself */
+    ref.nextOnQueue = first == null ? ref : first;
+    first = ref;
+    /* this wakes only one remove thread. */
+    notify();
+  }
+
+  /**
+   * Remove a reference from the queue, if there is one.
+   * @return the first element of the queue, or null if there isn't any.
+   */
+  private Reference dequeue()
+  {
+    if (first == null)
+      return null;
+
+    Reference result = first;
+    first = (first == first.nextOnQueue) ? null : first.nextOnQueue;
+    result.nextOnQueue = null;
+    return result;
+  }
+
+  /**
+   * Removes a reference from the queue, blocking for <code>timeout</code>
+   * until a reference is enqueued.
+   * @param timeout the timeout period in milliseconds, <code>0</code> means
+   * wait forever.
+   * @return the reference removed from the queue, or 
+   * <code>null</code> if timeout period expired.  
+   * @exception InterruptedException if the wait was interrupted.
+   */
+  public synchronized Reference remove(long timeout)
+    throws InterruptedException
+  {
+    if (first == null)
+      {
+	wait(timeout);
+      }
+
+    return dequeue();
+  }
+    
+
+  /**
+   * Removes a reference from the queue, blocking until a reference is
+   * enqueued.
+   *
+   * @return the reference removed from the queue.  
+   * @exception InterruptedException if the wait was interrupted.
+   */
+  public Reference remove()
+    throws InterruptedException
+  {
+    return remove(0L);
+  }
+}
diff --git a/libjava/java/lang/ref/SoftReference.java b/libjava/java/lang/ref/SoftReference.java
new file mode 100644
index 0000000..58bd14c
--- /dev/null
+++ b/libjava/java/lang/ref/SoftReference.java
@@ -0,0 +1,73 @@
+/* java.lang.ref.SoftReference
+   Copyright (C) 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+ 
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * A soft reference will be cleared, if the object is only softly
+ * reachable and the garbage collection needs more memory.  The garbage
+ * collection will use an intelligent strategy to determine which soft
+ * references it should clear.  This makes a soft reference ideal for
+ * caches.<br>
+ *
+ * @author Jochen Hoenicke 
+ */
+public class SoftReference 
+  extends Reference
+{
+  /**
+   * Create a new soft reference, that is not registered to any queue.
+   * @param referent the object we refer to.
+   */
+  public SoftReference(Object referent)
+  {
+    super(referent);
+  }
+
+  /**
+   * Create a new soft reference.
+   * @param referent the object we refer to.
+   * @param q the reference queue to register on.
+   * @exception NullPointerException if q is null.
+   */
+  public SoftReference(Object referent, ReferenceQueue q)
+  {
+    super(referent, q);
+  }
+  
+  /**
+   * Returns the object, this reference refers to.
+   * @return the object, this reference refers to, or null if the 
+   * reference was cleared.
+   */
+  public Object get()
+  {
+    /* Why is this overloaded??? 
+     * Maybe for a kind of LRU strategy. */
+    return super.get();
+  }
+}
diff --git a/libjava/java/lang/ref/WeakReference.java b/libjava/java/lang/ref/WeakReference.java
new file mode 100644
index 0000000..32d5b13
--- /dev/null
+++ b/libjava/java/lang/ref/WeakReference.java
@@ -0,0 +1,68 @@
+/* java.lang.ref.WeakReference
+   Copyright (C) 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+ 
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.lang.ref;
+
+/**
+ * A weak reference will be cleared, if the object is only weakly
+ * reachable.  It is useful for lookup tables, where you aren't
+ * interested in an entry, if the key isn't reachable anymore.
+ * <code>WeakHashtable</code> is a complete implementation of such a
+ * table. <br>
+ *
+ * It is also useful to make objects unique: You create a set of weak
+ * references to those objects, and when you create a new object you
+ * look in this set, if the object already exists and return it.  If
+ * an object is not referenced anymore, the reference will
+ * automatically cleared, and you may remove it from the set. <br>
+ *
+ * @author Jochen Hoenicke 
+ * @see java.util.WeakHashtable 
+ */
+public class WeakReference 
+  extends Reference
+{
+  /**
+   * Create a new weak reference, that is not registered to any queue.
+   * @param referent the object we refer to.
+   */
+  public WeakReference(Object referent)
+  {
+    super(referent);
+  }
+
+  /**
+   * Create a new weak reference.
+   * @param referent the object we refer to.
+   * @param q the reference queue to register on.
+   * @exception NullPointerException if q is null.
+   */
+  public WeakReference(Object referent, ReferenceQueue q)
+  {
+    super(referent, q);
+  }
+}
diff --git a/libjava/java/util/AbstractCollection.java b/libjava/java/util/AbstractCollection.java
index d75aff9..1bb73d7 100644
--- a/libjava/java/util/AbstractCollection.java
+++ b/libjava/java/util/AbstractCollection.java
@@ -332,14 +332,14 @@ public abstract class AbstractCollection implements Collection
   {
     Iterator itr = iterator();
     int size = size();
-    String r = "[";
+    StringBuffer r = new StringBuffer("[");
     for (int pos = 0; pos < size; pos++)
       {
-	r += itr.next();
+	r.append(itr.next());
 	if (pos < size - 1)
-	  r += ", ";
+	  r.append(", ");
       }
-    r += "]";
-    return r;
+    r.append("]");
+    return r.toString();
   }
 }
diff --git a/libjava/java/util/AbstractMap.java b/libjava/java/util/AbstractMap.java
index c4f9df0..7ce7305 100644
--- a/libjava/java/util/AbstractMap.java
+++ b/libjava/java/util/AbstractMap.java
@@ -227,15 +227,18 @@ public abstract class AbstractMap implements Map
   {
     Iterator entries = entrySet().iterator();
     int size = size();
-    String r = "{";
+    StringBuffer r = new StringBuffer("{");
     for (int pos = 0; pos < size; pos++)
       {
-	r += entries.next();
+        // Append the toString value of the entries rather than calling 
+	// getKey/getValue. This is more efficient and it matches the JDK
+	// behaviour.
+	r.append(entries.next());	
 	if (pos < size - 1)
-	  r += ", ";
+	  r.append(", ");
       }
-    r += "}";
-    return r;
+    r.append("}");
+    return r.toString();
   }
 
   public Collection values()
diff --git a/libjava/java/util/AbstractSet.java b/libjava/java/util/AbstractSet.java
index 1014e43..6c3f219 100644
--- a/libjava/java/util/AbstractSet.java
+++ b/libjava/java/util/AbstractSet.java
@@ -38,7 +38,6 @@ package java.util;
  */
 public abstract class AbstractSet extends AbstractCollection implements Set
 {
-
   /**
    * Tests whether the given object is equal to this Set. This implementation
    * first checks whether this set <em>is</em> the given object, and returns
diff --git a/libjava/java/util/BasicMapEntry.java b/libjava/java/util/BasicMapEntry.java
deleted file mode 100644
index 2d6d0e5..0000000
--- a/libjava/java/util/BasicMapEntry.java
+++ /dev/null
@@ -1,135 +0,0 @@
-/* BasicMapEntry.java -- a class providing a plain-vanilla implementation of
-   the Map.Entry interface; could be used anywhere in java.util
-   Copyright (C) 1998 Free Software Foundation, Inc.
-
-This file is part of GNU Classpath.
-
-GNU Classpath is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
- 
-GNU Classpath is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GNU Classpath; see the file COPYING.  If not, write to the
-Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
-02111-1307 USA.
-
-As a special exception, if you link this library with other files to
-produce an executable, this library does not by itself cause the
-resulting executable to be covered by the GNU General Public License.
-This exception does not however invalidate any other reasons why the
-executable file might be covered by the GNU General Public License. */
-
-
-package java.util;
-
-/**
- * a class which implements Map.Entry
- *
- * @author      Jon Zeppieri
- * @version     $Revision: 1.3 $
- * @modified    $Id: BasicMapEntry.java,v 1.3 2000/03/15 21:59:07 rao Exp $
- */
-class BasicMapEntry implements Map.Entry
-{
-    /** the key */
-    Object key;
-    /** the value */
-    Object value;
-    
-    /**
-     * construct a new BasicMapEntry with the given key and value
-     *
-     * @param     newKey       the key of this Entry
-     * @param     newValue     the value of this Entry
-     */
-    BasicMapEntry(Object newKey, Object newValue)
-    {
-	key = newKey;
-	value = newValue;
-    }
-    
-    /**
-     * returns true if <pre>o</pre> is a Map.Entry and 
-     * <pre> 
-     * (((o.getKey == null) ? (key == null) : 
-     * o.getKey().equals(key)) && 
-     * ((o.getValue() == null) ? (value == null) : 
-     * o.getValue().equals(value)))
-     * </pre>
-     *
-     * NOTE: the calls to getKey() and getValue() in this implementation
-     * are <i>NOT</i> superfluous and should not be removed.  They insure 
-     * that subclasses such as HashMapEntry work correctly
-     *
-     * @param      o        the Object being tested for equality
-     */
-    public boolean equals(Object o)
-    {
-	Map.Entry tester;
-	Object oTestingKey, oTestingValue;
-	Object oKey, oValue;
-	if (o instanceof Map.Entry)
-	    {
-		tester = (Map.Entry) o;
-		oKey = getKey();
-		oValue = getValue();
-		oTestingKey = tester.getKey();
-		oTestingValue = tester.getValue();
-		return (((oTestingKey == null) ? (oKey == null) : 
-			 oTestingKey.equals(oKey)) && 
-			((oTestingValue == null) ? (oValue == null) : 
-			 oTestingValue.equals(oValue)));
-	    }
-	    return false;
-    }
-
-    /** returns the key */
-    public Object getKey()
-	{
-	    return key;
-	}
-    
-    /** returns the value */
-    public Object getValue()
-    {
-	return value;
-    }
-    
-    /** the hashCode() for a Map.Entry is 
-     * <pre> 
-     * ((getKey() == null) ? 0 : getKey().hashCode()) ^ 
-     * ((getValue() == null) ? 0 : getValue().hashCode());
-     * </pre>
-     *
-     * NOTE: the calls to getKey() and getValue() in this implementation
-     * are <i>NOT</i> superfluous and should not be removed.  They insure 
-     * that subclasses such as HashMapEntry work correctly
-     */
-    public int hashCode()
-    {
-	Object oKey = getKey();
-	Object oValue = getValue();
-	return ((oKey == null) ? 0 : oKey.hashCode()) ^ 
-	    ((oValue == null) ? 0 : oValue.hashCode());
-    }
-    
-    /** 
-     * sets the value of this Map.Entry 
-     *
-     * @param     newValue         the new value of this Map.Entry
-     */
-    public Object setValue(Object newValue)
-	throws java.lang.UnsupportedOperationException, ClassCastException, 
-	       IllegalArgumentException, NullPointerException
-    {
-	Object oVal = value;
-	value = newValue;
-	return oVal;
-    }
-}
diff --git a/libjava/java/util/Bucket.java b/libjava/java/util/Bucket.java
deleted file mode 100644
index 8c0edf4..0000000
--- a/libjava/java/util/Bucket.java
+++ /dev/null
@@ -1,199 +0,0 @@
-/* Bucket.java -- a class providing a hash-bucket data structure 
-   (a lightweight linked list)
-   Copyright (C) 1998, 2000 Free Software Foundation, Inc.
-
-This file is part of GNU Classpath.
-
-GNU Classpath is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
- 
-GNU Classpath is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GNU Classpath; see the file COPYING.  If not, write to the
-Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
-02111-1307 USA.
-
-As a special exception, if you link this library with other files to
-produce an executable, this library does not by itself cause the
-resulting executable to be covered by the GNU General Public License.
-This exception does not however invalidate any other reasons why the
-executable file might be covered by the GNU General Public License. */
-
-
-package java.util;
-
-/**
- * a class representing a simple, lightweight linked-list, using Node
- * objects as its linked nodes; this is used by Hashtable and HashMap
- *
- * @author        Jon Zeppieri
- * @version       $Revision: 1.3 $
- * @modified      $Id: Bucket.java,v 1.3 2000/03/15 21:59:08 rao Exp $
- */
-class Bucket
-{
-    /** the first node of the lined list, originally null */
-    Node first;
-    
-    /** trivial constructor for a Bucket */
-    Bucket()
-    {
-    }
-    
-    /** add this key / value pair to the list
-     *
-     * @param    newNode    a Node object to be added to this list
-     * @return the old value mapped to the key if there was one, 
-     *  otherwise null.
-     */
-    Object add(Node newNode)
-    {
-	Object oKey;
-	Object oTestKey = newNode.getKey();
-	Node it = first;
-	Node prev = null;
-	if (it == null) // if the list is empty (the ideal case), we make a new single-node list
-	    {
-		first = newNode;
-		return null;
-	    }
-	else // otherwise try to find where this key already exists in the list,
-	    {// and if it does, replace the value with the new one (and return the old one)
-		while (it != null)  
-		    {
-			oKey = it.getKey();
-			if ((oKey == null) ? (oTestKey == null) :
-			    oKey.equals(oTestKey))
-			    {
-			        Object oldValue = it.value;
-				it.value = newNode.getValue();
-				return oldValue;
-			    }
-			prev = it;  
-			it = it.next;
-		    }
-		prev.next = newNode; // otherwise, just stick this at the 
-		return null;                   // end of the list
-	    }
-    }
-    
-    /**
-     * remove a Map.Entry in this list with the supplied key and return its value,
-     * if it exists, else return null
-     *
-     * @param     key       the key we are looking for in this list
-     */
-    Object removeByKey(Object key)
-    {
-	Object oEntryKey;
-	Node prev = null;
-	Node it = first;
-	while (it != null)
-	    {
-		oEntryKey = it.getKey();
-		if ((oEntryKey == null) ? (key == null) : oEntryKey.equals(key))
-		    {
-			if (prev == null) // we are removing the first element
-			    first = it.next;
-			else
-			    prev.next = it.next;
-			return it.getValue();
-		    }
-		else
-		    {
-			prev = it;
-			it = it.next;
-		    }
-	    }
-	return null;
-    }
-    
-    /**
-     * return the value which the supplied key maps to, if it maps to anything in this list,
-     * otherwise, return null
-     *
-     * @param      key       the key mapping to a value that we are looking for
-     */
-    Object getValueByKey(Object key)
-    {
-	Node entry = getEntryByKey(key);
-	return (entry == null) ? null : entry.getValue();
-    }
-
-    /**
-     * return the Map.Entry which the supplied key is a part of, if such a Map.Entry exists,
-     * null otherwise
-     *
-     * this method is important for HashMap, which can hold null values and the null key
-     *
-     * @param      key         the key for which we are finding the corresponding Map.Entry
-     */
-    Node getEntryByKey(Object key)
-    {
-	Object oEntryKey;
-	Node it = first;
-	while (it != null)
-	    {
-		oEntryKey = it.getKey();
-		if ((oEntryKey == null) ? (key == null) : oEntryKey.equals(key))
-		    return it;
-		it = it.next;
-	    }
-	return null;
-    }
-    
-    /**
-     * return true if this list has a Map.Entry whose value equals() the supplied value
-     *
-     * @param      value         the value we are looking to match in this list
-     */
-    boolean containsValue(Object value)
-    {
-	Object oEntryValue;
-	Node it = first;
-	while (it != null)
-	    {
-		oEntryValue = it.getValue();
-		if ((oEntryValue == null) ? (value == null) : oEntryValue.equals(value))
-		    return true;
-		it = it.next;
-	    }
-	return false;
-    }
-
-    // INNSER CLASSES ----------------------------------------------------------
-    
-    /**
-     * a class represnting a node in our lightweight linked-list
-     * that we use for hash buckets;  a Node object contains a Map.Entry as its
-     * <pre>value</pre> property and a reference (possibly, even hopefully, null) 
-     * to another Node as its <pre>next</pre> property.
-     *
-     * There <i>is</i> a reason for not using a highly generic "LinkedNode" type
-     * class:  we want to eliminate runtime typechecks.
-     *
-     * @author       Jon Zeppieri
-     * @version      $Revision: 1.3 $
-     * @modified     $Id: Bucket.java,v 1.3 2000/03/15 21:59:08 rao Exp $
-     */
-    static class Node extends BasicMapEntry implements Map.Entry
-    {
-	/** a reference to the next node in the linked list */
-	Node next;
-	
-	/** non-trivial contructor -- sets the <pre>value</pre> of the Bucket upon instantiation */
-	Node(Object key, Object value)
-	{
-	    super(key, value);
-	}
-
-	
-    }
-    // EOF ------------------------------------------------------------------------
-}
diff --git a/libjava/java/util/Collections.java b/libjava/java/util/Collections.java
index af90b45..9035e670 100644
--- a/libjava/java/util/Collections.java
+++ b/libjava/java/util/Collections.java
@@ -149,10 +149,10 @@ public class Collections
     // is sequential-access.
     if (l instanceof AbstractSequentialList)
       {
-	ListIterator i = l.listIterator();
-	while (i.hasNext())
+	ListIterator itr = l.listIterator();
+    	for (int i = l.size() - 1; i >= 0; --i)
 	  {
-	    final int d = compare(key, i.next(), c);
+	    final int d = compare(key, itr.next(), c);
 	    if (d == 0)
 	      {
 		return pos;
@@ -264,10 +264,18 @@ public class Collections
   {
     Iterator i1 = source.iterator();
     ListIterator i2 = dest.listIterator();
-    while (i1.hasNext())
+
+    try
+      {
+	for (int i = source.size() - 1; i >= 0; --i)
+	  {
+	    i2.next();
+	    i2.set(i1.next());
+	  }
+      }
+    catch (NoSuchElementException x)
       {
-	i2.next();
-	i2.set(i1.next());
+	throw new IndexOutOfBoundsException("Source doesn't fit in dest.");      
       }
   }
 
@@ -305,11 +313,11 @@ public class Collections
    */
   public static void fill(List l, Object val)
   {
-    ListIterator i = l.listIterator();
-    while (i.hasNext())
+    ListIterator itr = l.listIterator();
+    for (int i = l.size() - 1; i >= 0; --i)
       {
-	i.next();
-	i.set(val);
+	itr.next();
+	itr.set(val);
       }
   }
 
@@ -326,11 +334,12 @@ public class Collections
    */
   public static Object max(Collection c)
   {
-    Iterator i = c.iterator();
-    Comparable max = (Comparable) i.next();	// throws NoSuchElementException
-    while (i.hasNext())
+    Iterator itr = c.iterator();
+    Comparable max = (Comparable) itr.next();	// throws NoSuchElementException
+    int csize = c.size();
+    for (int i = 1; i < csize; i++)
       {
-	Object o = i.next();
+	Object o = itr.next();
 	if (max.compareTo(o) < 0)
 	  {
 	    max = (Comparable) o;
@@ -352,15 +361,14 @@ public class Collections
    */
   public static Object max(Collection c, Comparator order)
   {
-    Iterator i = c.iterator();
-    Object max = i.next();	// throws NoSuchElementException
-    while (i.hasNext())
+    Iterator itr = c.iterator();
+    Object max = itr.next();	// throws NoSuchElementException
+    int csize = c.size();
+    for (int i = 1; i < csize; i++)
       {
-	Object o = i.next();
+	Object o = itr.next();
 	if (order.compare(max, o) < 0)
-	  {
-	    max = o;
-	  }
+	  max = o;
       }
     return max;
   }
@@ -378,15 +386,14 @@ public class Collections
    */
   public static Object min(Collection c)
   {
-    Iterator i = c.iterator();
-    Comparable min = (Comparable) i.next();	// throws NoSuchElementException
-    while (i.hasNext())
+    Iterator itr = c.iterator();
+    Comparable min = (Comparable) itr.next();	// throws NoSuchElementException
+    int csize = c.size();
+    for (int i = 1; i < csize; i++)
       {
-	Object o = i.next();
+	Object o = itr.next();
 	if (min.compareTo(o) > 0)
-	  {
-	    min = (Comparable) o;
-	  }
+	  min = (Comparable) o;
       }
     return min;
   }
@@ -404,15 +411,14 @@ public class Collections
    */
   public static Object min(Collection c, Comparator order)
   {
-    Iterator i = c.iterator();
-    Object min = i.next();	// throws NoSuchElementExcception
-    while (i.hasNext())
+    Iterator itr = c.iterator();
+    Object min = itr.next();	// throws NoSuchElementExcception
+    int csize = c.size();
+    for (int i = 1; i < csize; i++)
       {
-	Object o = i.next();
+	Object o = itr.next();
 	if (order.compare(min, o) > 0)
-	  {
-	    min = o;
-	  }
+	  min = o;
       }
     return min;
   }
@@ -468,12 +474,16 @@ public class Collections
   public static void reverse(List l)
   {
     ListIterator i1 = l.listIterator();
-    ListIterator i2 = l.listIterator(l.size());
-    while (i1.nextIndex() < i2.previousIndex())
+    int pos1 = 0;
+    int pos2 = l.size();
+    ListIterator i2 = l.listIterator(pos2);
+    while (pos1 < pos2)
       {
 	Object o = i1.next();
 	i1.set(i2.previous());
 	i2.set(o);
+	++pos1;
+	--pos2;
       }
   }
 
@@ -513,9 +523,24 @@ public class Collections
    */
   public static void shuffle(List l)
   {
-    shuffle(l, new Random());
+    if (defaultRandom == null)
+      {
+        synchronized (Collections.class)
+	{
+	  if (defaultRandom == null)
+            defaultRandom = new Random();
+	}
+      }
+    shuffle(l, defaultRandom);
   }
 
+  /** Cache a single Random object for use by shuffle(List). This improves
+    * performance as well as ensuring that sequential calls to shuffle() will
+    * not result in the same shuffle order occuring: the resolution of 
+    * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
+    */
+  private static Random defaultRandom = null;
+
   /**
    * Shuffle a list according to a given source of randomness. The algorithm
    * used iterates backwards over the list, swapping each element with an
@@ -541,20 +566,21 @@ public class Collections
   public static void shuffle(List l, Random r)
   {
     Object[] a = l.toArray();	// Dump l into an array
-    ListIterator i = l.listIterator(l.size());
+    int lsize = l.size();
+    ListIterator i = l.listIterator(lsize);
 
     // Iterate backwards over l
-    while (i.hasPrevious())
+    for (int pos = lsize - 1; pos >= 0; --pos)
       {
-	// Obtain a random position to swap with. nextIndex is used so that the
+	// Obtain a random position to swap with. pos + 1 is used so that the
 	// range of the random number includes the current position.
-	int swap = r.nextInt(i.nextIndex());
+	int swap = r.nextInt(pos + 1);
 
 	// Swap the swapth element of the array with the next element of the
 	// list.
 	Object o = a[swap];
-	a[swap] = a[i.previousIndex()];
-	a[i.previousIndex()] = o;
+	a[swap] = a[pos];
+	a[pos] = o;
 
 	// Set the element in the original list accordingly.
 	i.previous();
@@ -658,7 +684,7 @@ public class Collections
     {
       public Set entrySet()
       {
-	return singleton(new BasicMapEntry(key, value));
+	return singleton(new HashMap.Entry(key, value));
       }
     };
   }
diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java
index 5d50660..6e5c434 100644
--- a/libjava/java/util/HashMap.java
+++ b/libjava/java/util/HashMap.java
@@ -8,7 +8,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -32,7 +32,10 @@ import java.io.IOException;
 import java.io.Serializable;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
-import java.io.ObjectStreamField;
+
+// NOTE: This implementation is very similar to that of Hashtable. If you fix
+// a bug in here, chances are you should make a similar change to the Hashtable
+// code.
 
 /**
  * This class provides a hashtable-backed implementation of the
@@ -55,804 +58,700 @@ import java.io.ObjectStreamField;
  * does not support "Enumeration views."
  *
  * @author         Jon Zeppieri
- * @version        $Revision: 1.6 $
- * @modified       $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+ * @author         Jochen Hoenicke
+ * @author	   Bryce McKinlay
+ * @version        $Revision: 1.8 $
+ * @modified       $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $
  */
-public class HashMap extends AbstractMap 
-    implements Map, Cloneable, Serializable
+public class HashMap extends AbstractMap
+  implements Map, Cloneable, Serializable
 {
-    // STATIC (CLASS) VARIABLES ------------------------------------------
-
-    /** 
-     * the default capacity for an instance of HashMap -- I think this
-     * is low, and perhaps it shoudl be raised; Sun's documentation mildly
-     * suggests that this (11) is the correct value, though
-     */
-    private static final int DEFAULT_CAPACITY = 11;
-
-    /** the default load factor of a HashMap */
-    private static final float DEFAULT_LOAD_FACTOR = 0.75F;
-
-    /** used internally to represent the null key */
-    private static final HashMap.Null NULL_KEY = new HashMap.Null();
-
-    /** used internally to parameterize the creation of set/collection views */
-    private static final int KEYS = 0;
-
-    /** used internally to parameterize the creation of set/collection views */
-    private static final int VALUES = 1;
-
-    /** used internally to parameterize the creation of set/collection views */
-    private static final int ENTRIES = 2;
-
-    private static final long serialVersionUID = 362498820763181265L;
-
-    // INSTANCE VARIABLES -------------------------------------------------
-
-    /** the capacity of this HashMap:  denotes the size of the bucket array */
-    transient int capacity;
-
-    /** the size of this HashMap:  denotes the number of key-value pairs */
-    private transient int size;
-
-    /** the load factor of this HashMap:  used in computing the threshold 
-     * @serial
-     */
-    float loadFactor;
-
-    /* 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
-     */
-    private int threshold;
-
-    /** 
-     * this data structure contains the actual key-value mappings; a
-     * <pre>BucketList</pre> is a lightweight linked list of "Buckets",
-     * which, in turn, are linked nodes containing a key-value mapping 
-     * and a reference to the "next" Bucket in the list
-     */
-    private transient Bucket[] buckets;
-
-    /** 
-     * counts the number of modifications this HashMap has undergone; used by Iterators
-     * to know when to throw ConcurrentModificationExceptions (idea ripped-off from
-     * Stuart Ballard's AbstractList implementation) 
-     */
-    private transient int modCount;
-
-
-    // CONSTRUCTORS ---------------------------------------------------------
+  /** Default number of buckets. This is the value the JDK 1.3 uses. Some 
+    * early documentation specified this value as 101. That is incorrect. */
+  private static final int DEFAULT_CAPACITY = 11;  
+  /** The defaulty load factor; this is explicitly specified by Sun */
+  private static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
+  private static final long serialVersionUID = 362498820763181265L;
+
+  /** 
+   * 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
+   */
+  int threshold;
+
+  /** Load factor of this HashMap:  used in computing the threshold.
+   * @serial
+   */
+  float loadFactor = DEFAULT_LOAD_FACTOR;
+
+  /** 
+   * Array containing the actual key-value mappings
+   */
+  transient Entry[] buckets;
+
+  /** 
+   * counts the number of modifications this HashMap has undergone, used 
+   * by Iterators to know when to throw ConcurrentModificationExceptions.
+   */
+  transient int modCount;
+
+  /** the size of this HashMap:  denotes the number of key-value pairs */
+  transient int size;
+
+  /**
+   * Class to represent an entry in the hash table. Holds a single key-value
+   * pair.
+   */
+  static class Entry implements Map.Entry
+  {
+    Object key;
+    Object value;
+    Entry next;
     
-    /**
-     * construct a new HashMap with the default capacity and the default
-     * load factor
-     */
-    public HashMap()
+    Entry(Object key, Object value)
     {
-	init(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+      this.key = key;
+      this.value = value;
     }
 
-    /**
-     * construct a new HashMap with a specific inital capacity and load factor
-     *
-     * @param   initialCapacity     the initial capacity of this HashMap (>=0)
-     * @param   initialLoadFactor   the load factor of this HashMap 
-     *                              (a misnomer, really, since the load factor of
-     *                              a HashMap does not change)
-     * 
-     * @throws   IllegalArgumentException    if (initialCapacity < 0) ||
-     *                                          (initialLoadFactor > 1.0) ||
-     *                                          (initialLoadFactor <= 0.0)
-     */
-    public HashMap(int initialCapacity, float initialLoadFactor)
-	throws IllegalArgumentException
+    public boolean equals(Object o)
     {
-	if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1)
-	    throw new IllegalArgumentException();
-	else
-	    init(initialCapacity, initialLoadFactor);
-    }
-
-    /**
-     * construct a new HashMap with a specific inital capacity 
-     *
-     * @param   initialCapacity     the initial capacity of this HashMap (>=0)
-     *
-     * @throws   IllegalArgumentException    if (initialCapacity < 0)
-     */
-    public HashMap(int initialCapacity)	
-	throws IllegalArgumentException 
-    {
-	if (initialCapacity < 0)
-	    throw new IllegalArgumentException();
-	else
-	    init(initialCapacity, DEFAULT_LOAD_FACTOR);
-    }
-
-    /**
-     * construct a new HashMap from the given Map
-     * 
-     * every element in Map t will be put into this new HashMap
-     *
-     * @param     t        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>
-     */
-    public HashMap(Map t)
-    {
-	int mapSize = t.size() * 2;
-	init(((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
-	putAll(t);
-    }
-
-
-    // PUBLIC METHODS ---------------------------------------------------------
-
-    /** returns the number of kay-value mappings currently in this Map */
-    public int size()
-    {
-	return size;
-    }
-
-    /** returns true if there are no key-value mappings currently in this Map */
-    public boolean isEmpty()
-    {
-	return size == 0;
-    }
-
-    /** empties this HashMap of all elements */
-    public void clear()
-    {
-	size = 0;
-	modCount++;
-	buckets = new Bucket[capacity];
-    }
-
-    /** 
-     * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but
-     * its contents are not)
-     */
-    public Object clone()
-    {
-	Map.Entry entry;
-	Iterator it = entrySet().iterator();
-	HashMap clone = new HashMap(capacity, loadFactor);
-	while (it.hasNext())
-	    {
-		entry = (Map.Entry) it.next();
-		clone.internalPut(entry.getKey(), entry.getValue());
-	    }
-	return clone;
-    }
-
-    /** returns a "set view" of this HashMap's keys */
-    public Set keySet()
-    {
-	return new HashMapSet(KEYS);
-    }
-
-    /** returns a "set view" of this HashMap's entries */
-    public Set entrySet()
-    {
-	return new HashMapSet(ENTRIES);
-    }
-
-    /** returns a "collection view" (or "bag view") of this HashMap's values */
-    public Collection values()
-    {
-	return new HashMapCollection();
-    }
-
-    /** 
-     * returns true if the supplied object equals (<pre>equals()</pre>) a key
-     * in this HashMap 
-     *
-     * @param       key        the key to search for in this HashMap
-     */
-    public boolean containsKey(Object key)
-    {
-	return (internalGet(key) != null);
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry e = (Map.Entry) o;
+      return (key == null ? e.getKey() == null : key.equals(e.getKey())
+              && value == null ? e.getValue() == null : 
+	         value.equals(e.getValue()));
     }
     
-    /**
-     * returns true if this HashMap contains a value <pre>o</pre>, such that
-     * <pre>o.equals(value)</pre>.
-     *
-     * @param      value       the value to search for in this Hashtable
-     */
-    public boolean containsValue(Object value)
+    public Object getKey()
     {
-	int i;
-	Bucket list;
-
-	for (i = 0; i < capacity; i++)
-	    {
-		list = buckets[i];
-		if (list != null && list.containsValue(value))
-		    return true;
-	    }
-	return false;
+      return key;
     }
     
-    /*
-     * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
-     * if the key maps to nothing
-     *
-     * @param     key      the key for which to fetch an associated value
-     */
-    public Object get(Object key)
+    public Object getValue()
     {
-	Map.Entry oResult = internalGet(key);
-	return (oResult == null) ? null : oResult.getValue();
+      return value;
     }
-
-    /**
-     * puts the supplied value into the Map, mapped by the supplied key
-     *
-     * @param       key        the HashMap key used to locate the value
-     * @param       value      the value to be stored in the HashMap
-     */
-    public Object put(Object key, Object value)
+    
+    public int hashCode()
     {
-	return internalPut(key, value);
+      int kc = (key == null ? 0 : key.hashCode());
+      int vc = (value == null ? 0 : value.hashCode());
+      return kc ^ vc;
     }
-
-    /**
-     * 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
-     *
-     * @param    key     the key used to locate the value to remove from the HashMap
-     */
-    public Object remove(Object key)
+    
+    public Object setValue(Object newVal)
     {
-	Bucket list;
-	int index;
-	Object result = null;
-	if (size > 0)
-	    {
-		index = hash(((key == null) ? NULL_KEY : key));
-		list = buckets[index];
-		if (list != null)
-		    {
-			result = list.removeByKey(key);
-			if (result != null)
-			    {
-				size--;
-				modCount++;
-				if (list.first == null)
-				    buckets[index] = null;
-			    }
-		    }
-	    }
-	return result;
+      Object r = value;
+      value = newVal;
+      return r;
     }
-
-
-    // PRIVATE METHODS -----------------------------------------------------------
-
-    /** 
-     * puts the given key-value pair into this HashMap; a private method is used
-     * because it is called by the rehash() method as well as the put() method,
-     * and if a subclass overrides put(), then rehash would do funky things
-     * if it called put()
-     *
-     * @param       key        the HashMap key used to locate the value
-     * @param       value      the value to be stored in the HashMap
-     */
-  private Object internalPut(Object key, Object value)
+    
+    public String toString()
     {
-	HashMapEntry entry;
-	Bucket list;
-	int hashIndex;
-	Object oResult;
-	Object oRealKey = ((key == null) ? NULL_KEY : key);
-
-	entry = new HashMapEntry(oRealKey, value);
-	hashIndex = hash(oRealKey);
-	list = buckets[hashIndex];
-	if (list == null)
+      return key + "=" + value;
+    }    
+  }
+
+  /**
+   * construct a new HashMap with the default capacity (11) and the default
+   * load factor (0.75).
+   */
+  public HashMap()
+  {
+    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * construct a new HashMap from the given Map
+   * 
+   * every element in Map t will be put into this new HashMap
+   *
+   * @param     t        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>
+   */
+  public HashMap(Map m)
+  {
+    int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
+    buckets = new Entry[size];
+    threshold = (int) (size * loadFactor);
+    putAll(m);
+  }
+
+  /**
+   * construct a new HashMap with a specific inital capacity 
+   *
+   * @param   initialCapacity     the initial capacity of this HashMap (>=0)
+   *
+   * @throws   IllegalArgumentException    if (initialCapacity < 0)
+   */
+  public HashMap(int initialCapacity) throws IllegalArgumentException
+  {
+    this(initialCapacity, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * construct a new HashMap with a specific inital capacity and load factor
+   *
+   * @param   initialCapacity  the initial capacity (>=0)
+   * @param   loadFactor       the load factor
+   * 
+   * @throws   IllegalArgumentException    if (initialCapacity < 0) ||
+   *                                          (initialLoadFactor > 1.0) ||
+   *                                          (initialLoadFactor <= 0.0)
+   */
+  public HashMap(int initialCapacity, float loadFactor)
+    throws IllegalArgumentException
+  {
+    if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
+      throw new IllegalArgumentException();
+    
+    buckets = new Entry[initialCapacity];
+    this.loadFactor = loadFactor;
+    this.threshold = (int) (initialCapacity * loadFactor);
+  }
+
+  /** returns the number of kay-value mappings currently in this Map */
+  public int size()
+  {
+    return size;
+  }
+
+  /** returns true if there are no key-value mappings currently in this Map */
+  public boolean isEmpty()
+  {
+    return size == 0;
+  }
+
+  /**
+   * returns true if this HashMap contains a value <pre>o</pre>, such that
+   * <pre>o.equals(value)</pre>.
+   *
+   * @param      value       the value to search for in this Hashtable
+   */
+  public boolean containsValue(Object value)
+  {
+    for (int i = 0; i < buckets.length; i++)
+      {
+	Entry e = buckets[i];
+	while (e != null)
 	  {
-	    list = new Bucket();
-	    buckets[hashIndex] = list;
+	    if (value == null ? e.value == null : value.equals(e.value))
+	      return true;
+	    e = e.next;
+	  }
+      }
+    return false;
+  }
+
+  /** 
+   * returns true if the supplied object equals (<pre>equals()</pre>) a key
+   * in this HashMap 
+   *
+   * @param       key        the key to search for in this HashMap
+   */
+  public boolean containsKey(Object key)
+  {
+    int idx = hash(key);
+    Entry e = buckets[idx];
+    while (e != null)
+      {
+        if (key == null ? e.key == null : key.equals(e.key))
+	  return true;
+	e = e.next;
+      }
+    return false;
+  }
+
+  /**
+   * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
+   * if the key maps to nothing
+   *
+   * @param     key      the key for which to fetch an associated value
+   */
+  public Object get(Object key)
+  {
+    int idx = hash(key);
+    Entry 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
+   *
+   * @param       key        the HashMap key used to locate the value
+   * @param       value      the value to be stored in the HashMap
+   */
+  public Object put(Object key, Object value)
+  {
+    modCount++;
+    int idx = hash(key);
+    Entry e = buckets[idx];
+    Entry last = e; // Final entry in bucket's linked list, if any.
+    
+    while (e != null)
+      {
+        if (key == null ? e.key == null : key.equals(e.key))
+	  {
+	    Object r = e.value;
+	    e.value = value;
+	    return r;
 	  }
-	oResult = list.add(entry);
-	if (oResult == null)
-	    {
-	        modCount++;
-		if (size++ == threshold)
-		    rehash();
-		return null;
-	    }
 	else
-	    {
-		// SEH: if key already exists, we don't rehash & we don't update the modCount
-		// because it is not a "structural" modification
-		return oResult;
-	    }
-    }
-
-    /** 
-     * a private method, called by all of the constructors to initialize a new HashMap
-     *
-     * @param   initialCapacity     the initial capacity of this HashMap (>=0)
-     * @param   initialLoadFactor   the load factor of this HashMap 
-     *                              (a misnomer, really, since the load factor of
-     *                              a HashMap does not change)
-     */ 
-    private void init(int initialCapacity, float initialLoadFactor)
-    {
-	size = 0;
-	modCount = 0;
-	capacity = initialCapacity;
-	loadFactor = initialLoadFactor;
-	threshold = (int) ((float) capacity * loadFactor);
-	buckets = new Bucket[capacity];
-    }
-
-    /** private -- simply hashes a non-null Object to its array index */
-    private int hash(Object key)
-    {
-	return Math.abs(key.hashCode() % capacity);
-    }
-
-    /** 
-     * 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
-     */
-    private void rehash()
-    {
-	int i;
-	Bucket[] data = buckets;
-	Bucket.Node node;
-
-	modCount++;
-	capacity = (capacity * 2) + 1;
-	size = 0;
-	threshold = (int) ((float) capacity * loadFactor);
-	buckets = new Bucket[capacity];
-	for (i = 0; i < data.length; i++)
-	    {
-		if (data[i] != null)
-		    {
-			node = data[i].first;
-			while (node != null)
-			    {
-				internalPut(node.getKey(), node.getValue());
-				node = node.next;
-			    }
-		    }
-	    }
-    }
-
-    /** 
-     * a private method which does the "dirty work" (or some of it anyway) of fetching a value
-     * with a key
-     *
-     *  @param     key      the key for which to fetch an associated value
-     */    
-    private Map.Entry internalGet(Object key)
-    {
-	Bucket list;
-	if (size == 0)
-	    {
-		return null;
-	    }
+	  {
+	    last = e;
+	    e = e.next;
+	  }
+      }
+    
+    // At this point, we know we need to add a new entry.
+    if (++size > threshold)
+      {
+	rehash();
+	// Need a new hash value to suit the bigger table.
+	idx = hash(key);
+      }
+
+    e = new Entry(key, value);
+    
+    if (last != null)
+      last.next = e;
+    else
+      buckets[idx] = e;
+    
+    return null;
+  }
+
+  /**
+   * 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
+   *
+   * @param    key     the key used to locate the value to remove from the HashMap
+   */
+  public Object remove(Object key)
+  {
+    modCount++;
+    int idx = hash(key);
+    Entry e = buckets[idx];
+    Entry last = null;
+
+    while (e != null)
+      {
+        if (key == null ? e.key == null : key.equals(e.key))
+	  {
+	    if (last == null)
+	      buckets[idx] = e.next;
+	    else
+	      last.next = e.next;
+	    size--;
+	    return e.value;
+	  }
+	last = e;
+	e = e.next;
+      }
+    return null;
+  }
+
+  public void putAll(Map m)
+  {
+    int msize = m.size();
+    Iterator itr = m.entrySet().iterator();
+    
+    for (int i=0; i < msize; i++)
+      {
+        Map.Entry e = (Map.Entry) itr.next();
+	// Optimize in case the Entry is one of our own.
+	if (e instanceof Entry)
+	  {
+	    Entry entry = (Entry) e;
+	    put(entry.key, entry.value);
+	  }
 	else
-	    {
-		list = buckets[hash(((key == null) ? NULL_KEY : key))];
-		return (list == null) ? null : list.getEntryByKey(key);
-	    }
-    }
-
-    /**
-     * a private method used by inner class HashMapSet to implement its own 
-     * <pre>contains(Map.Entry)</pre> method; returns true if the supplied
-     * key / value pair is found in this HashMap (again, using <pre>equals()</pre>,
-     * rather than <pre>==</pre>)
-     *
-     * @param      entry      a Map.Entry to match against key / value pairs in 
-     *                        this HashMap
-     */
-    private boolean containsEntry(Map.Entry entry)
+	  {
+            put(e.getKey(), e.getValue());
+	  }
+      }
+  }
+  
+  public void clear()
+  {
+    modCount++;
+    for (int i=0; i < buckets.length; i++)
+      {
+        buckets[i] = null;
+      }
+    size = 0;
+  }
+
+  /** 
+   * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but
+   * its contents are not)
+   */
+  public Object clone()
+  {
+    HashMap copy = null;
+    try
+      {
+        copy = (HashMap) super.clone();
+      }
+    catch (CloneNotSupportedException x)
+      {
+      }
+    copy.buckets = new Entry[buckets.length];
+    
+    for (int i=0; i < buckets.length; i++)
+      {
+        Entry e = buckets[i];
+	Entry last = null;
+	
+	while (e != null)
+	  {
+	    if (last == null)
+	      {
+		copy.buckets[i] = new Entry(e.key, e.value);
+		last = copy.buckets[i];
+              }
+	    else		
+              {
+	        last.next = new Entry(e.key, e.value);
+		last = last.next;
+	      }
+	    e = e.next;
+	  }
+      }
+    return copy;
+  }
+
+  /** returns a "set view" of this HashMap's keys */
+  public Set keySet()
+  {
+    // Create an AbstractSet with custom implementations of those methods that 
+    // can be overriden easily and efficiently.
+    return new AbstractSet()
     {
-	Map.Entry oInternalEntry;
-	if (entry == null)
-	    {
-		return false;
-	    }
-	else
-	    {
-		oInternalEntry = internalGet(entry.getKey());
-		return (oInternalEntry != null && oInternalEntry.equals(entry));
-	    }
-    }
-
-    /**
-     * Serializes this object to the given stream.
-     * @serialdata the <i>capacity</i>(int) that is the length of the
-     * bucket array, the <i>size</i>(int) of the hash map are emitted
-     * first.  They are followed by size entries, each consisting of
-     * a key (Object) and a value (Object).
-     */
-    private void writeObject(ObjectOutputStream s) 
-      throws IOException
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new HashIterator(HashIterator.KEYS);
+      }
+            
+      public void clear()
+      {
+        HashMap.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        return HashMap.this.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);
+      }
+    };
+  }
+  
+  /** Returns a "collection view" (or "bag view") of this HashMap's values. */
+  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()
     {
-        // the fields
-        s.defaultWriteObject();
-
-	s.writeInt(capacity);
-	s.writeInt(size);
-	Iterator it = entrySet().iterator();
-	while (it.hasNext())
-	    {
-		Map.Entry oEntry = (Map.Entry) it.next();
-		s.writeObject(oEntry.getKey());
-		s.writeObject(oEntry.getValue());
-	    }
-    }
-
-    /**
-     * Deserializes this object from the given stream.
-     * @serialdata the <i>capacity</i>(int) that is the length of the
-     * bucket array, the <i>size</i>(int) of the hash map are emitted
-     * first.  They are followed by size entries, each consisting of
-     * a key (Object) and a value (Object).
-     */
-    private void readObject(ObjectInputStream s)
-      throws IOException, ClassNotFoundException
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new HashIterator(HashIterator.VALUES);
+      }
+      
+      public void clear()
+      {
+        HashMap.this.clear();
+      }
+    };
+  }
+
+  /** Returns a "set view" of this HashMap's entries. */
+  public Set entrySet()
+  {
+    // Create an AbstractSet with custom implementations of those methods that 
+    // can be overriden easily and efficiently.
+    return new AbstractSet()
     {
-      // the fields
-      s.defaultReadObject();
-
-      capacity = s.readInt();
-      int iLen = s.readInt();
-      size = 0;
-      modCount = 0;
-      buckets = new Bucket[capacity];
-
-      for (int i = 0; i < iLen; i++)
-	{
-	  Object oKey = s.readObject();
-	  Object oValue = s.readObject();
-	  internalPut(oKey, oValue);
-	}
-    }
-
-    // INNER CLASSES -------------------------------------------------------------
-    // ---------------------------------------------------------------------------
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new HashIterator(HashIterator.ENTRIES);
+      }
+            
+      public void clear()
+      {
+        HashMap.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        if (!(o instanceof Map.Entry))
+	  return false;
+	Map.Entry me = (Map.Entry) o;
+	Entry e = getEntry(me);
+	return (e != null);
+      }
+      
+      public boolean remove(Object o)
+      {
+        if (!(o instanceof Map.Entry))
+	  return false;
+	Map.Entry me = (Map.Entry) o;
+	Entry e = getEntry(me);
+	if (e != null)
+	  {
+	    HashMap.this.remove(e.key);
+	    return true;
+	  }
+	return false;
+      }
+    };
+  }
+  
+  /** Return an index in the buckets array for `key' based on its hashCode() */
+  private int hash(Object key)
+  {
+    return (key == null ? 0 : Math.abs(key.hashCode() % buckets.length));
+  }
+
+  /** Return an Entry who's key and value equal the supplied Map.Entry. 
+    * This is used by entrySet's contains() and remove() methods. They can't
+    * use contains(key) and remove(key) directly because that would result
+    * in entries with the same key but a different value being matched. */
+  private Entry getEntry(Map.Entry me)
+  {
+    int idx = hash(me.getKey());
+    Entry e = buckets[idx];
+    while (e != null)
+      {
+        if (e.equals(me))
+	  return e;
+	e = e.next;
+      }
+    return null;
+  }
+  
+  /** 
+   * 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 
+   * the new hash table.
+   */
+  private void rehash()
+  {
+    Entry[] oldBuckets = buckets;
     
-    /**
-     * an inner class providing a Set view of a HashMap; this implementation is 
-     * parameterized to view either a Set of keys or a Set of Map.Entry objects
-     *
-     * Note:  a lot of these methods are implemented by AbstractSet, and would work 
-     * just fine without any meddling, but far greater efficiency can be gained by
-     * overriding a number of them.  And so I did.
-     *
-     * @author      Jon Zeppieri
-     * @version     $Revision: 1.6 $
-     * @modified    $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
-     */
-    private class HashMapSet extends AbstractSet
-	implements Set
-    {
-	/** the type of this Set view:  KEYS or ENTRIES */
-	private int setType;
-
-	/** construct a new HashtableSet with the supplied view type */
-	HashMapSet(int type)
-	{
-	    setType = type;
-	}
-
-	/**
-	 * adding an element is unsupported; this method simply throws an exception 
-	 *
-	 * @throws       UnsupportedOperationException
-	 */
-	public boolean add(Object o) throws UnsupportedOperationException
-	{
-	    throw new UnsupportedOperationException();
-	}
-
-	/**
-	 * adding an element is unsupported; this method simply throws an exception 
-	 *
-	 * @throws       UnsupportedOperationException
-	 */
-	public boolean addAll(Collection c) throws UnsupportedOperationException
-	{
-	    throw new UnsupportedOperationException();
-	}
-
-	/**
-	 * clears the backing HashMap; this is a prime example of an overridden implementation
-	 * which is far more efficient than its superclass implementation (which uses an iterator
-	 * and is O(n) -- this is an O(1) call)
-	 */
-	public void clear()
-	{
-	    HashMap.this.clear();
-	}
-
-	/**
-	 * returns true if the supplied object is contained by this Set
-	 *
-	 * @param     o       an Object being testing to see if it is in this Set
-	 */
-	public boolean contains(Object o)
-	{
-	    if (setType == KEYS)
-		return HashMap.this.containsKey(o);
-	    else
-		return (o instanceof Map.Entry) ? HashMap.this.containsEntry((Map.Entry) o) : false;
-	}
-
-	/** 
-	 * returns true if the backing HashMap is empty (which is the only case either a KEYS
-	 * Set or an ENTRIES Set would be empty)
-	 */
-	public boolean isEmpty()
-	{
-	    return HashMap.this.isEmpty();
-	}
-
-	/**
-	 * removes the supplied Object from the Set
-	 *
-	 * @param      o       the Object to be removed
-	 */
-	public boolean remove(Object o)
-	{
-	    if (setType == KEYS)
-		return (HashMap.this.remove(o) != null);
+    int newcapacity = (buckets.length * 2) + 1;
+    threshold = (int) (newcapacity * loadFactor);
+    buckets = new Entry[newcapacity];
+    
+    for (int i = 0; i < oldBuckets.length; i++)
+      {
+	Entry e = oldBuckets[i];
+        while (e != null)
+	  {
+	    int idx = hash(e.key);
+	    Entry dest = buckets[idx];
+
+	    if (dest != null)
+	      {
+		while (dest.next != null)
+        	  dest = dest.next;
+		dest.next = e;
+	      }
 	    else
-		return (o instanceof Map.Entry) ? 
-		    (HashMap.this.remove(((Map.Entry) o).getKey()) != null) : false;
-	}
-
-	/** returns the size of this Set (always equal to the size of the backing Hashtable) */
-	public int size()
-	{
-	    return HashMap.this.size();
-	}
+	      {
+        	buckets[idx] = e;
+	      }
 
-	/** returns an Iterator over the elements of this Set */
-	public Iterator iterator()
-	{
-	    return new HashMapIterator(setType);
-	}
-    }
-    
-    /**
-     * Like the above Set view, except this one if for values, which are not
-     * guaranteed to be unique in a Map; this prvides a Bag of values
-     * in the HashMap
-     *
-     * @author       Jon Zeppieri
-     * @version      $Revision: 1.6 $
-     * @modified     $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
-     */
-    private class HashMapCollection extends AbstractCollection
-	implements Collection
+	    Entry next = e.next;
+	    e.next = null;
+	    e = next;
+	  }
+      }
+  }
+
+  /**
+   * Serializes this object to the given stream.
+   * @serialdata the <i>capacity</i>(int) that is the length of the
+   * bucket array, the <i>size</i>(int) of the hash map are emitted
+   * first.  They are followed by size entries, each consisting of
+   * a key (Object) and a value (Object).
+   */
+  private void writeObject(ObjectOutputStream s) throws IOException
+  {
+    // the threshold and loadFactor fields
+    s.defaultWriteObject();
+
+    s.writeInt(buckets.length);
+    s.writeInt(size);
+    Iterator it = entrySet().iterator();
+    while (it.hasNext())
+      {
+	Map.Entry entry = (Map.Entry) it.next();
+	s.writeObject(entry.getKey());
+	s.writeObject(entry.getValue());
+      }
+  }
+
+  /**
+   * Deserializes this object from the given stream.
+   * @serialdata the <i>capacity</i>(int) that is the length of the
+   * bucket array, the <i>size</i>(int) of the hash map are emitted
+   * first.  They are followed by size entries, each consisting of
+   * a key (Object) and a value (Object).
+   */
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    // the threshold and loadFactor fields
+    s.defaultReadObject();
+
+    int capacity = s.readInt();
+    int len = s.readInt();
+    size = 0;
+    modCount = 0;
+    buckets = new Entry[capacity];
+
+    for (int i = 0; i < len; i++)
+      {
+	Object key = s.readObject();
+	Object value = s.readObject();
+	put(key, value);
+      }
+  }
+
+  /**
+   * a class which implements the Iterator interface and is used for
+   * iterating over HashMaps;
+   * this implementation is parameterized to give a sequential view of
+   * keys, values, or entries; it also allows the removal of elements, 
+   * as per the Javasoft spec.
+   *
+   * @author       Jon Zeppieri
+   * @version      $Revision: 1.8 $
+   * @modified     $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $
+   */
+  class HashIterator implements Iterator
+  {
+    static final int KEYS = 0,
+                     VALUES = 1,
+		     ENTRIES = 2;
+		    
+    // the type of this Iterator: KEYS, VALUES, or ENTRIES.
+    int type;
+    // the number of modifications to the backing Hashtable that we know about.
+    int knownMod;
+    // The total number of elements returned by next(). Used to determine if
+    // there are more elements remaining.
+    int count;
+    // Current index in the physical hash table.
+    int idx;
+    // The last Entry returned by a next() call.
+    Entry 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.
+    Entry next;
+
+    /* construct a new HashtableIterator with the supllied type: 
+       KEYS, VALUES, or ENTRIES */
+    HashIterator(int type)
     {
-	/** a trivial contructor for HashMapCollection */
-	HashMapCollection()
-	{
-	}
-
-	/** 
-	 * adding elements is not supported by this Collection;
-	 * this method merely throws an exception
-	 *
-	 * @throws     UnsupportedOperationException
-	 */
-	public boolean add(Object o) throws UnsupportedOperationException
-	{
-	    throw new UnsupportedOperationException();
-	}
-
-	/** 
-	 * adding elements is not supported by this Collection;
-	 * this method merely throws an exception
-	 *
-	 * @throws     UnsupportedOperationException
-	 */
-	public boolean addAll(Collection c) throws UnsupportedOperationException
-	{
-	    throw new UnsupportedOperationException();
-	}
-
-	/** removes all elements from this Collection (and from the backing HashMap) */
-	public void clear()
-	{
-	    HashMap.this.clear();
-	}
-
-	/** 
-	 * returns true if this Collection contains at least one Object which equals() the
-	 * supplied Object
-	 *
-	 * @param         o        the Object to compare against those in the Set
-	 */
-	public boolean contains(Object o)
-	{
-	    return HashMap.this.containsValue(o);
-	}
-
-	/** returns true IFF the Collection has no elements */
-	public boolean isEmpty()
-	{
-	    return HashMap.this.isEmpty();
-	}
-
-	/** returns the size of this Collection */
-	public int size()
-	{
-	    return HashMap.this.size();
-	}
-
-	/** returns an Iterator over the elements in this Collection */
-	public Iterator iterator()
-	{
-	    return new HashMapIterator(VALUES);
-	}
+      this.type = type;
+      knownMod = HashMap.this.modCount;
+      count = 0;
+      idx = buckets.length;
     }
 
-    /**
-     * a class which implements the Iterator interface and is used for
-     * iterating over HashMaps;
-     * this implementation is parameterized to give a sequential view of
-     * keys, values, or entries; it also allows the removal of elements, 
-     * as per the Javasoft spec.
-     *
-     * @author       Jon Zeppieri
-     * @version      $Revision: 1.6 $
-     * @modified     $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
-     */
-    class HashMapIterator implements Iterator
+    /** returns true if the Iterator has more elements */
+    public boolean hasNext()
     {
-	/** the type of this Iterator: KEYS, VALUES, or ENTRIES */
-	private int myType;
-	/** 
-	 * the number of modifications to the backing Hashtable for which
-	 * this Iterator can account (idea ripped off from Stuart Ballard)
-	 */
-	private int knownMods;
-	/** the location of our sequential "cursor" */
-	private int position;
-	/** the current index of the BucketList array */
-	private int bucketIndex;
-	/** a reference, originally null, to the specific Bucket our "cursor" is pointing to */
-	private Bucket.Node currentNode;
-	/** a reference to the current key -- used fro removing elements via the Iterator */
-	private Object currentKey;
-
-	/** construct a new HashtableIterator with the supllied type: KEYS, VALUES, or ENTRIES */
-	HashMapIterator(int type)
-	{
-	    myType = type;
-	    knownMods = HashMap.this.modCount;
-	    position = 0;
-	    bucketIndex = -1;
-	    currentNode = null;
-	    currentKey = null;
-	}
-
-	/** 
-	 * Stuart Ballard's code:  if the backing HashMap has been altered through anything 
-	 * but <i>this</i> Iterator's <pre>remove()</pre> method, we will give up right here,
-	 * rather than risking undefined behavior
-	 *
-	 * @throws    ConcurrentModificationException
-	 */
-	private void checkMod() 
-	{
-	    if (knownMods != HashMap.this.modCount)
-		throw new ConcurrentModificationException();
-	}
-
-	/** returns true if the Iterator has more elements */
-	public boolean hasNext()
-	{
-	    checkMod();
-	    return position < HashMap.this.size();
-	}
-
-	/** returns the next element in the Iterator's sequential view */
-	public Object next()
-	{
-	    Bucket list = null;
-	    Object result;
-	    checkMod();	    
-	    try
-		{
-		    while (currentNode == null)
-			{
-			    while (list == null)
-				list = HashMap.this.buckets[++bucketIndex];
-			    currentNode = list.first;
-			}
-		    currentKey = currentNode.getKey();
-		    result = (myType == KEYS) ? currentKey : 
-			((myType == VALUES) ? currentNode.getValue() : currentNode);
-		    currentNode = currentNode.next;
-		}
-	    catch(Exception e)
-		{
-		    throw new NoSuchElementException();
-		}
-	    position++;
-	    return result;
-	}
-
-	/** 
-	 * removes from the backing HashMap the last element which was fetched with the
-	 * <pre>next()</pre> method
-	 */
-	public void remove()
-	{
-	    checkMod();
-	    if (currentKey == null)
-		{
-		    throw new IllegalStateException();
-		}
-	    else
-		{
-		    HashMap.this.remove(currentKey);
-		    knownMods++;
-		    position--;
-		    currentKey = null;
-		}
-	}
+      if (knownMod != HashMap.this.modCount)
+	throw new ConcurrentModificationException();
+      return count < size;
     }
 
-    /**
-     * a singleton instance of this class (HashMap.NULL_KEY)
-     * is used to represent the null key in HashMap objects
-     *
-     * @author     Jon Zeppieri
-     * @version    $Revision: 1.6 $
-     * @modified   $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
-     */
-    private static class Null
+    /** returns the next element in the Iterator's sequential view */
+    public Object next()
     {
-	/** trivial constructor */
-	Null()
-	{
+      if (knownMod != HashMap.this.modCount)
+	throw new ConcurrentModificationException();
+      if (count == size)
+        throw new NoSuchElementException();
+      count++;
+      Entry e = null;
+      if (next != null)
+        e = next;
+
+      while (e == null)
+        {
+	  e = buckets[--idx];
 	}
+
+      next = e.next;
+      last = e;
+      if (type == VALUES)
+        return e.value;
+      else if (type == KEYS)
+        return e.key;
+      return e;
     }
 
-    /**
-     * a HashMap version of Map.Entry -- one thing in this implementation is
-     * HashMap-specific:  if the key is HashMap.NULL_KEY, getKey() will return
-     * null
-     *
-     * Simply, a key / value pair
-     *
-     * @author      Jon Zeppieri
-     * @version     $Revision: 1.6 $
-     * @modified    $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+    /** 
+     * removes from the backing HashMap the last element which was fetched with the
+     * <pre>next()</pre> method
      */
-    private static class HashMapEntry extends Bucket.Node implements Map.Entry
+    public void remove()
     {
-	/** construct a new HashMapEntry with the given key and value */
-	public HashMapEntry(Object key, Object value)
+      if (knownMod != HashMap.this.modCount)
+	throw new ConcurrentModificationException();
+      if (last == null)
 	{
-	    super(key, value);
+	  throw new IllegalStateException();
 	}
-
-	/**
-	 * if the key == HashMap.NULL_KEY, null is returned, otherwise the actual
-	 * key is returned
-	 */
-	public Object getKey()
+      else
 	{
-	    Object oResult = super.getKey();
-	    return (oResult == HashMap.NULL_KEY) ? null : oResult;
+	  HashMap.this.remove(last.key);
+	  knownMod++;
+	  count--;
+	  last = null;
 	}
     }
-    // EOF -----------------------------------------------------------------------
+  }
 }
diff --git a/libjava/java/util/HashSet.java b/libjava/java/util/HashSet.java
new file mode 100644
index 0000000..f7cb326
--- /dev/null
+++ b/libjava/java/util/HashSet.java
@@ -0,0 +1,221 @@
+/* HashSet.java -- a class providing a HashMap-backet Set
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+
+/**
+ * This class provides a HashMap-backed implementation of the 
+ * Set interface.
+ *
+ * Each element in the Set is a key in the backing HashMap; each key
+ * maps to a static token, denoting that the key does, in fact, exist.
+ *
+ * Most operations are O(1), assuming no hash collisions.  In the worst
+ * case (where all hases collide), operations are O(n).
+ *
+ * HashSet is a part of the JDK1.2 Collections API.
+ *
+ * @author      Jon Zeppieri
+ * @version     $Revision: 1.5 $
+ * @modified    $Id: HashSet.java,v 1.5 2000/10/26 10:19:00 bryce Exp $
+ */
+public class HashSet extends AbstractSet
+  implements Set, Cloneable, Serializable
+{
+  /** the HashMap which backs this Set */
+  transient HashMap map;
+  static final long serialVersionUID = -5024744406713321676L;
+
+  /**
+   * construct a new, empty HashSet whose backing HashMap has the default 
+   * capacity and loadFacor
+   */
+  public HashSet()
+  {
+    map = new HashMap();
+  }
+
+  /**
+   * construct a new, empty HashSet whose backing HashMap has the supplied
+   * capacity and the default load factor
+   *
+   * @param          initialCapacity          the initial capacity of the backing
+   *                                          HashMap
+   */
+  public HashSet(int initialCapacity)
+  {
+    map = new HashMap(initialCapacity);
+  }
+
+  /**
+   * construct a new, empty HashSet whose backing HashMap has the supplied
+   * capacity and load factor
+   *
+   * @param          initialCapacity          the initial capacity of the backing
+   *                                          HashMap
+   * @param          loadFactor               the load factor of the backing HashMap
+   */
+  public HashSet(int initialCapacity, float loadFactor)
+  {
+    map = new HashMap(initialCapacity, loadFactor);
+  }
+
+  /**
+   * construct a new HashSet with the same elements as are in the supplied
+   * collection (eliminating any duplicates, of course; the backing HashMap
+   * will have the default capacity and load factor
+   *
+   * @param          c          a collection containing the elements with
+   *                            which this set will be initialized
+   */
+  public HashSet(Collection c)
+  {
+    map = new HashMap();
+    addAll(c);
+  }
+
+  /**
+   * adds the given Object to the set if it is not already in the Set,
+   * returns true if teh element was added, false otherwise
+   *
+   * @param       o       the Object to add to this Set
+   */
+  public boolean add(Object o)
+  {
+    return (map.put(o, Boolean.TRUE) == null);
+  }
+
+  /**
+   * empties this Set of all elements; this is a fast operation [O(1)]
+   */
+  public void clear()
+  {
+    map.clear();
+  }
+
+  /**
+   * returns a shallow copy of this Set (the Set itself is cloned; its 
+   * elements are not)
+   */
+  public Object clone()
+  {
+    HashSet copy = null;
+    try
+      {
+	copy = (HashSet) super.clone();
+	copy.map = (HashMap) map.clone();
+      }
+    catch (CloneNotSupportedException ex)
+      {
+      }
+
+    return copy;
+  }
+
+  /**
+   * returns true if the supplied element is in this Set, false otherwise
+   *
+   * @param        o         the Object whose presence in this Set we are testing for
+   */
+  public boolean contains(Object o)
+  {
+    return map.containsKey(o);
+  }
+
+  /** 
+   * returns true if this set has no elements in it (size() == 0)
+   */
+  public boolean isEmpty()
+  {
+    return map.isEmpty();
+  }
+
+  /**
+   * returns an Iterator over the elements of this Set; the Iterator allows
+   * removal of elements
+   */
+  public Iterator iterator()
+  {
+    return map.keySet().iterator();
+  }
+
+  /**
+   * removes the supplied Object from this Set if it is in the Set; returns
+   * true if an element was removed, false otherwise
+   */
+  public boolean remove(Object o)
+  {
+    return (map.remove(o) != null);
+  }
+
+  /**
+   * returns the number of elements in this Set
+   */
+  public int size()
+  {
+    return map.size();
+  }
+
+  /** Serialize this Object in a manner which is binary-compatible with the 
+    * JDK */
+  private void writeObject(ObjectOutputStream s) throws IOException
+  {
+    Iterator it = iterator();
+    s.writeInt(map.buckets.length);
+    s.writeFloat(map.loadFactor);
+    s.writeInt(map.size);
+    while (it.hasNext())
+      s.writeObject(it.next());
+  }
+
+  /** Deserialize this Object in a manner which is binary-compatible with 
+    * the JDK */
+  private void readObject(ObjectInputStream s) throws IOException,
+    ClassNotFoundException
+  {
+    int i, size, capacity;
+    float loadFactor;
+    Object element;
+
+    capacity = s.readInt();
+    loadFactor = s.readFloat();
+    size = s.readInt();
+
+    map = new HashMap(capacity, loadFactor);
+
+    for (i = 0; i < size; i++)
+      {
+	element = s.readObject();
+	map.put(element, Boolean.TRUE);
+      }
+  }
+}
diff --git a/libjava/java/util/Hashtable.java b/libjava/java/util/Hashtable.java
index 2767b5b..92fa48f 100644
--- a/libjava/java/util/Hashtable.java
+++ b/libjava/java/util/Hashtable.java
@@ -25,14 +25,16 @@ resulting executable to be covered by the GNU General Public License.
 This exception does not however invalidate any other reasons why the
 executable file might be covered by the GNU General Public License. */
 
-
 package java.util;
 
 import java.io.IOException;
 import java.io.Serializable;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
-import java.io.ObjectStreamField;
+
+// NOTE: This implementation is very similar to that of HashMap. If you fix
+// a bug in here, chances are you should make a similar change to the HashMap
+// code.
 
 /**
  * a class which implements a Hashtable data structure
@@ -57,96 +59,97 @@ import java.io.ObjectStreamField;
  * Enumeration.  The latter can end up in an undefined state if the Hashtable
  * changes while the Enumeration is open.
  *
+ * Unlike HashMap, Hashtable does not accept `null' as a key value.
+ *
  * @author      Jon Zeppieri
- * @version     $Revision: 1.7 $
- * @modified    $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+ * @author	Warren Levy
+ * @author      Bryce McKinlay
+ * @version     $Revision: 1.6 $
+ * @modified    $Id: Hashtable.java,v 1.6 2000/08/19 18:19:42 green Exp $
  */
 public class Hashtable extends Dictionary 
   implements Map, Cloneable, Serializable
 {
-  // STATIC VARIABLES
-  // ----------------
-  
-  /**
-   * the default capacity of a Hashtable
-   *
-   * This value strikes me as absurdly low, an invitation to all manner of
-   * hash collisions.  Perhaps it should be raised.  I set it to 11 since the
-   * JDK-1.2b4 specification uses that value in the third constructor 
-   * Hashtable(Map t) if the given Map is small. */
-  private static final int DEFAULT_CAPACITY = 11;
-  
-  /** the defaulty load factor; this is explicitly specified by Sun */
-  private static final float DEFAULT_LOAD_FACTOR = 0.75F;
-  
-  // used internally for parameterizing inner classes
-  private static final int KEYS = 0;
-  private static final int VALUES = 1;
-  private static final int ENTRIES = 2; 
-  
-  // used for serializing instances of this class
-  private static final ObjectStreamField[] serialPersistentFields =
-  { new ObjectStreamField("loadFactor", float.class),
-    new ObjectStreamField("threshold", int.class) };
+  /** Default number of buckets. This is the value the JDK 1.3 uses. Some 
+    * early documentation specified this value as 101. That is incorrect. */
+  private static final int DEFAULT_CAPACITY = 11;  
+  /** The defaulty load factor; this is explicitly specified by Sun */
+  private static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
   private static final long serialVersionUID = 1421746759512286392L;
-  
-  // INSTANCE VARIABLES
-  // ------------------
-  
-  /** the capacity of this Hashtable:  denotes the size of the bucket array */
-  private int capacity;
-  
-  /** the size of this Hashtable:  denotes the number of elements currently in
-   * <pre>this</pre> */
-  private int size;
-  
-  /** the load factor of this Hashtable:  used in computing the threshold */
-  private float loadFactor;
-  
-  /* the rounded product of the capacity and the load factor; when the
-   * number of elements exceeds the threshold, the Hashtable calls
-   * <pre>rehash()</pre> */
-  private int threshold;
-  
-  /** where the data is actually stored; Bucket implements
-   * a very simple, lightweight (and hopefully fast) linked-list */
-  Bucket[] buckets;
-  
-  /** counts the number of modifications this Hashtable has undergone;
-   * used by Iterators to know when to throw
-   * ConcurrentModificationExceptions (idea ripped-off from Stuart
-   * Ballard's AbstractList implementation) */
-  int modCount;
-  
-    /**
-     * construct a new Hashtable with the default capacity and the
-     * default load factor */
+
+  /** 
+   * The rounded product of the capacity and the load factor; when the number 
+   * of elements exceeds the threshold, the Hashtable calls <pre>rehash()</pre>.
+   * @serial
+   */
+  int threshold;
+
+  /** Load factor of this Hashtable:  used in computing the threshold.
+   * @serial
+   */
+  float loadFactor = DEFAULT_LOAD_FACTOR;
+
+  /** 
+   * Array containing the actual key-value mappings
+   */
+  transient HashMap.Entry[] buckets;
+
+  /** 
+   * counts the number of modifications this Hashtable has undergone, used 
+   * by Iterators to know when to throw ConcurrentModificationExceptions. 
+   */
+  transient int modCount;
+
+  /** the size of this Hashtable:  denotes the number of key-value pairs */
+  transient int size;
+
+  /**
+   * Class to represent an entry in the hash table. Holds a single key-value
+   * pair. A Hashtable Entry is identical to a HashMap Entry, except that
+   * `null' is not allowed for keys and values. 
+   */
+  static class Entry extends HashMap.Entry
+  {
+    Entry(Object key, Object value)
+    {
+      super(key, value);
+    }
+
+    public Object setValue(Object newVal)
+    {
+      if (newVal == null)
+        throw new NullPointerException();
+      return super.setValue(newVal);
+    }
+  }
+
+  /**
+   * construct a new Hashtable with the default capacity (11) and the default
+   * load factor (0.75).
+   */
   public Hashtable()
   {
-    init (DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
   }
-  
+
   /**
-   * construct a new Hashtable with a specific inital capacity and load factor
-   *
-   * @param   initialCapacity     the initial capacity of this Hashtable (>=0)
-   * @param   initialLoadFactor   the load factor of this Hashtable 
-   *                              (a misnomer, really, since the load factor of
-   *                              a Hashtable does not change)
+   * construct a new Hashtable from the given Map
    * 
-   * @throws   IllegalArgumentException    if (initialCapacity < 0) ||
-   *                                          (initialLoadFactor > 1.0) ||
-   *                                          (initialLoadFactor <= 0.0)
+   * every element in Map t will be put into this new Hashtable
+   *
+   * @param     t        a Map whose key / value pairs will be put into
+   *                     the new Hashtable.  <b>NOTE: key / value pairs
+   *                     are not cloned in this constructor</b>
    */
-  public Hashtable(int initialCapacity, float initialLoadFactor)
-    throws IllegalArgumentException
+  public Hashtable(Map m)
   {
-    if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1)
-      throw new IllegalArgumentException();
-    else
-      init(initialCapacity, initialLoadFactor);
+    int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
+    buckets = new Entry[size];
+    threshold = (int) (size * loadFactor);
+    putAll(m);
   }
-  
+
   /**
    * construct a new Hashtable with a specific inital capacity 
    *
@@ -154,66 +157,55 @@ public class Hashtable extends Dictionary
    *
    * @throws   IllegalArgumentException    if (initialCapacity < 0)
    */
-  public Hashtable(int initialCapacity)	
-    throws IllegalArgumentException 
+  public Hashtable(int initialCapacity) throws IllegalArgumentException
   {
-    if (initialCapacity < 0)
-      throw new IllegalArgumentException();
-    else
-      init(initialCapacity, DEFAULT_LOAD_FACTOR);
+    this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }
-  
+
   /**
-   * construct a new Hashtable from the given Map
-   * 
-   * every element in Map t will be put into this new Hashtable
+   * construct a new Hashtable with a specific inital capacity and load factor
    *
-   * @param     t        a Map whose key / value pairs will be put into
-   *                     the new Hashtable.  <b>NOTE: key / value pairs
-   *                     are not cloned in this constructor</b>
+   * @param   initialCapacity  the initial capacity (>=0)
+   * @param   loadFactor       the load factor
+   * 
+   * @throws   IllegalArgumentException    if (initialCapacity < 0) ||
+   *                                          (initialLoadFactor > 1.0) ||
+   *                                          (initialLoadFactor <= 0.0)
    */
-  public Hashtable(Map t)
+  public Hashtable(int initialCapacity, float loadFactor)
+    throws IllegalArgumentException
   {
-    int mapSize = t.size() * 2;
-    init (((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY), 
-	  DEFAULT_LOAD_FACTOR);
-    putAll (t);
+    if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
+      throw new IllegalArgumentException();
+    
+    buckets = new Entry[initialCapacity];
+    this.loadFactor = loadFactor;
+    this.threshold = (int) (initialCapacity * loadFactor);
   }
-  
-  
-  /** returns the number of key / value pairs stored in this Hashtable */
-  public synchronized int size()
+
+  /** Returns the number of key-value mappings currently in this Map */
+  public int size()
   {
     return size;
   }
-  
-  /** returns true if this Hashtable is empty (size() == 0), false otherwise */
-  public synchronized boolean isEmpty()
+
+  /** returns true if there are no key-value mappings currently in this Map */
+  public boolean isEmpty()
   {
     return size == 0;
   }
-  
-  /** returns an Enumeration of the keys in this Hashtable
-   *
-   * <b>WARNING: if a Hashtable is changed while an Enumeration is
-   * iterating over it, the behavior of the Enumeration is undefined.
-   * Use keySet().iterator() if you want to be safe.</b> */
+
+  /** */
   public synchronized Enumeration keys()
   {
-    return new HashtableEnumeration(KEYS);
+    return new Enumerator(Enumerator.KEYS);
   }
   
-  /**
-   * returns an Enumeration of the values in this Hashtable
-   *
-   * <b>WARNING: if a Hashtable is changed while an Enumeration is
-   * iterating over it, the behavior of the Enumeration is undefined.
-   * Use values().ieterator() if you want to be safe.</b> */
   public synchronized Enumeration elements()
   {
-    return new HashtableEnumeration(VALUES);
+    return new Enumerator(Enumerator.VALUES);
   }
-  
+
   /**
    * returns true if this Hashtable contains a value <pre>o</pre>,
    * such that <pre>o.equals(value)</pre>.
@@ -224,325 +216,350 @@ public class Hashtable extends Dictionary
    *
    * @param     value        the value to search for in this Hashtable
    *
-   * @throws NullPointerException if <pre>value</pre> is null */
-  public boolean contains(Object value) throws NullPointerException
-  {
-    if (value == null)
-      throw new NullPointerException();
-    else
-      return containsValue(value);
-  }
-  
-  /**
-   * behaves identically to <pre>contains()</pre>, except it does not
-   * throw a NullPointerException when given a null argument (Note:
-   * Sun's implementation (JDK1.2beta4) <i>does</i> throw a
-   * NullPointerException when given a null argument, but this seems
-   * to go against the Collections Framework specifications, so I have
-   * not reproduced this behavior.  I have submitted a bug report to
-   * Sun on the mater, but have not received any response yet (26
-   * September 1998)
-   *
-   * @param value the value to search for in this Hashtable */
-  public synchronized boolean containsValue(Object value)
+   * @throws NullPointerException if <pre>value</pre> is null 
+   */
+  public synchronized boolean contains(Object value)
   {
-    int i;
-    Bucket list;
-    
-    for (i = 0; i < capacity; i++)
+    for (int i = 0; i < buckets.length; i++)
       {
-	list = buckets[i];
-	if (list != null && list.containsValue(value))
-	  return true;
+	HashMap.Entry e = buckets[i];
+	while (e != null)
+	  {
+	    if (value.equals(e.value))
+	      return true;
+	    e = e.next;
+	  }
       }
     return false;
   }
-  
+
   /**
-   * returns true if the supplied key is found in this Hashtable
-   * (strictly, if there exists a key <pre>k</pre> in the Hashtable,
-   * such that <pre>k.equals(key)</pre>)
+   * returns true if this Hashtable contains a value <pre>o</pre>, such that
+   * <pre>o.equals(value)</pre>.
    *
-   * @param key the key to search for in this Hashtable */
-  public synchronized boolean containsKey(Object key)
+   * @param      value       the value to search for in this Hashtable
+   *
+   * @throws NullPointerException if <pre>value</pre> is null 
+   */
+  public boolean containsValue(Object value)
   {
-    return (internalGet(key) != null);
+    return contains(value);
   }
-  
-  /**
-   * a private method used by inner class HashtableSet to implement
-   * its own <pre>contains(Map.Entry)</pre> method; returns true if
-   * the supplied key / value pair is found in this Hashtable (again,
-   * using <pre>equals()</pre>, rather than <pre>==</pre>)
+
+  /** 
+   * returns true if the supplied object equals (<pre>equals()</pre>) a key
+   * in this Hashtable 
    *
-   * @param      entry      a Map.Entry to match against key / value pairs in 
-   *                        this Hashtable */
-  private synchronized boolean containsEntry(Map.Entry entry)
+   * @param       key        the key to search for in this Hashtable
+   */
+  public synchronized boolean containsKey(Object key)
   {
-    Object o;
-    if (entry == null)
+    int idx = hash(key);
+    HashMap.Entry e = buckets[idx];
+    while (e != null)
       {
-	return false;
-      }
-    else
-      {
-	o = internalGet(entry.getKey());
-	return (o != null && o.equals(entry.getValue()));
+        if (key.equals(e.key))
+	  return true;
+	e = e.next;
       }
+    return false;
   }
-  
-  /*
-   * return the value in this Hashtable associated with the supplied
-   * key, or <pre>null</pre> if the key maps to nothing
+
+  /**
+   * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
+   * if the key maps to nothing
    *
-   * @param key the key for which to fetch an associated value */
+   * @param     key      the key for which to fetch an associated value
+   */
   public synchronized Object get(Object key)
   {
-    return internalGet(key);
-  }
-  
-  /** 
-   * a private method which does the "dirty work" (or some of it
-   * anyway) of fetching a value with a key
-   *
-   *  @param key the key for which to fetch an associated value */
-  private Object internalGet(Object key)
-  {
-    Bucket list;
-    if (key == null || size == 0)
+    int idx = hash(key);
+    HashMap.Entry e = buckets[idx];
+    while (e != null)
       {
-	return null;
-      }
-    else
-      {
-	list = buckets[hash(key)];
-	return (list == null) ? null : list.getValueByKey(key);
+        if (key.equals(e.key))
+	  return e.value;
+	e = e.next;
       }
+    return null;
   }
-  
-  /** 
-   * increases the size of the Hashtable and rehashes all keys to new
-   * array indices; this is called when the addition of a new value
-   * would cause size() > threshold */
-  protected void rehash()
+
+  /**
+   * puts the supplied value into the Map, mapped by the supplied key
+   *
+   * @param       key        the key used to locate the value
+   * @param       value      the value to be stored in the table
+   */
+  public synchronized Object put(Object key, Object value)
   {
-    int i;
-    Bucket[] data = buckets;
-    Bucket.Node node;
-    
     modCount++;
-    capacity = (capacity * 2) + 1;
-    size = 0;
-    threshold = (int) ((float) capacity * loadFactor);
-    buckets = new Bucket[capacity];
-    for (i = 0; i < data.length; i++)
+    int idx = hash(key);
+    HashMap.Entry e = buckets[idx];
+    HashMap.Entry last = e; // Final entry in bucket's linked list, if any.
+    
+    // Hashtable does not accept null values. This method doesn't dereference 
+    // `value' anywhere, so check for it explicitly.
+    if (value == null)
+      throw new NullPointerException();
+
+    while (e != null)
       {
-	if (data[i] != null)
+        if (key.equals(e.key))
 	  {
-	    node = data[i].first;
-	    while (node != null)
-	      {
-		internalPut(node.getKey(), node.getValue());
-		node = node.next;
-	      }
+	    Object r = e.value;
+	    e.value = value;
+	    return r;
+	  }
+	else
+	  {
+	    last = e;
+	    e = e.next;
 	  }
       }
-  }
-  
-  /**
-   * puts the supplied value into the Hashtable, mapped by the
-   * supplied key; neither the key nore the value is allowed to be
-   * <pre>null</pre>, otherwise a <pre>NullPointerException</pre> will
-   * be thrown
-   *
-   * @param       key        the Hashtable key used to locate the value
-   * @param value the value to be stored in the Hashtable */
-  public synchronized Object put(Object key, Object value) 
-    throws NullPointerException
-  {
-    if (key == null || value == null)
-      throw new NullPointerException();
-    else
-      return internalPut(key, value);
-  }
-  
-  /** 
-   * A private method with a semi-interesting history (it's at least
-   * two hours old now); orginally, this functionality was in the
-   * public <pre>put()</pre> method, but while searching (fruitlessly)
-   * on the JDC for some clarification of Javasoft's bizarre
-   * Serialization documentation, I instead came across a JDK bug
-   * which had been fixed in JDK-1.2b3.  Extending Hashtable was a
-   * pain, because <pre>put()</pre> was apparently being used
-   * internally by the class when the Hashtable was rehashed, and this
-   * was causing odd behavior for people who had overridden
-   * <pre>put()</pre> in a Hashtable subclass.  Well, I was also
-   * calling <pre>put()</pre> internally, and realized that my code
-   * would have the same problem. [No, I have never looked at the
-   * Javasoft code; it was just the easiest thing to do].  So I put
-   * the real work in a private method, and I call <i>this</i> for
-   * internal use.  Except...not all the time.  What about
-   * <pre>putAll()</pre>?  Well, it seems reasonably clear from the
-   * Collections spec that <pre>putAll()</pre> is <i>supposed</i> to
-   * call <pre>put()</pre>.  So, it still does.  Confused yet?
-   *
-   * @param       key        the Hashtable key used to locate the value
-   * @param value the value to be stored in the Hashtable */
-  private Object internalPut(Object key, Object value)
-  {
-    HashtableEntry entry;
-    Bucket list;
-    int hashIndex;
-    Object oResult;
     
-    modCount++;
-    if (size == threshold)
-      rehash();
-    entry = new HashtableEntry(key, value);
-    hashIndex = hash(key);
-    list = buckets[hashIndex];
-    if (list == null)
+    // At this point, we know we need to add a new entry.
+    if (++size > threshold)
       {
-	list = new Bucket();
-	buckets[hashIndex] = list;
-      }
-    oResult = list.add(entry);
-    if (oResult == null)
-      {
-	size++;
-	return null;
+	rehash();
+	// Need a new hash value to suit the bigger table.
+	idx = hash(key);
       }
+
+    e = new Entry(key, value);
+    
+    if (last != null)
+      last.next = e;
     else
-      {
-	return oResult;
-      }
+      buckets[idx] = e;
+    
+    return null;
   }
-  
+
   /**
-   * removes from the Hashtable and returns the value which is mapped
-   * by the supplied key; if the key maps to nothing, then the
-   * Hashtable remains unchanged, and <pre>null</pre> is returned
+   * removes from the table and returns the value which is mapped by the 
+   * supplied key; if the key maps to nothing, then the table remains 
+   * unchanged, and <pre>null</pre> is returned
    *
-   * @param key the key used to locate the value to remove from the Hashtable */
+   * @param    key     the key used to locate the value to remove
+   */
   public synchronized Object remove(Object key)
   {
-    Bucket list;
-    int index;
-    Object result = null;
-    if (key != null && size > 0)
+    modCount++;
+    int idx = hash(key);
+    HashMap.Entry e = buckets[idx];
+    HashMap.Entry last = null;
+
+    while (e != null)
       {
-	index = hash(key);
-	list = buckets[index];
-	if (list != null)
+        if (key.equals(e.key))
 	  {
-	    result = list.removeByKey(key);
-	    if (result != null)
-	      {
-		size--;
-		modCount++;
-		if (list.first == null)
-		  buckets[index] = null;
-	      }
+	    if (last == null)
+	      buckets[idx] = e.next;
+	    else
+	      last.next = e.next;
+	    size--;
+	    return e.value;
 	  }
+	last = e;
+	e = e.next;
       }
-    return result;
+    return null;
   }
-  
-  /**
-   * part of the Map interface; for each Map.Entry in t, the key/value
-   * pair is added to this Hashtable, <b>using the <pre>put()</pre>
-   * method -- this may not be you want, so be warned (see notes to
-   * <pre>internalPut()</pre>, above</b>
-   *
-   * @param t a Map whose key/value pairs will be added to this Hashtable */
-  public synchronized void putAll(Map t) throws NullPointerException
+
+  public synchronized void putAll(Map m)
   {
-    Map.Entry entry;
-    Iterator it = t.entrySet().iterator();
-    while (it.hasNext())
+    int msize = m.size();
+    Iterator itr = m.entrySet().iterator();
+    
+    for (int i=0; i < msize; i++)
       {
-	entry = (Map.Entry) it.next();
-	put(entry.getKey(), entry.getValue());
+        Map.Entry e = (Map.Entry) itr.next();
+	// Optimize in case the Entry is one of our own.
+	if (e instanceof Entry)
+	  {
+	    Entry entry = (Entry) e;
+	    put(entry.key, entry.value);
+	  }
+	else
+	  {
+            put(e.getKey(), e.getValue());
+	  }
       }
   }
   
-  
-  /** empties this Hashtable of all elements */
   public synchronized void clear()
   {
-    size = 0;
     modCount++;
-    buckets = new Bucket[capacity];
+    for (int i=0; i < buckets.length; i++)
+      {
+        buckets[i] = null;
+      }
+    size = 0;
   }
-  
+
   /** 
-   * returns a shallow clone of this Hashtable (i.e. the Hashtable
-   * itself is cloned, but its contents are not) */
+   * returns a shallow clone of this Hashtable (i.e. the Map itself is cloned, 
+   * but its contents are not)
+   */
   public synchronized Object clone()
   {
-    Map.Entry entry;
-    Iterator it = entrySet().iterator();
-    Hashtable clone = new Hashtable(capacity, loadFactor);
-    while (it.hasNext())
+    Hashtable copy = null;
+    try
+      {
+        copy = (Hashtable) super.clone();
+      }
+    catch (CloneNotSupportedException x)
+      {
+      }
+    copy.buckets = new Entry[buckets.length];
+    
+    for (int i=0; i < buckets.length; i++)
       {
-	entry = (Map.Entry) it.next();
-	clone.internalPut(entry.getKey(), entry.getValue());
+        HashMap.Entry e = buckets[i];
+	HashMap.Entry last = null;
+	
+	while (e != null)
+	  {
+	    if (last == null)
+	      {
+		copy.buckets[i] = new Entry(e.key, e.value);
+		last = copy.buckets[i];
+              }
+	    else		
+              {
+	        last.next = new Entry(e.key, e.value);
+		last = last.next;
+	      }
+	    e = e.next;
+	  }
       }
-    return clone;
+    return copy;
   }
   
-  /**
-   * returns a String representation of this Hashtable
-   *
-   * the String representation of a Hashtable is defined by Sun and
-   * looks like this:
-   * <pre>
-   * {name_1=value_1, name_2=value_2, name_3=value_3, ..., name_N=value_N}
-   * </pre>
-   * for N elements in this Hashtable */
   public synchronized String toString()
   {
-    Map.Entry entry;
-    Iterator it = entrySet().iterator();
-    StringBuffer sb = new StringBuffer("{");
-    boolean isFirst = true;
-    while (it.hasNext())
+    Iterator entries = entrySet().iterator();
+    StringBuffer r = new StringBuffer("{");
+    for (int pos = 0; pos < size; pos++)
       {
-	entry = (Map.Entry) it.next();
-	if (isFirst)
-	  isFirst = false;
-	else
-	  sb.append(", ");
-	sb.append(entry.getKey().toString()).append("=").append(entry.getValue().toString());
+        r.append(entries.next());
+	if (pos < size - 1)
+	  r.append(", ");
       }
-    sb.append("}");
-    return sb.toString();
+    r.append("}");
+    return r.toString();    
   }
-  
-  /** returns a Set of Keys in this Hashtable */
-  public synchronized Set keySet()
+
+  /** returns a "set view" of this Hashtable's keys */
+  public Set keySet()
   {
-    return new HashtableSet(KEYS);
+    // Create a synchronized AbstractSet with custom implementations of those 
+    // methods that can be overriden easily and efficiently.
+    Set r = new AbstractSet()
+    {
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new HashIterator(HashIterator.KEYS);
+      }
+            
+      public void clear()
+      {
+        Hashtable.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        return Hashtable.this.containsKey(o);
+      }
+      
+      public boolean remove(Object o)
+      {
+        return (Hashtable.this.remove(o) != null);
+      }
+    };
+
+    return Collections.synchronizedSet(r);
   }
   
-  /** 
-   * returns a Set of Map.Entry objects in this Hashtable;
-   * note, this was called <pre>entries()</pre> prior to JDK-1.2b4 */
-  public synchronized Set entrySet()
+  /** Returns a "collection view" (or "bag view") of this Hashtable's values. 
+    */
+  public Collection values()
   {
-    return new HashtableSet(ENTRIES);
+    // We don't bother overriding many of the optional methods, as doing so
+    // wouldn't provide any significant performance advantage.
+    Collection r = new AbstractCollection()
+    {
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new HashIterator(HashIterator.VALUES);
+      }
+      
+      public void clear()
+      {
+        Hashtable.this.clear();
+      }
+    };
+    
+    return Collections.synchronizedCollection(r);
   }
-  
-  // This is the pre JDK1.2b4 named method for the above
-  //     public Set entries()
-  //     {
-  // 	return entrySet();
-  //     }
-  
-  /** returns a Collection of values in this Hashtable */
-  public synchronized Collection values()
+
+  /** Returns a "set view" of this Hashtable's entries. */
+  public Set entrySet()
   {
-    return new HashtableCollection();
+    // Create an AbstractSet with custom implementations of those methods that 
+    // can be overriden easily and efficiently.
+    Set r = new AbstractSet()
+    {
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new HashIterator(HashIterator.ENTRIES);
+      }
+            
+      public void clear()
+      {
+        Hashtable.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        if (!(o instanceof Map.Entry))
+	  return false;
+	Map.Entry me = (Map.Entry) o;
+	HashMap.Entry e = getEntry(me);
+	return (e != null);
+      }
+      
+      public boolean remove(Object o)
+      {
+        if (!(o instanceof Map.Entry))
+	  return false;
+	Map.Entry me = (Map.Entry) o;
+	HashMap.Entry e = getEntry(me);
+	if (e != null)
+	  {
+	    Hashtable.this.remove(e.key);
+	    return true;
+	  }
+	return false;
+      }
+    };
+    
+    return Collections.synchronizedSet(r);
   }
   
   /** returns true if this Hashtable equals the supplied Object <pre>o</pre>;
@@ -555,522 +572,309 @@ public class Hashtable extends Dictionary
    * for each key in o.keySet(), o.get(key).equals(get(key))
    *</pre>
    */
-  public synchronized boolean equals(Object o)
+  public boolean equals(Object o)
   {
-    Map other;
-    Set keys = keySet();
-    Object currentKey;
-    Iterator it;
-    if (o instanceof Map)
+    if (o == this)
+      return true;
+    if (!(o instanceof Map))
+      return false;
+
+    Map m = (Map) o;
+    Set s = m.entrySet();
+    Iterator itr = entrySet().iterator();
+
+    if (m.size() != size)
+      return false;
+
+    for (int pos = 0; pos < size; pos++)
       {
-	other = (Map) o;
-	if (other.keySet().equals(keys))
-	  {
-	    it = keys.iterator();
-	    while (it.hasNext())
-	      {
-		currentKey = it.next();
-		if (!get(currentKey).equals(other.get(currentKey)))
-		  return false;
-	      }
-	    return true;
-	  }
+	if (!s.contains(itr.next()))
+	  return false;
       }
-    return false;
+    return true;    
   }
   
   /** a Map's hashCode is the sum of the hashCodes of all of its
       Map.Entry objects */
-  public synchronized int hashCode()
+  public int hashCode()
   {
-    Iterator it = entrySet().iterator();
-    int result = 0;
-    while (it.hasNext())
-      result += it.next().hashCode();
-    return result;
-  }
-  
-  /** 
-   * a private method, called by all of the constructors to initialize a new Hashtable
-   *
-   * @param   initialCapacity     the initial capacity of this Hashtable (>=0)
-   * @param   initialLoadFactor   the load factor of this Hashtable 
-   *                              (a misnomer, really, since the load factor of
-   *                              a Hashtable does not change)
-   */ 
-  private void init(int initialCapacity, float initialLoadFactor)
-  {
-    size = 0;
-    modCount = 0;
-    capacity = initialCapacity;
-    loadFactor = initialLoadFactor;
-    threshold = (int) ((float) capacity * loadFactor);
-    buckets = new Bucket[capacity];
+    int hashcode = 0;
+    Iterator itr = entrySet().iterator();
+    for (int pos = 0; pos < size; pos++)
+      {
+	hashcode += itr.next().hashCode();
+      }
+    return hashcode;  
   }
   
-  /** private -- simply hashes a non-null Object to its array index */
+  /** Return an index in the buckets array for `key' based on its hashCode() */
   private int hash(Object key)
   {
-    return Math.abs(key.hashCode() % capacity);
+    return Math.abs(key.hashCode() % buckets.length);
   }
-  
-  /** Serialize this Object in a manner which is binary-compatible
-      with the JDK */
-  private void writeObject(ObjectOutputStream s) throws IOException
+
+  private HashMap.Entry getEntry(Map.Entry me)
   {
-    ObjectOutputStream.PutField oFields;
-    Iterator it = entrySet().iterator();
-    Map.Entry oEntry;
-    oFields = s.putFields();
-    oFields.put("loadFactor", loadFactor);
-    oFields.put("threshold", threshold);
-    s.writeFields();
-    
-    s.writeInt(capacity);
-    s.writeInt(size);
-    while (it.hasNext())
+    int idx = hash(me.getKey());
+    HashMap.Entry e = buckets[idx];
+    while (e != null)
       {
-	oEntry = (Map.Entry) it.next();
-	s.writeObject(oEntry.getKey());
-	s.writeObject(oEntry.getValue());
+        if (e.equals(me))
+	  return e;
+	e = e.next;
       }
+    return null;
   }
   
-  /** Deserialize this Object in a manner which is binary-compatible
-      with the JDK */
-  private void readObject(ObjectInputStream s) 
-    throws IOException, ClassNotFoundException
+  /** 
+   * increases the size of the Hashtable 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 
+   * the new hash table.
+   */
+  protected void rehash()
   {
-    int i;
-    int iLen;
-    Object oKey, oValue;
-    ObjectInputStream.GetField oFields;
-    oFields = s.readFields();
-    loadFactor = oFields.get("loadFactor", DEFAULT_LOAD_FACTOR);
-    threshold = oFields.get("threshold", 
-			    (int) (DEFAULT_LOAD_FACTOR 
-				   * (float) DEFAULT_CAPACITY));
+    HashMap.Entry[] oldBuckets = buckets;
     
-    capacity = s.readInt();
-    iLen = s.readInt();
-    size = 0;
-    modCount = 0;
-    buckets = new Bucket[capacity];
+    int newcapacity = (buckets.length * 2) + 1;
+    threshold = (int) (newcapacity * loadFactor);
+    buckets = new Entry[newcapacity];
     
-    for (i = 0; i < iLen; i++)
+    for (int i = 0; i < oldBuckets.length; i++)
       {
-	oKey = s.readObject();
-	oValue = s.readObject();
-	internalPut(oKey, oValue);
+	HashMap.Entry e = oldBuckets[i];
+        while (e != null)
+	  {
+	    int idx = hash(e.key);
+	    HashMap.Entry dest = buckets[idx];
+
+	    if (dest != null)
+	      {
+		while (dest.next != null)
+        	  dest = dest.next;
+		dest.next = e;
+	      }
+	    else
+	      {
+        	buckets[idx] = e;
+	      }
+
+	    HashMap.Entry next = e.next;
+	    e.next = null;
+	    e = next;
+	  }
       }
   }
-  
+
   /**
-   * a Hashtable version of Map.Entry -- one thing in this implementation is
-   * Hashtable-specific:  a NullPointerException is thrown if someone calls
-   * <pre>setValue(null)</pre>
-   *
-   * Simply, a key / value pair
-   *
-   * @author      Jon Zeppieri
-   * @version     $Revision: 1.7 $
-   * @modified    $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+   * Serializes this object to the given stream.
+   * @serialdata the <i>capacity</i>(int) that is the length of the
+   * bucket array, the <i>size</i>(int) of the hash map are emitted
+   * first.  They are followed by size entries, each consisting of
+   * a key (Object) and a value (Object).
    */
-  private static class HashtableEntry extends Bucket.Node implements Map.Entry
-  {
-    /** construct a new HastableEntry with the given key and value */
-    public HashtableEntry(Object key, Object value)
-    {
-      super(key, value);
-    }
-    
-    /** sets the value of this Map.Entry; throws NullPointerException if 
-     * <pre>newValue</pre> is null 
-     *
-     * @throws     NullPointerException   if <pre>newValue</pre> is null 
-     */
-    public Object setValue(Object newValue)
-      throws UnsupportedOperationException, ClassCastException, 
-      IllegalArgumentException, NullPointerException
-    {
-      if (newValue == null)
-	throw new NullPointerException();
-      else
-	return super.setValue(newValue);
-    }
-  }
-  
-  
-  /**
-   * an inner class representing an Enumeration view of this
-   * Hashtable, providing sequential access to its elements; this
-   * implementation is parameterized to provide access either to the
-   * keys or to the values in the Hashtable
-   *
-   * @author       Jon Zeppieri
-   * @version      $Revision: 1.7 $
-   * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ */
-  private class HashtableEnumeration implements Enumeration
-  {
-    /** the type of Enumeration:  KEYS or VALUES */
-    private int myType;
-    /** where are we in our iteration over the elements of this Hashtable */
-    private int position;
-    /** our current index into the BucketList array */
-    private int bucketIndex;
-    /** a reference to the specific Bucket at which our "cursor" is positioned */
-    private Bucket.Node currentNode;
-    
-    /**
-     * construct a new HashtableEnumeration with the given type of view
-     *
-     * @param      type        KEYS or VALUES:  the type of view this Enumeration is
-     *                         providing
-     */
-    HashtableEnumeration(int type)
-    {
-      myType = type;
-      position = 0;
-      bucketIndex = -1;
-      currentNode = null;
-    }
-    
-    /**
-     * returns true if not all elements have been retrived from the Enuemration
-     *
-     * <b>NOTE: modifications to the backing Hashtable while iterating
-     * through an Enumeration can result in undefined behavior, as the
-     * cursor may no longer be appropriately positioned</b> */
-	public boolean hasMoreElements()
-    {
-      return position < Hashtable.this.size();
-    }
-    
-    /**
-     * returns the next element from the Enuemration
-     *
-     * <b>NOTE: modifications to the backing Hashtable while iterating
-     * through an Enumeration can result in undefined behavior, as the
-     * cursor may no longer be appropriately positioned</b>
-     *
-     * @throws    NoSuchElementException     if there are no more elements left in
-     *                                       the sequential view */
-    public Object nextElement()
-    {
-      Bucket list = null;
-      Object result;
-      try
-	{
-	  while (currentNode == null)
-	    {
-	      while (list == null)
-		list = Hashtable.this.buckets[++bucketIndex];
-	      currentNode = list.first;
-	    }
-	  result = (myType == KEYS) ? currentNode.getKey() : 
-	    currentNode.getValue();
-	  currentNode = currentNode.next;
-	}
-      catch(Exception e)
-	{
-	  throw new NoSuchElementException();
-	}
-      position++;
-      return result;
-    }
-  }
-  
-  /**
-   * an inner class providing a Set view of a Hashtable; this
-   * implementation is parameterized to view either a Set of keys or a
-   * Set of Map.Entry objects
-   *
-   * Note: a lot of these methods are implemented by AbstractSet, and
-   * would work just fine without any meddling, but far greater
-   * efficiency can be gained by overriding a number of them.  And so
-   * I did.
-   *
-   * @author      Jon Zeppieri
-   * @version     $Revision: 1.7 $
-   * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ */
-  private class HashtableSet extends AbstractSet
+  private void writeObject(ObjectOutputStream s) throws IOException
   {
-    /** the type of this Set view:  KEYS or ENTRIES */
-    private int setType;
-    
-    /** construct a new HashtableSet with the supplied view type */
-    HashtableSet(int type)
-    {
-      setType = type;
-    }
-    
-    /**
-     * adding an element is unsupported; this method simply throws an
-     * exception
-     *
-     * @throws UnsupportedOperationException */
-    public boolean add(Object o) throws UnsupportedOperationException
-    {
-      throw new UnsupportedOperationException();
-    }
-    
-    /**
-     * adding an element is unsupported; this method simply throws an
-     * exception
-     *
-     * @throws UnsupportedOperationException */
-    public boolean addAll(Collection c) throws UnsupportedOperationException
-    {
-      throw new UnsupportedOperationException();
-    }
-    
-    /**
-     * clears the backing Hashtable; this is a prime example of an
-     * overridden implementation which is far more efficient than its
-     * superclass implementation (which uses an iterator and is O(n)
-     * -- this is an O(1) call) */
-    public void clear()
-    {
-      Hashtable.this.clear();
-    }
-    
-    /**
-     * returns true if the supplied object is contained by this Set
-     *
-     * @param     o       an Object being testing to see if it is in this Set
-     */
-    public boolean contains(Object o)
-    {
-      if (setType == KEYS)
-	return Hashtable.this.containsKey(o);
-      else
-	return (o instanceof Map.Entry) ? Hashtable.this.containsEntry((Map.Entry) o) : false;
-    }
-    
-    /** 
-     * returns true if the backing Hashtable is empty (which is the
-     * only case either a KEYS Set or an ENTRIES Set would be empty) */
-    public boolean isEmpty()
-    {
-      return Hashtable.this.isEmpty();
-    }
-    
-    /**
-     * removes the supplied Object from the Set
-     *
-     * @param      o       the Object to be removed
-     */
-    public boolean remove(Object o)
-    {
-      if (setType == KEYS)
-	return (Hashtable.this.remove(o) != null);
-      else
-	return (o instanceof Map.Entry) ? 
-	  (Hashtable.this.remove(((Map.Entry) o).getKey()) != null) : false;
-    }
-    
-    /** returns the size of this Set (always equal to the size of the
-        backing Hashtable) */
-    public int size()
-    {
-      return Hashtable.this.size();
-    }
-    
-    /** returns an Iterator over the elements of this Set */
-    public Iterator iterator()
-    {
-      return new HashtableIterator(setType);
-    }
+    // the threshold and loadFactor fields
+    s.defaultWriteObject();
+
+    s.writeInt(buckets.length);
+    s.writeInt(size);
+    Iterator it = entrySet().iterator();
+    while (it.hasNext())
+      {
+	Map.Entry entry = (Map.Entry) it.next();
+	s.writeObject(entry.getKey());
+	s.writeObject(entry.getValue());
+      }
   }
-  
+
   /**
-   * Like the above Set view, except this one if for values, which are not
-   * guaranteed to be unique in a Hashtable; this prvides a Bag of values
-   * in the Hashtable
-   *
-   * @author       Jon Zeppieri
-   * @version      $Revision: 1.7 $
-   * @modified     $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+   * Deserializes this object from the given stream.
+   * @serialdata the <i>capacity</i>(int) that is the length of the
+   * bucket array, the <i>size</i>(int) of the hash map are emitted
+   * first.  They are followed by size entries, each consisting of
+   * a key (Object) and a value (Object).
    */
-  private class HashtableCollection extends AbstractCollection
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
   {
-    /** a trivial contructor for HashtableCollection */
-    HashtableCollection()
-    {
-    }
-    
-    /** 
-     * adding elements is not supported by this Collection;
-     * this method merely throws an exception
-     *
-     * @throws     UnsupportedOperationException
-     */
-    public boolean add(Object o) throws UnsupportedOperationException
-    {
-      throw new UnsupportedOperationException();
-    }
-    
-    /** 
-     * adding elements is not supported by this Collection;
-     * this method merely throws an exception
-     *
-     * @throws     UnsupportedOperationException
-     */
-    public boolean addAll(Collection c) throws UnsupportedOperationException
-    {
-      throw new UnsupportedOperationException();
-    }
-    
-    /** removes all elements from this Set (and from the backing Hashtable) */
-    public void clear()
-    {
-      Hashtable.this.clear();
-    }
-    
-    /** 
-     * returns true if this Collection contains at least one Object which equals() the
-     * supplied Object
-     *
-     * @param         o        the Object to compare against those in the Set
-     */
-    public boolean contains(Object o)
-    {
-      return Hashtable.this.containsValue(o);
-    }
-    
-    /** returns true IFF the Collection has no elements */
-    public boolean isEmpty()
-    {
-      return Hashtable.this.isEmpty();
-    }
-    
-    /** returns the size of this Collection */
-    public int size()
-    {
-      return Hashtable.this.size();
-    }
-    
-    /** returns an Iterator over the elements in this Collection */
-    public Iterator iterator()
-    {
-      return new HashtableIterator(VALUES);
-    }
+    // the threshold and loadFactor fields
+    s.defaultReadObject();
+
+    int capacity = s.readInt();
+    int len = s.readInt();
+    size = 0;
+    modCount = 0;
+    buckets = new Entry[capacity];
+
+    for (int i = 0; i < len; i++)
+      {
+	Object key = s.readObject();
+	Object value = s.readObject();
+	put(key, value);
+      }
   }
-  
+
   /**
-   * Hashtable's version of the JDK-1.2 counterpart to the Enumeration;
+   * a class which implements the Iterator interface and is used for
+   * iterating over Hashtables;
    * this implementation is parameterized to give a sequential view of
    * keys, values, or entries; it also allows the removal of elements, 
    * as per the Javasoft spec.
    *
    * @author       Jon Zeppieri
-   * @version      $Revision: 1.7 $
-   * @modified     $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $
+   * @version      $Revision: 1.8 $
+   * @modified     $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $
    */
-  class HashtableIterator implements Iterator
-  {
-    /** the type of this Iterator: KEYS, VALUES, or ENTRIES */
-    private int myType;
-    /** 
-     * the number of modifications to the backing Hashtable for which
-     * this Iterator can account (idea ripped off from Stuart Ballard)
-     */
-    private int knownMods;
-    /** the location of our sequential "cursor" */
-    private int position;
-    /** the current index of the BucketList array */
-    private int bucketIndex;
-    /** a reference, originally null, to the specific Bucket our
-        "cursor" is pointing to */
-    private Bucket.Node currentNode;
-    /** a reference to the current key -- used fro removing elements
-        via the Iterator */
-    private Object currentKey;
-    
-    /** construct a new HashtableIterator with the supllied type:
-        KEYS, VALUES, or ENTRIES */
-    HashtableIterator(int type)
-    {
-      myType = type;
-      knownMods = Hashtable.this.modCount;
-      position = 0;
-      bucketIndex = -1;
-      currentNode = null;
-      currentKey = null;
-    }
-    
-    /** 
-     * Stuart Ballard's code: if the backing Hashtable has been
-     * altered through anything but <i>this</i> Iterator's
-     * <pre>remove()</pre> method, we will give up right here, rather
-     * than risking undefined behavior
-     *
-     * @throws ConcurrentModificationException */
-    private void checkMod() 
+  class HashIterator implements Iterator
+  {
+    static final int KEYS = 0,
+                     VALUES = 1,
+		     ENTRIES = 2;
+		    
+    // The type of this Iterator: KEYS, VALUES, or ENTRIES.
+    int type;
+    // The number of modifications to the backing Hashtable that we know about.
+    int knownMod;
+    // The total number of elements returned by next(). Used to determine if
+    // there are more elements remaining.
+    int count;
+    // Current index in the physical hash table.
+    int idx;
+    // The last Entry returned by a next() call.
+    HashMap.Entry 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.
+    HashMap.Entry next;
+
+    /* Construct a new HashIterator with the supplied type: 
+       KEYS, VALUES, or ENTRIES */
+    HashIterator(int type)
     {
-      if (knownMods != Hashtable.this.modCount)
-	throw new ConcurrentModificationException();
+      this.type = type;
+      knownMod = Hashtable.this.modCount;
+      count = 0;
+      idx = buckets.length;
     }
-    
+
     /** returns true if the Iterator has more elements */
     public boolean hasNext()
     {
-      checkMod();
-      return position < Hashtable.this.size();
+      if (knownMod != Hashtable.this.modCount)
+	throw new ConcurrentModificationException();
+      return count < size;
     }
-    
-    /** returns the next element in the Iterator's sequential view */
+
+    /** Returns the next element in the Iterator's sequential view. */
     public Object next()
     {
-      Bucket list = null;
-      Object result;
-      checkMod();	    
-      try
-	{
-	  while (currentNode == null)
-	    {
-	      while (list == null)
-		list = Hashtable.this.buckets[++bucketIndex];
-	      currentNode = list.first;
-	    }
-	  currentKey = currentNode.getKey();
-	  result = (myType == KEYS) ? currentKey : 
-	    ((myType == VALUES) ? currentNode.getValue() : currentNode);
-	  currentNode = currentNode.next;
-	}
-      catch(Exception e)
-	{
-	  throw new NoSuchElementException();
+      if (knownMod != Hashtable.this.modCount)
+	throw new ConcurrentModificationException();
+      if (count == size)
+        throw new NoSuchElementException();
+      count++;
+      HashMap.Entry e = null;
+      if (next != null)
+        e = next;
+
+      while (e == null)
+        {
+	  e = buckets[--idx];
 	}
-      position++;
-      return result;
+
+      next = e.next;
+      last = e;
+      if (type == VALUES)
+        return e.value;
+      else if (type == KEYS)
+        return e.key;
+      return e;
     }
-    
+
     /** 
-     * removes from the backing Hashtable the last element which was
-     * fetched with the <pre>next()</pre> method */
+     * Removes from the backing Hashtable the last element which was fetched 
+     * with the <pre>next()</pre> method.
+     */
     public void remove()
     {
-      checkMod();
-      if (currentKey == null)
+      if (knownMod != Hashtable.this.modCount)
+	throw new ConcurrentModificationException();
+      if (last == null)
 	{
 	  throw new IllegalStateException();
 	}
       else
 	{
-	  Hashtable.this.remove(currentKey);
-	  knownMods++;
-	  position--;
-	  currentKey = null;
+	  Hashtable.this.remove(last.key);
+	  knownMod++;
+	  count--;
+	  last = null;
 	}
     }
   }
-}
-
-
 
 
+  /**
+   * Enumeration view of this Hashtable, providing sequential access to its 
+   * elements; this implementation is parameterized to provide access either 
+   * to the keys or to the values in the Hashtable.
+   *
+   * <b>NOTE: Enumeration is not safe if new elements are put in the table as
+   * this could cause a rehash and we'd completely lose our place.  Even
+   * without a rehash, it is undetermined if a new element added would
+   * appear in the enumeration.  The spec says nothing about this, but
+   * the "Java Class Libraries" book infers that modifications to the
+   * hashtable during enumeration causes indeterminate results.  Don't do it!
+   *
+   * @author       Jon Zeppieri
+   * @version      $Revision: 1.6 $
+   * @modified $Id: Hashtable.java,v 1.6 2000/08/19 18:19:42 green Exp $ */
+  class Enumerator implements Enumeration
+  {
+    static final int KEYS = 0;
+    static final int VALUES = 1;
+    
+    int type;
+    // The total number of elements returned by nextElement(). Used to 
+    // determine if there are more elements remaining.
+    int count;
+    // current index in the physical hash table.
+    int idx;
+    // the last Entry returned.
+    HashMap.Entry last;
+    
+    Enumerator(int type)
+    {
+      this.type = type;
+      this.count = 0;
+      this.idx = buckets.length;
+    }
 
+    public boolean hasMoreElements()
+    {
+      return count < Hashtable.this.size;    
+    }
 
+    public Object nextElement()
+    {
+      if (count >= size)
+        throw new NoSuchElementException();
+      count++;
+      HashMap.Entry e;
+      if (last != null)
+        e = last.next;
 
+      while (e == null)
+        {
+	  e = buckets[--idx];
+	}
 
+      last = e;
+      if (type == VALUES)
+        return e.value;
+      return e.key;
+    }
+  }  
+}
diff --git a/libjava/java/util/WeakHashMap.java b/libjava/java/util/WeakHashMap.java
new file mode 100644
index 0000000..c81ecee
--- /dev/null
+++ b/libjava/java/util/WeakHashMap.java
@@ -0,0 +1,731 @@
+/* java.util.WeakHashMap
+   Copyright (C) 1999, 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+import java.lang.ref.WeakReference;
+import java.lang.ref.ReferenceQueue;
+
+/**
+ * A weak hash map has only weak references to the key.  This means
+ * that it allows the key to be garbage collected if they are not used
+ * otherwise.  If this happens, the weak hash map will eventually
+ * remove the whole entry from this map. <br>
+ *
+ * A weak hash map makes most sense, if the keys doesn't override the
+ * <code>equals</code>-method: If there is no other reference to the
+ * key nobody can ever look up the key in this table and so the entry
+ * can be removed.  This table also works, if the <code>equals</code>
+ * method is overloaded, e.g. with Strings as keys, but you should be
+ * prepared that some entries disappear spontaneously. <br>
+ *
+ * You should also be prepared that this hash map behaves very
+ * strange: The size of this map may spontaneously shrink (even if you
+ * use a synchronized map and synchronize it); it behaves as if
+ * another thread removes entries from this table without
+ * synchronizations.  The entry set returned by <code>entrySet</code>
+ * has similar phenomenons: The size may spontaneously shrink, or an
+ * entry, that was in the set before, suddenly disappears. <br>
+ *
+ * A weak hash map is not meant for caches; use a normal map, with 
+ * soft references as values instead.  <br>
+ *
+ * The weak hash map supports null values and null keys.  Null keys
+ * are never deleted from the map (except explictly of course). 
+ * The performance of the methods are similar to that of a hash map. <br>
+ *
+ * The value object are strongly referenced by this table.  So if a
+ * value object maintains a strong reference to the key (either direct
+ * or indirect) the key will never be removed from this map.  According
+ * to Sun, this problem may be fixed in a future release.  It is not 
+ * possible to do it with the jdk 1.2 reference model, though.
+ *
+ * @since jdk1.2
+ * @author Jochen Hoenicke 
+ * @see HashMap
+ * @see WeakReference */
+public class WeakHashMap extends AbstractMap implements Map
+{
+  /** 
+   * The default capacity for an instance of HashMap.  
+   * Sun's documentation mildly suggests that this (11) is the correct
+   * value.  
+   */
+  private static final int DEFAULT_CAPACITY = 11;
+
+  /** 
+   * The default load factor of a HashMap 
+   */
+  private static final float DEFAULT_LOAD_FACTOR = 0.75F;
+
+  /**
+   * This is used instead of the key value <i>null</i>.  It is needed
+   * to distinguish between an null key and a removed key.  
+   */
+  private static final Object NULL_KEY = new Object();
+
+  /**
+   * The reference queue where our buckets (which are WeakReferences) are
+   * registered to.
+   */
+  private ReferenceQueue queue;
+
+  /**
+   * The number of entries in this hash map.
+   */
+  private int size;
+
+  /**
+   * The load factor of this WeakHashMap.  This is the maximum ratio of
+   * size versus number of buckets.  If size grows the number of buckets
+   * must grow, too.
+   */
+  private float loadFactor;
+
+  /**
+   * The rounded product of the capacity (i.e. number of buckets) and
+   * the load factor. When the number of elements exceeds the
+   * threshold, the HashMap calls <pre>rehash()</pre>.  
+   */
+  private int threshold;
+
+  /**
+   * The number of structural modifications.  This is used by
+   * iterators, to see if they should fail.  This doesn't count
+   * the silent key removals, when a weak reference is cleared
+   * by the garbage collection.  Instead the iterators must make
+   * sure to have strong references to the entries they rely on.
+   */
+  private int modCount;
+
+  /** 
+   * The entry set.  There is only one instance per hashmap, namely
+   * theEntrySet.  Note that the entry set may silently shrink, just
+   * like the WeakHashMap.
+   */
+  private class WeakEntrySet extends AbstractSet
+  {
+    /**
+     * Returns the size of this set. 
+     */
+    public int size()
+    {
+      return size;
+    }
+
+    /**
+     * Returns an iterator for all entries.
+     */
+    public Iterator iterator()
+    {
+      return new Iterator()
+      {
+	/** 
+	 * The entry that was returned by the last
+	 * <code>next()</code> call.  This is also the entry whose
+	 * bucket should be removed by the <code>remove</code> call. <br>
+	 *
+	 * It is null, if the <code>next</code> method wasn't 
+	 * called yet, or if the entry was already removed.  <br>
+	 *
+	 * Remembering this entry here will also prevent it from
+	 * being removed under us, since the entry strongly refers
+	 * to the key.
+	 */
+	WeakBucket.Entry lastEntry;
+
+	/** 
+	 * The entry that will be returned by the next
+	 * <code>next()</code> call.  It is <code>null</code> if there
+	 * is no further entry. <br>
+	 *
+	 * Remembering this entry here will also prevent it from
+	 * being removed under us, since the entry strongly refers
+	 * to the key.
+	 */
+	WeakBucket.Entry nextEntry = findNext(null);
+
+	/**
+	 * The known number of modification to the list, if it differs
+	 * from the real number, we through an exception.
+	 */
+	int knownMod = modCount;
+
+	/** 
+	 * Check the known number of modification to the number of
+	 * modifications of the table.  If it differs from the real
+	 * number, we throw an exception.
+	 * @exception ConcurrentModificationException if the number
+	 * of modifications doesn't match.
+	 */
+	private void checkMod()
+	{
+	  /* This method will get inlined */
+	  if (knownMod != modCount)
+	    throw new ConcurrentModificationException();
+	}
+
+	/**
+	 * Get a strong reference to the next entry after
+	 * lastBucket.
+	 * @param lastBucket the previous bucket, or null if we should
+	 * get the first entry.
+	 * @return the next entry.
+	 */
+	private WeakBucket.Entry findNext(WeakBucket.Entry lastEntry)
+	{
+	  int slot;
+	  WeakBucket nextBucket;
+	  if (lastEntry != null)
+	    {
+	      nextBucket = lastEntry.getBucket().next;
+	      slot = lastEntry.getBucket().slot;
+	    }
+	  else
+	    {
+	      nextBucket = buckets[0];
+	      slot = 0;
+	    }
+
+	  while (true)
+	    {
+	      while (nextBucket != null)
+		{
+		  WeakBucket.Entry entry = nextBucket.getEntry();
+		  if (entry != null)
+		    /* This is the next entry */
+		    return entry;
+
+		  /* entry was cleared, try next */
+		  nextBucket = nextBucket.next;
+		}
+
+	      slot++;
+	      if (slot == buckets.length)
+		/* No more buckets, we are through */
+		return null;
+
+	      nextBucket = buckets[slot];
+	    }
+	}
+
+
+	/**
+	 * Checks if there are more entries.
+	 * @return true, iff there are more elements.
+	 * @exception IllegalModificationException if the hash map was
+	 * modified.
+	 */
+	public boolean hasNext()
+	{
+	  cleanQueue();
+	  checkMod();
+	  return (nextEntry != null);
+	}
+
+	/**
+	 * Returns the next entry.
+	 * @return the next entry.
+	 * @exception IllegalModificationException if the hash map was
+	 * modified.
+	 * @exception NoSuchElementException if there is no entry.
+	 */
+	public Object next()
+	{
+	  cleanQueue();
+	  checkMod();
+	  if (nextEntry == null)
+	    throw new NoSuchElementException();
+	  lastEntry = nextEntry;
+	  nextEntry = findNext(lastEntry);
+	  return lastEntry;
+	}
+
+	/**
+	 * Removes the last returned entry from this set.  This will
+	 * also remove the bucket of the underlying weak hash map.
+	 * @exception IllegalModificationException if the hash map was
+	 * modified.
+	 * @exception IllegalStateException if <code>next()</code> was
+	 * never called or the element was already removed. 
+	 */
+	public void remove()
+	{
+	  cleanQueue();
+	  checkMod();
+	  if (lastEntry == null)
+	    throw new IllegalStateException();
+	  internalRemove(lastEntry.getBucket());
+	  lastEntry = null;
+	  modCount++;
+	  knownMod = modCount;
+	}
+      };
+    }
+  }
+
+  /**
+   * A bucket is a weak reference to the key, that contains a strong
+   * reference to the value, a pointer to the next bucket and its slot
+   * number. <br>
+   *
+   * It would be cleaner to have a WeakReference as field, instead of
+   * extending it, but if a weak reference get cleared, we only get
+   * the weak reference (by queue.poll) and wouldn't know where to
+   * look for this reference in the hashtable, to remove that entry.
+   *
+   * @author Jochen Hoenicke 
+   */
+  private static class WeakBucket extends WeakReference
+  {
+    /**
+     * The value of this entry.  The key is stored in the weak
+     * reference that we extend.  
+     */
+    Object value;
+
+    /**
+     * The next bucket describing another entry that uses the same
+     * slot.  
+     */
+    WeakBucket next;
+
+    /**
+     * The slot of this entry. This should be 
+     * <pre>
+     *  Math.abs(key.hashCode() % buckets.length)
+     * </pre>
+     * But since the key may be silently removed we have to remember
+     * the slot number.
+     * If this bucket was removed the slot is -1.  This marker will
+     * prevent the bucket from being removed twice.
+     */
+    int slot;
+
+    /**
+     * Creates a new bucket for the given key/value pair and the specified
+     * slot.
+     * @param key the key
+     * @param value the value
+     * @param slot the slot.  This must match the slot where this bucket
+     * will be enqueued.
+     */
+    public WeakBucket(Object key, ReferenceQueue queue, Object value,
+		      int slot)
+    {
+      super(key, queue);
+      this.value = value;
+      this.slot = slot;
+    }
+
+    /**
+     * This class gives the <code>Entry</code> representation of the 
+     * current bucket.  It also keeps a strong reference to the
+     * key; bad things may happen otherwise.
+     */
+    class Entry implements Map.Entry
+    {
+      /**
+       * The strong ref to the key.
+       */
+      Object key;
+
+      /**
+       * Creates a new entry for the key.
+       */
+      public Entry(Object key)
+      {
+	this.key = key;
+      }
+
+      /**
+       * Returns the underlying bucket.
+       */
+      public WeakBucket getBucket()
+      {
+	return WeakBucket.this;
+      }
+
+      /**
+       * Returns the key.
+       */
+      public Object getKey()
+      {
+	return key == NULL_KEY ? null : key;
+      }
+
+      /**
+       * Returns the value.
+       */
+      public Object getValue()
+      {
+	return value;
+      }
+
+      /**
+       * This changes the value.  This change takes place in 
+       * the underlying hash map.
+       */
+      public Object setValue(Object newVal)
+      {
+	Object oldVal = value;
+	value = newVal;
+	return oldVal;
+      }
+
+      /**
+       * The hashCode as specified in the Entry interface.
+       */
+      public int hashCode()
+      {
+	return (key == NULL_KEY ? 0 : key.hashCode())
+	  ^ (value == null ? 0 : value.hashCode());
+      }
+
+      /**
+       * The equals method as specified in the Entry interface.
+       */
+      public boolean equals(Object o)
+      {
+	if (o instanceof Map.Entry)
+	  {
+	    Map.Entry e = (Map.Entry) o;
+	    return (key == NULL_KEY
+		    ? e.getKey() == null : key.equals(e.getKey()))
+	      && (value == null
+		  ? e.getValue() == null : value.equals(e.getValue()));
+	  }
+	return false;
+      }
+    }
+
+    /**
+     * This returns the entry stored in this bucket, or null, if the
+     * bucket got cleared in the mean time.
+     */
+    Entry getEntry()
+    {
+      final Object key = this.get();
+      if (key == null)
+	return null;
+      return new Entry(key);
+    }
+  }
+
+  /**
+   * The entry set returned by <code>entrySet()</code>.
+   */
+  private WeakEntrySet theEntrySet;
+
+  /**
+   * The hash buckets.  This are linked lists.
+   */
+  private WeakBucket[] buckets;
+
+  /**
+   * Creates a new weak hash map with default load factor and default
+   * capacity.
+   */
+  public WeakHashMap()
+  {
+    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Creates a new weak hash map with default load factor and the given
+   * capacity.
+   * @param initialCapacity the initial capacity 
+   */
+  public WeakHashMap(int initialCapacity)
+  {
+    this(initialCapacity, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Creates a new weak hash map with the given initial capacity and
+   * load factor.  
+   * @param initialCapacity the initial capacity.
+   * @param loadFactor the load factor (see class description of HashMap).
+   */
+  public WeakHashMap(int initialCapacity, float loadFactor)
+  {
+    if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
+      throw new IllegalArgumentException();
+    this.loadFactor = loadFactor;
+    threshold = (int) (initialCapacity * loadFactor);
+    theEntrySet = new WeakEntrySet();
+    queue = new ReferenceQueue();
+    buckets = new WeakBucket[initialCapacity];
+  }
+
+  /** 
+   * simply hashes a non-null Object to its array index 
+   */
+  private int hash(Object key)
+  {
+    return Math.abs(key.hashCode() % buckets.length);
+  }
+
+  /**
+   * Cleans the reference queue.  This will poll all references (which
+   * are WeakBuckets) from the queue and remove them from this map.
+   * This will not change modCount, even if it modifies the map.  The
+   * iterators have to make sure that nothing bad happens.  <br>
+   *
+   * Currently the iterator maintains a strong reference to the key, so
+   * that is no problem.
+   */
+  private void cleanQueue()
+  {
+    Object bucket = queue.poll();
+    while (bucket != null)
+      {
+	internalRemove((WeakBucket) bucket);
+	bucket = queue.poll();
+      }
+  }
+
+  /**
+   * Rehashes this hashtable.  This will be called by the
+   * <code>add()</code> method if the size grows beyond the threshold.  
+   * It will grow the bucket size at least by factor two and allocates
+   * new buckets.
+   */
+  private void rehash()
+  {
+    WeakBucket[] oldBuckets = buckets;
+    int newsize = buckets.length * 2 + 1;	// XXX should be prime.
+    threshold = (int) (newsize * loadFactor);
+    buckets = new WeakBucket[newsize];
+
+    /* Now we have to insert the buckets again.
+     */
+    for (int i = 0; i < oldBuckets.length; i++)
+      {
+	WeakBucket bucket = oldBuckets[i];
+	WeakBucket nextBucket;
+	while (bucket != null)
+	  {
+	    nextBucket = bucket.next;
+
+	    Object key = bucket.get();
+	    if (key == null)
+	      {
+		/* This bucket should be removed; it is probably
+		 * already on the reference queue.  We don't insert it
+		 * at all, and mark it as cleared.  */
+		bucket.slot = -1;
+		size--;
+	      }
+	    else
+	      {
+		/* add this bucket to its new slot */
+		int slot = hash(key);
+		bucket.slot = slot;
+		bucket.next = buckets[slot];
+		buckets[slot] = bucket;
+	      }
+	    bucket = nextBucket;
+	  }
+      }
+  }
+
+  /**
+   * Finds the entry corresponding to key.  Since it returns an Entry
+   * it will also prevent the key from being removed under us.
+   * @param key the key. It may be null.
+   * @return The WeakBucket.Entry or null, if the key wasn't found.
+   */
+  private WeakBucket.Entry internalGet(Object key)
+  {
+    if (key == null)
+      key = NULL_KEY;
+    int slot = hash(key);
+    WeakBucket bucket = buckets[slot];
+    while (bucket != null)
+      {
+	WeakBucket.Entry entry = bucket.getEntry();
+	if (entry != null && key.equals(entry.key))
+	  return entry;
+
+	bucket = bucket.next;
+      }
+    return null;
+  }
+
+  /**
+   * Adds a new key/value pair to the hash map.
+   * @param key the key. This mustn't exists in the map. It may be null.
+   * @param value the value.
+   */
+  private void internalAdd(Object key, Object value)
+  {
+    if (key == null)
+      key = NULL_KEY;
+    int slot = hash(key);
+    WeakBucket bucket = new WeakBucket(key, queue, value, slot);
+    bucket.next = buckets[slot];
+    buckets[slot] = bucket;
+    size++;
+  }
+
+  /**
+   * Removes a bucket from this hash map, if it wasn't removed before
+   * (e.g. one time through rehashing and one time through reference queue)
+   * @param bucket the bucket to remove.  
+   */
+  private void internalRemove(WeakBucket bucket)
+  {
+    int slot = bucket.slot;
+    if (slot == -1)
+      /* this bucket was already removed. */
+      return;
+
+    /* mark the bucket as removed.  This is necessary, since the
+     * bucket may be enqueued later by the garbage collection and
+     * internalRemove, will be called a second time.  
+     */
+    bucket.slot = -1;
+    if (buckets[slot] == bucket)
+      buckets[slot] = bucket.next;
+    else
+      {
+	WeakBucket prev = buckets[slot];
+	/* This may throw a NullPointerException.  It shouldn't but if
+	 * a race condition occured (two threads removing the same
+	 * bucket at the same time) it may happen.  <br>
+	 * But with race condition many much worse things may happen
+	 * anyway.
+	 */
+	while (prev.next != bucket)
+	  prev = prev.next;
+	prev.next = bucket.next;
+      }
+    size--;
+  }
+
+  /**
+   * Returns the size of this hash map.  Note that the size() may shrink
+   * spontanously, if the some of the keys were only weakly reachable.
+   * @return the number of entries in this hash map.
+   */
+  public int size()
+  {
+    cleanQueue();
+    return size;
+  }
+
+  /**
+   * Tells if the map is empty.  Note that the result may change
+   * spontanously, if all of the keys were only weakly reachable.
+   * @return true, iff the map is empty.
+   */
+  public boolean isEmpty()
+  {
+    cleanQueue();
+    return size == 0;
+  }
+
+  /**
+   * Tells if the map contains the given key.  Note that the result
+   * may change spontanously, if all the key was only weakly
+   * reachable.  
+   * @return true, iff the map contains an entry for the given key. 
+   */
+  public boolean containsKey(Object key)
+  {
+    cleanQueue();
+    return internalGet(key) != null;
+  }
+
+  /**
+   * Gets the value the key will be mapped to.
+   * @return the value the key was mapped to.  It returns null if
+   * the key wasn't in this map, or if the mapped value was explicitly
+   * set to null.  
+   */
+  public Object get(Object key)
+  {
+    cleanQueue();
+    WeakBucket.Entry entry = internalGet(key);
+    return entry == null ? null : entry.getValue();
+  }
+
+  /**
+   * Adds a new key/value mapping to this map.
+   * @param key the key. This may be null.
+   * @param value the value. This may be null.
+   * @return the value the key was mapped to previously.  It returns
+   * null if the key wasn't in this map, or if the mapped value was
+   * explicitly set to null.  
+   */
+  public Object put(Object key, Object value)
+  {
+    cleanQueue();
+    WeakBucket.Entry entry = internalGet(key);
+    if (entry != null)
+      return entry.setValue(value);
+
+    if (size >= threshold)
+      rehash();
+
+    internalAdd(key, value);
+    modCount++;
+    return null;
+  }
+
+  /**
+   * Removes the key and the corresponding value from this map.
+   * @param key the key. This may be null.
+   * @return the value the key was mapped to previously.  It returns
+   * null if the key wasn't in this map, or if the mapped value was
+   * explicitly set to null.  */
+  public Object remove(Object key)
+  {
+    cleanQueue();
+    WeakBucket.Entry entry = internalGet(key);
+    if (entry == null)
+      {
+	return null;
+      }
+    internalRemove(entry.getBucket());
+    modCount++;
+    return entry.getValue();
+  }
+
+  /**
+   * Returns a set representation of the entries in this map.  This
+   * set will not have strong references to the keys, so they can be
+   * silently removed.  The returned set has therefore the same
+   * strange behaviour (shrinking size(), disappearing entries) as
+   * this weak hash map.  
+   * @return a set representation of the entries.  */
+  public Set entrySet()
+  {
+    cleanQueue();
+    return theEntrySet;
+  }
+}