rust-concurrent-hashmap

文档

这是一个 Rust 实现的并发哈希表。

如果禁用默认功能，则该 crate 在稳定 Rust 上运行

[depdencies.concurrent-hashmap]
version = "0.2.1"
default-features = false

然而，由于使用了不稳定的功能，使用 nightly rustc 可以获得更好的性能。

用法

extern crate concurrent_hashmap;

use concurrent_hashmap::*;

fn main() {
    // Create a table mapping u32 to u32, using defaults
    let map = ConcHashMap::<u32, u32>::new();
    map.insert(1, 2);
    map.insert(30, 12);
    if let Some(mut val) = map.find_mut(&30) {
        // Update a value in-place if it exists
        // This mapping can not be modified while we have a reference to it
        *val.get() += 3;
    }
    // Update the value with key 129, or insert a default (3)
    map.upsert(129, 3, &|x| *x *= 3);  // 129 => 3
    map.upsert(129, 3, &|x| *x *= 3);  // 129 => 9
    map.remove(&1);
    for (&k, &v) in map.iter() {
        println!("{} => {}", k, v);
    }
}

为了在线程间共享映射，通常希望将其放在一个 Arc 中。可以在 examples/wordcount.rs 中找到一个更不人为（实际上是多线程）的示例。

实现

这个哈希表通过根据哈希值的初始位将键分配到几个独立的哈希表中来工作。每个分区都由自己的锁保护，因此访问一个分区的键不会阻止访问其他分区的键。在假设哈希函数均匀地将键分配到分区的情况下，通过分区数相等的一个因子减少了争用。键永远不会在分区之间移动，因此它们可以独立且无需锁定其他分区进行缩放。

每个分区是一个开放寻址哈希表，使用二次探测。删除由墓碑处理，桶占用由位图跟踪。

单线程插入性能与 std::collections::HashMap 相似或更好，而读取性能较差。

并发注意事项

这不是一个无锁哈希表。为了达到良好的性能，在持有锁的情况下应该尽量减少工作。持有锁的情况包括使用 .find()/.find_mut() 的结果，运行 .upsert() 中的更新闭包，以及遍历映射。为了减少竞争，可以使用 ConcHashMap::with_options() 构造函数将 concurrency 参数设置为期望同时访问表的线程数。

遍历不能提供表内容的稳定快照。在遍历表时执行的操作可能或可能不会反映在迭代中。遍历是通过每次锁定一个分区来工作的。