cc 哈希算法有很多变体，使其可以在不同的场景下应用。下面我们就来了解一种可以有效解决分布式缓存问题的哈希算法——一致性哈希算法。
一致性哈希算法简介
一致性哈希算法是麻省理工学院在1997年提出的一种特殊的哈希算法，在分布式系统中有着广泛的应用。
简单来说就是在移除或者添加一个服务器时，此算法能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，尽可能满足单调性的要求。
一致性哈希算法的原理
一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环，称为Hash环；
接着将各个服务器使用Hash函数进行哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，从而确定每台机器在哈希环上的位置；
最后使用算法定位数据访问到相应服务器，将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针寻找，第一台遇到的服务器就是其应该定位到的服务器。
一致性哈希算法的具体流程
一致性哈希算法是对 2^32 取模，具体步骤如下：
步骤一：哈希环的组织
我们将 2^32 想象成一个圆，像钟表一样，钟表的圆可以理解成由60个点组成的圆，而此处我们把这个圆想象成由2^32个点组成的圆。
圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1，我们把这个由 2^32 个点组成的圆环称为hash环。
步骤二：确定服务器在哈希环的位置
哈希算法为：hash（服务器的IP）% 2^32
上述公式的计算结果一定是 0 到 2^32-1 之间的整数，那么上图中的 hash 环上必定有一个点与这个整数对应，所以我们可以使用这个整数代表服务器，也就是服务器就可以映射到这个环上，假设我们有 ABC 三台服务器，那么它们在哈希环上的示意图如下：
步骤三：将数据映射到哈希环上
我们还是使用图片的名称作为 key，所以我们使用下面算法将图片映射在哈希环上：hash（图片名称）% 2^32，假设我们有4张图片，映射后的示意图如下，其中橘黄色的点表示图片：
只要从图片的位置开始，沿顺时针方向遇到的第一个服务器就是图片存放的服务器了。最终，1号、2号图片将会被缓存到服务器A上，3号图片将会被缓存到服务器B上，4号图片将会被缓存到服务器C上。
一致性哈希算法的特
- 平衡性：不同key通过算法映射后，可以比较均衡地分布到所有的后端节点上。
- 单调性：当有新的节点上线后，系统中原有的key要么还是映射到原来的节点上，要么映射到新加入的节点上，不会出现从一个老节点重新映射到另一个老节点。
- 稳定性：当服务发生扩缩容的时候，发生迁移的数据量尽可能少。
免责声明：素材源于网络，如有侵权，请联系删稿。
