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

Print this page
rev 5431 : 7126277: Alternative hashing implementation


 158      */
 159     static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
 160 
 161     /**
 162      * The maximum number of segments to allow; used to bound
 163      * constructor arguments. Must be power of two less than 1 << 24.
 164      */
 165     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
 166 
 167     /**
 168      * Number of unsynchronized retries in size and containsValue
 169      * methods before resorting to locking. This is used to avoid
 170      * unbounded retries if tables undergo continuous modification
 171      * which would make it impossible to obtain an accurate result.
 172      */
 173     static final int RETRIES_BEFORE_LOCK = 2;
 174 
 175     /* ---------------- Fields -------------- */
 176 
 177     /**






 178      * Mask value for indexing into segments. The upper bits of a
 179      * key's hash code are used to choose the segment.
 180      */
 181     final int segmentMask;
 182 
 183     /**
 184      * Shift value for indexing within segments.
 185      */
 186     final int segmentShift;
 187 
 188     /**
 189      * The segments, each of which is a specialized hash table.
 190      */
 191     final Segment<K,V>[] segments;
 192 
 193     transient Set<K> keySet;
 194     transient Set<Map.Entry<K,V>> entrySet;
 195     transient Collection<V> values;
 196 
 197     /**


 245             (HashEntry<K,V>) UNSAFE.getObjectVolatile
 246             (tab, ((long)i << TSHIFT) + TBASE);
 247     }
 248 
 249     /**
 250      * Sets the ith element of given table, with volatile write
 251      * semantics. (See above about use of putOrderedObject.)
 252      */
 253     static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
 254                                        HashEntry<K,V> e) {
 255         UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
 256     }
 257 
 258     /**
 259      * Applies a supplemental hash function to a given hashCode, which
 260      * defends against poor quality hash functions.  This is critical
 261      * because ConcurrentHashMap uses power-of-two length hash tables,
 262      * that otherwise encounter collisions for hashCodes that do not
 263      * differ in lower or upper bits.
 264      */
 265     private static int hash(int h) {








 266         // Spread bits to regularize both segment and index locations,
 267         // using variant of single-word Wang/Jenkins hash.
 268         h += (h <<  15) ^ 0xffffcd7d;
 269         h ^= (h >>> 10);
 270         h += (h <<   3);
 271         h ^= (h >>>  6);
 272         h += (h <<   2) + (h << 14);
 273         return h ^ (h >>> 16);
 274     }
 275 
 276     /**
 277      * Segments are specialized versions of hash tables.  This
 278      * subclasses from ReentrantLock opportunistically, just to
 279      * simplify some locking and avoid separate construction.
 280      */
 281     static final class Segment<K,V> extends ReentrantLock implements Serializable {
 282         /*
 283          * Segments maintain a table of entry lists that are always
 284          * kept in a consistent state, so can be read (via volatile
 285          * reads of segments and tables) without locking.  This


 900             }
 901         }
 902         return overflow ? Integer.MAX_VALUE : size;
 903     }
 904 
 905     /**
 906      * Returns the value to which the specified key is mapped,
 907      * or {@code null} if this map contains no mapping for the key.
 908      *
 909      * <p>More formally, if this map contains a mapping from a key
 910      * {@code k} to a value {@code v} such that {@code key.equals(k)},
 911      * then this method returns {@code v}; otherwise it returns
 912      * {@code null}.  (There can be at most one such mapping.)
 913      *
 914      * @throws NullPointerException if the specified key is null
 915      */
 916     @SuppressWarnings("unchecked")
 917     public V get(Object key) {
 918         Segment<K,V> s; // manually integrate access methods to reduce overhead
 919         HashEntry<K,V>[] tab;
 920         int h = hash(key.hashCode());
 921         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
 922         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
 923             (tab = s.table) != null) {
 924             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
 925                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
 926                  e != null; e = e.next) {
 927                 K k;
 928                 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
 929                     return e.value;
 930             }
 931         }
 932         return null;
 933     }
 934 
 935     /**
 936      * Tests if the specified object is a key in this table.
 937      *
 938      * @param  key   possible key
 939      * @return <tt>true</tt> if and only if the specified object
 940      *         is a key in this table, as determined by the
 941      *         <tt>equals</tt> method; <tt>false</tt> otherwise.
 942      * @throws NullPointerException if the specified key is null
 943      */
 944     @SuppressWarnings("unchecked")
 945     public boolean containsKey(Object key) {
 946         Segment<K,V> s; // same as get() except no need for volatile value read
 947         HashEntry<K,V>[] tab;
 948         int h = hash(key.hashCode());
 949         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
 950         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
 951             (tab = s.table) != null) {
 952             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
 953                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
 954                  e != null; e = e.next) {
 955                 K k;
 956                 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
 957                     return true;
 958             }
 959         }
 960         return false;
 961     }
 962 
 963     /**
 964      * Returns <tt>true</tt> if this map maps one or more keys to the
 965      * specified value. Note: This method requires a full internal
 966      * traversal of the hash table, and so is much slower than
 967      * method <tt>containsKey</tt>.
 968      *


1037     }
1038 
1039     /**
1040      * Maps the specified key to the specified value in this table.
1041      * Neither the key nor the value can be null.
1042      *
1043      * <p> The value can be retrieved by calling the <tt>get</tt> method
1044      * with a key that is equal to the original key.
1045      *
1046      * @param key key with which the specified value is to be associated
1047      * @param value value to be associated with the specified key
1048      * @return the previous value associated with <tt>key</tt>, or
1049      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
1050      * @throws NullPointerException if the specified key or value is null
1051      */
1052     @SuppressWarnings("unchecked")
1053     public V put(K key, V value) {
1054         Segment<K,V> s;
1055         if (value == null)
1056             throw new NullPointerException();
1057         int hash = hash(key.hashCode());
1058         int j = (hash >>> segmentShift) & segmentMask;
1059         if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
1060              (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
1061             s = ensureSegment(j);
1062         return s.put(key, hash, value, false);
1063     }
1064 
1065     /**
1066      * {@inheritDoc}
1067      *
1068      * @return the previous value associated with the specified key,
1069      *         or <tt>null</tt> if there was no mapping for the key
1070      * @throws NullPointerException if the specified key or value is null
1071      */
1072     @SuppressWarnings("unchecked")
1073     public V putIfAbsent(K key, V value) {
1074         Segment<K,V> s;
1075         if (value == null)
1076             throw new NullPointerException();
1077         int hash = hash(key.hashCode());
1078         int j = (hash >>> segmentShift) & segmentMask;
1079         if ((s = (Segment<K,V>)UNSAFE.getObject
1080              (segments, (j << SSHIFT) + SBASE)) == null)
1081             s = ensureSegment(j);
1082         return s.put(key, hash, value, true);
1083     }
1084 
1085     /**
1086      * Copies all of the mappings from the specified map to this one.
1087      * These mappings replace any mappings that this map had for any of the
1088      * keys currently in the specified map.
1089      *
1090      * @param m mappings to be stored in this map
1091      */
1092     public void putAll(Map<? extends K, ? extends V> m) {
1093         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1094             put(e.getKey(), e.getValue());
1095     }
1096 
1097     /**
1098      * Removes the key (and its corresponding value) from this map.
1099      * This method does nothing if the key is not in the map.
1100      *
1101      * @param  key the key that needs to be removed
1102      * @return the previous value associated with <tt>key</tt>, or
1103      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
1104      * @throws NullPointerException if the specified key is null
1105      */
1106     public V remove(Object key) {
1107         int hash = hash(key.hashCode());
1108         Segment<K,V> s = segmentForHash(hash);
1109         return s == null ? null : s.remove(key, hash, null);
1110     }
1111 
1112     /**
1113      * {@inheritDoc}
1114      *
1115      * @throws NullPointerException if the specified key is null
1116      */
1117     public boolean remove(Object key, Object value) {
1118         int hash = hash(key.hashCode());
1119         Segment<K,V> s;
1120         return value != null && (s = segmentForHash(hash)) != null &&
1121             s.remove(key, hash, value) != null;
1122     }
1123 
1124     /**
1125      * {@inheritDoc}
1126      *
1127      * @throws NullPointerException if any of the arguments are null
1128      */
1129     public boolean replace(K key, V oldValue, V newValue) {
1130         int hash = hash(key.hashCode());
1131         if (oldValue == null || newValue == null)
1132             throw new NullPointerException();
1133         Segment<K,V> s = segmentForHash(hash);
1134         return s != null && s.replace(key, hash, oldValue, newValue);
1135     }
1136 
1137     /**
1138      * {@inheritDoc}
1139      *
1140      * @return the previous value associated with the specified key,
1141      *         or <tt>null</tt> if there was no mapping for the key
1142      * @throws NullPointerException if the specified key or value is null
1143      */
1144     public V replace(K key, V value) {
1145         int hash = hash(key.hashCode());
1146         if (value == null)
1147             throw new NullPointerException();
1148         Segment<K,V> s = segmentForHash(hash);
1149         return s == null ? null : s.replace(key, hash, value);
1150     }
1151 
1152     /**
1153      * Removes all of the mappings from this map.
1154      */
1155     public void clear() {
1156         final Segment<K,V>[] segments = this.segments;
1157         for (int j = 0; j < segments.length; ++j) {
1158             Segment<K,V> s = segmentAt(segments, j);
1159             if (s != null)
1160                 s.clear();
1161         }
1162     }
1163 
1164     /**
1165      * Returns a {@link Set} view of the keys contained in this map.


1456                     }
1457                 }
1458             } finally {
1459                 seg.unlock();
1460             }
1461         }
1462         s.writeObject(null);
1463         s.writeObject(null);
1464     }
1465 
1466     /**
1467      * Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1468      * stream (i.e., deserializes it).
1469      * @param s the stream
1470      */
1471     @SuppressWarnings("unchecked")
1472     private void readObject(java.io.ObjectInputStream s)
1473             throws java.io.IOException, ClassNotFoundException {
1474         s.defaultReadObject();
1475 




1476         // Re-initialize segments to be minimally sized, and let grow.
1477         int cap = MIN_SEGMENT_TABLE_CAPACITY;
1478         final Segment<K,V>[] segments = this.segments;
1479         for (int k = 0; k < segments.length; ++k) {
1480             Segment<K,V> seg = segments[k];
1481             if (seg != null) {
1482                 seg.threshold = (int)(cap * seg.loadFactor);
1483                 seg.table = (HashEntry<K,V>[]) new HashEntry<?,?>[cap];
1484             }
1485         }
1486 
1487         // Read the keys and values, and put the mappings in the table
1488         for (;;) {
1489             K key = (K) s.readObject();
1490             V value = (V) s.readObject();
1491             if (key == null)
1492                 break;
1493             put(key, value);
1494         }
1495     }
1496 
1497     // Unsafe mechanics
1498     private static final sun.misc.Unsafe UNSAFE;
1499     private static final long SBASE;
1500     private static final int SSHIFT;
1501     private static final long TBASE;
1502     private static final int TSHIFT;

1503 
1504     static {
1505         int ss, ts;
1506         try {
1507             UNSAFE = sun.misc.Unsafe.getUnsafe();
1508             Class<?> tc = HashEntry[].class;
1509             Class<?> sc = Segment[].class;
1510             TBASE = UNSAFE.arrayBaseOffset(tc);
1511             SBASE = UNSAFE.arrayBaseOffset(sc);
1512             ts = UNSAFE.arrayIndexScale(tc);
1513             ss = UNSAFE.arrayIndexScale(sc);


1514         } catch (Exception e) {
1515             throw new Error(e);
1516         }
1517         if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1518             throw new Error("data type scale not a power of two");
1519         SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1520         TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1521     }
1522 
1523 }


 158      */
 159     static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
 160 
 161     /**
 162      * The maximum number of segments to allow; used to bound
 163      * constructor arguments. Must be power of two less than 1 << 24.
 164      */
 165     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
 166 
 167     /**
 168      * Number of unsynchronized retries in size and containsValue
 169      * methods before resorting to locking. This is used to avoid
 170      * unbounded retries if tables undergo continuous modification
 171      * which would make it impossible to obtain an accurate result.
 172      */
 173     static final int RETRIES_BEFORE_LOCK = 2;
 174 
 175     /* ---------------- Fields -------------- */
 176 
 177     /**
 178      * A randomizing value associated with this instance that is applied to  
 179      * hash code of keys to make hash collisions harder to find.
 180      */
 181    private transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
 182     
 183     /**
 184      * Mask value for indexing into segments. The upper bits of a
 185      * key's hash code are used to choose the segment.
 186      */
 187     final int segmentMask;
 188 
 189     /**
 190      * Shift value for indexing within segments.
 191      */
 192     final int segmentShift;
 193 
 194     /**
 195      * The segments, each of which is a specialized hash table.
 196      */
 197     final Segment<K,V>[] segments;
 198 
 199     transient Set<K> keySet;
 200     transient Set<Map.Entry<K,V>> entrySet;
 201     transient Collection<V> values;
 202 
 203     /**


 251             (HashEntry<K,V>) UNSAFE.getObjectVolatile
 252             (tab, ((long)i << TSHIFT) + TBASE);
 253     }
 254 
 255     /**
 256      * Sets the ith element of given table, with volatile write
 257      * semantics. (See above about use of putOrderedObject.)
 258      */
 259     static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
 260                                        HashEntry<K,V> e) {
 261         UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
 262     }
 263 
 264     /**
 265      * Applies a supplemental hash function to a given hashCode, which
 266      * defends against poor quality hash functions.  This is critical
 267      * because ConcurrentHashMap uses power-of-two length hash tables,
 268      * that otherwise encounter collisions for hashCodes that do not
 269      * differ in lower or upper bits.
 270      */
 271     private int hash(Object k) {        
 272        int h = hashSeed;
 273 
 274         if (k instanceof String) {
 275             return ((String) k).hash32();
 276         }
 277 
 278         h ^= k.hashCode();
 279 
 280         // Spread bits to regularize both segment and index locations,
 281         // using variant of single-word Wang/Jenkins hash.
 282         h += (h <<  15) ^ 0xffffcd7d;
 283         h ^= (h >>> 10);
 284         h += (h <<   3);
 285         h ^= (h >>>  6);
 286         h += (h <<   2) + (h << 14);
 287         return h ^ (h >>> 16);
 288     }
 289 
 290     /**
 291      * Segments are specialized versions of hash tables.  This
 292      * subclasses from ReentrantLock opportunistically, just to
 293      * simplify some locking and avoid separate construction.
 294      */
 295     static final class Segment<K,V> extends ReentrantLock implements Serializable {
 296         /*
 297          * Segments maintain a table of entry lists that are always
 298          * kept in a consistent state, so can be read (via volatile
 299          * reads of segments and tables) without locking.  This


 914             }
 915         }
 916         return overflow ? Integer.MAX_VALUE : size;
 917     }
 918 
 919     /**
 920      * Returns the value to which the specified key is mapped,
 921      * or {@code null} if this map contains no mapping for the key.
 922      *
 923      * <p>More formally, if this map contains a mapping from a key
 924      * {@code k} to a value {@code v} such that {@code key.equals(k)},
 925      * then this method returns {@code v}; otherwise it returns
 926      * {@code null}.  (There can be at most one such mapping.)
 927      *
 928      * @throws NullPointerException if the specified key is null
 929      */
 930     @SuppressWarnings("unchecked")
 931     public V get(Object key) {
 932         Segment<K,V> s; // manually integrate access methods to reduce overhead
 933         HashEntry<K,V>[] tab;
 934         int h = hash(key);
 935         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
 936         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
 937             (tab = s.table) != null) {
 938             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
 939                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
 940                  e != null; e = e.next) {
 941                 K k;
 942                 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
 943                     return e.value;
 944             }
 945         }
 946         return null;
 947     }
 948 
 949     /**
 950      * Tests if the specified object is a key in this table.
 951      *
 952      * @param  key   possible key
 953      * @return <tt>true</tt> if and only if the specified object
 954      *         is a key in this table, as determined by the
 955      *         <tt>equals</tt> method; <tt>false</tt> otherwise.
 956      * @throws NullPointerException if the specified key is null
 957      */
 958     @SuppressWarnings("unchecked")
 959     public boolean containsKey(Object key) {
 960         Segment<K,V> s; // same as get() except no need for volatile value read
 961         HashEntry<K,V>[] tab;
 962         int h = hash(key);
 963         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
 964         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
 965             (tab = s.table) != null) {
 966             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
 967                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
 968                  e != null; e = e.next) {
 969                 K k;
 970                 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
 971                     return true;
 972             }
 973         }
 974         return false;
 975     }
 976 
 977     /**
 978      * Returns <tt>true</tt> if this map maps one or more keys to the
 979      * specified value. Note: This method requires a full internal
 980      * traversal of the hash table, and so is much slower than
 981      * method <tt>containsKey</tt>.
 982      *


1051     }
1052 
1053     /**
1054      * Maps the specified key to the specified value in this table.
1055      * Neither the key nor the value can be null.
1056      *
1057      * <p> The value can be retrieved by calling the <tt>get</tt> method
1058      * with a key that is equal to the original key.
1059      *
1060      * @param key key with which the specified value is to be associated
1061      * @param value value to be associated with the specified key
1062      * @return the previous value associated with <tt>key</tt>, or
1063      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
1064      * @throws NullPointerException if the specified key or value is null
1065      */
1066     @SuppressWarnings("unchecked")
1067     public V put(K key, V value) {
1068         Segment<K,V> s;
1069         if (value == null)
1070             throw new NullPointerException();
1071         int hash = hash(key);
1072         int j = (hash >>> segmentShift) & segmentMask;
1073         if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
1074              (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
1075             s = ensureSegment(j);
1076         return s.put(key, hash, value, false);
1077     }
1078 
1079     /**
1080      * {@inheritDoc}
1081      *
1082      * @return the previous value associated with the specified key,
1083      *         or <tt>null</tt> if there was no mapping for the key
1084      * @throws NullPointerException if the specified key or value is null
1085      */
1086     @SuppressWarnings("unchecked")
1087     public V putIfAbsent(K key, V value) {
1088         Segment<K,V> s;
1089         if (value == null)
1090             throw new NullPointerException();
1091         int hash = hash(key);
1092         int j = (hash >>> segmentShift) & segmentMask;
1093         if ((s = (Segment<K,V>)UNSAFE.getObject
1094              (segments, (j << SSHIFT) + SBASE)) == null)
1095             s = ensureSegment(j);
1096         return s.put(key, hash, value, true);
1097     }
1098 
1099     /**
1100      * Copies all of the mappings from the specified map to this one.
1101      * These mappings replace any mappings that this map had for any of the
1102      * keys currently in the specified map.
1103      *
1104      * @param m mappings to be stored in this map
1105      */
1106     public void putAll(Map<? extends K, ? extends V> m) {
1107         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1108             put(e.getKey(), e.getValue());
1109     }
1110 
1111     /**
1112      * Removes the key (and its corresponding value) from this map.
1113      * This method does nothing if the key is not in the map.
1114      *
1115      * @param  key the key that needs to be removed
1116      * @return the previous value associated with <tt>key</tt>, or
1117      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
1118      * @throws NullPointerException if the specified key is null
1119      */
1120     public V remove(Object key) {
1121         int hash = hash(key);
1122         Segment<K,V> s = segmentForHash(hash);
1123         return s == null ? null : s.remove(key, hash, null);
1124     }
1125 
1126     /**
1127      * {@inheritDoc}
1128      *
1129      * @throws NullPointerException if the specified key is null
1130      */
1131     public boolean remove(Object key, Object value) {
1132         int hash = hash(key);
1133         Segment<K,V> s;
1134         return value != null && (s = segmentForHash(hash)) != null &&
1135             s.remove(key, hash, value) != null;
1136     }
1137 
1138     /**
1139      * {@inheritDoc}
1140      *
1141      * @throws NullPointerException if any of the arguments are null
1142      */
1143     public boolean replace(K key, V oldValue, V newValue) {
1144         int hash = hash(key);
1145         if (oldValue == null || newValue == null)
1146             throw new NullPointerException();
1147         Segment<K,V> s = segmentForHash(hash);
1148         return s != null && s.replace(key, hash, oldValue, newValue);
1149     }
1150 
1151     /**
1152      * {@inheritDoc}
1153      *
1154      * @return the previous value associated with the specified key,
1155      *         or <tt>null</tt> if there was no mapping for the key
1156      * @throws NullPointerException if the specified key or value is null
1157      */
1158     public V replace(K key, V value) {
1159         int hash = hash(key);
1160         if (value == null)
1161             throw new NullPointerException();
1162         Segment<K,V> s = segmentForHash(hash);
1163         return s == null ? null : s.replace(key, hash, value);
1164     }
1165 
1166     /**
1167      * Removes all of the mappings from this map.
1168      */
1169     public void clear() {
1170         final Segment<K,V>[] segments = this.segments;
1171         for (int j = 0; j < segments.length; ++j) {
1172             Segment<K,V> s = segmentAt(segments, j);
1173             if (s != null)
1174                 s.clear();
1175         }
1176     }
1177 
1178     /**
1179      * Returns a {@link Set} view of the keys contained in this map.


1470                     }
1471                 }
1472             } finally {
1473                 seg.unlock();
1474             }
1475         }
1476         s.writeObject(null);
1477         s.writeObject(null);
1478     }
1479 
1480     /**
1481      * Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1482      * stream (i.e., deserializes it).
1483      * @param s the stream
1484      */
1485     @SuppressWarnings("unchecked")
1486     private void readObject(java.io.ObjectInputStream s)
1487             throws java.io.IOException, ClassNotFoundException {
1488         s.defaultReadObject();
1489         
1490         // set hashMask
1491         UNSAFE.putIntVolatile(this, HASHSEED_OFFSET, 
1492                  sun.misc.Hashing.randomHashSeed(this));
1493 
1494         // Re-initialize segments to be minimally sized, and let grow.
1495         int cap = MIN_SEGMENT_TABLE_CAPACITY;
1496         final Segment<K,V>[] segments = this.segments;
1497         for (int k = 0; k < segments.length; ++k) {
1498             Segment<K,V> seg = segments[k];
1499             if (seg != null) {
1500                 seg.threshold = (int)(cap * seg.loadFactor);
1501                 seg.table = (HashEntry<K,V>[]) new HashEntry<?,?>[cap];
1502             }
1503         }
1504 
1505         // Read the keys and values, and put the mappings in the table
1506         for (;;) {
1507             K key = (K) s.readObject();
1508             V value = (V) s.readObject();
1509             if (key == null)
1510                 break;
1511             put(key, value);
1512         }
1513     }
1514 
1515     // Unsafe mechanics
1516     private static final sun.misc.Unsafe UNSAFE;
1517     private static final long SBASE;
1518     private static final int SSHIFT;
1519     private static final long TBASE;
1520     private static final int TSHIFT;
1521     private static final long HASHSEED_OFFSET;
1522 
1523     static {
1524         int ss, ts;
1525         try {
1526             UNSAFE = sun.misc.Unsafe.getUnsafe();
1527             Class<?> tc = HashEntry[].class;
1528             Class<?> sc = Segment[].class;
1529             TBASE = UNSAFE.arrayBaseOffset(tc);
1530             SBASE = UNSAFE.arrayBaseOffset(sc);
1531             ts = UNSAFE.arrayIndexScale(tc);
1532             ss = UNSAFE.arrayIndexScale(sc);
1533             HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
1534                 ConcurrentHashMap.class.getDeclaredField("hashSeed"));                        
1535         } catch (Exception e) {
1536             throw new Error(e);
1537         }
1538         if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1539             throw new Error("data type scale not a power of two");
1540         SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1541         TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1542     }
1543 
1544 }