- 日常应用:计算从业者几乎每天都接触哈希函数,如安装软件包时用其验证真实性,浏览网页时用于检查 Web 服务器证书。非加密哈希函数也随处可见,写代码用字典(常由哈希函数实现),使用负载均衡器时用其分配负载,还有用于数据计数和去重的算法也利用非加密哈希提高效率。
- 功能特点:加密和非加密哈希函数的共同特点是将任意大小的数据输入转换为特定长度的确定性输出,是单向过程,无需解密。加密哈希函数有抗碰撞和抗原像等安全要求,设计时涉及位操作、查找表和重复轮次等以混合输入数据;非加密哈希函数主要要求将输入数据以合理方式映射到资源,通常追求输出均匀分布,以提高效率。
- 常见示例及测试:列举了 FNV-1a、FNV-1、Murmur2、DJBX33A 等常见非加密哈希函数及其伪代码和特点,通过将它们用于填充哈希表来评估行为,如使用不同数据集(婴儿名字、常用单词、偏置数据、IP 地址等),观察空桶数量和 p 值等,发现不同哈希函数在处理不同数据集时表现各异,且选择合适的桶数(M 值)也会影响结果。
- 雪崩准则:常用的设计非加密哈希函数的原则是雪崩准则,即改变输入的一位会使输出的每一位有 50%的概率改变。Murmur2 设计时考虑了该准则,表现出色;FNV 哈希函数和 DJBX33A 相对简单,在输入字节的处理上存在一些导致输出模式保留的问题。雪崩准则针对单比特输入变化,在实际数据中并不常见。
- 历史渊源:早期在讨论数据加密标准(DES)中的 S 盒时出现类似雪崩准则的内容,后来在一些关于非加密哈希函数的论文中也提到雪崩效应,但这些引用要么本身是死胡同,要么对雪崩准则的普遍适用性持保留态度。
- 包装雪崩:雪崩准则针对 32 位输出的均匀性,而应用通常要求输出在 M 个资源上均匀分布,除非 M 是 2 的幂次方,否则会存在偏差问题,随机数生成器中已有相关研究,哈希函数领域相对较少。
- 总结思考:加密和非加密哈希函数虽常见,但设计方式存在差距,非加密哈希函数虽有历史但未被充分探索,均匀分布对实际数据集有意义但面对特定模式数据集有挑战,雪崩准则对加密哈希函数重要,但对哈希表中条目分布影响不大,研究针对特定情况的哈希函数有助于明确如何评估非加密哈希函数。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。