哈希函数将任意容量的数据映射为固定容量的数据，其返回值称为哈希值、哈希码、哈希和或哈希。计算机软件里用于快速数据查找的数据结构：哈希表。哈希函数通过检测大文件中的重复记录来加速数据库查询。哈希函数也常用于密码学。通过加密哈希函数可以将一些输入数据映射到指定的哈希值，但是很难从哈希值反推出输入数据。用于保证数据完整性，也是提供消息认证的HMAC的基础。

与哈希函数相关又容易混淆的概念包括，校验和（checksums）、校验位（check digits）、指纹（fingerprints）、随机函数（randomization function）、纠错码（error-correcting codes）、密码（ciphers）。这些概念有些交叉，具有不同的使用场景和需求，不同的设计和优化。

使用场景

哈希函数常用于哈希表，通过检索关键字（search key）快速定位一条数据记录，比如查字典。具体来说，哈希函数用于将检索关键字映射到索引（index）。索引给出了哈希表中对应记录的存储位置。哈希表用于实现关联数组（associative arrays）和动态集合（dynamic sets）。

通常，哈希函数的域(domain）（可能的key集合）大于其范围（range）（表索引数量），因此key和index是多对一的关系。哈希表的每个槽（slot）关联一组记录，因此哈希表的槽称为桶（bucket），哈希值也称为桶索引（bucket index）。

哈希函数仅仅提示了记录存储的位置——从何处开始查找。在半满的表中，好的哈希函数可以将搜索范围压缩到一个或两个条目。

缓存

哈希函数也可以用于构建慢速设备中存储的大数据集的缓存。缓存通常比哈希查找表简单，因为任何冲突都可以靠丢弃或写回冲突项的旧版本来解决。这种方式也用在文件比较中。

布隆过滤器（Bloom filters）

哈希函数是布隆过滤器（Bloom filter）的重要组成部分，布隆过滤器是一种节省空间的概率数据结构，用于检测某个元素是否是集合的成员。

查找重复记录

当存储记录在大的未排序文件中时，可以利用哈希表将记录映射到表T的一条索引，将哈希值都是i的记录存储在桶T[i]中。重复的记录会存放在同一个桶中。对每个所含元素多于两个的桶进行扫描，取出记录并比较。如果选择了合适容量的表，这种方法比其他替代方案要快很多，例如对文件排序并比较所有相邻对。

保护数据

哈希值可用于唯一标识机密信息。要求哈希函数是抗碰撞的（collision resistant），也就是说很难找到不同的数据生成同样的哈希值。这些函数分为加密哈希函数和可证安全哈希函数。可证安全哈希函数是最安全的，但是实际应用中速度太慢。抗碰撞性有部分是通过产生非常大的哈希值来实现的。例如，SHA-1，最安全的加密哈希函数，生成160位的值。

查找相似记录

哈希函数还可以用来查找具有相似key的记录。需要一种哈希函数，将相似的key映射最多相差m的哈希值，m是小整数（例如，1或2）。假设包含所有记录的表为T，利用这种哈希函数，类似的记录被哈希到同一个桶或邻近的桶中。那么只需要查找桶T[i]和T[i+k]中的记录，其中，k在-m和m之间。

包括所谓的声音指纹算法，用于在大规模音频文件集合中定位相似的声音条目。对于这种应用，哈希函数必须对数据捕获或传输错误，以及一些不重要的改变如时长、音量、压缩等不敏感。

查找相似子串

也可以在一堆字符串中查找相等或类似的字符串，例如文档库或基因组数据库。输入字符串被分成多个小块，哈希函数用于查找相等的块。

Rabin-Karp算法是一种快速的字符串查找算法，平均时间复杂度O(n)，其基于哈希来比较字符串。

几何哈希

这一原则被广泛地应用于计算机图形学，计算几何等诸多学科，解决许多二维或三维空间中的邻近问题（proximity problem），例如查找一组点中相距最近的点对，多个图形中最接近的图形，图像数据库中最相似的图像，等等。输入集合是某种度量空间，哈希函数就是将这种空间分为网格单元（cell)。哈希表就是具有两个或更多索引的矩阵（grid file, grid index, bucket grid)，哈希函数返回的是index tuple。这种特殊用例称为几何哈希（geometric hashing）或网格方法。几何哈希也用于电信，通常用于矢量量化（vector quantization），用来编码和压缩多维信号。

密码学中哈希的常见用途

认证、消息完整性检测（使用HMAC（哈希MAC））、消息指纹、数据损坏检测、数字签名效率。

特性

好的哈希函数通常需要满足以下特性，具体需求因应用而异，例如适合索引数据的哈希函数可能不是好的加密哈希函数。

确定性（Determinism）

哈希过程必须具有确定性，相同的输入总是生成相同的哈希值。从数学角度来看，必须是被哈希数据的函数。此需求排除了依赖外部变量的函数，例如伪随机数生成器或当前时间。也排除了依赖被哈希对象存储位置的函数，因为执行过程中存储位置可能会改变（可能在具有垃圾回收功能的系统中）。

均匀性（Uniformity）

好的哈希函数会将输入尽可能均匀地映射到输出区间。即，输出区间的每个哈希值生成概率是大致相同的。如果冲突增加，那么基于哈希的算法代价会变大。

注意，仅仅需要哈希值均匀分布，但不一定需要随机。不考虑性能的话，好的随机函数通常都是好的哈希函数，但是反过来不一定。

如果m条记录被哈希到n槽哈希表中，每个桶中记录数超过m/n的概率必须非常小。具体来说，如果m小于n，那么应该仅有少数桶的记录个数超过1或2。（在“完美哈希函数”中，每个桶中记录数都不超过1；但即使n大于m，也可能存在冲突，参见生日悖论）。哈希值的分布均匀性可以通过皮尔逊卡方检验（chi-squared test）来测定。

确定的范围

哈希函数的输出通常具有确定的范围。例如，用于加快数据查询的哈希，其输出限制在32位整型值。另一方面，加密哈希函数的输出范围较大，以防止蛮力破解。

从变长输入生成固定长度输出可以通过将输入分成固定大小的块来实现。用于数据查询的哈希函数对输入的块（例如字符串中的字符）进行迭代算数运算，来生成哈希值。在加密哈希函数中，这些块是通过单向压缩函数（one-way compression function）处理的。在这种情况下，块大小（block size）远大于哈希值大小。例如SHA-1，哈希值是160位，块大小是512位。

可变范围

许多应用中，每次程序运行，哈希值范围都是不一样的，在运行过程中也可能是不一样的（例如，当哈希表需要扩充时）。这种情况下，哈希函数参数变为两个——输入数据z和哈希值数量n。

常见的解决方案是输出范围很大（例如0至2^32 -1）的哈希函数，将结果除以n并取余数。如果n是2的幂，那么这个操作可以通过位掩码（bit masking）和移位来完成。使用这种方法，需要选择哈希函数，确保对于任意可能的n，结果都能均匀分布在0和n-1之间。根据所选哈希函数，余数可能仅对特定的n是均匀的，例如奇数或素数。

我们允许n不是2的幂，而且不使用除法和求余操作，这些操作有时很耗时。例如，n可以远小于2^b。考虑伪随机数生成器（PRNG）函数P(key)均匀分布在区间[0,2^b-1]。均匀分布在[0,n-1]上的哈希函数是nP(key)/2^b，除法就可以用移位来完成。

具有最小移动的可变范围（动态哈希函数）

当哈希函数用于在哈希表中存储值，并且程序运行结束后依然存在，那么哈希表应能够扩充或收缩，这种哈希表称为动态哈希表。

哈希函数会重定位最少数量的记录。z是被哈希的key，n是哈希值的数量，那么H(z,n + 1) = H(z,n)的概率为n/(n+1)。

线性哈希（Linear hashing）和螺旋式存储（spiral storage）是执行时间固定的哈希函数，但是放松了均匀的特性，以实现最小移动的特性。

可扩展哈希（Extendible hashing）的动态哈希函数需要与n成正比的空间，其成为已经插入的key的函数。

有些算法保留了均匀性，但是计算H(z,n)的时间与n成正比。

数据标准化

在一些应用中，输入数据可能包含了一些与比较无关的特征。例如，查找个人姓名时，需要忽略大小写差别。哈希函数需要兼容数据相等的标准，即认为相同的输入生成相同的哈希值。可以通过对输入进行预处理来解决。

连续性（Continuity）

用于查找相似数据的哈希函数必须尽可能地连续：相差不大的两个输入所得到的哈希值应该相等或近似相等。

注意，对于校验和、加密哈希函数来说，连续性反而是严重的缺陷。连续性仅用于某些应用的哈希函数，例如用于最邻近搜索（Nearest neighbor search）的哈希表。

不可逆

在加密应用中，哈希函数通常是几乎不可逆的，意味着不进行海量时间的计算，从哈希值h(x)重建输入数据x是不可能的。

哈希函数算法

对于多数哈希函数来说，哈希函数的选择主要取决于特定应用中输入数据及其概率分布。

Trivial hash function

如果被哈希的数据足够小，可以直接使用数据本身作为哈希值。哈希函数运算的代价为零。这种哈希函数是完美的，因为其将每个输入映射为不同的哈希值。

“足够小”取决于哈希值类型的大小。例如，Java中哈希码是32位整数。因此32位整数Integer和32位浮点数Float对象就可以使用本身的值；而64位整数Long和64位浮点数Double不能使用这种方法。

其他类型的数据也可以使用这种完美哈希模式。例如，对于字符大小写之间的映射，可以使用每个字符的二进制编码，作为表的索引，表中给出了字符的另一种形式（“a”=>“A”，“8”=>“8”等）。如果是存储为8位的字符（ASCII或ISO Latin 1），哈希表仅有2^8=256个表项；如果是Unicode字符，表中有17*2^16=1114112个表项。

同样的技术可以用在将双字母国家码（如“us”或“za”）映射为国家名（26^2=676个表项），5位数字邮政编码（如13083）映射为城市名（10000个表项）等。无效数据值（例如国家码“xx”或邮政编码00000）在表中为未定义，或者映射为”null“值。

完美哈希（Perfect hashing）

哈希函数是内射的（injective）——也就是说，每个合法输入映射为不同的哈希值——称之为完美。对于完美哈希，可以直接找到所要搜索的数据，不需要额外的搜索。

最小完美哈希（Minimal perfect hashing）

如果key数量为n的完美哈希函数输出范围是n个连续整数（通常为0至n-1），则称之为最小完美哈希。除了提供单步查找，最小完美哈希也会产生紧凑的哈希表，没有任何空槽。最小完美哈希比具有较大输出范围的完美哈希更难寻找。

哈希均匀分布的数据

如果输入是有界长度字符串且每个输入独立发生的概率均匀（如电话号码，车牌照，发票号码等），那么哈希函数应该将大致相同数量的输入映射为每个哈希值。例如，假设输入为整数z，范围[0, N-1]，输出为h，范围为[0, n-1]，其中N远大于n。那么哈希函数可以是h=z mod n（z除以n的余数）或者是h=(z*n)/N，或者其他公式。

h=z mod n被用于早期的随机数生成器，但是存在一些问题，其中一个问题就是当n接近N时函数变得越来越不均匀。

哈希具有其他分布的数据

这些公式不适用于非均匀分布或者非相互独立的数据。例如，每个超时的顾客住在同一地理区域，所以他们的电话号码开头3到4个数字是相同的。这种情况下，如果m是10000左右，除法公式(z*m)/M依赖开头的数字，会产生很多冲突；而余数公式z mod m，对尾部数字比较敏感，所产生的结果依然是均匀分布的。

哈希变长数据

如果数据是长字符串（长度可变）——例如个人姓名、网页地址、邮件信息——其分布往往是不均匀的，且依赖比较复杂。例如，自然语言中的文字中字符、字符对的分布是非常不均匀的。对于这种数据，比较明智的做法是使用依赖字符串中所有字符的哈希函数——以不同的方式依赖每个字符。

在加密哈希函数中， 通常使用Merkle–Damgård construction。通常的方案是，将输入分为小单元序列（位、字符、字等），并将所有单元b[1], b[2], …, b[m]顺序组合起来，如下

S ← S0;                         // Initialize the state.
for k in 1, 2, ..., m do        // Scan the input data units:
  S ← F(S, b[k]);               // Combine data unit k into the state.
return G(S, n)                  // Extract the hash value from the state.

这种模式也用在文本校验和和指纹算法中。状态变量S可以是32位或64位无符号整数；S0可以是0，G(S,n)可以是S mod n。F比较难选择，依赖数据本身的特征。如果单元b[k]是单个位，那么F(S,b)可以是，例如

if highbit(S) = 0 then
   return 2 * S + b
 else
   return (2 * S + b) ^ P

highbit(S)表示S最重要的位；‘*’操作符表示丢失溢出的无整形乘法；‘^’是按位异或或者按字操作；P是适当的固定字。

专用哈希函数

在很多情况下，可以设计专用（启发式）哈希函数，产生的冲突比通用哈希函数更少。例如，假设输入数据是文件名，例如FILE0000.CHK, FILE0001.CHK, FILE0002.CHK等，其中包含连续的数字。对于这种数据，提取文件名中的数字部分k，然后返回k mod n基本是最优的。毋庸置疑的是，对于不同分布的数据，专用哈希函数的性能要差很多。

滚动哈希（Rolling hash）

在一些应用中，例如子串查找，对于给定的n个字符的字符串t，必须计算每k个字符子串的哈希函数h；其中k是固定整数。最直接的做法就是提取t的每个这种子串s，分别计算h(s)，需要的操作次数与k·n成比例。然而，选择合适的h，就可以利用滚动哈希的技术将操作次数降为与k+n成比例。

通用哈希（Universal hashing）

通用哈希方案就是从一组哈希函数中选出函数h的随机算法，使用这种方式，任意两个不同的key冲突的概率为1/n，其中n是不同的哈希值数量。通用哈希（从概率意义上）保证，对于输入数据的任何分布，哈希函数应用就像利用随机函数一样。但是通用哈希比完美哈希的冲突要多，一般比专用哈希的操作也多。参见Unique Permutation Hashing。

利用校验和函数哈希

可以对校验和或指纹算法进行适当调整，作为哈希函数。这些算法会将任意长度字符串数据z映射为32位或64位字符串，然后再获取范围为[0, n-1]的哈希值。

这个方法可以产生足够均匀分布的哈希值，只要哈希值范围大小n小于校验和或指纹函数的范围。然而，在雪崩测试（avalanche test）中一些校验和效果不佳，许多应用可能需要考虑这一点。具体来说，CRC32校验和仅提供16位（结果的高位）用于哈希。此外，输入的每个位都对CRC32的每个位具有决定作用，也就是说如果输入的位翻转，在不看输入剩余位的情况下，可以知道输出的哪些位会翻转；所有用校验和计算哈希值的时候需要考虑所有32位。

利用加密哈希函数哈希

一些加密哈希函数，例如SHA-1，其均匀性比校验和或指纹更强，因此可以提供更好的哈希函数。

在一些传统应用中，此方法的优势不足以抵消其代价。然而，在key是由恶意代理选择的情况下，这种方法也可以保证均匀性。这种特性可以用于保护服务，免受拒绝服务攻击。

通过非线性表来哈希

随机数表（例如256个随机32位整数）可以提供高质量的线性函数，用作哈希函数，或者用于加密。哈希的key被分为8位（单字节）的部分，每个部分用作非线性表的一个索引。表中的值是通过对哈希输出值进行算术或XOR和添加的。因为表所占用的空间为1024字节，可以放入现代微处理器的缓存中，使得哈希算法的计算速度很快。因为表的值平均大于8位，输入的每个位都会影响几乎所有输出的位。这不同于乘法哈希函数的高位只影响结果的高位。

此算法的哈希过程很快，结果也很好（尤其是对于整数key的哈希）。

字符串的有效哈希

现代微处理器的处理速度已经很快，如果8位字符的字符串的哈希过程不是每次处理一个字符，而是将字符串当做32位或64位整数数组，然后通过算术操作（例如乘以常数和移位）对这些“宽字”整数值进行哈希/累加。剩余的字符小于CPU字长时需要特别对待（例如，每次处理一个字符）。

在字长为64位的微处理器上可以将哈希过程速度提高到原先的5倍或更多。

另一种方法是将字符串转化为32位或64位数值，然后执行哈希函数。避免字符串太过类似（“Aaaaaaaaaa”和“Aaaaaaaaab”）的方法就是用字符串的循环冗余校验（CRC）来计算32位或64位值。当然，两个不同的字符串的CRC可能一样，概率很小，仅需要检查实际的字符串来决定是否完全匹配。对于“Aaaaaaaaaa”和“Aaaaaaaaab”，CRC是不一样的。虽然CRC可以用作哈希值，但是并不是加密安全的，因为不具有抗冲突性。

局部敏感哈希（Locality-sensitive hashing）

参见 http://blog.csdn.net/icvpr/article/details/12342159

哈希函数列表

https://en.wikipedia.org/wiki/List_of_hash_functions

一致性哈希

一致性哈希是可变范围哈希的一种，当哈希表的size变化时，平均只有K/n个key需要重新映射，其中K是key的个数，n是槽的个数。传统的哈希表size变化时，几乎所有的key都需要重新映射。

最初用于实现鲁棒性较高的分布式缓存，少数缓存节点的故障不会对整个分布式缓存系统的缓存失效，进而造成内容服务器请求过多。

一致性哈希也用于实现分布式哈希表（DHT），DHT利用一致性哈希将key分配到一组分布式节点，并提供连接key对应节点的覆盖网络。

特点

“spread” “load” “smoothness” “balance” “monotonicity”

实现

参考wikipedia里的链接 https://en.wikipedia.org/wiki/Consistent_hashing

Implentations in various languages: C++ C# Erlang Go Java PHP Python Ruby Perl

改进

参考：http://blog.chinaunix.net/uid-122937-id-143168.html

里面介绍了分布式哈希（DHT）的几种常用哈希算法，对一致性哈希进行改进和另外的解决方式。

Rendezvous哈希也实现了一致性，使用的方法是Highest Random Weight (HRW)算法。