时间戳

首页 > 解决方案 > 是否可以将这种无锁 32 位哈希表算法用于 64 位密钥？

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

问题描述

问题和背景

这篇文章描述了一种无锁的 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 作为原语。

问题

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

标签： calgorithmparallel-processinghashmapatomic

解决方案

我不确定您是否仍想保留无锁特性，或者只是想启动和运行 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 上失败。
- 一个密钥条目的一半的 CAS 创建可能会被另一个线程踩踏，在第二个 CAS 上失败。
- 数组初始化器“nil”的 32 位表示应该被排除在 64 位键或值的一半之外

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

推荐阅读