是否可以将这种无锁 32 位哈希-table 算法改编为 64 位密钥？

Question

问题与背景

This post 描述了一个无锁的 32 位哈希-table 算法。该算法的核心是一个无锁线性搜索，用于在一个（逻辑）列表中插入一个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;
        }
    }
}

对于特定问题，我需要在 table 中插入随机键值对。因此，我至少需要 64 位密钥，因为对于 32 位密钥，在 65536 次插入后发生冲突的可能性为 50%，这太低了。不幸的是，我 64 位 cmpxchg 作为原语。

问题

是否可以仅使用 32 位 cmpxchg 将上面的 hash-table 概括为 64 位密钥？

Answer 1

从问题中我不确定您是仍想保留无锁特性，还是只想获得 64 位 key/value 存储空间 & 运行。 (?)

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

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

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

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

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

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

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

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

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

的一半出现之外

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

是否可以将这种无锁 32 位哈希-table 算法改编为 64 位密钥？

Is it possible to adapt this lock-free 32-bit hash-table algorithm for 64-bit keys?

c

algorithm

parallel-processing

atomic

hashmap

问题与背景

问题