hamt-rs

基于Phil Bagwell的Ideal Hash Trees论文的哈希数组映射Trie实现。这是Scala和Clojure标准库中使用的持久化映射数据结构。使用特殊冲突节点来处理哈希冲突的想法来自Clojure的实现。

用法

let mut map = HamtMap::new();

for i in range(0, size) {
    map = map.plus(i, i);
}

if map.find(&0) == Some(1) {
    ...
}

let (without_10, size_changed_10) = map.remove(&10);
let (without_20, size_changed_20) = map.remove(&20);

for (k, v) in map.iter() {
    ...
}

性能

到目前为止看起来相当不错，对于一个完全持久化的数据结构。以下基准测试是在Core i7-4712MQ上进行的，使用随机数和编译标志-C lto -C opt=3 -C target-feature=+popcnt。

查找

在包含ELEMENT COUNT个元素的集合中进行一千次查找的时间（键和值类型为u64）。

相对于std::HashMap的百分比（小于100%表示更快，更大表示比std::HashMap慢）。

HAMT与std::HashMap相当，即使是对于更大的集合。 不幸的是，LLVM（目前）还没有正确地转换cntpop内建函数（这在许多架构上可能只是一个CPU指令，但当前转换为更昂贵的指令序列）。 如在Reddit上指出，正确配置LLVM（例如，通过设置target-cpu选项）对于它能够发出popcnt指令是必要的。

插入

在包含ELEMENT COUNT个元素的集合中进行一千次插入的时间（键和值类型为u64）。

相对于std::HashMap的百分比（小于100%表示更快，更大表示比std::HashMap慢）。

如上图所示，HAMT与非持久化std::HashMap相比表现相当好。