Index: modules/luni/src/main/java/java/util/LinkedHashMap.java =================================================================== --- modules/luni/src/main/java/java/util/LinkedHashMap.java (revision 416296) +++ modules/luni/src/main/java/java/util/LinkedHashMap.java (working copy) @@ -132,7 +132,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 m = (LinkedHashMapEntry) associatedMap.elementData[index]; if (m == lastEntry) { associatedMap.elementData[index] = lastEntry.next; @@ -190,6 +190,12 @@ chainBackward = null; } + LinkedHashMapEntry(K theKey, int hash) { + super(theKey, hash); + chainForward = null; + chainBackward = null; + } + public Object clone() { LinkedHashMapEntry entry = (LinkedHashMapEntry) super.clone(); entry.chainBackward = chainBackward; @@ -219,7 +225,14 @@ * @return mapped value or null if the key is not in the map */ public V get(Object key) { - LinkedHashMapEntry m = (LinkedHashMapEntry) getEntry(key); + LinkedHashMapEntry m; + if (key == null) { + m = (LinkedHashMapEntry)findNullKeyEntry(); + } else { + int hash = key.hashCode(); + int index = (hash & 0x7FFFFFFF) % elementData.length; + m = (LinkedHashMapEntry)findNonNullKeyEntry(key, index, hash); + } if (m == null) return null; if (accessOrder && tail != m) { @@ -249,6 +262,14 @@ return m; } + Entry createHashedEntry(K key, int index, int hash) { + LinkedHashMapEntry m = new LinkedHashMapEntry(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. * @@ -260,25 +281,37 @@ * otherwise. */ public V put(K key, V value) { - int index = getModuloHash(key); - LinkedHashMapEntry m = (LinkedHashMapEntry) 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 m; + if (key == null) { + m = (LinkedHashMapEntry)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) createHashedEntry(key, 0, 0); + } else { + linkEntry(m); } - m = (LinkedHashMapEntry) createEntry(key, index, null); } else { - linkEntry(m); + int hash = key.hashCode(); + int index = (hash & 0x7FFFFFFF) % elementData.length; + m = (LinkedHashMapEntry)findNonNullKeyEntry(key, index, hash); + if (m == null) { + modCount++; + if (++elementCount > threshold) { + rehash(); + index = (hash & 0x7FFFFFFF) % elementData.length; + } + m = (LinkedHashMapEntry) createHashedEntry(key, index, hash); + } else { + linkEntry(m); + } } - V result = m.value; m.value = value; Index: modules/luni/src/main/java/java/util/HashMap.java =================================================================== --- modules/luni/src/main/java/java/util/HashMap.java (revision 416296) +++ modules/luni/src/main/java/java/util/HashMap.java (working copy) @@ -45,6 +45,11 @@ Entry next; + Entry(K theKey, int hash) { + super(theKey, null); + this.hash = hash; + } + Entry(K theKey, V theValue) { super(theKey, theValue); this.hash = (theKey == null) ? 0 : theKey.hashCode(); @@ -62,9 +67,6 @@ return key + "=" + value; } - public int hashCode() { - return hash; - } } static class HashMapIterator implements Iterator { @@ -180,8 +182,15 @@ public boolean contains(Object object) { if (object instanceof Map.Entry) { - Entry entry = associatedMap.getEntry(((Map.Entry) object) - .getKey()); + Object key = ((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; @@ -321,24 +330,18 @@ * otherwise */ public boolean containsKey(Object key) { - return getEntry(key) != null; + Entry m; + if (key == null) { + m = findNullKeyEntry(); + } else { + int hash = key.hashCode(); + int index = (hash & 0x7FFFFFFF) % elementData.length; + m = findNonNullKeyEntry(key, index, hash); + } + return m != 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 entry) { - return entry.hashCode() == k1.hashCode() && k1.equals(entry.key); - } - - /** * Searches this HashMap for the specified value. * * @param value @@ -390,37 +393,32 @@ * @return the value of the mapping with the specified key */ public V get(Object key) { - Entry m = getEntry(key); + Entry 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 getEntry(Object key) { - int index = getModuloHash(key); - return findEntry(key, index); - } - - int getModuloHash(Object key) { - if (key == null) { - return 0; + final Entry findNonNullKeyEntry(Object key, int index, int keyHash) { + Entry m = elementData[index]; + while (m != null && (m.hash != keyHash || !key.equals(m.key))) { + m = m.next; } - return (key.hashCode() & 0x7FFFFFFF) % elementData.length; + return m; } - - Entry findEntry(Object key, int index) { - Entry 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 findNullKeyEntry() { + Entry m = elementData[0]; + while (m != null && m.key != null) + m = m.next; return m; } @@ -458,11 +456,8 @@ } public boolean remove(Object key) { - if (containsKey(key)) { - HashMap.this.remove(key); - return true; - } - return false; + Entry entry = HashMap.this.removeEntry(key); + return entry != null; } public Iterator iterator() { @@ -488,17 +483,28 @@ * if there was no mapping */ public V put(K key, V value) { - int index = getModuloHash(key); - Entry entry = findEntry(key, index); - + Entry 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 = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF) - % elementData.length; + index = (hash & 0x7FFFFFFF) % elementData.length; + } + entry = createHashedEntry(key, index, hash); } - entry = createEntry(key, index, null); } V result = entry.value; entry.value = value; @@ -512,6 +518,13 @@ return entry; } + Entry createHashedEntry(K key, int index, int hash) { + Entry entry = new Entry(key,hash); + entry.next = elementData[index]; + elementData[index] = entry; + return entry; + } + /** * Copies every mapping in the specified Map to this HashMap. * @@ -531,9 +544,7 @@ for (int i = 0; i < elementData.length; i++) { Entry entry = elementData[i]; while (entry != null) { - Object key = entry.key; - int index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF) - % length; + int index = (entry.hash & 0x7FFFFFFF) % length; Entry next = entry.next; entry.next = newData[index]; newData[index] = entry; @@ -565,9 +576,10 @@ Entry entry; Entry 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.hash == hash && key.equals(entry.key))) { last = entry; entry = entry.next; }