49 |
|
* are typically useful only when a map is not undergoing concurrent |
50 |
|
* updates in other threads. Otherwise the results of these methods |
51 |
|
* reflect transient states that may be adequate for monitoring |
52 |
< |
* purposes, but not for program control. |
52 |
> |
* or estimation purposes, but not for program control. |
53 |
|
* |
54 |
< |
* <p> Resizing this or any other kind of hash table is a relatively |
55 |
< |
* slow operation, so, when possible, it is a good idea to provide |
56 |
< |
* estimates of expected table sizes in constructors. Also, for |
57 |
< |
* compatibility with previous versions of this class, constructors |
58 |
< |
* may optionally specify an expected {@code concurrencyLevel} as an |
59 |
< |
* additional hint for internal sizing. |
54 |
> |
* <p> The table is dynamically expanded when there are too many |
55 |
> |
* collisions (i.e., keys that have distinct hash codes but fall into |
56 |
> |
* the same slot modulo the table size), with the expected average |
57 |
> |
* effect of maintaining roughly two bins per mapping. There may be |
58 |
> |
* much variance around this average as mappings are added and |
59 |
> |
* removed, but overall, this maintains a commonly accepted time/space |
60 |
> |
* tradeoff for hash tables. However, resizing this or any other kind |
61 |
> |
* of hash table may be a relatively slow operation. When possible, it |
62 |
> |
* is a good idea to provide a size estimate as an optional {@code |
63 |
> |
* initialCapacity} constructor argument. An additional optional |
64 |
> |
* {@code loadFactor} constructor argument provides a further means of |
65 |
> |
* customizing initial table capacity by specifying the table density |
66 |
> |
* to be used in calculating the amount of space to allocate for the |
67 |
> |
* given number of elements. Also, for compatibility with previous |
68 |
> |
* versions of this class, constructors may optionally specify an |
69 |
> |
* expected {@code concurrencyLevel} as an additional hint for |
70 |
> |
* internal sizing. Note that using many keys with exactly the same |
71 |
> |
* {@code hashCode{}} is a sure way to slow down performance of any |
72 |
> |
* hash table. |
73 |
|
* |
74 |
|
* <p>This class and its views and iterators implement all of the |
75 |
|
* <em>optional</em> methods of the {@link Map} and {@link Iterator} |
169 |
|
* of alternatives: Under random hash codes, the frequency of |
170 |
|
* nodes in bins follows a Poisson distribution |
171 |
|
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a |
172 |
< |
* parameter of 0.5 on average under the default loadFactor of |
173 |
< |
* 0.75. The expected number of locks covering different elements |
174 |
< |
* (i.e., bins with 2 or more nodes) is approximately 10% at |
175 |
< |
* steady state. Lock contention probability for two threads |
176 |
< |
* accessing distinct elements is roughly 1 / (8 * #elements). |
177 |
< |
* Function "spread" performs hashCode randomization that improves |
178 |
< |
* the likelihood that these assumptions hold unless users define |
179 |
< |
* exactly the same value for too many hashCodes. |
172 |
> |
* parameter of about 0.5 on average, given the resizing threshold |
173 |
> |
* of 0.75, although with a large variance because of resizing |
174 |
> |
* granularity. Ignoring variance, the expected occurrences of |
175 |
> |
* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The |
176 |
> |
* first few values are: |
177 |
> |
* |
178 |
> |
* 0: 0.607 |
179 |
> |
* 1: 0.303 |
180 |
> |
* 2: 0.076 |
181 |
> |
* 3: 0.012 |
182 |
> |
* more: 0.002 |
183 |
> |
* |
184 |
> |
* Lock contention probability for two threads accessing distinct |
185 |
> |
* elements is roughly 1 / (8 * #elements). Function "spread" |
186 |
> |
* performs hashCode randomization that improves the likelihood |
187 |
> |
* that these assumptions hold unless users define exactly the |
188 |
> |
* same value for too many hashCodes. |
189 |
|
* |
190 |
|
* The table is resized when occupancy exceeds a threshold. Only |
191 |
|
* a single thread performs the resize (using field "resizing", to |
219 |
|
* and also avoids resizings when the first operation is from a |
220 |
|
* putAll, constructor with map argument, or deserialization. |
221 |
|
* These cases attempt to override the targetCapacity used in |
222 |
< |
* growTable (which may harmlessly fail to take effect in cases of |
223 |
< |
* races with other ongoing resizings). |
222 |
> |
* growTable. These harmlessly fail to take effect in cases of |
223 |
> |
* races with other ongoing resizings. Uses of the threshold and |
224 |
> |
* targetCapacity during attempted initializations or resizings |
225 |
> |
* are racy but fall back on checks to preserve correctness. |
226 |
|
* |
227 |
|
* The element count is maintained using a LongAdder, which avoids |
228 |
|
* contention on updates but can encounter cache thrashing if read |
229 |
|
* too frequently during concurrent access. To avoid reading so |
230 |
|
* often, resizing is normally attempted only upon adding to a bin |
231 |
< |
* already holding two or more nodes. Under the default load |
232 |
< |
* factor and uniform hash distributions, the probability of this |
233 |
< |
* occurring at threshold is around 13%, meaning that only about 1 |
234 |
< |
* in 8 puts check threshold (and after resizing, many fewer do |
235 |
< |
* so). But this approximation has high variance for small table |
236 |
< |
* sizes, so we check on any collision for sizes <= 64. Further, |
237 |
< |
* to increase the probability that a resize occurs soon enough, |
238 |
< |
* we offset the threshold (see THRESHOLD_OFFSET) by the expected |
239 |
< |
* number of puts between checks. This is currently set to 8, in |
216 |
< |
* accord with the default load factor. In practice, this default |
217 |
< |
* is rarely overridden, and in any case is close enough to other |
218 |
< |
* plausible values not to waste dynamic probability computation |
219 |
< |
* for the sake of more precision. |
231 |
> |
* already holding two or more nodes. Under uniform hash |
232 |
> |
* distributions, the probability of this occurring at threshold |
233 |
> |
* is around 13%, meaning that only about 1 in 8 puts check |
234 |
> |
* threshold (and after resizing, many fewer do so). But this |
235 |
> |
* approximation has high variance for small table sizes, so we |
236 |
> |
* check on any collision for sizes <= 64. Further, to increase |
237 |
> |
* the probability that a resize occurs soon enough, we offset the |
238 |
> |
* threshold (see THRESHOLD_OFFSET) by the expected number of puts |
239 |
> |
* between checks. |
240 |
|
* |
241 |
|
* Maintaining API and serialization compatibility with previous |
242 |
|
* versions of this class introduces several oddities. Mainly: We |
248 |
|
/* ---------------- Constants -------------- */ |
249 |
|
|
250 |
|
/** |
251 |
< |
* The largest allowed table capacity. Must be a power of 2, at |
252 |
< |
* most 1<<30 to stay within Java array size limits. |
251 |
> |
* The largest possible table capacity. This value must be |
252 |
> |
* exactly 1<<30 to stay within Java array allocation and indexing |
253 |
> |
* bounds for power of two table sizes. |
254 |
|
*/ |
255 |
|
private static final int MAXIMUM_CAPACITY = 1 << 30; |
256 |
|
|
261 |
|
private static final int DEFAULT_CAPACITY = 16; |
262 |
|
|
263 |
|
/** |
264 |
< |
* The default load factor for this table, used when not otherwise |
265 |
< |
* specified in a constructor. |
264 |
> |
* The load factor for this table. Overrides of this value in |
265 |
> |
* constructors affect only the initial table capacity. The |
266 |
> |
* actual floating point value isn't normally used, because it is |
267 |
> |
* simpler to rely on the expression {@code n - (n >>> 2)} for the |
268 |
> |
* associated resizing threshold. |
269 |
|
*/ |
270 |
< |
private static final float DEFAULT_LOAD_FACTOR = 0.75f; |
247 |
< |
|
248 |
< |
/** |
249 |
< |
* The default concurrency level for this table. Unused, but |
250 |
< |
* defined for compatibility with previous versions of this class. |
251 |
< |
*/ |
252 |
< |
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; |
270 |
> |
private static final float LOAD_FACTOR = 0.75f; |
271 |
|
|
272 |
|
/** |
273 |
|
* The count value to offset thresholds to compensate for checking |
276 |
|
*/ |
277 |
|
private static final int THRESHOLD_OFFSET = 8; |
278 |
|
|
279 |
+ |
/** |
280 |
+ |
* The default concurrency level for this table. Unused except as |
281 |
+ |
* a sizing hint, but defined for compatibility with previous |
282 |
+ |
* versions of this class. |
283 |
+ |
*/ |
284 |
+ |
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; |
285 |
+ |
|
286 |
|
/* ---------------- Nodes -------------- */ |
287 |
|
|
288 |
|
/** |
330 |
|
private transient int threshold; |
331 |
|
/** The target capacity; volatile to cover initialization races. */ |
332 |
|
private transient volatile int targetCapacity; |
308 |
– |
/** The target load factor for the table */ |
309 |
– |
private transient final float loadFactor; |
333 |
|
|
334 |
|
// views |
335 |
|
private transient KeySet<K,V> keySet; |
396 |
|
try { |
397 |
|
for (;;) { |
398 |
|
Node[] tab = table; |
399 |
< |
int n, c; |
399 |
> |
int n, c, m; |
400 |
|
if (tab == null) |
401 |
|
n = (c = targetCapacity) > 0 ? c : DEFAULT_CAPACITY; |
402 |
< |
else if ((n = tab.length) < MAXIMUM_CAPACITY && |
403 |
< |
counter.sum() >= threshold) |
404 |
< |
n <<= 1; |
402 |
> |
else if ((m = tab.length) < MAXIMUM_CAPACITY && |
403 |
> |
counter.sum() >= (long)threshold) |
404 |
> |
n = m << 1; |
405 |
|
else |
406 |
|
break; |
407 |
+ |
threshold = n - (n >>> 2) - THRESHOLD_OFFSET; |
408 |
|
Node[] nextTab = new Node[n]; |
385 |
– |
threshold = (int)(n * loadFactor) - THRESHOLD_OFFSET; |
409 |
|
if (tab != null) |
410 |
|
transfer(tab, nextTab, |
411 |
|
new Node(SIGN_BIT, nextTab, null, null)); |
428 |
|
* either stay at same index, or move with a power of two |
429 |
|
* offset. We eliminate unnecessary node creation by catching |
430 |
|
* cases where old nodes can be reused because their next fields |
431 |
< |
* won't change. Statistically, at the default loadFactor, only |
432 |
< |
* about one-sixth of them need cloning when a table doubles. The |
433 |
< |
* nodes they replace will be garbage collectable as soon as they |
434 |
< |
* are no longer referenced by any reader thread that may be in |
435 |
< |
* the midst of concurrently traversing table. |
431 |
> |
* won't change. Statistically, only about one-sixth of them need |
432 |
> |
* cloning when a table doubles. The nodes they replace will be |
433 |
> |
* garbage collectable as soon as they are no longer referenced by |
434 |
> |
* any reader thread that may be in the midst of concurrently |
435 |
> |
* traversing table. |
436 |
|
* |
437 |
|
* Transfers are done from the bottom up to preserve iterator |
438 |
|
* traversability. On each step, the old bin is locked, |
570 |
|
} |
571 |
|
if (validated) { |
572 |
|
if (checkSize && tab.length < MAXIMUM_CAPACITY && |
573 |
< |
resizing == 0 && counter.sum() >= threshold) |
573 |
> |
resizing == 0 && counter.sum() >= (long)threshold) |
574 |
|
growTable(); |
575 |
|
break; |
576 |
|
} |
709 |
|
} |
710 |
|
if (validated) { |
711 |
|
if (checkSize && tab.length < MAXIMUM_CAPACITY && |
712 |
< |
resizing == 0 && counter.sum() >= threshold) |
712 |
> |
resizing == 0 && counter.sum() >= (long)threshold) |
713 |
|
growTable(); |
714 |
|
break; |
715 |
|
} |
851 |
|
/* ---------------- Public operations -------------- */ |
852 |
|
|
853 |
|
/** |
854 |
< |
* Creates a new, empty map with the specified initial |
832 |
< |
* capacity, load factor and concurrency level. |
833 |
< |
* |
834 |
< |
* @param initialCapacity the initial capacity. The implementation |
835 |
< |
* performs internal sizing to accommodate this many elements. |
836 |
< |
* @param loadFactor the load factor threshold, used to control resizing. |
837 |
< |
* Resizing may be performed when the average number of elements per |
838 |
< |
* bin exceeds this threshold. |
839 |
< |
* @param concurrencyLevel the estimated number of concurrently |
840 |
< |
* updating threads. The implementation may use this value as |
841 |
< |
* a sizing hint. |
842 |
< |
* @throws IllegalArgumentException if the initial capacity is |
843 |
< |
* negative or the load factor or concurrencyLevel are |
844 |
< |
* nonpositive. |
854 |
> |
* Creates a new, empty map with the default initial table size (16), |
855 |
|
*/ |
856 |
< |
public ConcurrentHashMapV8(int initialCapacity, |
847 |
< |
float loadFactor, int concurrencyLevel) { |
848 |
< |
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) |
849 |
< |
throw new IllegalArgumentException(); |
850 |
< |
int cap = tableSizeFor(initialCapacity); |
856 |
> |
public ConcurrentHashMapV8() { |
857 |
|
this.counter = new LongAdder(); |
858 |
< |
this.loadFactor = loadFactor; |
853 |
< |
this.targetCapacity = cap; |
858 |
> |
this.targetCapacity = DEFAULT_CAPACITY; |
859 |
|
} |
860 |
|
|
861 |
|
/** |
862 |
< |
* Creates a new, empty map with the specified initial capacity |
863 |
< |
* and load factor and with the default concurrencyLevel (16). |
862 |
> |
* Creates a new, empty map with an initial table size |
863 |
> |
* accommodating the specified number of elements without the need |
864 |
> |
* to dynamically resize. |
865 |
|
* |
866 |
|
* @param initialCapacity The implementation performs internal |
867 |
|
* sizing to accommodate this many elements. |
862 |
– |
* @param loadFactor the load factor threshold, used to control resizing. |
863 |
– |
* Resizing may be performed when the average number of elements per |
864 |
– |
* bin exceeds this threshold. |
868 |
|
* @throws IllegalArgumentException if the initial capacity of |
869 |
< |
* elements is negative or the load factor is nonpositive |
867 |
< |
* |
868 |
< |
* @since 1.6 |
869 |
> |
* elements is negative. |
870 |
|
*/ |
871 |
< |
public ConcurrentHashMapV8(int initialCapacity, float loadFactor) { |
872 |
< |
this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL); |
871 |
> |
public ConcurrentHashMapV8(int initialCapacity) { |
872 |
> |
if (initialCapacity < 0) |
873 |
> |
throw new IllegalArgumentException(); |
874 |
> |
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? |
875 |
> |
MAXIMUM_CAPACITY : |
876 |
> |
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); |
877 |
> |
this.counter = new LongAdder(); |
878 |
> |
this.targetCapacity = cap; |
879 |
|
} |
880 |
|
|
881 |
|
/** |
882 |
< |
* Creates a new, empty map with the specified initial capacity, |
876 |
< |
* and with default load factor (0.75) and concurrencyLevel (16). |
882 |
> |
* Creates a new map with the same mappings as the given map. |
883 |
|
* |
884 |
< |
* @param initialCapacity the initial capacity. The implementation |
879 |
< |
* performs internal sizing to accommodate this many elements. |
880 |
< |
* @throws IllegalArgumentException if the initial capacity of |
881 |
< |
* elements is negative. |
884 |
> |
* @param m the map |
885 |
|
*/ |
886 |
< |
public ConcurrentHashMapV8(int initialCapacity) { |
887 |
< |
this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); |
886 |
> |
public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) { |
887 |
> |
this.counter = new LongAdder(); |
888 |
> |
this.targetCapacity = DEFAULT_CAPACITY; |
889 |
> |
putAll(m); |
890 |
|
} |
891 |
|
|
892 |
|
/** |
893 |
< |
* Creates a new, empty map with a default initial capacity (16), |
894 |
< |
* load factor (0.75) and concurrencyLevel (16). |
893 |
> |
* Creates a new, empty map with an initial table size based on |
894 |
> |
* the given number of elements ({@code initialCapacity}) and |
895 |
> |
* initial table density ({@code loadFactor}). |
896 |
> |
* |
897 |
> |
* @param initialCapacity the initial capacity. The implementation |
898 |
> |
* performs internal sizing to accommodate this many elements, |
899 |
> |
* given the specified load factor. |
900 |
> |
* @param loadFactor the load factor (table density) for |
901 |
> |
* establishing the initial table size. |
902 |
> |
* @throws IllegalArgumentException if the initial capacity of |
903 |
> |
* elements is negative or the load factor is nonpositive |
904 |
> |
* |
905 |
> |
* @since 1.6 |
906 |
|
*/ |
907 |
< |
public ConcurrentHashMapV8() { |
908 |
< |
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); |
907 |
> |
public ConcurrentHashMapV8(int initialCapacity, float loadFactor) { |
908 |
> |
this(initialCapacity, loadFactor, 1); |
909 |
|
} |
910 |
|
|
911 |
|
/** |
912 |
< |
* Creates a new map with the same mappings as the given map. |
913 |
< |
* The map is created with a capacity of 1.5 times the number |
914 |
< |
* of mappings in the given map or 16 (whichever is greater), |
915 |
< |
* and a default load factor (0.75) and concurrencyLevel (16). |
912 |
> |
* Creates a new, empty map with an initial table size based on |
913 |
> |
* the given number of elements ({@code initialCapacity}), table |
914 |
> |
* density ({@code loadFactor}), and number of concurrently |
915 |
> |
* updating threads ({@code concurrencyLevel}). |
916 |
|
* |
917 |
< |
* @param m the map |
917 |
> |
* @param initialCapacity the initial capacity. The implementation |
918 |
> |
* performs internal sizing to accommodate this many elements, |
919 |
> |
* given the specified load factor. |
920 |
> |
* @param loadFactor the load factor (table density) for |
921 |
> |
* establishing the initial table size. |
922 |
> |
* @param concurrencyLevel the estimated number of concurrently |
923 |
> |
* updating threads. The implementation may use this value as |
924 |
> |
* a sizing hint. |
925 |
> |
* @throws IllegalArgumentException if the initial capacity is |
926 |
> |
* negative or the load factor or concurrencyLevel are |
927 |
> |
* nonpositive. |
928 |
|
*/ |
929 |
< |
public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) { |
930 |
< |
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); |
931 |
< |
putAll(m); |
929 |
> |
public ConcurrentHashMapV8(int initialCapacity, |
930 |
> |
float loadFactor, int concurrencyLevel) { |
931 |
> |
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) |
932 |
> |
throw new IllegalArgumentException(); |
933 |
> |
if (initialCapacity < concurrencyLevel) // Use at least as many bins |
934 |
> |
initialCapacity = concurrencyLevel; // as estimated threads |
935 |
> |
long size = (long)(1.0 + (long)initialCapacity / loadFactor); |
936 |
> |
int cap = ((size >= (long)MAXIMUM_CAPACITY) ? |
937 |
> |
MAXIMUM_CAPACITY: tableSizeFor((int)size)); |
938 |
> |
this.counter = new LongAdder(); |
939 |
> |
this.targetCapacity = cap; |
940 |
|
} |
941 |
|
|
942 |
|
/** |
1082 |
|
if (table == null) { |
1083 |
|
int size = m.size(); |
1084 |
|
int cap = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : |
1085 |
< |
tableSizeFor(size + (size >>> 1)); |
1085 |
> |
tableSizeFor(size + (size >>> 1) + 1); |
1086 |
|
if (cap > targetCapacity) |
1087 |
|
targetCapacity = cap; |
1088 |
|
} |
1601 |
|
segments = (Segment<K,V>[]) |
1602 |
|
new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL]; |
1603 |
|
for (int i = 0; i < segments.length; ++i) |
1604 |
< |
segments[i] = new Segment<K,V>(DEFAULT_LOAD_FACTOR); |
1604 |
> |
segments[i] = new Segment<K,V>(LOAD_FACTOR); |
1605 |
|
} |
1606 |
|
s.defaultWriteObject(); |
1607 |
|
InternalIterator it = new InternalIterator(table); |
1624 |
|
throws java.io.IOException, ClassNotFoundException { |
1625 |
|
s.defaultReadObject(); |
1626 |
|
this.segments = null; // unneeded |
1627 |
< |
// initalize transient final fields |
1627 |
> |
// initalize transient final field |
1628 |
|
UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder()); |
1595 |
– |
UNSAFE.putFloatVolatile(this, loadFactorOffset, DEFAULT_LOAD_FACTOR); |
1629 |
|
this.targetCapacity = DEFAULT_CAPACITY; |
1630 |
|
|
1631 |
|
// Create all nodes, then place in table once size is known |
1653 |
|
n = MAXIMUM_CAPACITY; |
1654 |
|
else { |
1655 |
|
int sz = (int)size; |
1656 |
< |
n = tableSizeFor(sz + (sz >>> 1)); |
1656 |
> |
n = tableSizeFor(sz + (sz >>> 1) + 1); |
1657 |
|
} |
1658 |
< |
threshold = (n - (n >>> 2)) - THRESHOLD_OFFSET; |
1658 |
> |
threshold = n - (n >>> 2) - THRESHOLD_OFFSET; |
1659 |
|
Node[] tab = new Node[n]; |
1660 |
|
int mask = n - 1; |
1661 |
|
while (p != null) { |
1684 |
|
// Unsafe mechanics |
1685 |
|
private static final sun.misc.Unsafe UNSAFE; |
1686 |
|
private static final long counterOffset; |
1654 |
– |
private static final long loadFactorOffset; |
1687 |
|
private static final long resizingOffset; |
1688 |
|
private static final long ABASE; |
1689 |
|
private static final int ASHIFT; |
1695 |
|
Class<?> k = ConcurrentHashMapV8.class; |
1696 |
|
counterOffset = UNSAFE.objectFieldOffset |
1697 |
|
(k.getDeclaredField("counter")); |
1666 |
– |
loadFactorOffset = UNSAFE.objectFieldOffset |
1667 |
– |
(k.getDeclaredField("loadFactor")); |
1698 |
|
resizingOffset = UNSAFE.objectFieldOffset |
1699 |
|
(k.getDeclaredField("resizing")); |
1700 |
|
Class<?> sc = Node[].class; |