是否有可能为64位密钥调整这种无锁32位散列表算法？

Question

问题和背景

这篇文章描述了一个无锁的32位哈希表算法.算法的核心是无锁线性搜索,用于在(逻辑)列表中插入key-val对:

这是提供的代码:

void ArrayOfItems::SetItem(uint32_t key, uint32_t value)
{
    for (uint32_t idx = 0;; idx++)
    {
        uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);
        if ((prevKey == 0) || (prevKey == key))
        {
            mint_store_32_relaxed(&m_entries[idx].value, value);
            return;
        }
    }
}

对于特定问题,我需要在表中插入随机键 - 值对.因此,我需要至少64位密钥,因为对于32位,在65536次插入后有50%的冲突几率,这太低了.不幸的是,我没有 64位cmpxchg作为原语.

题

是否可以将上面的哈希表概括为64位密钥,仅使用32位cmpxchg？

Answer 1

从这个问题中我不确定您是否仍然想保留无锁特性，或者只是想启动并运行 64 位键/值存储。（？）

@kol 在这里发布了一个 64 位 MurmurHash3： 将一个小数哈希为随机的 64 位整数

显然，如果您引入第二个数组来断言键位置所有权，并尊重其值存储，那么您可以分两步读取和 CAS 64 位值，然后释放所有权。当然，这并不能让你无锁。

--------------- 编辑： ---------------
作者的哈希表上至少有两个视频，均来自 2007 年：

编程语言高级主题：无锁哈希表 https://www.youtube.com/watch?v=HJ-719EGIts

快速无等待哈希表
https://youtu.be/WYXgtXWejRM

他将他的程序流程与有限状态机联系起来。忽略增长表的问题，在将潜在突变应用于该位置之前，该位置可以处于四种状态。键/值 = [nil/nil]、[X/nil]、[X/X]、[nil/X]。

读取状态以准备突变并不能保证在并发情况下状态在应用突变时保持不变。

对于 32 位操作，我们有以下逻辑：
- 如果读取的键 = 所需的键，则可以将值写入该位置。
- 如果读取的键 = nil，并且值 = 非 nil，则另一个线程正在改变该位置。
- 如果读取的键 = nil，并且值 = nil，则可以通过成功的键 CAS 写入该位置。

如果你想使用32位原子操作来存储64位数据而不加锁，那么状态图的大小就会增加，失败状态也会更多，例如：
- 你可以读取一个半创建的Key。
- 一半值条目的 CAS 更新可能会被另一个线程阻止，从而在第二个 CAS 上失败。
- 半个 Key 条目的 CAS 创建可能会被另一个线程破坏，从而在第二个 CAS 上失败。
- 数组初始值设定项“nil”的 32 位表示形式不应作为 64 位键或值的一半出现

增加表大小的过程还增加了一些需要考虑的状态。