并发哈希表。

这是一个 https://gitlab.redox-os.org/redox-os/chashmap 的分支，在撰写本文时，它似乎没有得到很好的维护。

这个crate实现了基于桶级多读锁的并发哈希表。它具有出色的性能特征¹，并支持调整大小、原地修改等。

API直接来自 std::collections::HashMap，因此它感觉非常熟悉。

¹请注意，它严重依赖于您程序的行为，但在大多数情况下，它确实很好。在某些情况下（非常罕见），您可能希望使用原子哈希表。

工作原理

chashmap 不是无锁的，但它将锁分布在哈希表上，使得锁竞争（这可能导致访问成本高昂）非常罕见。

哈希表由所谓的“桶”组成，每个桶定义了表中的一个潜在条目。某些键值对的桶由键的哈希值确定。通过为每个桶持有读写锁，我们可以确保您通常只需要一个或两个锁定子程序即可插入、读取、修改等。

特殊情况：重新分配。当表已满，几乎没有任何空闲桶时（请注意，这是“几乎”没有，而不是“没有”，因为负载因子不应该太高，因为它会损害性能），在重新哈希表时获得全局锁。这非常低效，但这种情况很少发生，并且由于容量的自适应性，它仅在地图初始化后的几次才会发生。

冲突解决

当两个哈希值冲突时，它们不能共享同一个桶，因此必须有一种算法可以解决冲突。在我们的情况下，我们使用线性探测，这意味着我们取它后面的桶，并重复直到找到空闲的桶。

这种方法远远不是理想的，但像Robin-Hood哈希这样的更优方法在并发结构中（如果有的话）效果很差。

API

如果您熟悉libstd哈希表实现，API应该非常熟悉。它们共享许多方法，我已经仔细确保所有在libstd中具有类似名称的项目在语义和行为上都匹配。