harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r554615 - /harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
Date Mon, 09 Jul 2007 12:17:28 GMT
Author: tellison
Date: Mon Jul  9 05:17:27 2007
New Revision: 554615

URL: http://svn.apache.org/viewvc?view=rev&rev=554615
Log:
Fix for HARMONY-4064 ([classlib][luni] Performance improvement of java.util.HashMap)

Modified:
    harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java?view=diff&rev=554615&r1=554614&r2=554615
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java Mon
Jul  9 05:17:27 2007
@@ -21,7 +21,6 @@
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
-import java.math.BigInteger;
 
 /**
  * HashMap is an implementation of Map. All optional operations are supported,
@@ -192,7 +191,7 @@
                     entry = associatedMap.findNullKeyEntry();
                 } else {
                     int hash = key.hashCode();
-                    int index = (hash & 0x7FFFFFFF) % associatedMap.elementData.length;
+                    int index = hash & (associatedMap.elementData.length - 1);
                     entry = associatedMap.findNonNullKeyEntry(key, index, hash);
                 }
                 return object.equals(entry);
@@ -241,14 +240,31 @@
      */
     public HashMap(int capacity) {
         if (capacity >= 0) {
+            capacity = caculateCapacity(capacity);
             elementCount = 0;
-            elementData = newElementArray(capacity == 0 ? 1 : capacity);
+            elementData = newElementArray(capacity);
             loadFactor = 0.75f; // Default load factor of 0.75
             computeMaxSize();
         } else {
             throw new IllegalArgumentException();
         }
     }
+    
+    private static final int caculateCapacity(int x) {
+        if(x >= 1 << 30){
+            return 1 << 30;
+        }
+        if(x == 0){
+            return 16;
+        }
+        x = x -1;
+        x |= x >> 1;
+        x |= x >> 2;
+        x |= x >> 4;
+        x |= x >> 8;
+        x |= x >> 16;
+        return x + 1;
+    }
 
     /**
      * Constructs a new instance of HashMap with the specified capacity and load
@@ -346,7 +362,7 @@
             m = findNullKeyEntry();
         } else {
             int hash = key.hashCode();
-            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            int index = hash & (elementData.length - 1);
             m = findNonNullKeyEntry(key, index, hash);
         }
         return m != null;
@@ -412,7 +428,7 @@
             m = findNullKeyEntry();
         } else {
             int hash = key.hashCode();
-            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            int index = hash & (elementData.length - 1);
             m = findNonNullKeyEntry(key, index, hash);
         }
         if (m != null) {
@@ -522,13 +538,13 @@
             }
         } else {
             int hash = key.hashCode();
-            int index = (hash & 0x7FFFFFFF) % elementData.length;
+            int index = hash & (elementData.length - 1);
             entry = findNonNullKeyEntry(key, index, hash);
             if (entry == null) {
                 modCount++;
                 if (++elementCount > threshold) {
                     rehash();
-                    index = (hash & 0x7FFFFFFF) % elementData.length;
+                    index = hash & (elementData.length - 1);
                 }
                 entry = createHashedEntry(key, index, hash);
             }
@@ -580,27 +596,14 @@
         }
     }
 
-    private static final int PRIMES[] = { 7, 37, 79, 163, 331, 673, 1361, 2729,
-            5471, 10949, 21911, 43853, 87719, 175447, 350899, 701819 };
-
-    private int nextLength(int capacity) {
-        int nextNumber = capacity << 1;
-        for (int i = 0; i < PRIMES.length; i++) {
-            if (nextNumber < PRIMES[i]) {
-                return PRIMES[i];
-            }
-        }
-        // This could overflow an int, but in practice never will.
-        return BigInteger.valueOf(nextNumber).nextProbablePrime().intValue();
-    }
-
     void rehash(int capacity) {
-        int length = nextLength(capacity);
+        int length = caculateCapacity((capacity == 0 ? 1 : capacity << 1));
+
         Entry<K, V>[] newData = newElementArray(length);
         for (int i = 0; i < elementData.length; i++) {
             Entry<K, V> entry = elementData[i];
             while (entry != null) {
-                int index = (entry.origKeyHash & 0x7FFFFFFF) % length;
+                int index = entry.origKeyHash & (length - 1);
                 Entry<K, V> next = entry.next;
                 entry.next = newData[index];
                 newData[index] = entry;
@@ -638,7 +641,7 @@
         Entry<K, V> last = null;
         if (key != null) {
             int hash = key.hashCode();
-            index = (hash & 0x7FFFFFFF) % elementData.length;
+            index = hash & (elementData.length - 1);
             entry = elementData[index];
             while (entry != null && !(entry.origKeyHash == hash && key.equals(entry.key)))
{
                 last = entry;
@@ -736,8 +739,7 @@
         elementCount = stream.readInt();
         for (int i = elementCount; --i >= 0;) {
             K key = (K) stream.readObject();
-            int index = (null == key) ? 0 : (key.hashCode() & 0x7FFFFFFF)
-                    % length;
+            int index = (null == key) ? 0 : (key.hashCode() & (length - 1));
             createEntry(key, index, (V) stream.readObject());
         }
     }



Mime
View raw message