翻译自http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
在二叉搜索树中，我们通过对集合中数据进行排序然后对比Key使得查找数据很快，由二叉树的结构可计算出查找的时间复杂度最大为O(log N)。但是当遇到退化树（树中只有一个叶子结点，每个非叶子结点只有一个孩子。一棵退化树等价于一个链表）的几率增大时，二叉搜索树的时间复杂度也将会随之增大。
一个可以想到的方法是建立一张表，将Key来作为表索引，然后在对应表项中存储对应的值，这样的话时间复杂度将降低到O(log N)以下，查找或者其他操作的时间复杂将接近常数O(1)。
不幸的是并不是所有的Key都适合用来作为表索引。比如字符串就是不合适的，因为表索引需要一个整数。即使对整数而言，当整数的值超过了表的最大长度时，也会导致数组越界错误。解决这个问题的办法就是使用哈希。
当数据的Key为整数时我们很容易想到将Key转换为表索引的办法，一般的操作时将这个Key强制转化为表长度以内的数值，使用最多的就是求余算法。
unsigned index = key % N;但是，由于两个原因导致这种算法并不适用在大多数情况中。首先，在大多数情况下Key为字符串，所以往往需要一种将字符串转换为整型数的方法，否者哈希将无法进行下去。第二，将整型Key转换为小范围的数值时，可能会出现不同的Key转换成同一表索引的情况。这种情况被称为冲突，哈希算法的设计者应尽量避免出现哈希冲突。
将字符串哈希成表索引比整型数据要复杂的多，因为字符串是由多个字符组成的，所以在使用字符串时要选择良好的哈希函数。幸运的是哈希字符串可以看作是哈希一段连续的内存块，这样的话可以避免为不同的数据类型设计不同的哈希函数。接下来的篇幅将介绍这种操作时如何实现，并且介绍一些常用的哈希函数。
哈希的使用
就目前而言，哈希使用最多的场景就是将Key转换为数组的索引。这种数组结构被称为哈希表，被非常广泛地应用在各种场景中。例如，在编译器中，关键词与标志符往往存放在哈希表中，因为它们的信息需要快速地被查找获取出来。除此之外，编译器可能（可以说应该）使用哈希表来对switch语句进行优化等其它一些重要用途。同时，哈希表非常适合用来实现Cache功能，很多web浏览器与操作系统的Cache往往就是这样实现的。
哈希的另一众所周知的可能就是用在加密系统了，用以生成鉴权或者验证完整性的数字指纹。虽然查找哈希不像加密哈希那样复杂或者说功能强大，但是按照加密哈希的设计原则来实现查找哈希往往会使查找哈希具有更好的性能。
本篇教程重点在介绍查找哈希。
鸽巢定律
当把一个Key哈希成一个数组的索引时，我们很容易意识到这个数组的大小应不小于Key所在的集合大小。这是显而易见的，有些人可能认为这说了跟没说一样:)，但是专业术语来说这就被称为鸽巢定律：当把M个元素放置在N个容器中，如果M大于N，那么总会有容器中的元素大于1个的。这是有助于理解哈希冲突的两个定律之一。
哈希冲突指的是两个Key经过哈希之后成为了相同的索引。鸽巢原理证明了在Key的数量大于数组大小的情况下，不存在哈希算法能够把每一个Key都哈希成不同的数组索引。因为大多数查找哈希的使用往往是具有大范围的Key并且将这些Key转换为小范围的索引，所以这也是为什么不存在一个哈希算法可以完美地将一连串的未知Key值转换为不同的索引值。
完美哈希
在告诉大家哈希冲突是不可避免的噩梦，打破了你认为存在完美哈希算法的美梦之后，接下来我将自相矛盾地说确实存在完美哈希。然而，尽管存在完美的哈希算法，但是去预知输入Key的多少以及确切的Key的构成（注：即Key的构成特点）也是几乎不可能的。正是这样，虽然对于每一个输入都有与之对应的完美哈希算法，但是一直期望去找出它是不合理的，我们应该建立一个哈希算法去减少冲突而不是消灭冲突、去一味地寻找所谓的完美哈希。
构建一个完美哈希
在得知输入Key的数量以及Key的构成特点之后一个完美哈希算法是可以设计出来的。例如，现在我们需要将十个产品编号进行哈希，这十个产品编号的第4位和第5位上的数字都是不相同的，那么针对这个产品编号我们很容易可以设计出一个完美的哈希算法：
unsigned hash(unsigned pid)
{
return pid / 1000 % 100;
}然而，值得注意的是尽管只有10个产品编号，但是我们需要创建一个100大小的数组去容纳它们因为这个哈希算法的结果是个两位数。这简直是对内存空间的浪费，可是如果我们用恰好10个元素容量的数组去存放结果，那么又将会导致冲突。正是由于这样，鸽巢定律生效，我们不能去保证这个哈希算法就是完美的。
最小完美哈希
一个最小完美哈希算法可以将每一个Key映射到每一个存储空间中，而且不会造成存储空间的浪费。与上面的完美哈希不同，当对产品编号的第4、5位数字进行哈希后存放在大小为10的数组中时，一个最小完美哈希是不会存在冲突的。去发现这样的算法是极度困难的，这还仅仅是处理两个数字的情况。
一个最小完美哈希只能耗费大量的人力去寻找或者只适用于一些特殊的例子中。例如，把0~9这10个一位数哈希之后存放在大小为10的数组中是极其简单的，但是如果是10个两位数那么这个问题将变得复杂起来。通常来说，一个最小完美哈希只能通过不断的寻找和尝试才能被发现。
一些用来寻找完美和最小完美哈希的工具已经被设计出来了，如果需要的话这些工具将比人工寻找哈希算法要好得多。很多这样的小工具在网上都是可以免费获取的。
理想哈希的性质
在理解大多数情况下冲突是不可避免的之后，去设计一个查找哈希的目标应该是尽量减少冲突。这一般意味着要使得哈希值有着不同的分布，就像一个随机数生成器那样。和随机数生成器有所不同的是，哈希这个过程是可重复的，这样相同的Key经过哈希之后会输出相同的索引，不同的Key将不会这样。这个目标分开来说就是理想哈希具有的两个通用性质。
一个理想哈希会置换Key的内部状态（注：使用Key变换后作为输入），这样每一个哈希结果是由唯一的输入产生的。任何使用Key的每个部分来计算哈希值的哈希算法都满足这个需求，但是一般情况下仅仅使用Key的一部分来参与计算的算法性能是很糟糕的，因为参与计算的Key的那一部分可能恰好是Key之间的相同之处。例如我们只使用一个字符串的前四个或者五个字符对这个字符串进行哈希，如果输入是一个URL，字符串开头是“http://”，那么哈希所有的URL结果都是都是一样。
如果一个哈希算法对输入只有一个位不同的Key哈希结果都有着很大的不同，我们称这样的效果为雪崩。这种效应有利于哈希结果分布，因为相似的Key并没有相似的哈希结果。一个能够将哈希结果足够分散的哈希算法可以极大地降低冲突并且填充数组更具有随机性。雪崩这个定义来源于加密哈希，但是将它的概念应于用查找哈希可以使查找哈希工作得更好。
你可能经常会看到一些自称“字符串最佳”或“整型数最佳”的哈希算法。这些算法尽量避免使用，因为如果一个算法不能够适用于所有的数据类型那么这个算法通常来说可能是一个烂算法。虽然这么说，有时一个哈希算法可能出于性能考虑会对某一数据类型作出优化。学着去区分上面这两种算法是很有好处的，但是使用一些常用的、大众好评的哈希函数是最安全的。这篇教程将提供一些常用的比较好的哈希函数。
使用已有的哈希函数
设计哈希函数是一个黑魔法。正因为如此，我们最好还是使用一些大众认可的算法而不是自己去造轮子。哈希函数在某种程度上和随机数生成器很相似，和随机发生器一样，设计一个烂的哈希函数比设计一个一般般的哈希函数要容易的多:)。这篇教程加下来将介绍几种优秀的哈希函数，避免当需要的时候自己去设计这样的函数。我们也会去看一下并不是那么好的哈希函数，这样在实际使用时我们可能学会如何去辨别它们。
加法哈希
对一连串的整型值（比如一个字符串）进行哈希可能最简单的方法就是把所有的字符值加起来，然后将得到的值通过求余限定在一定范围内。给出这个例子的原因是一般教科书在介绍哈希冲突时往往以此举例。这个算法是很糟糕的。
unsigned add_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h += p[i];
}
return h;
}一般来说，任何主要依赖于可交换操作的散列算法将具有非常差的分布。这个哈希算法没有对待不同的排列，所以“abc”，“cba”，“cab”都将生成同样的哈希结果。
尽管这个算法很糟糕，但是这个例子在介绍如何设计哈希算法时还是很有用处的。加法哈希可以用来哈希字符串、整型、浮点型以及标量数组等任何你能想到的，因为任何类型的对象都可以当作由一个字符数组组成。
XOR hash
这个算法相对加法哈希是有很大的进步的，但是依旧不是很好，因为内部的状态并没有充分的混合达到雪崩的程度，仅仅异或产生的效果也没有对内部序列进行改变。
unsigned xor_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h ^= p[i];
}
return h;
}下面的几种哈希函数都有较好的功能，但是实际项目中需要测试之后再做选择。
Rotating hash
unsigned rot_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h = (h << 4) ^ (h >> 28) ^ p[i];
}
return h;
}Bernstein hash
unsigned djb_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h = 33 * h + p[i];
}
return h;
}Modified Bernstein
unsigned djb_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h = 33 * h ^ p[i];
}
return h;
}Shift-Add-XOR hash
unsigned sax_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h ^= (h << 5) + (h >> 2) + p[i];
}
return h;
}FNV hash
unsigned fnv_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 2166136261;
int i;
for (i = 0; i < len; i++)
{
h = (h * 16777619) ^ p[i];
}
return h;
}One-at-a-Time hash
unsigned oat_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h += p[i];
h += (h << 10);
h ^= (h >> 6);
}
h += (h << 3);
h ^= (h >> 11);
h += (h << 15);
return h;
}JSW hash
unsigned jsw_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 16777551;
int i;
for (i = 0; i < len; i++)
{
h = (h << 1 | h >> 31) ^ tab[p[i]];
}
return h;
}ELF hash
unsigned elf_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0, g;
int i;
for (i = 0; i < len; i++)
{
h = (h << 4) + p[i];
g = h & 0xf0000000L;
if (g != 0)
{
h ^= g >> 24;
}
h &= ~g;
}
return h;
}Jenkins hash
#define hashsize(n) (1U << (n))
#define hashmask(n) (hashsize(n) - 1)
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c >> 13); \
b -= c; b -= a; b ^= (a << 8); \
c -= a; c -= b; c ^= (b >> 13); \
a -= b; a -= c; a ^= (c >> 12); \
b -= c; b -= a; b ^= (a << 16); \
c -= a; c -= b; c ^= (b >> 5); \
a -= b; a -= c; a ^= (c >> 3); \
b -= c; b -= a; b ^= (a << 10); \
c -= a; c -= b; c ^= (b >> 15); \
}
unsigned jen_hash(unsigned char *k, unsigned length, unsigned initval)
{
unsigned a, b;
unsigned c = initval;
unsigned len = length;
a = b = 0x9e3779b9;
while (len >= 12)
{
a += (k[0] + ((unsigned)k[1] << 8) + ((unsigned)k[2] << 16) + ((unsigned)k[3] << 24));
b += (k[4] + ((unsigned)k[5] << 8) + ((unsigned)k[6] << 16) + ((unsigned)k[7] << 24));
c += (k[8] + ((unsigned)k[9] << 8) + ((unsigned)k[10] << 16) + ((unsigned)k[11] << 24));
mix(a, b, c);
k += 12;
len -= 12;
}
c += length;
switch (len)
{
case 11: c += ((unsigned)k[10] << 24);
case 10: c += ((unsigned)k[9] << 16);
case 9: c += ((unsigned)k[8] << 8);
/* First byte of c reserved for length */
case 8: b += ((unsigned)k[7] << 24);
case 7: b += ((unsigned)k[6] << 16);
case 6: b += ((unsigned)k[5] << 8);
case 5: b += k[4];
case 4: a += ((unsigned)k[3] << 24);
case 3: a += ((unsigned)k[2] << 16);
case 2: a += ((unsigned)k[1] << 8);
case 1: a += k[0];
}
mix(a, b, c);
return c;
}