在正式先容Consistent Hashing算法之前我们先来看一个大略的hash算法，便是用取余数的办法来选择节点。详细的步骤如下：
一、根据集群做事的节点数创建一个哈希表二、然后根据键名打算出键名的整数哈希值，用该哈希值对节点数取余。三、末了根据余数在哈希表中取出节点。
假设在一个集群中有n个做事器节点，对这些节点编号为0,1,2,…,n-1 。然后，将一条数据(key,value)存储到做事器中。这时我们该如何来选择做事器节点呢？根据上面的步骤我们须要对key打算hash值，然后再对n（节点个数）取余数。末了得到的值便是我们所要的节点。用一个公式来表示：num = hash(key) % n。hash()是一个打算hash值的函数，这里对hash()函数还是有一定的哀求的，如果我们利用的hash()函数很优化的话，那打算出的num是均匀分布在0,1,2,…,n-1之间的，从而使尽可能多的做事器节点都能被利用。而不是所有的数据都集中在一个或者几个做事器节点上面。详细的hash()实现不是本章谈论的重点。
这种纯挚的取余数的办法虽然大略，但是如果将其运用到实际生产系统中会涌现很大的问题。假设我们有23个做事节点。那么根据上面的办法，一个key映射到每个节点的概率都是1/23。假设增加了一个做事节点的话，之前的hash(key) % n 就会变成hash(key) % (n+1) 。也便是说对付key来说有23/24的概率会被重新分配到新的节点。相反只会有1/24的概率会被分配到原节点。同样，当你减少一个节点的时候，有22/23的概率会被重新分配到新的节点上去。
鉴于这种情形，就须要有一种办法来避免或者减少在横向扩展的时候命中率降落的情形的发生。这种方法便是我们将要先容的Consistent Hashing算法，我们称其为同等性hash算法。为了理解Consistent Hashing算法是如何事情的，我们假设单位区间 [ 0 , 1 ) 依顺时针的方向均匀的分布在圆上。
同等性hash算法初始
假使有n个做事节点，为每个做事节点编号为0, 1, 2, …, n-1。然后我们须要有一个hash()函数来对做事节点打算hash值。如果选用的hash()函数返回值的取值范围为[ 0, R )，那么利用公式 v = hash(n) / R。这样得到的v会分布在单位区间[ 0, 1 )内。以是，通过这个办法就可以使我们的做事节点分布在圆上面。
当然，以单位区间[ 0, 1 ) 画圆只是一种办法，还有很多其他的画圆办法，比如说：以区间[ 0, 2^32-1 ) 为圆，然后利用hash()函数对做事节点打算hash()值。选用的hash()函数产生的值当然也必须在0 – (2^32-1) 范围之内了。
这里我们还是以[ 0, 1 )为例来先容。
我们以3个做事节点为例来进行解释
同等性hash算法节点
这三个节点随机的分布在这个圆上面。现在假设我们有一条数据(key,value)须要存储，接下来要做的便是将这条数据通过同样的方法映射到圆上面。
同等性hash算法映射
然后从key所坐落在圆上的位置开始顺时针查找做事节点所在的位置，找到的第一个做事节点即是要存储的节点。以是说这条数据将要存储在做事节点1上。
同理，当有其它的(key,value)对须要存储的时候，也是按照上面的办法进行做事节点的选择。
同等性hash算法多映射
现在我们来看该方法对付我们刚开始提到的横向扩展的问题是否能够很好的办理呢？
假设我们须要增加一个做事节点3
同等性hash算法增加做事节点
通过上图，我们可以看出，只有key1会改变其存储做事节点。对付大部分的数据来说依然会找到原来的节点。因此，对付n个做事节点的集群来说，当有做事节点增加的时候一条数据只有1/(n+1)的概率会改变其存储的做事节点。这个概率远比取余数法所得的概率要小得多。同样，减少一个做事节点和增加做事节点的事理是相同的，其每条数据重新选择做事节点的概率为1/(n-1)。同样这个概率也是很小的。
下面就用一段php代码来大略的实现这个过程
$nodes = array('192.168.5.201','192.168.5.102','192.168.5.111');$keys = array('onmpw', 'jiyi', 'onmpw_key', 'jiyi_key', 'www','www_key','key1');$buckets = array(); //节点的hash字典$maps = array(); //存储key和节点之间的映射关系/ 天生节点字典 —— 使节点分布在单位区间[0,1)的圆上 /foreach( $nodes as $key) {$crc = crc32($key)/pow(2,32); // CRC値$buckets[] = array('index'=>$crc,'node'=>$key);}/ 根据索引进行排序 /sort($buckets);/ 对每个key进行hash打算，找到其在圆上的位置 然后在该位置开始依顺时针方向找到第一个做事节点 /foreach($keys as $key){$flag = false; //表示是否有找到做事节点$crc = crc32($key)/pow(2,32);//打算key的hash值for($i = 0; $i < count($buckets); $i++){ if($buckets[$i]['index'] > $crc){ / 由于已经对buckets进行了排序 以是第一个index大于key的hash值的节点即是要找的节点 / $maps[$key] = $buckets[$i]['node']; $flag = true; break; }}if(!$flag){ //没有找到，则利用buckets中的第一个做事节点 $maps[$key] = $buckets[0]['node'];}}foreach($maps as $key=>$val){echo $key.'=>'.$val,"<br />";}
这段代码运行的结果如下
onmpw=>192.168.5.102jiyi=>192.168.5.201onmpw_key=>192.168.5.201jiyi_key=>192.168.5.102www=>192.168.5.201www_key=>192.168.5.201key1=>192.168.5.111
然后我们添加一个做事节点，修正代码如下
$nodes = array('192.168.5.201','192.168.5.102','192.168.5.111','192.168.5.11');
其它代码不变，连续运行结果如下
onmpw=>192.168.5.102jiyi=>192.168.5.201onmpw_key=>192.168.5.11jiyi_key=>192.168.5.102www=>192.168.5.201www_key=>192.168.5.201key1=>192.168.5.111
我们看到，只有onmpw_key重新选择了做事节点。其它的都是原来的节点。
到这里我们看到，较之于取余数法命中的概率提高了相称多了。那这里是不是就办理了我们前面碰着的问题了呢？
实在，还没有。由于这些值的分布毕竟不是那么的均匀。在系统中有可能这些做事节点分布非常的集中，这可能导致的情形便是所有的key都映射到个中的一个或者几个节点上面，剩下的做事节点都没有被用到。虽然这并不是什么很严重的问题，那为什么我们要摧残浪费蹂躏哪怕只是一台做事器呢。
同等性hash算法数据集中
我们看，这种情形就造成了数据集中在一个做事节点上面，造成了其它做事节点的摧残浪费蹂躏。那如何办理这个问题呢？人们就又想出了一种新的办法：便是为每个节点建立虚拟的节点。什么意思呢？便是说对付节点j，为其建立m个复制品。这m个复制出来的节点都通过hash()函数得出不同的hash值，但是每个虚拟节点保存的节点信息都是节点j的。然后这些虚拟节点都会随机的分布在圆上面。举例子来说，我们有两个做事节点。并且为每个节点都复制出三个虚拟节点。这些节点（包括虚拟节点都随机的分布在圆上面）
同等性hash算法均匀分布
这样看起来做事节点在圆上分布还是比较均匀的了。实在，总结起来便是在上面的那种办法上轻微做了一下改进——给每个节点复制一些虚拟节点。
因此，我们的代码也不须要做过多的修正。为了看代码比较直不雅观，我在这里还是将整段代码罗列在这。
$nodes = array('192.168.5.201','192.168.5.102','192.168.5.111');$keys = array('onmpw', 'jiyi', 'onmpw_key', 'jiyi_key', 'www','www_key','key1');//添加的变量 修正的地方$replicas = 160; //每个节点的复制的个数$buckets = array(); //节点的hash字典$maps = array(); //存储key和节点之间的映射关系/ 天生节点字典 —— 使节点分布在单位区间[0,1)的圆上 /foreach( $nodes as $key) { //修正的地方 for($i=1;$i<=$replicas;$i++){ $crc = crc32($key.'.'.$i)/pow(2,32); // CRC値 $buckets[] = array('index'=>$crc,'node'=>$key); }}/ 根据索引进行排序 /sort($buckets);/ 对每个key进行hash打算，找到其在圆上的位置 然后在该位置开始依顺时针方向找到第一个做事节点 /foreach($keys as $key){$flag = false; //表示是否有找到做事节点$crc = crc32($key)/pow(2,32);//打算key的hash值for($i = 0; $i < count($buckets); $i++){ if($buckets[$i]['index'] > $crc){ / 由于已经对buckets进行了排序 以是第一个index大于key的hash值的节点即是要找的节点 / $maps[$key] = $buckets[$i]['node']; $flag = true; break; } } if(!$flag){ //没有找到，则利用buckets中的第一个做事节点 $maps[$key] = $buckets[0]['node']; }}foreach($maps as $key=>$val){echo $key.'=>'.$val,"<br />";}
有改动的地方在代码里已经标注出来了。可以看到，修正的地方还是比较少的。
至此，相信大家对Consistent Hashing该当有了一个比较清晰的认识。hash算法的用途还是很广泛的，比如在memcache集群，nginx负载等方面都有用到。
我们在 带你深入理解Memcached中的分布式思想 这篇文章中用实际的案例先容了同等性hash算法在Memcache中的运用。这里我们所有的代码都是用PHP实现的，如果对PHP不熟习的有兴趣的可以参考以下教程，PHP教程——迹忆客。
综上，由于hash算法的用场很广，因此理解hash算法对付我们是有很大的帮助的。
上述算法过程的表述有不清楚或者不得当的地方，欢迎大家不吝见教。
