为什么 TreeBin 在 ConcurrentHashMap 中维护了读写锁？

Question

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

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 ……检查锁是否已被释放。“寄生”锁定是它的实现。