--- 4.0/IdentityHashMap.java	2005-01-30 21:08:12.000000000 +0100
+++ 4.0.new/IdentityHashMap.java	2005-01-30 21:16:21.000000000 +0100
@@ -94,8 +94,16 @@
 public class IdentityHashMap extends AbstractMap
   implements Map, Serializable, Cloneable
 {
+  /** 
+   * How many conflicting keys can be stored.  The value should be
+   * ceil(CLUSTER_SIZE*.75)+1 <= CLUSTER_SIZE.
+   * @see #hash(Object)
+   * @see #getHashCode(Object)
+   */
+  private static final int CLUSTER_SIZE = 8;
+
   /** The default capacity. */
-  private static final int DEFAULT_CAPACITY = 21;
+  private static final int DEFAULT_CAPACITY = CLUSTER_SIZE*3*2;
 
   /**
    * This object is used to mark deleted items. Package visible for use by
@@ -143,7 +151,7 @@
   private transient int threshold;
 
   /**
-   * Create a new IdentityHashMap with the default capacity (21 entries).
+   * Create a new IdentityHashMap with the default capacity (3*CLUSTER_SIZE keys).
    */
   public IdentityHashMap()
   {
@@ -163,9 +171,9 @@
   {
     if (max < 0)
       throw new IllegalArgumentException();
-    // Need at least two slots, or hash() will break.
-    if (max < 2)
-      max = 2;
+    // Need at least three clusters
+    if (max < CLUSTER_SIZE*3)
+      max = CLUSTER_SIZE*3;
     table = new Object[max << 1];
     Arrays.fill(table, emptyslot);
     threshold = (max >> 2) * 3;
@@ -180,7 +188,9 @@
    */
   public IdentityHashMap(Map m)
   {
-    this(Math.max(m.size() << 1, DEFAULT_CAPACITY));
+    // round to the next odd number of clusters
+    this((m.size()/CLUSTER_SIZE + (m.size()%CLUSTER_SIZE==0?0:1) + 
+	 (m.size()/CLUSTER_SIZE + (m.size()%CLUSTER_SIZE==0?0:1)%2)) * CLUSTER_SIZE * 2);
     putAll(m);
   }
 
@@ -491,9 +501,9 @@
     if (size > threshold)
       {
         Object[] old = table;
-        // This isn't necessarily prime, but it is an odd number of key/value
-        // slots, which has a higher probability of fewer collisions.
-        table = new Object[(old.length * 1) + 2];
+        // This isn't necessarily prime, but it is an odd number of clusters 
+        // which has a higher probability of fewer collisions.
+        table = new Object[(old.length * 2) + (2*CLUSTER_SIZE)];
         Arrays.fill(table, emptyslot);
         size = 0;
         threshold = (table.length >>> 3) * 3;
@@ -629,6 +639,17 @@
     return values;
   }
 
+  /** 
+   * Private function for the hash implementation.  
+   *
+   * <strong> If the System.identityHashCode() is changed, the
+   * getHashCode() must also be changed.</strong><p>
+   */
+  private static int getHashCode(Object key) 
+  {
+     return System.identityHashCode(key)>>>3;
+  }
+
   /**
    * Helper method which computes the hash code, then traverses the table
    * until it finds the key, or the spot where the key would go.
@@ -641,16 +662,21 @@
   // Package visible for use by nested classes.
   int hash(Object key)
   {
-    // Implementation note: it is feasible for the table to have no
-    // emptyslots, if it is full with entries and tombstones, so we must
-    // remember where we started. If we encounter the key or an emptyslot,
-    // we are done.  If we encounter a tombstone, the key may still be in
-    // the array.  If we don't encounter the key, we use the first emptyslot
-    // or tombstone we encountered as the location where the key would go.
-    // By requiring at least 2 key/value slots, and rehashing at 75%
-    // capacity, we guarantee that there will always be either an emptyslot
-    // or a tombstone somewhere in the table.
-    int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1;
+
+    /* Mappings are stored in clusters of CLUSTER_SIZE elements and the
+    * hash function spreads the keys over these clusters. To make sure
+    * that each cluster gets filled not much more than 75%, the number
+    * of clusters should be a prime or at least be an odd number.
+    *
+    * Within a cluster a linear probe is used.  Filling the last
+    * element of a cluster causes the cluster to overflow and the
+    * search expands to the following cluster until the next rehash.
+    *
+    * "tombstones" mark slots which belong to the current cluster;
+    * they can "expand" a cluster into the next one.
+    */
+    int clusters = (table.length>>1)/CLUSTER_SIZE;
+    int h = ((getHashCode(key) % clusters)*CLUSTER_SIZE)<<1;
     int del = -1;
     int save = h;