Java Reference
In-Depth Information
be unevenly distributed among buckets; in the degenerate case, a poor hash function will turn
a hash table into a linked list. Traversing a long list and calling
equals
on some or all of the
elements can take a long time, and during that time no other thread can access the collection.
ConcurrentHashMap
is a hash-based
Map
like
HashMap
, but it uses an entirely different
locking strategy that offers better concurrency and scalability. Instead of synchronizing every
method on a common lock, restricting access to a single thread at a time, it uses a finer-
grained locking mechanism called
lockstriping
(see
Section 11.4.3
) to allow a greater degree
of shared access. Arbitrarily many reading threads can access the map concurrently, readers
can access the map concurrently with writers, and a limited number of writers can modify
the map concurrently. The result is far higher throughput under concurrent access, with little
performance penalty for single-threaded access.
ConcurrentHashMap
, along with the other concurrent collections, further improve on
the synchronized collection classes by providing iterators that do not throw
Concur-
rentModificationException
, thus eliminating the need to lock the collection during
iteration. The iterators returned by
ConcurrentHashMap
are
weakly consistent
instead of
fail-fast. A weakly consistent iterator can tolerate concurrent modification, traverses elements
as they existed when the iterator was constructed, and may (but is not guaranteed to) reflect
modifications to the collection after the construction of the iterator.
As with all improvements, there are still a few tradeoffs. The semantics of methods that op-
erate on the entire
Map
, such as
size
and
isEmpty
, have been slightly weakened to reflect
the concurrent nature of the collection. Since the result of
size
could be out of date by the
time it is computed, it is really only an estimate, so
size
is allowed to return an approxima-
tion instead of an exact count. While at first this may seem disturbing, in reality methods like
size
and
isEmpty
are far less useful in concurrent environments because these quantities
are moving targets. So the requirements for these operations were weakened to enable per-
formance optimizations for the most important operations, primarily
get
,
put
,
contain-
sKey
, and
remove
.
The one feature offered by the synchronized
Map
implementations but not by
Concur-
rentHashMap
is the ability to lock the map for exclusive access. With
Hashtable
and
synchronizedMap
, acquiring the
Map
lock prevents any other thread from accessing it.
This might be necessary in unusual cases such as adding several mappings atomically, or it-
erating the
Map
several times and needing to see the same elements in the same order. On
the whole, though, this is a reasonable tradeoff: concurrent collections should be expected to
change their contents continuously.