我目前有大约 15 个工作线程在 CPU 绑定(bind)循环中处理数据。每次确定结果时，都会获得一个 RW 锁，因此可以将结果存储在一个共享的 KV 结构(哈希表)中，键是唯一的。
由于很多时间花在获取锁上，我正在探索不同的选项来提高性能。我玩过无锁哈希表(concurrent_unordered_map 和 Intel TBB 无锁结构)，但一直想知道是否让每个线程将其结果记录在单独的哈希表中，一旦所有线程完成，执行某种冲突解决。
冲突解决基本上是针对每个 [K1,V1], [K1,V2], .... [K1,Vn] 应该合并成 [K1,F(V1,V2,...Vn) ].
我很好奇哪种数据结构最适合从其他结构迭代同一键的所有值。我敢肯定，一定有比分别迭代每个结构更好的方法。创建一个多图，批量添加单独的结构，然后解决冲突等等？
最佳答案
使用允许您直接访问其后备数组的哈希表，并为每个线程的哈希表使用相同大小的后备数组。然后当需要合并哈希表时，在工作线程之间划分支持数组 - 例如，有 15 个工作线程并假设支持数组大小为 1500，worker_thread_1 将从 [0, 100), worker_thread_2 将从 [100, 200) 开始遍历每个哈希表的后备数组，等等。这样每个工作线程都可以执行合并而无需获取任何锁或以任何其他方式与其他工作线程通信。直接遍历后备数组会带来一些低效率，因为一些数组元素将为空(可能有 10-50% 的元素将为空，具体取决于哈希表的负载因子)，但同时直接遍历您不需要执行散列函数的后备数组，这应该可以弥补遍历空元素的低效率。
您需要为每个线程的哈希表使用相同大小的后备数组，以确保每个键哈希到相同的数组元素(尽管在划分子数组时可能有一种方法可以纠正不同大小的后备数组)你的工作线程 - 我只是想不出合适的算法)。
您还需要使用一个哈希表，该哈希表使用链接列表来解决冲突 - 使用探测冲突的哈希表会使事情变得过于复杂。
您可以通过使用有序映射(例如平衡二叉树或跳跃列表)并在工作线程之间平均分配键来完成同样的事情，但这不会那么有效，因为您将使用哈希表的 O(log(n)) 插入和查找，而不是恒定时间(平均)插入和查找。
关于algorithm - 用于合并唯一键的最快 KV 数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17014302/