无锁哈希表实际上是如何工作的

Question

我经历了http://preshing.com/20130529/a-lock-free-linear-search/ 和 https://code.google.com/p/nbds/

我不明白这些哈希表中的任何一个都是锁定费。我的意思是如果我们在哈希表 getItem 和 setItem 上有两个方法。这是我的功能

function increment2(key):
    val = hashtable.getItem(key) + 2
    hashtable.setItem(val)

现在这个函数在 2 个线程中运行，现在如果我不在这个函数中使用锁，hashtable.getItem(key) 的值可以增加 2 或 4。我很困惑有人可以帮助我理解

Answer 1

当谈到并发容器时，我们通常指的是单操作，为这个容器定义，是原子的。在您的情况下，hashtable.getItem(key) 和 hashtable.setItem(key, val) 是 atomic 操作。例如。如果 .getItem() 与 .setItem() 同时执行，那么它将 return 新值或旧值，但不是它们的混合。

但是并发容器不保证其两个或多个操作的序列是原子的。如果用户需要 atomic 属性用于操作序列，他不应该从容器的实现中期望这个属性而是手动实现这个属性。在你的情况下，如果你需要 increment2 函数是 atomic，你需要自己实现这个属性。

通常可以很容易地修改基于锁的并发容器，使某些操作序列成为原子操作。

从另一方面来说，无锁并发容器很难被扩展以让操作序列成为原子的。在这个意义上，无锁算法非常脆弱。

无锁哈希表实际上是如何工作的

How does lock free hashtable actually work

multithreading

locking

hashmap

concurrenthashmap