并发哈希表。

这是对 https://gitlab.redox-os.org/redox-os/chashmap 的分支，当时似乎很少维护。

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

API直接源自 std::collections::HashMap，因此具有熟悉的感觉。

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

工作原理

chashmap 不是无锁的，但它将锁分布在整个映射中，使得锁竞争（这可能会使访问变得昂贵）非常罕见。

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

有一个特殊情况：重新分配。当表填满到几乎没有空闲桶（注意，这“几乎没有”而不是“没有”，因为负载因子不应过高，因为它会损害性能）时，在重新哈希表时获取全局锁。这非常低效，但这种情况很少发生，并且由于容量是自适应的，因此它只在映射刚刚初始化时发生几次。

冲突解决

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

这种方法远非理想，但像Robin-Hood哈希这样的更优方法在并发结构中工作得不好（如果有的话）。

API

如果您习惯了libstd哈希表实现，API将感觉非常熟悉。它们共享许多方法，并且我已经仔细确保所有与libstd中类似命名的项在语义和行为上是一致的。