c++ - 具有多线程支持的 C++ HashMap

Question

我需要在 C++ 中使用 HashMap/HashTable 实现，并且我有以下要求

1-当新数据被插入hashmap时，完整的hashmap没有被锁定，并且允许其他线程读取和更新hashmap中的其他键/值

2- 多个键/值应该可以同时更新。即一个线程更新密钥x，而另一个线程更新密钥y。

C++ stl 或任何其他库中是否存在这样的实现？还是我需要自己写一些东西？

Answer 1

我相信微软 PPL 实现concurrent_unordered_map和英特尔 TBB 实现目前每个哈希仓都有一个锁。TBB 的语义也concurrent_hash_map略有不同。他们都不保证其规范中的任何数量的并发性。规范唯一保证的是没有数据竞争。

如果您的算法对并发哈希表写入的性能敏感，那么您可能会遇到麻烦。每次访问时获取和释放锁的成本类似于进行哈希表插入的成本。因此，由于锁定开销，您将失去一半的性能，并且需要更多的并行性来恢复它。您确定每个线程不能有一个哈希表，然后在完成后合并所有哈希表吗？（有些算法会让你侥幸逃脱，有些则不会。）

编辑：我刚刚注意到您要求能够同时更新密钥。这在我知道的任何并发哈希表实现下都是不可能的。原因是这是一个读取-修改-更新操作，正如@JoopEggen 指出的那样，它只是不适用于并发容器类型。实际上，这是一个读取-修改-更新-修改-更新操作。为了修改键，您需要使整个操作序列原子化。并发容器类型是监视器：每个单独的方法调用可以是原子的，但它们的序列不是。