c - 是否可以将这种无锁的 32 位哈希表算法用于 64 位 key ？

Question

问题与背景

This帖子描述了一个无锁的 32 位哈希表算法。该算法的核心是无锁线性搜索，用于在(逻辑)列表中插入键值对:

这里是提供的代码:

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 位 key ，因为对于 32 位 key ，在 65536 次插入后发生冲突的可能性为 50%，这太低了。不幸的是，我do not have 64 位 cmpxchg 作为原语。

问题

是否可以仅使用 32 位 cmpxchg 将上述哈希表泛化为 64 位 key ？

Answer 1

我不确定您是仍想保留无锁特性，还是只想启动和运行 64 位键/值存储。 (?)

@kol 在这里发布了一个 64 位的 MurmurHash3: hashing a small number to a random looking 64 bit integer

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

---------------- 编辑:----------------
作者的哈希表中至少有两个视频，都是 2007 年的:

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

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

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

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

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

如果想用32位的原子操作存储64位的数据，不加锁，那么状态图就变大了，失败状态也多了，eg:
- 你可以读取一个创建了一半的 key 。
- 一半值条目的 CAS 更新可能会被另一个线程阻止，在第二个 CAS 上失败。
- 一半 key 条目的 CAS 创建可能会被另一个线程阻止，在第二个 CAS 上失败。
- 数组初始值设定项“nil”的 32 位表示应排除在 64 位键或值的一半之外

增加表大小的过程也会增加一些要考虑的状态。