java - 为什么 TreeBin 在 ConcurrentHashMap 中维护一个读写锁？

Question

ConcurrentHashMap 的 TreeBin 维护了一个寄生的读写锁。谁能告诉我为什么要维护读写锁？

标签： javaconcurrenthashmap

Answer 1

代码中有一条注释解释了 TreeBin 寄生锁定策略，如下所示：

/*
 * TreeBins also require an additional locking mechanism.  While
 * list traversal is always possible by readers even during
 * updates, tree traversal is not, mainly because of tree-rotations
 * that may change the root node and/or its linkages.  TreeBins
 * include a simple read-write lock mechanism parasitic on the
 * main bin-synchronization strategy: Structural adjustments
 * associated with an insertion or removal are already bin-locked
 * (and so cannot conflict with other writers) but must wait for
 * ongoing readers to finish. Since there can be only one such
 * waiter, we use a simple scheme using a single "waiter" field to
 * block writers.  However, readers need never block.  If the root
 * lock is held, they proceed along the slow traversal path (via
 * next-pointers) until the lock becomes available or the list is
 * exhausted, whichever comes first. These cases are not fast, but
 * maximize aggregate expected throughput.
 */

后面的评论解释了“为什么”：

/**
 * TreeNodes used at the heads of bins. TreeBins do not hold user
 * keys or values, but instead point to list of TreeNodes and
 * their root. They also maintain a parasitic read-write lock
 * forcing writers (who hold bin lock) to wait for readers (who do
 * not) to complete before tree restructuring operations.
 */

简而言之，整体锁定策略是避免锁定读取路径。所以地图被划分为“bins”，每个bin都有一个多读/单写锁。

除了如果存在锁竞争，读者实际上不会被阻塞。相反，它们遍历整个 bin ... 检查是否已释放锁。“寄生”锁定就是它的实现。