scala – 纯功能并发跳过列表

具体来说，跳过列表包含如下结构：

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

现在，如果您有更新，例如删除NODE2b或NODE1b，您可以在本地进行处理：您只需分别指向2a至2c或2a至2a，即可完成。不幸的是，由于叶节点都指向一个，所以它不是功能(不可变)更新的良好结构。

因此，树结构对于不变性是更好的(因为损害总是在局部限制 – 只是你关心的节点，它的直接父母通过树的根)。

并发更新对于不可变数据结构不能正常工作。如果您想到，任何功能解决方案都将A更新为f(A)。如果你想要两个更新，一个由f给出，一个由g给出，那么你几乎必须做f(g(A))或g(f(A))，或者你必须拦截请求并创建一个新的操作h = f，g，您可以一次性应用所有(或者您必须做各种其他高度聪明的东西)。

然而，并发读取与不可变数据结构非常好地工作，因为您保证没有状态更改。如果您不认为在任何其他写入可以中断之前可以读取/写入循环，那么您永远不必锁定读取。

因此，写入繁重的数据结构可能更好地实现(并且具有类似跳过列表的东西，您只需要在本地进行锁定)，而读取重的数据结构可能会更好地实现(其中树是更自然的数据结构)。