1.2　非加密散列函数

相较于加密散列函数，非加密函数并非为了抵御旨在发现散列碰撞的攻击而设计，因此不需要安全性和较高的抗碰撞性。这样的函数必须能快速计算并且保证低的散列碰撞概率，因而允许以合理的错误概率快速对大量数据进行散列。

（1）Fowler/Noll/Vo

Fowler/Noll/Vo（FNV或FNV1）非加密散列算法的基本思想来自于1991年，由Glenn Fowler和Phong Vo发送给IEEE POSIX P1003.2委员会作为评审意见的一个想法，随后由Landon Curt Noll进行了改进［Fo18］。

FNV算法保持初始化为特殊偏差量的内部状态。之后，算法对8比特的输入块进行迭代，并对FNV质数（FNV Prime）的较大数值常量执行状态乘法，然后对输入块应用逻辑异或（XOR）。在处理完最后一个输入之后，状态的结果值将作为散列被报告。

FNV质数和偏差量基常数是设计参数，取决于生成的散列值的位长。正如Landon Curt Noll所提到的，素数的选择是FNV算法很奇妙的一部分。对于相同的散列大小，一些素数的散列效果优于其他方法的素数散列效果。

当前必须首选的FNV1a替代算法是FNV算法的一个较小变体，仅在内部XOR和乘法运算的顺序上有所不同。尽管FNV1a与FNV1使用相同的参数和FNV质数，但其XOR折叠提供了更好的分散效果，而不会影响CPU性能。

当前，FNV散列函数族包含用于32位、64位、128位、256位、512位和1024位散列值的算法。

FNV的实现非常简单，但是其散列值的高度分散性使其非常适合散列几乎相同的字符串。它广泛用于DNS服务器、推特(twitter)、数据库索引散列、网页搜索引擎以及其他地方。几年前，FNV1a的32位版本被推荐作为IPv6流标签生成的散列算法［An12］。

（2）MurmurHash

Austin Appleby在2008年发布了另一个著名的散列函数族，称为MurmurHash，并在2011年最终确定为MurmurHash3算法［Ap11］。

MurmurHash算法使用一种特殊的概率技术来近似全局最优值，以找到一种散列函数，能以最佳方式混合输入值比特以产生输出散列比特。MurmurHash算法的各代主要在混合功能方面有所不同。

该算法的速度是速度优化的lookup3散列函数[1]的两倍。MurmurHash3包括适用于x86和x64平台的32位和64位版本。

当前，MurmurHash3是最流行的算法之一，并用于Apache Hadoop、Apache Cassandra、Elasticsearch、libstdc++、nginx等。

（3）CityHash与FarmHash

Google在2011年发布了由Geoff Pike和Jyrki Alakuijala［Pi11］开发的新字符串散列函数族，名为CityHash。CityHash函数是基于MurmurHash2算法的简单非加密散列函数。

CityHash散列函数族的开发重点是对概率数据结构和散列表最感兴趣的短字符串（例如，最大为64B）。它包括32位、64位、128位和256位版本。对于这样的短字符串，64位版本的CityHash64比MurmurHash更快，并且胜过128位的CityHash128。然而，尽管对于具有至少几百个字节的长字符串而言，CityHash128比CityHash系列的其他散列函数更可取，但实际上，最好使用MurmurHash3。

CityHash的一个缺点是它相当复杂，并且会导致在不同编译器上出现非最佳行为，从而大大降低其速度。

2014年，Google发布了由Geoff Pike［Pi14］开发的CityHash的后继产品，称为FarmHash。新算法包含CityHash中使用的大多数技术（不幸的是，同时继承了其复杂性）和新一代MurmurHash。FarmHash函数会完全混合输入比特，但该操作并不足以用于加密。

FarmHash使用特定于CPU的优化，但仍需要调整编译器以获得最佳性能，并且依赖于平台。值得注意的是，所计算的散列值在不同平台之间也有所不同。

FarmHash函数存在于多个版本中，而64位版本的Farm64在包括手机在内的许多平台的测试中均优于CityHash、MurmurHash3和FNV等算法。

[1] 散列函数和块密码见https://burtleburtle.net/bob/hash/