src/share/classes/java/util/concurrent/ConcurrentHashMap.java

Print this page
rev 5382 : 7126277: Alternative hashing implementation

*** 173,182 **** --- 173,188 ---- static final int RETRIES_BEFORE_LOCK = 2; /* ---------------- Fields -------------- */ /** + * A randomizing value associated with this instance that is applied to + * hash code of keys to make hash collisions harder to find. + */ + private transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this); + + /** * Mask value for indexing into segments. The upper bits of a * key's hash code are used to choose the segment. */ final int segmentMask;
*** 260,270 **** * defends against poor quality hash functions. This is critical * because ConcurrentHashMap uses power-of-two length hash tables, * that otherwise encounter collisions for hashCodes that do not * differ in lower or upper bits. */ ! private static int hash(int h) { // Spread bits to regularize both segment and index locations, // using variant of single-word Wang/Jenkins hash. h += (h << 15) ^ 0xffffcd7d; h ^= (h >>> 10); h += (h << 3); --- 266,284 ---- * defends against poor quality hash functions. This is critical * because ConcurrentHashMap uses power-of-two length hash tables, * that otherwise encounter collisions for hashCodes that do not * differ in lower or upper bits. */ ! private int hash(Object k) { ! int h = hashSeed; ! ! if (k instanceof String) { ! return h ^ ((String) k).hash32(); ! } ! ! h ^= k.hashCode(); ! // Spread bits to regularize both segment and index locations, // using variant of single-word Wang/Jenkins hash. h += (h << 15) ^ 0xffffcd7d; h ^= (h >>> 10); h += (h << 3);
*** 915,925 **** */ @SuppressWarnings("unchecked") public V get(Object key) { Segment<K,V> s; // manually integrate access methods to reduce overhead HashEntry<K,V>[] tab; ! int h = hash(key.hashCode()); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); --- 929,939 ---- */ @SuppressWarnings("unchecked") public V get(Object key) { Segment<K,V> s; // manually integrate access methods to reduce overhead HashEntry<K,V>[] tab; ! int h = hash(key); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
*** 943,953 **** */ @SuppressWarnings("unchecked") public boolean containsKey(Object key) { Segment<K,V> s; // same as get() except no need for volatile value read HashEntry<K,V>[] tab; ! int h = hash(key.hashCode()); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); --- 957,967 ---- */ @SuppressWarnings("unchecked") public boolean containsKey(Object key) { Segment<K,V> s; // same as get() except no need for volatile value read HashEntry<K,V>[] tab; ! int h = hash(key); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
*** 1052,1062 **** @SuppressWarnings("unchecked") public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); ! int hash = hash(key.hashCode()); int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment s = ensureSegment(j); return s.put(key, hash, value, false); --- 1066,1076 ---- @SuppressWarnings("unchecked") public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); ! int hash = hash(key); int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment s = ensureSegment(j); return s.put(key, hash, value, false);
*** 1072,1082 **** @SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); ! int hash = hash(key.hashCode()); int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment<K,V>)UNSAFE.getObject (segments, (j << SSHIFT) + SBASE)) == null) s = ensureSegment(j); return s.put(key, hash, value, true); --- 1086,1096 ---- @SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); ! int hash = hash(key); int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment<K,V>)UNSAFE.getObject (segments, (j << SSHIFT) + SBASE)) == null) s = ensureSegment(j); return s.put(key, hash, value, true);
*** 1102,1123 **** * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt> * @throws NullPointerException if the specified key is null */ public V remove(Object key) { ! int hash = hash(key.hashCode()); Segment<K,V> s = segmentForHash(hash); return s == null ? null : s.remove(key, hash, null); } /** * {@inheritDoc} * * @throws NullPointerException if the specified key is null */ public boolean remove(Object key, Object value) { ! int hash = hash(key.hashCode()); Segment<K,V> s; return value != null && (s = segmentForHash(hash)) != null && s.remove(key, hash, value) != null; } --- 1116,1137 ---- * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt> * @throws NullPointerException if the specified key is null */ public V remove(Object key) { ! int hash = hash(key); Segment<K,V> s = segmentForHash(hash); return s == null ? null : s.remove(key, hash, null); } /** * {@inheritDoc} * * @throws NullPointerException if the specified key is null */ public boolean remove(Object key, Object value) { ! int hash = hash(key); Segment<K,V> s; return value != null && (s = segmentForHash(hash)) != null && s.remove(key, hash, value) != null; }
*** 1125,1135 **** * {@inheritDoc} * * @throws NullPointerException if any of the arguments are null */ public boolean replace(K key, V oldValue, V newValue) { ! int hash = hash(key.hashCode()); if (oldValue == null || newValue == null) throw new NullPointerException(); Segment<K,V> s = segmentForHash(hash); return s != null && s.replace(key, hash, oldValue, newValue); } --- 1139,1149 ---- * {@inheritDoc} * * @throws NullPointerException if any of the arguments are null */ public boolean replace(K key, V oldValue, V newValue) { ! int hash = hash(key); if (oldValue == null || newValue == null) throw new NullPointerException(); Segment<K,V> s = segmentForHash(hash); return s != null && s.replace(key, hash, oldValue, newValue); }
*** 1140,1150 **** * @return the previous value associated with the specified key, * or <tt>null</tt> if there was no mapping for the key * @throws NullPointerException if the specified key or value is null */ public V replace(K key, V value) { ! int hash = hash(key.hashCode()); if (value == null) throw new NullPointerException(); Segment<K,V> s = segmentForHash(hash); return s == null ? null : s.replace(key, hash, value); } --- 1154,1164 ---- * @return the previous value associated with the specified key, * or <tt>null</tt> if there was no mapping for the key * @throws NullPointerException if the specified key or value is null */ public V replace(K key, V value) { ! int hash = hash(key); if (value == null) throw new NullPointerException(); Segment<K,V> s = segmentForHash(hash); return s == null ? null : s.replace(key, hash, value); }
*** 1471,1480 **** --- 1485,1498 ---- @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); + // set hashMask + UNSAFE.putIntVolatile(this, HASHSEED_OFFSET, + sun.misc.Hashing.randomHashSeed(this)); + // Re-initialize segments to be minimally sized, and let grow. int cap = MIN_SEGMENT_TABLE_CAPACITY; final Segment<K,V>[] segments = this.segments; for (int k = 0; k < segments.length; ++k) { Segment<K,V> seg = segments[k];
*** 1498,1507 **** --- 1516,1526 ---- private static final sun.misc.Unsafe UNSAFE; private static final long SBASE; private static final int SSHIFT; private static final long TBASE; private static final int TSHIFT; + private static final long HASHSEED_OFFSET; static { int ss, ts; try { UNSAFE = sun.misc.Unsafe.getUnsafe();
*** 1509,1518 **** --- 1528,1539 ---- Class<?> sc = Segment[].class; TBASE = UNSAFE.arrayBaseOffset(tc); SBASE = UNSAFE.arrayBaseOffset(sc); ts = UNSAFE.arrayIndexScale(tc); ss = UNSAFE.arrayIndexScale(sc); + HASHSEED_OFFSET = UNSAFE.objectFieldOffset( + ConcurrentHashMap.class.getDeclaredField("hashSeed")); } catch (Exception e) { throw new Error(e); } if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0) throw new Error("data type scale not a power of two");