jdk: 7126277: Alternative String hashing implementation (original) (raw)

Ulf Zibis Ulf.Zibis at gmx.de
Thu May 31 08:40:38 UTC 2012

Previous message: hg: jdk8/tl/jdk: 7126277: Alternative String hashing implementation
Next message: hg: jdk8/tl/jdk: 7126277: Alternative String hashing implementation
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Hi Mike,

some more questions:

public class Hashmap<K,V> {

int hash(Object k) {
```
   int h = hashSeed;
```
```
   if (k instanceof String) {
```
```
   return ((String) k).hash32();
```
```
   } else {
```
```
       h ^= k.hashCode();
```
```
   }
```

   // This function ensures that hashCodes that differ only by

   // constant multiples at each bit position have a bounded

   // number of collisions (approximately 8 at default load factor).

```
   h ^= (h >>> 20) ^ (h >>> 12);
```
```
   return h ^ (h >>> 7) ^ (h >>> 4);
}
```

Why you declare and assign variable h before the if statement? And why you set h ^= k.hashCode(); in the else branch, but not the remaining instructions to complete the calculation? Similar (but why little different?) for: Hashtable WeakHashMap ConcurrentHashMap So couldn't method hash(Object) be moved to AbstractMap? Why in WeakHashMap method hash(Object) is not final? (In this case I could exceptionally override it for a custom implementation as former desired for all hash maps.)

-Ulf

Am 31.05.2012 07:19, schrieb mike.duigou at oracle.com:

Changeset: 43bd5ee0205e Author: mduigou Date: 2012-05-30 22:18 -0700 URL: http://hg.openjdk.java.net/jdk8/tl/jdk/rev/43bd5ee0205e

7126277: Alternative String hashing implementation Summary: All of the hashing based Map implementations: HashMap, Hashtable, LinkedHashMap, WeakHashMap and ConcurrentHashMap are modified to use an enhanced hashing algorithm for string keys when the capacity of the hash table has ever grown beyond 512 entries. The enhanced hashing implementation uses the murmur3 hashing algorithm along with random hash seeds and index masks. These enhancements mitigate cases where colliding String hash values could result in a performance bottleneck. Reviewed-by: alanb, forax, dl ! make/java/java/FILESjava.gmk ! src/share/classes/java/lang/String.java ! src/share/classes/java/util/HashMap.java ! src/share/classes/java/util/Hashtable.java ! src/share/classes/java/util/LinkedHashMap.java ! src/share/classes/java/util/WeakHashMap.java ! src/share/classes/java/util/concurrent/ConcurrentHashMap.java + src/share/classes/sun/misc/Hashing.java ! test/java/util/Collection/BiggernYours.java ! test/java/util/Hashtable/HashCode.java ! test/java/util/Hashtable/SimpleSerialization.java + test/java/util/Map/Collisions.java ! test/java/util/Map/Get.java + test/sun/misc/Hashing.java

Previous message: hg: jdk8/tl/jdk: 7126277: Alternative String hashing implementation
Next message: hg: jdk8/tl/jdk: 7126277: Alternative String hashing implementation
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the core-libs-dev mailing list