Print this page
Split |
Close |
Expand all |
Collapse all |
--- old/src/share/classes/java/util/concurrent/ConcurrentHashMap.java
+++ new/src/share/classes/java/util/concurrent/ConcurrentHashMap.java
1 1 /*
2 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 3 *
4 4 * This code is free software; you can redistribute it and/or modify it
5 5 * under the terms of the GNU General Public License version 2 only, as
6 6 * published by the Free Software Foundation. Oracle designates this
7 7 * particular file as subject to the "Classpath" exception as provided
8 8 * by Oracle in the LICENSE file that accompanied this code.
9 9 *
10 10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 13 * version 2 for more details (a copy is included in the LICENSE file that
14 14 * accompanied this code).
15 15 *
16 16 * You should have received a copy of the GNU General Public License version
17 17 * 2 along with this work; if not, write to the Free Software Foundation,
18 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 19 *
20 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 21 * or visit www.oracle.com if you need additional information or have any
22 22 * questions.
23 23 */
24 24
25 25 /*
26 26 * This file is available under and governed by the GNU General Public
27 27 * License version 2 only, as published by the Free Software Foundation.
28 28 * However, the following notice accompanied the original version of this
29 29 * file:
30 30 *
31 31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 32 * Expert Group and released to the public domain, as explained at
33 33 * http://creativecommons.org/licenses/publicdomain
34 34 */
35 35
36 36 package java.util.concurrent;
37 37 import java.util.concurrent.locks.*;
38 38 import java.util.*;
39 39 import java.io.Serializable;
40 40 import java.io.IOException;
41 41 import java.io.ObjectInputStream;
42 42 import java.io.ObjectOutputStream;
43 43
44 44 /**
45 45 * A hash table supporting full concurrency of retrievals and
46 46 * adjustable expected concurrency for updates. This class obeys the
47 47 * same functional specification as {@link java.util.Hashtable}, and
48 48 * includes versions of methods corresponding to each method of
49 49 * <tt>Hashtable</tt>. However, even though all operations are
50 50 * thread-safe, retrieval operations do <em>not</em> entail locking,
51 51 * and there is <em>not</em> any support for locking the entire table
52 52 * in a way that prevents all access. This class is fully
53 53 * interoperable with <tt>Hashtable</tt> in programs that rely on its
54 54 * thread safety but not on its synchronization details.
55 55 *
56 56 * <p> Retrieval operations (including <tt>get</tt>) generally do not
57 57 * block, so may overlap with update operations (including
58 58 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
59 59 * of the most recently <em>completed</em> update operations holding
60 60 * upon their onset. For aggregate operations such as <tt>putAll</tt>
61 61 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
62 62 * removal of only some entries. Similarly, Iterators and
63 63 * Enumerations return elements reflecting the state of the hash table
64 64 * at some point at or since the creation of the iterator/enumeration.
65 65 * They do <em>not</em> throw {@link ConcurrentModificationException}.
66 66 * However, iterators are designed to be used by only one thread at a time.
67 67 *
68 68 * <p> The allowed concurrency among update operations is guided by
69 69 * the optional <tt>concurrencyLevel</tt> constructor argument
70 70 * (default <tt>16</tt>), which is used as a hint for internal sizing. The
71 71 * table is internally partitioned to try to permit the indicated
72 72 * number of concurrent updates without contention. Because placement
73 73 * in hash tables is essentially random, the actual concurrency will
74 74 * vary. Ideally, you should choose a value to accommodate as many
75 75 * threads as will ever concurrently modify the table. Using a
76 76 * significantly higher value than you need can waste space and time,
77 77 * and a significantly lower value can lead to thread contention. But
78 78 * overestimates and underestimates within an order of magnitude do
79 79 * not usually have much noticeable impact. A value of one is
80 80 * appropriate when it is known that only one thread will modify and
81 81 * all others will only read. Also, resizing this or any other kind of
82 82 * hash table is a relatively slow operation, so, when possible, it is
83 83 * a good idea to provide estimates of expected table sizes in
84 84 * constructors.
85 85 *
86 86 * <p>This class and its views and iterators implement all of the
87 87 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
88 88 * interfaces.
89 89 *
90 90 * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
91 91 * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
92 92 *
93 93 * <p>This class is a member of the
94 94 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
95 95 * Java Collections Framework</a>.
96 96 *
97 97 * @since 1.5
98 98 * @author Doug Lea
99 99 * @param <K> the type of keys maintained by this map
100 100 * @param <V> the type of mapped values
101 101 */
102 102 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
103 103 implements ConcurrentMap<K, V>, Serializable {
104 104 private static final long serialVersionUID = 7249069246763182397L;
105 105
106 106 /*
107 107 * The basic strategy is to subdivide the table among Segments,
108 108 * each of which itself is a concurrently readable hash table.
109 109 */
110 110
111 111 /* ---------------- Constants -------------- */
112 112
113 113 /**
114 114 * The default initial capacity for this table,
115 115 * used when not otherwise specified in a constructor.
116 116 */
117 117 static final int DEFAULT_INITIAL_CAPACITY = 16;
118 118
119 119 /**
120 120 * The default load factor for this table, used when not
121 121 * otherwise specified in a constructor.
122 122 */
123 123 static final float DEFAULT_LOAD_FACTOR = 0.75f;
124 124
125 125 /**
126 126 * The default concurrency level for this table, used when not
127 127 * otherwise specified in a constructor.
128 128 */
129 129 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
130 130
131 131 /**
132 132 * The maximum capacity, used if a higher value is implicitly
133 133 * specified by either of the constructors with arguments. MUST
134 134 * be a power of two <= 1<<30 to ensure that entries are indexable
135 135 * using ints.
136 136 */
137 137 static final int MAXIMUM_CAPACITY = 1 << 30;
138 138
139 139 /**
140 140 * The maximum number of segments to allow; used to bound
141 141 * constructor arguments.
142 142 */
143 143 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
144 144
145 145 /**
146 146 * Number of unsynchronized retries in size and containsValue
147 147 * methods before resorting to locking. This is used to avoid
148 148 * unbounded retries if tables undergo continuous modification
149 149 * which would make it impossible to obtain an accurate result.
150 150 */
151 151 static final int RETRIES_BEFORE_LOCK = 2;
152 152
153 153 /* ---------------- Fields -------------- */
154 154
155 155 /**
156 156 * Mask value for indexing into segments. The upper bits of a
157 157 * key's hash code are used to choose the segment.
158 158 */
159 159 final int segmentMask;
160 160
161 161 /**
162 162 * Shift value for indexing within segments.
163 163 */
164 164 final int segmentShift;
165 165
166 166 /**
167 167 * The segments, each of which is a specialized hash table
168 168 */
169 169 final Segment<K,V>[] segments;
170 170
171 171 transient Set<K> keySet;
172 172 transient Set<Map.Entry<K,V>> entrySet;
173 173 transient Collection<V> values;
174 174
175 175 /* ---------------- Small Utilities -------------- */
176 176
177 177 /**
178 178 * Applies a supplemental hash function to a given hashCode, which
179 179 * defends against poor quality hash functions. This is critical
180 180 * because ConcurrentHashMap uses power-of-two length hash tables,
181 181 * that otherwise encounter collisions for hashCodes that do not
182 182 * differ in lower or upper bits.
183 183 */
184 184 private static int hash(int h) {
185 185 // Spread bits to regularize both segment and index locations,
186 186 // using variant of single-word Wang/Jenkins hash.
187 187 h += (h << 15) ^ 0xffffcd7d;
188 188 h ^= (h >>> 10);
189 189 h += (h << 3);
190 190 h ^= (h >>> 6);
191 191 h += (h << 2) + (h << 14);
192 192 return h ^ (h >>> 16);
193 193 }
194 194
195 195 /**
196 196 * Returns the segment that should be used for key with given hash
197 197 * @param hash the hash code for the key
198 198 * @return the segment
199 199 */
200 200 final Segment<K,V> segmentFor(int hash) {
201 201 return segments[(hash >>> segmentShift) & segmentMask];
202 202 }
203 203
204 204 /* ---------------- Inner Classes -------------- */
205 205
206 206 /**
207 207 * ConcurrentHashMap list entry. Note that this is never exported
208 208 * out as a user-visible Map.Entry.
209 209 *
210 210 * Because the value field is volatile, not final, it is legal wrt
211 211 * the Java Memory Model for an unsynchronized reader to see null
212 212 * instead of initial value when read via a data race. Although a
213 213 * reordering leading to this is not likely to ever actually
214 214 * occur, the Segment.readValueUnderLock method is used as a
215 215 * backup in case a null (pre-initialized) value is ever seen in
216 216 * an unsynchronized access method.
217 217 */
218 218 static final class HashEntry<K,V> {
219 219 final K key;
220 220 final int hash;
221 221 volatile V value;
222 222 final HashEntry<K,V> next;
223 223
224 224 HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
225 225 this.key = key;
226 226 this.hash = hash;
227 227 this.next = next;
228 228 this.value = value;
229 229 }
230 230
231 231 @SuppressWarnings("unchecked")
232 232 static final <K,V> HashEntry<K,V>[] newArray(int i) {
233 233 return new HashEntry[i];
234 234 }
235 235 }
236 236
237 237 /**
238 238 * Segments are specialized versions of hash tables. This
239 239 * subclasses from ReentrantLock opportunistically, just to
240 240 * simplify some locking and avoid separate construction.
241 241 */
242 242 static final class Segment<K,V> extends ReentrantLock implements Serializable {
243 243 /*
244 244 * Segments maintain a table of entry lists that are ALWAYS
245 245 * kept in a consistent state, so can be read without locking.
246 246 * Next fields of nodes are immutable (final). All list
247 247 * additions are performed at the front of each bin. This
248 248 * makes it easy to check changes, and also fast to traverse.
249 249 * When nodes would otherwise be changed, new nodes are
250 250 * created to replace them. This works well for hash tables
251 251 * since the bin lists tend to be short. (The average length
252 252 * is less than two for the default load factor threshold.)
253 253 *
254 254 * Read operations can thus proceed without locking, but rely
255 255 * on selected uses of volatiles to ensure that completed
256 256 * write operations performed by other threads are
257 257 * noticed. For most purposes, the "count" field, tracking the
258 258 * number of elements, serves as that volatile variable
259 259 * ensuring visibility. This is convenient because this field
260 260 * needs to be read in many read operations anyway:
261 261 *
262 262 * - All (unsynchronized) read operations must first read the
263 263 * "count" field, and should not look at table entries if
264 264 * it is 0.
265 265 *
266 266 * - All (synchronized) write operations should write to
267 267 * the "count" field after structurally changing any bin.
268 268 * The operations must not take any action that could even
269 269 * momentarily cause a concurrent read operation to see
270 270 * inconsistent data. This is made easier by the nature of
271 271 * the read operations in Map. For example, no operation
272 272 * can reveal that the table has grown but the threshold
273 273 * has not yet been updated, so there are no atomicity
274 274 * requirements for this with respect to reads.
275 275 *
276 276 * As a guide, all critical volatile reads and writes to the
277 277 * count field are marked in code comments.
278 278 */
279 279
280 280 private static final long serialVersionUID = 2249069246763182397L;
281 281
282 282 /**
283 283 * The number of elements in this segment's region.
284 284 */
285 285 transient volatile int count;
286 286
287 287 /**
288 288 * Number of updates that alter the size of the table. This is
289 289 * used during bulk-read methods to make sure they see a
290 290 * consistent snapshot: If modCounts change during a traversal
291 291 * of segments computing size or checking containsValue, then
292 292 * we might have an inconsistent view of state so (usually)
293 293 * must retry.
294 294 */
295 295 transient int modCount;
296 296
297 297 /**
298 298 * The table is rehashed when its size exceeds this threshold.
299 299 * (The value of this field is always <tt>(int)(capacity *
300 300 * loadFactor)</tt>.)
301 301 */
302 302 transient int threshold;
303 303
304 304 /**
305 305 * The per-segment table.
306 306 */
307 307 transient volatile HashEntry<K,V>[] table;
308 308
309 309 /**
310 310 * The load factor for the hash table. Even though this value
311 311 * is same for all segments, it is replicated to avoid needing
312 312 * links to outer object.
313 313 * @serial
314 314 */
315 315 final float loadFactor;
316 316
317 317 Segment(int initialCapacity, float lf) {
318 318 loadFactor = lf;
319 319 setTable(HashEntry.<K,V>newArray(initialCapacity));
320 320 }
321 321
322 322 @SuppressWarnings("unchecked")
323 323 static final <K,V> Segment<K,V>[] newArray(int i) {
324 324 return new Segment[i];
325 325 }
326 326
327 327 /**
328 328 * Sets table to new HashEntry array.
329 329 * Call only while holding lock or in constructor.
330 330 */
331 331 void setTable(HashEntry<K,V>[] newTable) {
332 332 threshold = (int)(newTable.length * loadFactor);
333 333 table = newTable;
334 334 }
335 335
336 336 /**
337 337 * Returns properly casted first entry of bin for given hash.
338 338 */
339 339 HashEntry<K,V> getFirst(int hash) {
340 340 HashEntry<K,V>[] tab = table;
341 341 return tab[hash & (tab.length - 1)];
342 342 }
343 343
344 344 /**
345 345 * Reads value field of an entry under lock. Called if value
346 346 * field ever appears to be null. This is possible only if a
347 347 * compiler happens to reorder a HashEntry initialization with
348 348 * its table assignment, which is legal under memory model
349 349 * but is not known to ever occur.
350 350 */
351 351 V readValueUnderLock(HashEntry<K,V> e) {
352 352 lock();
353 353 try {
354 354 return e.value;
355 355 } finally {
356 356 unlock();
357 357 }
358 358 }
359 359
360 360 /* Specialized implementations of map methods */
361 361
362 362 V get(Object key, int hash) {
363 363 if (count != 0) { // read-volatile
364 364 HashEntry<K,V> e = getFirst(hash);
365 365 while (e != null) {
366 366 if (e.hash == hash && key.equals(e.key)) {
367 367 V v = e.value;
368 368 if (v != null)
369 369 return v;
370 370 return readValueUnderLock(e); // recheck
371 371 }
372 372 e = e.next;
373 373 }
374 374 }
375 375 return null;
376 376 }
377 377
378 378 boolean containsKey(Object key, int hash) {
379 379 if (count != 0) { // read-volatile
380 380 HashEntry<K,V> e = getFirst(hash);
381 381 while (e != null) {
382 382 if (e.hash == hash && key.equals(e.key))
383 383 return true;
384 384 e = e.next;
385 385 }
386 386 }
387 387 return false;
388 388 }
389 389
390 390 boolean containsValue(Object value) {
391 391 if (count != 0) { // read-volatile
392 392 HashEntry<K,V>[] tab = table;
393 393 int len = tab.length;
394 394 for (int i = 0 ; i < len; i++) {
395 395 for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
396 396 V v = e.value;
397 397 if (v == null) // recheck
398 398 v = readValueUnderLock(e);
399 399 if (value.equals(v))
400 400 return true;
401 401 }
402 402 }
403 403 }
404 404 return false;
405 405 }
406 406
407 407 boolean replace(K key, int hash, V oldValue, V newValue) {
408 408 lock();
409 409 try {
410 410 HashEntry<K,V> e = getFirst(hash);
411 411 while (e != null && (e.hash != hash || !key.equals(e.key)))
412 412 e = e.next;
413 413
414 414 boolean replaced = false;
415 415 if (e != null && oldValue.equals(e.value)) {
416 416 replaced = true;
417 417 e.value = newValue;
418 418 }
419 419 return replaced;
420 420 } finally {
421 421 unlock();
422 422 }
423 423 }
424 424
425 425 V replace(K key, int hash, V newValue) {
426 426 lock();
427 427 try {
428 428 HashEntry<K,V> e = getFirst(hash);
429 429 while (e != null && (e.hash != hash || !key.equals(e.key)))
430 430 e = e.next;
431 431
432 432 V oldValue = null;
433 433 if (e != null) {
434 434 oldValue = e.value;
435 435 e.value = newValue;
436 436 }
437 437 return oldValue;
438 438 } finally {
439 439 unlock();
440 440 }
441 441 }
442 442
443 443
444 444 V put(K key, int hash, V value, boolean onlyIfAbsent) {
445 445 lock();
446 446 try {
447 447 int c = count;
448 448 if (c++ > threshold) // ensure capacity
449 449 rehash();
450 450 HashEntry<K,V>[] tab = table;
451 451 int index = hash & (tab.length - 1);
452 452 HashEntry<K,V> first = tab[index];
453 453 HashEntry<K,V> e = first;
454 454 while (e != null && (e.hash != hash || !key.equals(e.key)))
455 455 e = e.next;
456 456
457 457 V oldValue;
458 458 if (e != null) {
459 459 oldValue = e.value;
460 460 if (!onlyIfAbsent)
461 461 e.value = value;
462 462 }
463 463 else {
464 464 oldValue = null;
465 465 ++modCount;
466 466 tab[index] = new HashEntry<K,V>(key, hash, first, value);
467 467 count = c; // write-volatile
468 468 }
469 469 return oldValue;
470 470 } finally {
471 471 unlock();
472 472 }
473 473 }
474 474
475 475 void rehash() {
476 476 HashEntry<K,V>[] oldTable = table;
477 477 int oldCapacity = oldTable.length;
478 478 if (oldCapacity >= MAXIMUM_CAPACITY)
479 479 return;
480 480
481 481 /*
482 482 * Reclassify nodes in each list to new Map. Because we are
483 483 * using power-of-two expansion, the elements from each bin
484 484 * must either stay at same index, or move with a power of two
485 485 * offset. We eliminate unnecessary node creation by catching
486 486 * cases where old nodes can be reused because their next
487 487 * fields won't change. Statistically, at the default
488 488 * threshold, only about one-sixth of them need cloning when
489 489 * a table doubles. The nodes they replace will be garbage
490 490 * collectable as soon as they are no longer referenced by any
491 491 * reader thread that may be in the midst of traversing table
492 492 * right now.
493 493 */
494 494
495 495 HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
496 496 threshold = (int)(newTable.length * loadFactor);
497 497 int sizeMask = newTable.length - 1;
498 498 for (int i = 0; i < oldCapacity ; i++) {
499 499 // We need to guarantee that any existing reads of old Map can
500 500 // proceed. So we cannot yet null out each bin.
501 501 HashEntry<K,V> e = oldTable[i];
502 502
503 503 if (e != null) {
504 504 HashEntry<K,V> next = e.next;
505 505 int idx = e.hash & sizeMask;
506 506
507 507 // Single node on list
508 508 if (next == null)
509 509 newTable[idx] = e;
510 510
511 511 else {
512 512 // Reuse trailing consecutive sequence at same slot
513 513 HashEntry<K,V> lastRun = e;
514 514 int lastIdx = idx;
515 515 for (HashEntry<K,V> last = next;
516 516 last != null;
517 517 last = last.next) {
518 518 int k = last.hash & sizeMask;
519 519 if (k != lastIdx) {
520 520 lastIdx = k;
521 521 lastRun = last;
522 522 }
523 523 }
524 524 newTable[lastIdx] = lastRun;
525 525
526 526 // Clone all remaining nodes
527 527 for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
528 528 int k = p.hash & sizeMask;
529 529 HashEntry<K,V> n = newTable[k];
530 530 newTable[k] = new HashEntry<K,V>(p.key, p.hash,
531 531 n, p.value);
532 532 }
533 533 }
534 534 }
535 535 }
536 536 table = newTable;
537 537 }
538 538
539 539 /**
540 540 * Remove; match on key only if value null, else match both.
541 541 */
542 542 V remove(Object key, int hash, Object value) {
543 543 lock();
544 544 try {
545 545 int c = count - 1;
546 546 HashEntry<K,V>[] tab = table;
547 547 int index = hash & (tab.length - 1);
548 548 HashEntry<K,V> first = tab[index];
549 549 HashEntry<K,V> e = first;
550 550 while (e != null && (e.hash != hash || !key.equals(e.key)))
551 551 e = e.next;
552 552
553 553 V oldValue = null;
554 554 if (e != null) {
555 555 V v = e.value;
556 556 if (value == null || value.equals(v)) {
557 557 oldValue = v;
558 558 // All entries following removed node can stay
559 559 // in list, but all preceding ones need to be
560 560 // cloned.
561 561 ++modCount;
562 562 HashEntry<K,V> newFirst = e.next;
563 563 for (HashEntry<K,V> p = first; p != e; p = p.next)
564 564 newFirst = new HashEntry<K,V>(p.key, p.hash,
565 565 newFirst, p.value);
566 566 tab[index] = newFirst;
567 567 count = c; // write-volatile
568 568 }
569 569 }
570 570 return oldValue;
571 571 } finally {
572 572 unlock();
573 573 }
574 574 }
575 575
576 576 void clear() {
577 577 if (count != 0) {
578 578 lock();
579 579 try {
580 580 HashEntry<K,V>[] tab = table;
581 581 for (int i = 0; i < tab.length ; i++)
582 582 tab[i] = null;
583 583 ++modCount;
584 584 count = 0; // write-volatile
585 585 } finally {
586 586 unlock();
587 587 }
588 588 }
589 589 }
590 590 }
591 591
592 592
593 593
594 594 /* ---------------- Public operations -------------- */
595 595
596 596 /**
597 597 * Creates a new, empty map with the specified initial
598 598 * capacity, load factor and concurrency level.
599 599 *
600 600 * @param initialCapacity the initial capacity. The implementation
601 601 * performs internal sizing to accommodate this many elements.
602 602 * @param loadFactor the load factor threshold, used to control resizing.
603 603 * Resizing may be performed when the average number of elements per
604 604 * bin exceeds this threshold.
605 605 * @param concurrencyLevel the estimated number of concurrently
606 606 * updating threads. The implementation performs internal sizing
607 607 * to try to accommodate this many threads.
608 608 * @throws IllegalArgumentException if the initial capacity is
609 609 * negative or the load factor or concurrencyLevel are
610 610 * nonpositive.
611 611 */
612 612 public ConcurrentHashMap(int initialCapacity,
613 613 float loadFactor, int concurrencyLevel) {
614 614 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
615 615 throw new IllegalArgumentException();
616 616
617 617 if (concurrencyLevel > MAX_SEGMENTS)
618 618 concurrencyLevel = MAX_SEGMENTS;
619 619
620 620 // Find power-of-two sizes best matching arguments
621 621 int sshift = 0;
622 622 int ssize = 1;
623 623 while (ssize < concurrencyLevel) {
624 624 ++sshift;
625 625 ssize <<= 1;
626 626 }
627 627 segmentShift = 32 - sshift;
628 628 segmentMask = ssize - 1;
629 629 this.segments = Segment.newArray(ssize);
630 630
631 631 if (initialCapacity > MAXIMUM_CAPACITY)
632 632 initialCapacity = MAXIMUM_CAPACITY;
633 633 int c = initialCapacity / ssize;
634 634 if (c * ssize < initialCapacity)
635 635 ++c;
636 636 int cap = 1;
637 637 while (cap < c)
638 638 cap <<= 1;
639 639
640 640 for (int i = 0; i < this.segments.length; ++i)
641 641 this.segments[i] = new Segment<K,V>(cap, loadFactor);
642 642 }
643 643
644 644 /**
645 645 * Creates a new, empty map with the specified initial capacity
646 646 * and load factor and with the default concurrencyLevel (16).
647 647 *
648 648 * @param initialCapacity The implementation performs internal
649 649 * sizing to accommodate this many elements.
650 650 * @param loadFactor the load factor threshold, used to control resizing.
651 651 * Resizing may be performed when the average number of elements per
652 652 * bin exceeds this threshold.
653 653 * @throws IllegalArgumentException if the initial capacity of
654 654 * elements is negative or the load factor is nonpositive
655 655 *
656 656 * @since 1.6
657 657 */
658 658 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
659 659 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
660 660 }
661 661
662 662 /**
663 663 * Creates a new, empty map with the specified initial capacity,
664 664 * and with default load factor (0.75) and concurrencyLevel (16).
665 665 *
666 666 * @param initialCapacity the initial capacity. The implementation
667 667 * performs internal sizing to accommodate this many elements.
668 668 * @throws IllegalArgumentException if the initial capacity of
669 669 * elements is negative.
670 670 */
671 671 public ConcurrentHashMap(int initialCapacity) {
672 672 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
673 673 }
674 674
675 675 /**
676 676 * Creates a new, empty map with a default initial capacity (16),
677 677 * load factor (0.75) and concurrencyLevel (16).
678 678 */
679 679 public ConcurrentHashMap() {
680 680 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
681 681 }
682 682
683 683 /**
684 684 * Creates a new map with the same mappings as the given map.
685 685 * The map is created with a capacity of 1.5 times the number
686 686 * of mappings in the given map or 16 (whichever is greater),
687 687 * and a default load factor (0.75) and concurrencyLevel (16).
688 688 *
689 689 * @param m the map
690 690 */
691 691 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
692 692 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
693 693 DEFAULT_INITIAL_CAPACITY),
694 694 DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
695 695 putAll(m);
696 696 }
697 697
698 698 /**
699 699 * Returns <tt>true</tt> if this map contains no key-value mappings.
700 700 *
701 701 * @return <tt>true</tt> if this map contains no key-value mappings
702 702 */
703 703 public boolean isEmpty() {
704 704 final Segment<K,V>[] segments = this.segments;
705 705 /*
706 706 * We keep track of per-segment modCounts to avoid ABA
707 707 * problems in which an element in one segment was added and
708 708 * in another removed during traversal, in which case the
709 709 * table was never actually empty at any point. Note the
710 710 * similar use of modCounts in the size() and containsValue()
711 711 * methods, which are the only other methods also susceptible
712 712 * to ABA problems.
713 713 */
714 714 int[] mc = new int[segments.length];
715 715 int mcsum = 0;
716 716 for (int i = 0; i < segments.length; ++i) {
717 717 if (segments[i].count != 0)
718 718 return false;
719 719 else
720 720 mcsum += mc[i] = segments[i].modCount;
721 721 }
722 722 // If mcsum happens to be zero, then we know we got a snapshot
723 723 // before any modifications at all were made. This is
724 724 // probably common enough to bother tracking.
725 725 if (mcsum != 0) {
726 726 for (int i = 0; i < segments.length; ++i) {
727 727 if (segments[i].count != 0 ||
728 728 mc[i] != segments[i].modCount)
729 729 return false;
730 730 }
731 731 }
732 732 return true;
733 733 }
734 734
735 735 /**
736 736 * Returns the number of key-value mappings in this map. If the
737 737 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
738 738 * <tt>Integer.MAX_VALUE</tt>.
739 739 *
740 740 * @return the number of key-value mappings in this map
741 741 */
742 742 public int size() {
743 743 final Segment<K,V>[] segments = this.segments;
744 744 long sum = 0;
745 745 long check = 0;
746 746 int[] mc = new int[segments.length];
747 747 // Try a few times to get accurate count. On failure due to
748 748 // continuous async changes in table, resort to locking.
749 749 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
750 750 check = 0;
751 751 sum = 0;
752 752 int mcsum = 0;
753 753 for (int i = 0; i < segments.length; ++i) {
754 754 sum += segments[i].count;
755 755 mcsum += mc[i] = segments[i].modCount;
756 756 }
757 757 if (mcsum != 0) {
758 758 for (int i = 0; i < segments.length; ++i) {
759 759 check += segments[i].count;
760 760 if (mc[i] != segments[i].modCount) {
761 761 check = -1; // force retry
762 762 break;
763 763 }
764 764 }
765 765 }
766 766 if (check == sum)
767 767 break;
768 768 }
769 769 if (check != sum) { // Resort to locking all segments
770 770 sum = 0;
771 771 for (int i = 0; i < segments.length; ++i)
772 772 segments[i].lock();
773 773 for (int i = 0; i < segments.length; ++i)
774 774 sum += segments[i].count;
775 775 for (int i = 0; i < segments.length; ++i)
776 776 segments[i].unlock();
777 777 }
778 778 if (sum > Integer.MAX_VALUE)
779 779 return Integer.MAX_VALUE;
780 780 else
781 781 return (int)sum;
782 782 }
783 783
784 784 /**
785 785 * Returns the value to which the specified key is mapped,
786 786 * or {@code null} if this map contains no mapping for the key.
787 787 *
788 788 * <p>More formally, if this map contains a mapping from a key
789 789 * {@code k} to a value {@code v} such that {@code key.equals(k)},
790 790 * then this method returns {@code v}; otherwise it returns
791 791 * {@code null}. (There can be at most one such mapping.)
792 792 *
793 793 * @throws NullPointerException if the specified key is null
794 794 */
795 795 public V get(Object key) {
796 796 int hash = hash(key.hashCode());
797 797 return segmentFor(hash).get(key, hash);
798 798 }
799 799
800 800 /**
801 801 * Tests if the specified object is a key in this table.
802 802 *
803 803 * @param key possible key
804 804 * @return <tt>true</tt> if and only if the specified object
805 805 * is a key in this table, as determined by the
806 806 * <tt>equals</tt> method; <tt>false</tt> otherwise.
807 807 * @throws NullPointerException if the specified key is null
808 808 */
809 809 public boolean containsKey(Object key) {
810 810 int hash = hash(key.hashCode());
811 811 return segmentFor(hash).containsKey(key, hash);
812 812 }
813 813
814 814 /**
815 815 * Returns <tt>true</tt> if this map maps one or more keys to the
816 816 * specified value. Note: This method requires a full internal
817 817 * traversal of the hash table, and so is much slower than
818 818 * method <tt>containsKey</tt>.
819 819 *
820 820 * @param value value whose presence in this map is to be tested
821 821 * @return <tt>true</tt> if this map maps one or more keys to the
822 822 * specified value
823 823 * @throws NullPointerException if the specified value is null
824 824 */
825 825 public boolean containsValue(Object value) {
826 826 if (value == null)
827 827 throw new NullPointerException();
828 828
829 829 // See explanation of modCount use above
830 830
831 831 final Segment<K,V>[] segments = this.segments;
832 832 int[] mc = new int[segments.length];
833 833
834 834 // Try a few times without locking
835 835 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
836 836 int sum = 0;
837 837 int mcsum = 0;
838 838 for (int i = 0; i < segments.length; ++i) {
839 839 int c = segments[i].count;
840 840 mcsum += mc[i] = segments[i].modCount;
841 841 if (segments[i].containsValue(value))
842 842 return true;
843 843 }
844 844 boolean cleanSweep = true;
845 845 if (mcsum != 0) {
846 846 for (int i = 0; i < segments.length; ++i) {
847 847 int c = segments[i].count;
848 848 if (mc[i] != segments[i].modCount) {
849 849 cleanSweep = false;
850 850 break;
851 851 }
852 852 }
853 853 }
854 854 if (cleanSweep)
855 855 return false;
856 856 }
857 857 // Resort to locking all segments
858 858 for (int i = 0; i < segments.length; ++i)
859 859 segments[i].lock();
860 860 boolean found = false;
861 861 try {
862 862 for (int i = 0; i < segments.length; ++i) {
863 863 if (segments[i].containsValue(value)) {
864 864 found = true;
865 865 break;
866 866 }
867 867 }
868 868 } finally {
869 869 for (int i = 0; i < segments.length; ++i)
870 870 segments[i].unlock();
871 871 }
872 872 return found;
873 873 }
874 874
875 875 /**
876 876 * Legacy method testing if some key maps into the specified value
877 877 * in this table. This method is identical in functionality to
878 878 * {@link #containsValue}, and exists solely to ensure
879 879 * full compatibility with class {@link java.util.Hashtable},
880 880 * which supported this method prior to introduction of the
881 881 * Java Collections framework.
882 882
883 883 * @param value a value to search for
884 884 * @return <tt>true</tt> if and only if some key maps to the
885 885 * <tt>value</tt> argument in this table as
886 886 * determined by the <tt>equals</tt> method;
887 887 * <tt>false</tt> otherwise
888 888 * @throws NullPointerException if the specified value is null
889 889 */
890 890 public boolean contains(Object value) {
891 891 return containsValue(value);
892 892 }
893 893
894 894 /**
895 895 * Maps the specified key to the specified value in this table.
896 896 * Neither the key nor the value can be null.
897 897 *
898 898 * <p> The value can be retrieved by calling the <tt>get</tt> method
899 899 * with a key that is equal to the original key.
900 900 *
901 901 * @param key key with which the specified value is to be associated
902 902 * @param value value to be associated with the specified key
903 903 * @return the previous value associated with <tt>key</tt>, or
904 904 * <tt>null</tt> if there was no mapping for <tt>key</tt>
905 905 * @throws NullPointerException if the specified key or value is null
906 906 */
907 907 public V put(K key, V value) {
908 908 if (value == null)
909 909 throw new NullPointerException();
910 910 int hash = hash(key.hashCode());
911 911 return segmentFor(hash).put(key, hash, value, false);
912 912 }
913 913
914 914 /**
915 915 * {@inheritDoc}
916 916 *
917 917 * @return the previous value associated with the specified key,
918 918 * or <tt>null</tt> if there was no mapping for the key
919 919 * @throws NullPointerException if the specified key or value is null
920 920 */
921 921 public V putIfAbsent(K key, V value) {
922 922 if (value == null)
923 923 throw new NullPointerException();
924 924 int hash = hash(key.hashCode());
925 925 return segmentFor(hash).put(key, hash, value, true);
926 926 }
927 927
928 928 /**
929 929 * Copies all of the mappings from the specified map to this one.
930 930 * These mappings replace any mappings that this map had for any of the
931 931 * keys currently in the specified map.
932 932 *
933 933 * @param m mappings to be stored in this map
934 934 */
935 935 public void putAll(Map<? extends K, ? extends V> m) {
936 936 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
937 937 put(e.getKey(), e.getValue());
938 938 }
939 939
940 940 /**
941 941 * Removes the key (and its corresponding value) from this map.
942 942 * This method does nothing if the key is not in the map.
943 943 *
944 944 * @param key the key that needs to be removed
945 945 * @return the previous value associated with <tt>key</tt>, or
946 946 * <tt>null</tt> if there was no mapping for <tt>key</tt>
947 947 * @throws NullPointerException if the specified key is null
948 948 */
949 949 public V remove(Object key) {
950 950 int hash = hash(key.hashCode());
951 951 return segmentFor(hash).remove(key, hash, null);
952 952 }
953 953
954 954 /**
955 955 * {@inheritDoc}
956 956 *
957 957 * @throws NullPointerException if the specified key is null
958 958 */
959 959 public boolean remove(Object key, Object value) {
960 960 int hash = hash(key.hashCode());
961 961 if (value == null)
962 962 return false;
963 963 return segmentFor(hash).remove(key, hash, value) != null;
964 964 }
965 965
966 966 /**
967 967 * {@inheritDoc}
968 968 *
969 969 * @throws NullPointerException if any of the arguments are null
970 970 */
971 971 public boolean replace(K key, V oldValue, V newValue) {
972 972 if (oldValue == null || newValue == null)
973 973 throw new NullPointerException();
974 974 int hash = hash(key.hashCode());
975 975 return segmentFor(hash).replace(key, hash, oldValue, newValue);
976 976 }
977 977
978 978 /**
979 979 * {@inheritDoc}
980 980 *
981 981 * @return the previous value associated with the specified key,
982 982 * or <tt>null</tt> if there was no mapping for the key
983 983 * @throws NullPointerException if the specified key or value is null
984 984 */
985 985 public V replace(K key, V value) {
986 986 if (value == null)
987 987 throw new NullPointerException();
988 988 int hash = hash(key.hashCode());
989 989 return segmentFor(hash).replace(key, hash, value);
990 990 }
991 991
992 992 /**
993 993 * Removes all of the mappings from this map.
994 994 */
995 995 public void clear() {
996 996 for (int i = 0; i < segments.length; ++i)
997 997 segments[i].clear();
998 998 }
999 999
1000 1000 /**
1001 1001 * Returns a {@link Set} view of the keys contained in this map.
1002 1002 * The set is backed by the map, so changes to the map are
1003 1003 * reflected in the set, and vice-versa. The set supports element
1004 1004 * removal, which removes the corresponding mapping from this map,
1005 1005 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1006 1006 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1007 1007 * operations. It does not support the <tt>add</tt> or
1008 1008 * <tt>addAll</tt> operations.
1009 1009 *
1010 1010 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1011 1011 * that will never throw {@link ConcurrentModificationException},
1012 1012 * and guarantees to traverse elements as they existed upon
1013 1013 * construction of the iterator, and may (but is not guaranteed to)
1014 1014 * reflect any modifications subsequent to construction.
1015 1015 */
1016 1016 public Set<K> keySet() {
1017 1017 Set<K> ks = keySet;
1018 1018 return (ks != null) ? ks : (keySet = new KeySet());
1019 1019 }
1020 1020
1021 1021 /**
1022 1022 * Returns a {@link Collection} view of the values contained in this map.
1023 1023 * The collection is backed by the map, so changes to the map are
1024 1024 * reflected in the collection, and vice-versa. The collection
1025 1025 * supports element removal, which removes the corresponding
1026 1026 * mapping from this map, via the <tt>Iterator.remove</tt>,
1027 1027 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1028 1028 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not
1029 1029 * support the <tt>add</tt> or <tt>addAll</tt> operations.
1030 1030 *
1031 1031 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1032 1032 * that will never throw {@link ConcurrentModificationException},
1033 1033 * and guarantees to traverse elements as they existed upon
1034 1034 * construction of the iterator, and may (but is not guaranteed to)
1035 1035 * reflect any modifications subsequent to construction.
1036 1036 */
1037 1037 public Collection<V> values() {
1038 1038 Collection<V> vs = values;
1039 1039 return (vs != null) ? vs : (values = new Values());
1040 1040 }
1041 1041
1042 1042 /**
1043 1043 * Returns a {@link Set} view of the mappings contained in this map.
1044 1044 * The set is backed by the map, so changes to the map are
1045 1045 * reflected in the set, and vice-versa. The set supports element
1046 1046 * removal, which removes the corresponding mapping from the map,
1047 1047 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1048 1048 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1049 1049 * operations. It does not support the <tt>add</tt> or
1050 1050 * <tt>addAll</tt> operations.
1051 1051 *
1052 1052 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1053 1053 * that will never throw {@link ConcurrentModificationException},
1054 1054 * and guarantees to traverse elements as they existed upon
1055 1055 * construction of the iterator, and may (but is not guaranteed to)
1056 1056 * reflect any modifications subsequent to construction.
1057 1057 */
1058 1058 public Set<Map.Entry<K,V>> entrySet() {
1059 1059 Set<Map.Entry<K,V>> es = entrySet;
1060 1060 return (es != null) ? es : (entrySet = new EntrySet());
1061 1061 }
1062 1062
1063 1063 /**
1064 1064 * Returns an enumeration of the keys in this table.
1065 1065 *
1066 1066 * @return an enumeration of the keys in this table
1067 1067 * @see #keySet()
1068 1068 */
1069 1069 public Enumeration<K> keys() {
1070 1070 return new KeyIterator();
1071 1071 }
1072 1072
1073 1073 /**
1074 1074 * Returns an enumeration of the values in this table.
1075 1075 *
1076 1076 * @return an enumeration of the values in this table
1077 1077 * @see #values()
1078 1078 */
1079 1079 public Enumeration<V> elements() {
1080 1080 return new ValueIterator();
1081 1081 }
1082 1082
1083 1083 /* ---------------- Iterator Support -------------- */
1084 1084
1085 1085 abstract class HashIterator {
1086 1086 int nextSegmentIndex;
1087 1087 int nextTableIndex;
1088 1088 HashEntry<K,V>[] currentTable;
1089 1089 HashEntry<K, V> nextEntry;
1090 1090 HashEntry<K, V> lastReturned;
1091 1091
1092 1092 HashIterator() {
1093 1093 nextSegmentIndex = segments.length - 1;
1094 1094 nextTableIndex = -1;
1095 1095 advance();
1096 1096 }
1097 1097
1098 1098 public boolean hasMoreElements() { return hasNext(); }
1099 1099
1100 1100 final void advance() {
1101 1101 if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1102 1102 return;
1103 1103
1104 1104 while (nextTableIndex >= 0) {
1105 1105 if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1106 1106 return;
1107 1107 }
1108 1108
1109 1109 while (nextSegmentIndex >= 0) {
1110 1110 Segment<K,V> seg = segments[nextSegmentIndex--];
1111 1111 if (seg.count != 0) {
1112 1112 currentTable = seg.table;
1113 1113 for (int j = currentTable.length - 1; j >= 0; --j) {
1114 1114 if ( (nextEntry = currentTable[j]) != null) {
1115 1115 nextTableIndex = j - 1;
1116 1116 return;
1117 1117 }
1118 1118 }
1119 1119 }
1120 1120 }
1121 1121 }
1122 1122
1123 1123 public boolean hasNext() { return nextEntry != null; }
1124 1124
1125 1125 HashEntry<K,V> nextEntry() {
1126 1126 if (nextEntry == null)
1127 1127 throw new NoSuchElementException();
1128 1128 lastReturned = nextEntry;
1129 1129 advance();
1130 1130 return lastReturned;
1131 1131 }
1132 1132
1133 1133 public void remove() {
1134 1134 if (lastReturned == null)
1135 1135 throw new IllegalStateException();
1136 1136 ConcurrentHashMap.this.remove(lastReturned.key);
1137 1137 lastReturned = null;
1138 1138 }
1139 1139 }
1140 1140
1141 1141 final class KeyIterator
1142 1142 extends HashIterator
1143 1143 implements Iterator<K>, Enumeration<K>
1144 1144 {
1145 1145 public K next() { return super.nextEntry().key; }
1146 1146 public K nextElement() { return super.nextEntry().key; }
1147 1147 }
1148 1148
1149 1149 final class ValueIterator
1150 1150 extends HashIterator
1151 1151 implements Iterator<V>, Enumeration<V>
1152 1152 {
1153 1153 public V next() { return super.nextEntry().value; }
1154 1154 public V nextElement() { return super.nextEntry().value; }
1155 1155 }
1156 1156
1157 1157 /**
1158 1158 * Custom Entry class used by EntryIterator.next(), that relays
1159 1159 * setValue changes to the underlying map.
1160 1160 */
1161 1161 final class WriteThroughEntry
1162 1162 extends AbstractMap.SimpleEntry<K,V>
1163 1163 {
1164 1164 WriteThroughEntry(K k, V v) {
1165 1165 super(k,v);
1166 1166 }
1167 1167
1168 1168 /**
1169 1169 * Set our entry's value and write through to the map. The
1170 1170 * value to return is somewhat arbitrary here. Since a
1171 1171 * WriteThroughEntry does not necessarily track asynchronous
1172 1172 * changes, the most recent "previous" value could be
1173 1173 * different from what we return (or could even have been
1174 1174 * removed in which case the put will re-establish). We do not
1175 1175 * and cannot guarantee more.
1176 1176 */
1177 1177 public V setValue(V value) {
1178 1178 if (value == null) throw new NullPointerException();
1179 1179 V v = super.setValue(value);
1180 1180 ConcurrentHashMap.this.put(getKey(), value);
1181 1181 return v;
1182 1182 }
1183 1183 }
1184 1184
1185 1185 final class EntryIterator
1186 1186 extends HashIterator
1187 1187 implements Iterator<Entry<K,V>>
1188 1188 {
1189 1189 public Map.Entry<K,V> next() {
1190 1190 HashEntry<K,V> e = super.nextEntry();
1191 1191 return new WriteThroughEntry(e.key, e.value);
1192 1192 }
1193 1193 }
1194 1194
1195 1195 final class KeySet extends AbstractSet<K> {
1196 1196 public Iterator<K> iterator() {
1197 1197 return new KeyIterator();
1198 1198 }
1199 1199 public int size() {
1200 1200 return ConcurrentHashMap.this.size();
1201 1201 }
1202 1202 public boolean isEmpty() {
1203 1203 return ConcurrentHashMap.this.isEmpty();
1204 1204 }
1205 1205 public boolean contains(Object o) {
1206 1206 return ConcurrentHashMap.this.containsKey(o);
1207 1207 }
1208 1208 public boolean remove(Object o) {
1209 1209 return ConcurrentHashMap.this.remove(o) != null;
1210 1210 }
1211 1211 public void clear() {
1212 1212 ConcurrentHashMap.this.clear();
1213 1213 }
1214 1214 }
1215 1215
1216 1216 final class Values extends AbstractCollection<V> {
1217 1217 public Iterator<V> iterator() {
1218 1218 return new ValueIterator();
1219 1219 }
1220 1220 public int size() {
1221 1221 return ConcurrentHashMap.this.size();
1222 1222 }
1223 1223 public boolean isEmpty() {
1224 1224 return ConcurrentHashMap.this.isEmpty();
1225 1225 }
1226 1226 public boolean contains(Object o) {
1227 1227 return ConcurrentHashMap.this.containsValue(o);
1228 1228 }
1229 1229 public void clear() {
1230 1230 ConcurrentHashMap.this.clear();
1231 1231 }
1232 1232 }
1233 1233
1234 1234 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1235 1235 public Iterator<Map.Entry<K,V>> iterator() {
1236 1236 return new EntryIterator();
1237 1237 }
1238 1238 public boolean contains(Object o) {
1239 1239 if (!(o instanceof Map.Entry))
1240 1240 return false;
1241 1241 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1242 1242 V v = ConcurrentHashMap.this.get(e.getKey());
1243 1243 return v != null && v.equals(e.getValue());
1244 1244 }
1245 1245 public boolean remove(Object o) {
1246 1246 if (!(o instanceof Map.Entry))
1247 1247 return false;
1248 1248 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1249 1249 return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1250 1250 }
1251 1251 public int size() {
1252 1252 return ConcurrentHashMap.this.size();
1253 1253 }
1254 1254 public boolean isEmpty() {
1255 1255 return ConcurrentHashMap.this.isEmpty();
1256 1256 }
1257 1257 public void clear() {
1258 1258 ConcurrentHashMap.this.clear();
1259 1259 }
1260 1260 }
1261 1261
1262 1262 /* ---------------- Serialization Support -------------- */
↓ open down ↓ |
1262 lines elided |
↑ open up ↑ |
1263 1263
1264 1264 /**
1265 1265 * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1266 1266 * stream (i.e., serialize it).
1267 1267 * @param s the stream
1268 1268 * @serialData
1269 1269 * the key (Object) and value (Object)
1270 1270 * for each key-value mapping, followed by a null pair.
1271 1271 * The key-value mappings are emitted in no particular order.
1272 1272 */
1273 - private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1273 + private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1274 1274 s.defaultWriteObject();
1275 1275
1276 1276 for (int k = 0; k < segments.length; ++k) {
1277 1277 Segment<K,V> seg = segments[k];
1278 1278 seg.lock();
1279 1279 try {
1280 1280 HashEntry<K,V>[] tab = seg.table;
1281 1281 for (int i = 0; i < tab.length; ++i) {
1282 1282 for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1283 1283 s.writeObject(e.key);
1284 1284 s.writeObject(e.value);
1285 1285 }
1286 1286 }
1287 1287 } finally {
1288 1288 seg.unlock();
1289 1289 }
1290 1290 }
↓ open down ↓ |
7 lines elided |
↑ open up ↑ |
1291 1291 s.writeObject(null);
1292 1292 s.writeObject(null);
1293 1293 }
1294 1294
1295 1295 /**
1296 1296 * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1297 1297 * stream (i.e., deserialize it).
1298 1298 * @param s the stream
1299 1299 */
1300 1300 private void readObject(java.io.ObjectInputStream s)
1301 - throws IOException, ClassNotFoundException {
1301 + throws IOException, ClassNotFoundException {
1302 1302 s.defaultReadObject();
1303 1303
1304 1304 // Initialize each segment to be minimally sized, and let grow.
1305 1305 for (int i = 0; i < segments.length; ++i) {
1306 1306 segments[i].setTable(new HashEntry[1]);
1307 1307 }
1308 1308
1309 1309 // Read the keys and values, and put the mappings in the table
1310 1310 for (;;) {
1311 1311 K key = (K) s.readObject();
1312 1312 V value = (V) s.readObject();
1313 1313 if (key == null)
1314 1314 break;
1315 1315 put(key, value);
1316 1316 }
1317 1317 }
1318 1318 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX