为什么需要一致性hash
传统hash算法常用方式为：hash(object)%N N为一个固定值。 N设置较小时容易产生冲突碰撞问题。而N设置较大时则带来开销问题。
对于我们常用的单机程序时是内存开销变大。而用在分布式环境时，该N值和机器数目相关，则是需要的机器数增加。因此，N值应该是一个随着
业务不断变大，而逐步提升的值。而该传统的hash算法带来的问题是N值改变，比如最初N为5,后续提升，N值改变为7
则对应从0-13的数组取模按照该hash计算的结果如下表
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
| 5 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 |
| 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
通过该表我们可以明显的看出。N值改变带来的问题是hash计算的值和之前的值几乎都不同了。运用在分布式环境中，之前的机器数为5，后面增加到7
带来的问题从该分界后面部分cache的数据失效了。这可以说是一种灾难。
而改变该问题的就是一致性hash算法(consistent hashing)
一致性hash的算法原理
由于通常的hash算法我们都是对数值进行hash，而通过hash函数，我们也可以把任意的字符串转变为一个32位或者64位的数值。因此我们仍讨论对数值进行hash。
这里以32位数值为例。其数值范围就是0-2^32-1. 之前的hash方式可以理解为将该数值看做线段的等分，如下图所示。
而一致性hash则将该区间看做一个封闭的圆环，假设最初为hash值为4(认为有4台机器)。 那么数据的划分就如下图所示，圆环分4个区间
一致性hash的基本思想是将对象和cache都映射到同一个hash数据空间。
由于一致性hash一般都是顺时针寻找cache机器(个人认为这个顺时针逆时针不重要，把握思想即可)。因此我们数据的分布规定如下
A机器 ： 2^32/4-1
B机器 : 2^32/2-1
C机器: 3*2^32/4-1
D机器: 2^32-1
这样A机器的key范围就是[0 - 2^32/4-1] B机器的key范围是[2^32/4 - 2^32/2-1],
C机器的key范围是[2^32/2 – 3*2^32/4-1],D机器的key范围是[3*2^32/4 – 2^32-1],
这样给定一个值，我们顺时针找到的第一个cache，就是其需要存放的机器。
我们插入5个key，如下图所示
此时我们讨论下当cache数变更的情况。
场景一：cache数减少
建设B挂掉。根据我们上面顺时针的规定。此时受影响的僵尸A到B之间的key，即上面的key2 和key3.此时这部分key需要映射到C上面。
此时情况为：
A机器 ： 2^32/4-1
C机器: 3*2^32/4-1
D机器: 2^32-1
此时 A机器的key范围就是[0 - 2^32/4-1] ，C机器的key范围是[2^32/4 – 3*2^32/4-1],D机器的key范围是[3*2^32/4 – 2^32-1],
如下图所示。改变的只是A和B之间的，即原本存储在B机器的key。其他的不需要改变。
场景二：cache数增加
为描述和画图方便，我们仍基于上面的4台机器的场景说明。我们增加一台机器E。机器机器变成5，此时我们假设E插入在A和B之间。此时情况应该为
A机器 ： 2^32/4-1
E机器： 3*2^32/8-1
B机器 : 2^32/2-1
C机器: 3*2^32/4-1
D机器: 2^32-1
这样A机器的key范围就是[0 - 2^32/4-1]，E机器的key范围是[2^32/4 -3^32/8-1],， B机器的key范围是[3^32/8 - 2^32/2-1],
C机器的key范围是[2^32/2 – 3*2^32/4-1],D机器的key范围是[3*2^32/4 – 2^32-1],
此时受影响的为逆时针方向从E到A之间的，即key2，此时只需要将key2映射到E机器即可。其他的都不需要变动。
通过上面两种场景，我们看出一致性hash 对于机器数的增加不会导致全部的cache失效，只需要改变部分key值的映射关系即可。能较好的支撑机器的改变。
虚拟节点
通过上面的cache数增加和减少的场景我们也发现，机器数改变时，如果不是倍数关系的改变。可能会导致不同机器承担的数据不均衡。比如上面机器数减少1时，C机器负责的范围增加，容易导致其上面的数据增多。而增加1时，E和B机器的范围比其他机器都少。
针对该问题，一致性hash引入了“虚拟节点”的概念。所谓的虚拟节点就是不再根据实际的机器数，一个实际的机器节点可以对应多个虚拟节点。我们按照虚机节点对hash空间进行划分。
引入虚机节点之后的好处是，每个节点负责的区间变小。而机器对应的是虚拟节点(可以不再是连续的一大块空间)，一台机器改变时，影响的将可能不再是连续的一大块空间。从而可以将其负责的数据均摊到其他的实际机器上面。而增加机器时，可以从每个机器的虚拟节点中抽取一部分转移到新增加的机器上，以提升数据的均衡性。 在此不再详述
refer：http://blog.csdn.net/sparkliang/article/details/5279393
http://www.codeproject.com/Articles/56138/Consistent-hashing 一个c的实现