哈希器

此crate是一组与哈希相关的功能集合，用于与Rust的std::collections::HashMap、HashSet等一起使用。

此外，还包括哈希函数的基准测试和一些用于测试哈希质量的统计测试。

免责声明

这些都不是 加密安全 的。不建议将此用于加密目的。我不是密码学家；我甚至不在电视上扮演这个角色。

许多（大多数？所有？）这些函数都不是设计来防止基于碰撞的拒绝服务攻击的。Rust的默认哈希函数是SipHash（1-3？），它是为了这个目的而设计的。许多这些函数旨在用于需要那种形式安全的地方的性能目的。

什么是哈希器？

在我们的目的中，哈希函数是一个函数，它接受另一个，一般的，值作为输入，并返回一个数字，这个数字理想上对那个值是唯一的。这个数字可以用来在数组中存储该值，然后稍后再不搜索数组的情况下找到它；换句话说，在O(1)时间内。更多或更少：还有很多其他细节。更多信息，请参阅Rust的HashMap和网上各种信息来源。

在Rust中，std:#️⃣:Hasher是一个特质

pub trait Hasher {
    fn finish(&self) -> u64;
    fn write(&mut self, bytes: &[u8]);

    fn write_u8(&mut self, i: u8) { ... }
    fn write_u16(&mut self, i: u16) { ... }
    ...
}

哈希器有两个必需的方法，finish 和 write，以及其他一些有用方法的默认实现，如 write_u8 和 write_u16，通过调用 write 实现。在使用中，创建一个哈希器的实现，使用各种 write 方法向其中提供数据，然后使用 finish 方法返回结果以获取哈希数字。

在Rust中使用自定义哈希函数

长期以来，使用Rust的HashMap或HashSet中的自定义哈希函数一直被视为一个深奥的秘密。现在，我将揭开无知之幕，揭示所有的秘密！

或者说类似的事情。这实际上并不是什么大问题。

创建使用自定义哈希器实现的HashMap有两种方法：在HashMap实例上设置哈希器，以及类型级别的技巧。

显式告诉HashMap使用哪个哈希器

每次需要哈希一个值，例如在插入或查询HashMap时，都会创建一个新的哈希器实例。（记住，哈希器特质的唯一方法是更新其状态或返回最终值。）

因此，我们不是传递一个哈希器，而是传递另一个特质的实例，即std::hash::BuildHash。Rust的标准库目前有两个该特质的实现

• std::collections::hash_map::RandomState，它创建DefaultHasher的实例，这是Rust实现SIP-something的哈希器，使用加密密钥防止拒绝服务攻击。
• std::hash::BuildHasherDefault，可以创建实现Default特质的任何Hasher实现的实例。

这个集合中的所有哈希器也实现了Default。

use std::collections::HashMap;
use std::hash::BuildHasherDefault;

use hashers::fx_hash::FxHasher;

// BuildHasherDefault also implements Default---it's not really interesting.
let mut map =
  HashMap::with_hasher( BuildHasherDefault::<FxHasher>::default() );

map.insert(1, 2);
assert_eq!(map.get(&1), Some(&2));

使用类型指定要使用的哈希器

作为替代方案，HashMap有三个类型级别的参数：键的类型、值的类型以及实现std::hash::BuildHash的类型。默认情况下，后者是RandomState，它安全地创建DefaultHashers。通过替换RandomState，可以由HashMap的具体类型确定使用的哈希器。std::hash::BuildHasherDefault在这里也很有用。

use std::collections::HashMap;
use std::hash::BuildHasherDefault;

use hashers::fnv::FNV1aHasher64;

// This could be more complicated.
fn gimmie_a_map() -> HashMap<i32,i32,BuildHasherDefault<FNV1aHasher64>> {
    HashMap::default()
}

let mut map = gimmie_a_map();

map.insert(1,2);
assert_eq!(map.get(&1), Some(&2));

一个更复杂的例子是这个模块包含的anagrams-hashmap.rs示例程序。

关于这个包

这个哈希器集合基于

• http://www.cse.yorku.ca/~oz/hash.html Oz的哈希函数。（oz）
• http://www.burtleburtle.net/bob/hash/doobs.html Bob Jenkins的（更新后的）1997年Dr. Dobbs文章。（jenkins）
• http://burtleburtle.net/bob/hash/spooky.html Jenkins的SpookyHash。（jenkins::spooky_hash）
• Rust的内置DefaultHasher（SIP 1-3？）（default）
• https://github.com/cbreeden/fxhash 从Firefox内部哈希器派生出的快速、非安全哈希算法。（fx_hash）
• http://www.isthe.com/chongo/tech/comp/fnv/ Fowler/Noll/Vo哈希算法。（fnv）
• https://hbfs.wordpress.com/2015/11/17/and-a-good-one-hash-functions-part vi/ Steven Pigeon的Bricolage哈希算法。
• 两个“空”哈希器：NullHasher对所有输入返回0，PassThroughHasher返回数据的最后8个字节。

每个子模块实现了一个或多个哈希器以及一个最小的测试模块。此外，该模块还有一个基准测试模块，用于比较哈希器，以及一些示例程序，使用统计测试来测试各种哈希器。

示例程序

chi2

卡方检验用于确定一个或多个类别中预期的频率与观察到的频率之间是否存在显著差异。-- 卡方检验

这个程序尝试计算一个数据集的哈希值，然后在128个桶的哈希表（2^7 - 1掩码）中使用这些值进行模拟，并尝试确定哈希桶是否均匀分布。我想是这样的。我不是统计学家，显然也不是一个很好的程序员。抱歉。

无论如何，它展示了对于多个样本以及每个Hasher的哈希值的低位可能进行的chi2测试。数值越接近0越好，介于3.0和-3.0之间显然“还可以”。也许吧。

样本包括

• 1000个均匀分布的6字节二进制值。
• 1000个均匀分布的6字节字母数字（ASCII）值。
• 1000个形式为'annnnn'的生成标识符。
• 来自data/words.txt的单词

kolmogorov-smirnov

Kolmogorov–Smirnov 统计量量化样本的经验分布函数与参考分布的累积分布函数之间的距离。[Kolmogorov–Smirnov test].

好吧，我对这个稍微更有信心。它与chi2程序相同的样本进行哈希处理，然后尝试确定64位哈希值与均匀分布的偏离程度，报告介于0.0和1.0之间的值。数值越低越好。然而，32位哈希如DJB2在这个测试中显然会失败，尽管它们可能对于少于2^32个条目的HashMap来说是可以的。

anagrams-hashmap

此程序根据data/anadict.txt中的anagrams词典，计算出可以由字母"asdwtribnowplfglewhqagnbe"组成的单词数量。（共有7440个。）它使用了通过Hashers参数化的HashMap和HashSet实现，并报告了每个hasher的耗时以及与默认hasher的比较。

更多信息，请查看我的古老博客系列

• https://maniagnosis.crsr.net/2013/02/creating-letterpress-cheating-program.html
• https://maniagnosis.crsr.net/2014/01/letterpress-cheating-in-rust-09.html
• https://maniagnosis.crsr.net/2016/01/letterpress-cheating-in-rust-16-how.html 及其他。