rust-fnv

Fowler–Noll–Vo散列函数的实现。

阅读文档

关于

FNV散列函数是一个定制的Hasher实现，对于较小的散列键更有效率。

Rust常见问题解答中提到，尽管默认的Hasher实现，SipHash，在许多情况下表现良好，但它与其他短键算法（如整数到其他值的映射）相比，速度明显较慢。在这些情况下，FNV的速度明显更快。

其缺点是它在较大的输入上表现不佳，并且无法提供对碰撞攻击的保护，恶意用户可以设计特定的键来减慢散列器的速度。因此，确保您使用的是小散列键，并且您的程序不可能暴露于恶意输入（包括网络服务器）中，这一点非常重要。

Rust编译器本身使用FNV，因为它不担心拒绝服务攻击，并且可以假设其输入将是小的——这是FNV的一个完美的用例。

用法

要将此crate包含到您的程序中，请将以下内容添加到您的Cargo.toml

[dependencies]
fnv = "1.0.3"

在HashMap中使用FNV

FnvHashMap类型别名是使用带有FNV的标准库的HashMap的最简单方式。

use fnv::FnvHashMap;

let mut map = FnvHashMap::default();
map.insert(1, "one");
map.insert(2, "two");

map = FnvHashMap::with_capacity_and_hasher(10, Default::default());
map.insert(1, "one");
map.insert(2, "two");

注意，标准库的HashMap::new和HashMap::with_capacity仅实现了RandomState散列器，因此使用Default来获取散列器是次优选项。

在 HashSet 中使用 FNV

同样地，FnvHashSet 是标准库中 HashSet 使用 FNV 的类型别名。

use fnv::FnvHashSet;

let mut set = FnvHashSet::default();
set.insert(1);
set.insert(2);

set = FnvHashSet::with_capacity_and_hasher(10, Default::default());
set.insert(1);
set.insert(2);