能否基于仅32位cmpxchg原语，将无锁32位哈希表适配为64位键？

问题与背景 #

本文介绍了一种无锁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位键——32位键在插入65536条数据后碰撞概率达50%，无法满足需求。但遗憾的是，我不具备64位cmpxchg原语。

问题 #

能否基于仅有的32位cmpxchg原语，将上述哈希表推广为支持64位键的版本？

当然可以实现！核心思路是把64位键拆成两个32位字段，用双阶段的32位CAS操作来模拟原子的64位键插入，同时处理并发场景下的竞争情况。下面是具体的实现方案和细节：

方案思路 #

我们把每个表项的键拆分为两个32位成员：key_high和key_low，同时引入一个状态标记位（可以复用key_high的最高位，或者单独加一个32位状态字段）来标识当前项的状态：

• 空闲状态：key_high和key_low都为0，状态标记为空闲
• 正在插入状态：先用CAS抢占key_high为一个带标记的非零值（比如键的高32位加上一个占位标记），表示当前有线程正在插入这个项
• 已插入状态：key_high和key_low完整存储64位键，状态标记为已完成

通过两次32位CAS就能完成原子的64位键插入，同时避免并发冲突。

具体实现代码 #

假设我们修改表项结构如下：

struct Entry {
    uint32_t key_high;
    uint32_t key_low;
    uint32_t value;
};

对应的SetItem实现：

void ArrayOfItems::SetItem(uint64_t key, uint32_t value) {
    const uint32_t key_high = static_cast<uint32_t>(key >> 32);
    const uint32_t key_low = static_cast<uint32_t>(key & 0xFFFFFFFF);
    // 用key_high的最高位作为"正在插入"的标记（确保业务键不会用到这个位）
    const uint32_t inserting_mark = 0x80000000;
    const uint32_t occupied_high = key_high | inserting_mark;

    for (uint32_t idx = 0;; idx++) {
        Entry& entry = m_entries[idx];
        uint32_t current_high = mint_load_32_relaxed(&entry.key_high);

        // 情况1：项是空闲的，尝试抢占为插入中状态
        if (current_high == 0) {
            if (mint_compare_exchange_strong_32_relaxed(&entry.key_high, 0, occupied_high)) {
                // 抢占成功，安全写入key_low
                mint_store_32_relaxed(&entry.key_low, key_low);
                // 清除插入标记，标记为已完成
                mint_store_32_relaxed(&entry.key_high, key_high);
                // 写入值
                mint_store_32_relaxed(&entry.value, value);
                return;
            }
            // 抢占失败，说明有其他线程先操作，继续循环
            continue;
        }

        // 情况2：项正在被其他线程插入，跳过当前项继续搜索
        if ((current_high & inserting_mark) != 0) {
            continue;
        }

        // 情况3：项已有完整键，检查是否匹配
        if (current_high == key_high) {
            uint32_t current_low = mint_load_32_relaxed(&entry.key_low);
            if (current_low == key_low) {
                // 键匹配，更新值
                mint_store_32_relaxed(&entry.value, value);
                return;
            }
        }

        // 情况4：键不匹配，继续线性搜索下一个项
    }
}

关键细节说明 #

1. 插入标记的作用：避免两个线程同时抢占同一个空闲项，确保只有一个线程能进入写入key_low的阶段，防止出现半写入的无效键。
2. 内存顺序：这里沿用原算法的relaxed内存顺序，如果需要更强的内存可见性，可以根据场景调整为acquire/release。
3. 冲突处理：遇到正在插入的项时选择跳过，你也可以加入短暂自旋等待，减少无效搜索次数，提升性能。
4. 键的兼容性：如果业务64位键的高32位可能用到0x80000000位，可以换用其他未使用的位，或者单独增加一个state字段标记插入状态。

额外优化：哈希分桶 #

原算法是全局线性搜索，表项增多后性能会下降。你可以把64位键的哈希值拆分为两部分：一部分用于选择桶的索引，另一部分用于在桶内线性搜索，减少每个线程需要遍历的项数，提升并发性能。

内容的提问来源于stack exchange，提问作者MaiaVictor