为 Rust 实现的 QP-Trie

API 文档

qp-trie 是一种快速且紧凑的关联数组。

它与 crit-bit trie 类似，每个内部节点有更大的分支因子，以节省内存并减少查找成本。

它以高速支持以下操作

• 检查键是否在 trie 中并检索关联的可选值
• 将 (key, value) 对添加到 trie 中
• 从 trie 中删除键
• 查找匹配给定前缀的所有键

此实现使用每个索引 4 位，且不需要键以零终止。

示例

use qptrie::Trie;

let mut trie = Trie::new();
trie.insert("key number one", 1);
trie.insert("key number two", 2);

for (k, v) in trie.prefix_iter(&"key").include_prefix() {
     println!("{} => {}", k, v);
}

trie.remove(&"key number one");

let v = trie.get(&"key number two").unwrap();

基准测试

~500,000 个 4 字节键以随机顺序访问 (源)，使用 rustc 1.15.0-dev (d9aae6362 2016-12-08)

test test::bench_btreemap_get    ... bench: 112,349,209 ns/iter (+/- 9,450,753)
test test::bench_btreemap_insert ... bench: 115,952,204 ns/iter (+/- 7,066,195)
test test::bench_hashmap_get     ... bench:  52,239,122 ns/iter (+/- 2,225,861)
test test::bench_hashmap_insert  ... bench:  60,889,965 ns/iter (+/- 27,314,557)
test test::bench_qptrie_get      ... bench:  51,843,861 ns/iter (+/- 18,878,702)
test test::bench_qptrie_insert   ... bench:  67,449,566 ns/iter (+/- 16,887,173)

qp-tries 的速度比 Rust 的 BTreeMap 快两倍以上，与 Rust 的优秀 HashMap 实现速度相当，同时更紧凑，并允许范围查询。