一致性hash参考：一致性哈希
Hash函数也称为散列表，是一种常用的数据结构。哈希表优点：可以提供快速插入和查找操作，无论有多少数据项，插入与查找只需接近常量的时间：O(1)时间级。而且编程很容易实现。哈希表的缺点：它是基于数组的，数组一旦被创建，就难以拓展；某些哈希表的填充因子（填入的元素个数/哈希表长度)过大，性能会急剧下降。
Hash函数在多个领域均有应用，而在数字签名和数据库实现时又用的最多，比如基于hash的索引，是最好的单值查找索引；同时，在当前数据爆炸的场景下，执行相似item的查找时，在内存受限时，均可以采取LSH（local sensitive hash）进行分段处理。具体用途很多，不赘述，下面介绍一些常用的知识：hash函数本质；简单的hash函数生成法；hash的冲突消解；
一个国外牛人的个人网站，有非常全面的hash算法列表：http://burtleburtle.net/bob/hash/
1)冲突是如何产生的？
上文中谈到，哈希函数是指如何对关键字进行编址的，这里的关键字的范围很广，可视为无限集，如何保证无限集的原数据在编址的时候不会出现重复呢？规则本身无法实现这个目的。
举一个例子，仍然用班级同学做比喻，现有如下同学数据：张三，李四，王五，赵刚，吴露.....
假如我们编址规则为取姓氏中姓的开头字母在字母表的相对位置作为地址，则会产生如下的哈希表
| 位置 | 字母 | 姓名 | |
| 0 | a | ||
| 1 | b | ||
| 2 | c |
...
| 10 | L | 李四 |
...
| 22 | W | 王五，吴露 |
..
| 25 | Z | 张三，赵刚 |
我们注意到，灰色背景标示的两行里面，关键字王五，吴露被编到了同一个位置，关键字张三，赵刚也被编到了同一个位置。老师再拿号来找张三，座位上有两个人，"你们俩谁是张三？"
2)如何解决冲突问题
既然不能避免冲突，那么如何解决冲突呢，显然需要附加的步骤。通过这些步骤，以制定更多的规则来管理关键字集合，通常的办法有:
a)开放地址法
开放地执法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称线性探测再散列。
会出现的问题：一次聚集，即使表相对较空，这样占据的单元也会开始形成一些区块，散列到区块中的任何关键字都要经过多次探测才能解决冲突，然后该关键字又加入到相应块区中。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...kk,-kk(k<=m/2)
称二次探测再散列。
二次探测可以解决线性探测的一次聚集问题，但是会出现二次聚集：散列到同一位置上的那些元素将探测相同的备选单元。
为了解决上述的二次聚集，另一个解决冲突的方法是：双散列
比如选择di = i * Hash2(key)，即发生冲突时，我们将第二个散列函数应用到key并在距离Hash2(key)、 2Hash2(key)、……进行探测。
如果di取值可能为伪随机数列。称伪随机探测再散列。仍然以学生排号作为例子，
现有两名同学，李四，吴用。李四与吴用事先已排好序，现新来一名同学，名字叫王五，对它进行编制
| 10.. | .... | 22 | .. | .. | 25 |
|---|---|---|---|---|---|
| 李四.. | .... | 吴用 | .. | .. | 25 |
赵刚未来之前
| 10.. | .. | 22 | 23 | 25 |
| 李四.. | 吴用 | 王五 |
(a)线性探测再散列对赵刚进行编址，且di=1
| 10... | 20 | 22 | .. | 25 |
| 李四.. | 王五 | 吴用 |
(b)二次探测再散列，且di=-2
| 1... | 10... | 22 | .. | 25 |
| 王五.. | 李四.. | 吴用 |
(c)伪随机探测再散列,伪随机序列为:5,3,2
b)再哈希法
当散列表较满时，冲突增加，插入可能失败。于是建立另外一个大约两倍大的散列表（而且使用新的散列函数），扫描原来散列表，计算每个未删除元素的新的散列值，并将其插入到新表中。
缺点：这是非常昂贵的操作，运行时间O(N)，不过再散列不是经常发生，实际效果没那么差
c)链地址法
将所有关键字为同义词的记录存储在同一线性链表中。如下：
d.建立一个公共溢出区（比较常见于实际操作中）
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
经过以上方法，基本可以解决掉hash算法冲突的问题。
还有许多用于散列表的方法，比如散列函数不好或装填因子过大，都会使堆积现象加剧。为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找)，而应使探查序列跳跃式地散列在整个散列表中。衍生出二次探查法，双重散列表法。
参考资料：
http://hunteagle.iteye.com/blog/118551
数据结构（C语言版） 严蔚敏