首页 ❯

高效的并发树

concurrency java tree
2022-09-04 02:27:42

我正在寻找一种有效的方法来实现并发树结构。如果这有帮助，假设我的读取访问权限比对结构的更改要多得多。

树应支持以下操作：

  • 添加和删除节点
  • 每次插入新节点时对分支进行排序
  • 迭代所有节点（无 ConcurrentModificationException）
  • 按路径查找元素

答案 1

看看： Google代码上的并发树，了解一种在不锁定的情况下修改树状结构的方法。

该项目为 Java 提供了并发基数和后缀树。它们支持并发读写，并且读取是无锁的。它的工作原理是以原子方式将补丁应用于树。虽然这些类型的树可能不完全是您想要的，但 TreeDesign 中描述的使用“修补”的方法对于任何类型的树状结构都很有用。

这些树适用于高并发读取（主要是用例），其中（例如）后台线程可能正在从树中插入或删除条目，而许多前台线程将继续遍历它而不会受到修改的阻碍。


答案 2

最接近您可能需要的Java结构是ConversalSkipListSet（或者可能是ConcurrentSkipListMap）。

如果需要更自定义的方法，则可以在具有分层读写锁的情况下实现自定义树结构。以下是有关如何实现重入读写锁的类似问题的答案：https://stackoverflow.com/a/6154873/272388


推荐
更多 »
标签
更多 »
php pass-by-reference optional-parameters default-value javascript arrays dom function string object serialization tostring visibility syntax jslint use-strict operators equality equality-operator identity-operator datetime timestamp date-arithmetic redirect angularjs loops foreach iteration scope variables
推荐
更多 »