从仅具有本地锁的 BST 进行多线程删除
Multithreaded deletion from a BST with only local locks
在 Java 中编写 BST 的多线程实现时，我遇到了以下问题。这个 BST 不应该使用全局锁，而是尽可能少地锁定，特别是只锁定正在更改的节点（添加和删除命令）。因此，只要其他线程不尝试更改与您相同的节点，它们就可以在树中处于活动状态。
我找不到实现删除具有 2 个子节点的节点的方法。正常算法说找到要删除的节点的顺序后继，将其放在被删除节点的位置，然后删除复制的节点。但这会对位于这两个节点之间并需要复制节点的线程产生问题，在传输之后，线程将找不到请求的节点，即使它在树中也是如此。
看下面的例子：胎面 1 正在执行 remove(5)。它找到下一个键 (6) 并将其复制到节点，然后从副本中删除该节点。但与此同时，另一个线程正在执行 contains(6) 命令并在节点 8 上等待，在执行节点号 6 将不再在其路径中之后，它会 return 一个错误的结果，即使 6节点仍在树中。
删除命令之前的状态说明（蓝色箭头表示 2nd 线程所在的位置。
删除命令后的状态说明（蓝色箭头表示 2nd 线程所在的位置。
如何在不锁定整个树的情况下解决这个问题？
独立于 BST 同步节点。这意味着如果您要删除一个节点，您将需要锁定受影响的最顶层节点及其下方的所有节点，以防止其他线程读取或修改这些节点。不幸的是，对于 BST，这可能意味着根据操作锁定根节点，这将有效地防止任何读取发生。
我相信这将是您尝试执行的最快的实现。
如果排序无关紧要，我建议改用 HashMap 实现。您只需要锁定存储桶而不是可能锁定整个地图。
我认为用哈希集支持 BST 可能是解决此问题的方法。这样你的查找将独立于 BST 锁定并且会给你一个 O(1) 包含。
我使用的解决方案是为 BST 设置一个版本号，每次有两个子节点需要 remove 时，我都会在删除重复节点之前增加版本号。
然后，每个操作在开始之前都会检查版本号，如果我得到的结果表明没有找到密钥，我会检查版本号是否仍然相同，如果不一样，我会重试操作。
这意味着：
- 对于
remove 和 contains - 如果操作失败（意味着未找到密钥）并且版本已更改，请重试。
- 对于
insert - 我检查版本号，不是在操作结束时，而是在我处于叶节点时以及在创建和添加新节点之前。如果我要添加一个新节点，则意味着我没有找到具有该键的节点，我想在更改它并创建新叶子之前确保该键确实不在树中，以防止出现以下情况一个双键将添加到树中，然后我需要通过删除节点重做此操作。
在 Java 中编写 BST 的多线程实现时，我遇到了以下问题。这个 BST 不应该使用全局锁，而是尽可能少地锁定，特别是只锁定正在更改的节点（添加和删除命令）。因此，只要其他线程不尝试更改与您相同的节点，它们就可以在树中处于活动状态。
我找不到实现删除具有 2 个子节点的节点的方法。正常算法说找到要删除的节点的顺序后继，将其放在被删除节点的位置，然后删除复制的节点。但这会对位于这两个节点之间并需要复制节点的线程产生问题，在传输之后，线程将找不到请求的节点，即使它在树中也是如此。
看下面的例子：胎面 1 正在执行 remove(5)。它找到下一个键 (6) 并将其复制到节点，然后从副本中删除该节点。但与此同时，另一个线程正在执行 contains(6) 命令并在节点 8 上等待，在执行节点号 6 将不再在其路径中之后，它会 return 一个错误的结果，即使 6节点仍在树中。
删除命令之前的状态说明（蓝色箭头表示 2nd 线程所在的位置。
删除命令后的状态说明（蓝色箭头表示 2nd 线程所在的位置。
如何在不锁定整个树的情况下解决这个问题？
独立于 BST 同步节点。这意味着如果您要删除一个节点，您将需要锁定受影响的最顶层节点及其下方的所有节点，以防止其他线程读取或修改这些节点。不幸的是，对于 BST，这可能意味着根据操作锁定根节点，这将有效地防止任何读取发生。
我相信这将是您尝试执行的最快的实现。
如果排序无关紧要，我建议改用 HashMap 实现。您只需要锁定存储桶而不是可能锁定整个地图。
我认为用哈希集支持 BST 可能是解决此问题的方法。这样你的查找将独立于 BST 锁定并且会给你一个 O(1) 包含。
我使用的解决方案是为 BST 设置一个版本号，每次有两个子节点需要 remove 时，我都会在删除重复节点之前增加版本号。
然后，每个操作在开始之前都会检查版本号，如果我得到的结果表明没有找到密钥，我会检查版本号是否仍然相同，如果不一样，我会重试操作。
这意味着：
- 对于
remove和contains- 如果操作失败（意味着未找到密钥）并且版本已更改，请重试。 - 对于
insert- 我检查版本号，不是在操作结束时，而是在我处于叶节点时以及在创建和添加新节点之前。如果我要添加一个新节点，则意味着我没有找到具有该键的节点，我想在更改它并创建新叶子之前确保该键确实不在树中，以防止出现以下情况一个双键将添加到树中，然后我需要通过删除节点重做此操作。