引出

上一章节讲到的散列表的hash算法，是算出hash值后对数组size进行取模，得到一个数组下标。当扩容的时候，对所有数据rehash，分配到的新的数组下标下，大量的数据迁移，服务器会有很大的风险。所以痛点就是当存储值的节点扩大或者缩小的时候，数据大量迁移。为了解决大量数据的迁移，一致性hash就诞生了。

基本概念

其实，一致性哈希算法也是使用取模的方法。不是因为模的值会变化导致，模后的值（下标）变化么，那模一个最大值不就好了么，模后的值（下标）不就不变了嘛。hash算法输出一个int类型的非负整数值，那么这个最大值就是int的最大值：2^32

首先，我们把2^{32次方想象成一个圆，这个圆由2}32次方个点组成。

一致性哈希圆.png

0点右侧第一个点代表1，以此类推2、3、4、5.......直到2^32 - 1，我们把这个由2^32个点组成的圆环称为hash环。

假设现在有三个台服务器，类比散列表就是散列表数组size为3。在生产环境中，这三台服务器肯定有自己的ip地址，我们使用ip地址进行hash计算，使用哈希后的结果对2^32取模

hash() % 2^32
通过上述公式我们得到的一定是一个 0-2^32 -1 之间的一个整数。来放入圆内。

hash环.png

hash环完成了，当有数据进来，存入哪个index呢？这个环是顺时针转的，顺时针的第一个index，就是该元素要存储的index。

填充元素的hash环.png

entry1、entry2 存在 A下
entry3、entry5 存在B下
entry4 存在C下

扩容缩容

当indexB移除时

移除B节点.png

entry3、entry5 就会重新存在C下

之前是所有元素rehash。现在只会对存在B上的元素重新存储，因为hash值是固定的，所以也不会rehash，减少了计算。

虚拟节点

极度不均匀情况.png

当我们把index映射到hash环上的时候，很有可能出现hash环偏斜的情况，这时候怎么办呢。我们的宗旨是尽可能让index均匀分布到hash换上，既然物理的产生了偏斜，那整几个虚拟节点出来不就好了，虚拟节点和物理节点有映射关系，分配到虚拟节点上的元素，实际上存储在该虚拟节点映射的物理节点上，这样不就完美了么。

虚拟节点.png