qp-trie-rs：纯Rust实现的QP-trie

QP-trie（“Quelques-bits Popcount trie”或“Quad-bit Popcount trie”）是键的基数 trie，可以解释为 nybble（nybble是半个字节，或四位）的字符串。QP-tries本质上是一种 Patricia trie，它以 nybble 而不是单个位进行分支；因此，QP-trie 的分支因子（和基数）为16。

通过Serde进行序列化/反序列化

可选的，qp_trie::Trie 类型支持通过 serde 进行（反）序列化。启用 serde 功能将启用对 Deserialize 和 Serialize 实现的编译。

何时应该使用QP-trie？

此crate中实现的QP-tries是任何实现了 Borrow<[u8]> 的键的键值映射。当需要像 HashMap 或 BTreeMap 那样的操作，但需要稍微更快一些（QP-tries与Rust的默认哈希器的 HashMap 一样快或更快）以及/或能够有效地查询具有给定前缀的元素集合时，它们非常有用。

QP-tries支持高效地查找/插入/删除单个元素，以及查找/删除具有给定前缀键的值集合。

示例

键可以是任何实现了 Borrow<[u8]> 的类型。遗憾的是，目前这排除了 String 类型——尽管这个 trie 仍然可以用来存储字符串，但必须手动将它们转换为字节切片和 Vec<u8> 用于键。以下是一个简单的例子，将 9 个 2 元素的字节数组放入 trie 中，然后删除所有以 "1" 开头的字节数组

use qp_trie::Trie;

let mut trie = Trie::new();

for i in 0u8..3 {
    for j in 0u8..3 {
        trie.insert([i, j], i + j);
    }
}

for i in 0u8..3 {
    trie.remove([1, i]);
}

assert!(trie.iter().all(|(&key, _)| key[0] != 1));

这是一个稍微不那么天真但效率更高的方法

use qp_trie::Trie;

let mut trie = Trie::new();

for i in 0u8..3 {
    trie.extend((0u8..3).map(|j| ([i, j], i + j)));
}

trie.remove_prefix([1]);

assert!(trie.iter().all(|(&key, _)| key[0] != 1));

尽管 extend 真的并没有更高效（在 trie 中为 n 个元素预分配空间是很困难的），但我们保证 trie.remove_prefix([1]) 只会真正删除 trie 中的一个节点——具有给定前缀的所有节点的父节点。QP-tries，就像所有的基数 trie 一样，在处理与前缀相关的事情时非常高效。这包括对前缀的迭代

use qp_trie::Trie;

let mut trie = Trie::new();

for i in 0u8..3 {
    trie.extend((0u8..3).map(|k| ([i, j], i + j)));
}

let mut iter = trie.iter_prefix([1]);

assert_eq!(iter.next(), Some((&[1, 0], &1)));
assert_eq!(iter.next(), Some((&[1, 1], &2)));
assert_eq!(iter.next(), Some((&[1, 2], &3)));
assert_eq!(iter.next(), None);

与 qptrie crate 的差异

这个 crate 最初是 qptrie 的一个分支；然而，我发现代码难以工作，充满了不安全的指针操作，我认为可以避免。为了避免一个基本上重写整个库的 pull request，我决定自己写一个。

test bench_btreemap_get      ... bench: 111,468,098 ns/iter (+/- 10,103,247)
test bench_btreemap_insert   ... bench: 112,124,846 ns/iter (+/- 14,296,195)
test bench_exotrie_get       ... bench:  46,195,582 ns/iter (+/- 16,943,561)
test bench_exotrie_insert    ... bench:  52,886,847 ns/iter (+/- 15,574,538)
test bench_fnvhashmap_get    ... bench:   9,530,109 ns/iter (+/- 820,763)
test bench_fnvhashmap_insert ... bench:  21,281,107 ns/iter (+/- 7,254,084)
test bench_hashmap_get       ... bench:  49,653,426 ns/iter (+/- 7,004,051)
test bench_hashmap_insert    ... bench:  47,771,824 ns/iter (+/- 4,979,606)
test bench_trie_get          ... bench:  40,898,914 ns/iter (+/- 13,400,062)
test bench_trie_insert       ... bench:  50,966,392 ns/iter (+/- 18,077,240)