Author: tellison
Date: Fri Sep 14 05:35:16 2007
New Revision: 575658
URL: http://svn.apache.org/viewvc?rev=575658&view=rev
Log:
Optimization for Integer keys in 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?rev=575658&r1=575657&r2=575658&view=diff
==============================================================================
---
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
Fri Sep 14 05:35:16 2007
@@ -43,18 +43,28 @@
private static final int DEFAULT_SIZE = 16;
static class Entry<K, V> extends MapEntry<K, V> {
- final int origKeyHash;
+ final int storedKeyHash;
Entry<K, V> next;
Entry(K theKey, int hash) {
super(theKey, null);
- this.origKeyHash = hash;
+ if (theKey instanceof Integer) {
+ this.storedKeyHash = hash | 0x00000001;
+ } else {
+ this.storedKeyHash = hash & 0xFFFFFFFE;
+ }
}
Entry(K theKey, V theValue) {
super(theKey, theValue);
- origKeyHash = (theKey == null ? 0 : theKey.hashCode());
+ if (theKey == null) {
+ storedKeyHash = 0;
+ } else if (theKey instanceof Integer) {
+ storedKeyHash = theKey.hashCode() | 0x00000001;
+ } else {
+ storedKeyHash = theKey.hashCode() & 0xFFFFFFFE;
+ }
}
@Override
@@ -251,13 +261,16 @@
}
private static final int calculateCapacity(int x) {
- if(x >= 1 << 30){
+ if (x >= 1 << 30) {
return 1 << 30;
}
- if(x == 0){
+ if (x == 0) {
return 16;
}
- x = x -1;
+ if (x == 1) {
+ return 2;
+ }
+ x = x - 1;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
@@ -445,16 +458,25 @@
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;
+ if (key instanceof Integer) {
+ int storedKeyHash = keyHash | 0x00000001;
+ while (m != null && (m.storedKeyHash != storedKeyHash)) {
+ m = m.next;
+ }
+ } else {
+ int storedKeyHash = keyHash & 0xFFFFFFFE;
+ while (m != null && (m.storedKeyHash != storedKeyHash ||
!key.equals(m.key))) {
+ m = m.next;
+ }
}
return m;
}
final Entry<K,V> findNullKeyEntry() {
Entry<K,V> m = elementData[0];
- while (m != null && m.key != null)
+ while (m != null && m.key != null) {
m = m.next;
+ }
return m;
}
@@ -569,7 +591,7 @@
}
Entry<K,V> createHashedEntry(K key, int index, int hash) {
- Entry<K,V> entry = new Entry<K,V>(key,hash);
+ Entry<K,V> entry = new Entry<K,V>(key, hash);
entry.next = elementData[index];
elementData[index] = entry;
return entry;
@@ -609,7 +631,8 @@
for (int i = 0; i < elementData.length; i++) {
Entry<K, V> entry = elementData[i];
while (entry != null) {
- int index = entry.origKeyHash & (length - 1);
+ int actualHash = (i & 0x00000001) | (entry.storedKeyHash &
0xFFFFFFFE);
+ int index = actualHash & (length - 1);
Entry<K, V> next = entry.next;
entry.next = newData[index];
newData[index] = entry;
@@ -646,12 +669,22 @@
Entry<K, V> entry;
Entry<K, V> last = null;
if (key != null) {
- int hash = key.hashCode();
- index = hash & (elementData.length - 1);
+ int keyHash = key.hashCode();
+ index = keyHash & (elementData.length - 1);
entry = elementData[index];
- while (entry != null && !(entry.origKeyHash == hash &&
key.equals(entry.key))) {
- last = entry;
- entry = entry.next;
+
+ if (key instanceof Integer) {
+ int storedKeyHash = keyHash | 0x00000001;
+ while (entry != null && (entry.storedKeyHash !=
storedKeyHash)) {
+ last = entry;
+ entry = entry.next;
+ }
+ } else {
+ int storedKeyHash = keyHash & 0xFFFFFFFE;
+ while (entry != null && (entry.storedKeyHash != storedKeyHash
|| !key.equals(entry.key))) {
+ last = entry;
+ entry = entry.next;
+ }
}
} else {
entry = elementData[0];
