You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by te...@apache.org on 2007/02/19 17:42:52 UTC
svn commit: r509249 - in
/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util:
HashMap.java LinkedHashMap.java
Author: tellison
Date: Mon Feb 19 08:42:52 2007
New Revision: 509249
URL: http://svn.apache.org/viewvc?view=rev&rev=509249
Log:
Apply patch HARMONY-642 (Performance improvement for HashMap and LinkedHashMap classes)
Modified:
harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.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=509249&r1=509248&r2=509249
==============================================================================
--- 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 Feb 19 08:42:52 2007
@@ -47,6 +47,11 @@
Entry<K, V> next;
+ Entry(K theKey, int hash) {
+ super(theKey, null);
+ this.origKeyHash = hash;
+ }
+
Entry(K theKey, V theValue) {
super(theKey, theValue);
origKeyHash = (theKey == null ? 0 : theKey.hashCode());
@@ -180,8 +185,15 @@
@Override
public boolean contains(Object object) {
if (object instanceof Map.Entry) {
- Entry<KT, VT> entry = associatedMap
- .getEntry(((Map.Entry<?, ?>) object).getKey());
+ Object key = ((Map.Entry<?, ?>) object).getKey();
+ Entry entry;
+ if (key == null) {
+ entry = associatedMap.findNullKeyEntry();
+ } else {
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % associatedMap.elementData.length;
+ entry = associatedMap.findNonNullKeyEntry(key, index, hash);
+ }
return object.equals(entry);
}
return false;
@@ -328,29 +340,15 @@
*/
@Override
public boolean containsKey(Object key) {
- return getEntry(key) != null;
- }
-
- /**
- * Tests two keys for equality. This method just calls key.equals but can be
- * overridden.
- *
- * @param k1
- * first key to compare
- * @param k2
- * second key to compare
- * @return true if the keys are considered equal
- */
- boolean keysEqual(Object k1, Entry<K, V> entry) {
- int k1Hash = k1 == null ? 0 : k1.hashCode();
- if (k1Hash != entry.origKeyHash) {
- return false;
- }
- if (k1 == null && entry.key == null) {
- return true;
+ Entry<K, V> m;
+ if (key == null) {
+ m = findNullKeyEntry();
+ } else {
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % elementData.length;
+ m = findNonNullKeyEntry(key, index, hash);
}
- assert k1 != null;
- return k1.equals(entry.key);
+ return m != null;
}
/**
@@ -408,37 +406,32 @@
*/
@Override
public V get(Object key) {
- Entry<K, V> m = getEntry(key);
+ Entry<K, V> m;
+ if (key == null) {
+ m = findNullKeyEntry();
+ } else {
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % elementData.length;
+ m = findNonNullKeyEntry(key, index, hash);
+ }
if (m != null) {
return m.value;
}
return null;
}
- Entry<K, V> getEntry(Object key) {
- int index = getModuloHash(key);
- return findEntry(key, index);
- }
-
- int getModuloHash(Object key) {
- if (key == null) {
- return 0;
+ final Entry<K,V> findNonNullKeyEntry(Object key, int index, int keyHash) {
+ Entry<K,V> m = elementData[index];
+ while (m != null && (m.origKeyHash != keyHash || !key.equals(m.key))) {
+ m = m.next;
}
- return (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+ return m;
}
-
- Entry<K, V> findEntry(Object key, int index) {
- Entry<K, V> m;
- m = elementData[index];
- if (key != null) {
- while (m != null && !keysEqual(key, m)) {
- m = m.next;
- }
- } else {
- while (m != null && m.key != null) {
- m = m.next;
- }
- }
+
+ final Entry<K,V> findNullKeyEntry() {
+ Entry<K,V> m = elementData[0];
+ while (m != null && m.key != null)
+ m = m.next;
return m;
}
@@ -482,11 +475,8 @@
@Override
public boolean remove(Object key) {
- if (containsKey(key)) {
- HashMap.this.remove(key);
- return true;
- }
- return false;
+ Entry<K, V> entry = HashMap.this.removeEntry(key);
+ return entry != null;
}
@Override
@@ -519,18 +509,28 @@
}
private V putImpl(K key, V value) {
- int index = getModuloHash(key);
- Entry<K, V> entry = findEntry(key, index);
-
- if (entry == null) {
- modCount++;
- if (++elementCount > threshold) {
- rehash();
- index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
- % elementData.length;
+ Entry<K,V> entry;
+ if(key == null) {
+ entry = findNullKeyEntry();
+ if (entry == null) {
+ modCount++;
+ if (++elementCount > threshold) {
+ rehash();
+ }
+ entry = createHashedEntry(key, 0, 0);
+ }
+ } else {
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % elementData.length;
+ entry = findNonNullKeyEntry(key, index, hash);
+ if (entry == null) {
+ modCount++;
+ if (++elementCount > threshold) {
+ rehash();
+ index = (hash & 0x7FFFFFFF) % elementData.length;
+ }
+ entry = createHashedEntry(key, index, hash);
}
- createEntry(key, index, value);
- return null;
}
V result = entry.value;
@@ -545,6 +545,13 @@
return entry;
}
+ Entry<K,V> createHashedEntry(K key, int index, int hash) {
+ Entry<K,V> entry = new Entry<K,V>(key,hash);
+ entry.next = elementData[index];
+ elementData[index] = entry;
+ return entry;
+ }
+
/**
* Copies all the mappings in the given map to this map. These mappings will
* replace all mappings that this map had for any of the keys currently in
@@ -579,9 +586,7 @@
for (int i = 0; i < elementData.length; i++) {
Entry<K, V> entry = elementData[i];
while (entry != null) {
- Object key = entry.key;
- int index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
- % length;
+ int index = (entry.origKeyHash & 0x7FFFFFFF) % length;
Entry<K, V> next = entry.next;
entry.next = newData[index];
newData[index] = entry;
@@ -618,9 +623,10 @@
Entry<K, V> entry;
Entry<K, V> last = null;
if (key != null) {
- index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+ int hash = key.hashCode();
+ index = (hash & 0x7FFFFFFF) % elementData.length;
entry = elementData[index];
- while (entry != null && !keysEqual(key, entry)) {
+ while (entry != null && !(entry.origKeyHash == hash && key.equals(entry.key))) {
last = entry;
entry = entry.next;
}
Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java?view=diff&rev=509249&r1=509248&r2=509249
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/LinkedHashMap.java Mon Feb 19 08:42:52 2007
@@ -139,7 +139,7 @@
canRemove = false;
associatedMap.modCount++;
- int index = associatedMap.getModuloHash(lastEntry.key);
+ int index = (lastEntry.key == null)? 0 : (lastEntry.key.hashCode() & 0x7FFFFFFF) % associatedMap.elementData.length;
LinkedHashMapEntry<KT, VT> m = (LinkedHashMapEntry<KT, VT>) associatedMap.elementData[index];
if (m == lastEntry) {
associatedMap.elementData[index] = lastEntry.next;
@@ -201,6 +201,13 @@
chainBackward = null;
}
+ LinkedHashMapEntry(K theKey, int hash) {
+ super(theKey, hash);
+ chainForward = null;
+ chainBackward = null;
+ }
+
+
@Override
@SuppressWarnings("unchecked")
public Object clone() {
@@ -236,7 +243,14 @@
*/
@Override
public V get(Object key) {
- LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) getEntry(key);
+ LinkedHashMapEntry<K, V> m;
+ if (key == null) {
+ m = (LinkedHashMapEntry<K, V>)findNullKeyEntry();
+ } else {
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % elementData.length;
+ m = (LinkedHashMapEntry<K, V>)findNonNullKeyEntry(key, index, hash);
+ }
if (m == null) {
return null;
}
@@ -269,6 +283,14 @@
return m;
}
+ Entry<K,V> createHashedEntry(K key, int index, int hash) {
+ LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key, hash);
+ m.next = elementData[index];
+ elementData[index] = m;
+ linkEntry(m);
+ return m;
+ }
+
/**
* Set the mapped value for the given key to the given value.
*
@@ -281,23 +303,36 @@
*/
@Override
public V put(K key, V value) {
- int index = getModuloHash(key);
- LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) findEntry(key, index);
-
- if (m == null) {
- modCount++;
- // Check if we need to remove the oldest entry
- // The check includes accessOrder since an accessOrder LinkedHashMap
- // does not record
- // the oldest member in 'head'.
- if (++elementCount > threshold) {
- rehash();
- index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
- % elementData.length;
+ LinkedHashMapEntry<K, V> m;
+ if (key == null) {
+ m = (LinkedHashMapEntry<K, V>)findNullKeyEntry();
+ if (m == null) {
+ modCount++;
+ // Check if we need to remove the oldest entry
+ // The check includes accessOrder since an accessOrder LinkedHashMap
+ // does not record
+ // the oldest member in 'head'.
+ if (++elementCount > threshold) {
+ rehash();
+ }
+ m = (LinkedHashMapEntry<K, V>) createHashedEntry(key, 0, 0);
+ } else {
+ linkEntry(m);
}
- m = (LinkedHashMapEntry<K, V>) createEntry(key, index, null);
} else {
- linkEntry(m);
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % elementData.length;
+ m = (LinkedHashMapEntry<K, V>)findNonNullKeyEntry(key, index, hash);
+ if (m == null) {
+ modCount++;
+ if (++elementCount > threshold) {
+ rehash();
+ index = (hash & 0x7FFFFFFF) % elementData.length;
+ }
+ m = (LinkedHashMapEntry<K, V>) createHashedEntry(key, index, hash);
+ } else {
+ linkEntry(m);
+ }
}
V result = m.value;