理论
共同性哈希算法是一种常用的散布式算法，其主要用途是在散布式体系中，将数据依据其键（key）进行散列（hash），然后将散列成果映射到环上，再依据数据节点的数量，将环划分为多个区间，每个节点负责处理环上必定区间范围内的数据。
一般哈希的问题
散布式集群中，对机器的添加删去，或者机器毛病后自动脱离集群这些操作是集群办理最基本的功用。假如采用常用的hash(object)%N取模的方法，在节点进行添加或者删去后，需求从头进行搬迁改动映射联系，否则或许导致原有的数据无法找到。
举个栗子
跟着业务和流量的添加，假设咱们的Redis查询服务节点扩展到了3个，为了将查询请求进行均衡，每次请求都在相同的Redis中，使用hv = hash(key) % 3的方法核算，对每次查询请求都经过hash值核算，得出来0、1 、2的值分别对应服务节点的编号，核算得到的hv的值就去对应的节点处理。
可是这里有个问题，服务增减是需求对此刻的key进行从头核算，比方减少一个服务的时分，此刻需求按 hv = hash(key) % 2核算，而添加一个服务节点的时分需求按hv = hash(key) % 4核算，而这种取模基数的改变会改动大部分本来的映射联系。
这个时分只能进行数据搬迁，实在太麻烦了，而共同性哈希算法显然是一个更好挑选！
共同性hash算法
共同性哈希相同使用了取模的方法，不同的是对 ****2^32 这个固定的值进行取模运算。
在使用共同哈希算法后，哈希表槽位数（巨细）的改动均匀只需求对 K/n 个关键字从头映射，其中K是关键字的数量， n是槽位数量，而不需求对一切的映射联系进行从头映射！
Hsh环
咱们可以把共同哈希算法是对 2^32 进行取模运算的成果值虚拟成一个圆环，环上的刻度对应一个 0~2^32 – 1 之间的数值，如下图：
节点入环
下图咱们三个节点（A/B/C）经过哈希核算，放入下面环中，一般咱们会依据服务器的IP或者唯一别名进行哈希核算。
那数据是如何进行联系映射呢，相同key值经过哈希之后，成果映射到哈希环上，然后将成果值按顺时针方向找到离自己最近的节点上，将value存储到那个节点上。
如下图：
k1、k2、k3经过哈希核算后在哈希环的位置，顺时针方向找到离自己最近的节点，比方k1最近的节点是A，节点A就是存储 k1数据value的节点。
新增节点
新添加点D，节点的数量添加到了四个，而此刻k2最近的节点是D，所以会搬迁到D，k1和k3不受影响
删去节点
删去节点B之后，存储在B节点上的k2，将会从头映射找到离它最近的节点C，此刻k2的数据存储在C节点上，k1、k3不受影响。
不平衡问题
咱们经过新增节点和删去节点，知道了该方法会影响该节点的后一个节点，其他节点不受影响。
可是因为生成哈希值的散布并不是均匀的，如下图新增k4、k5，假如节点B宕机了，那么大部分请求就落到节点C了，假如数量更多呢，此刻会导致节点C压力陡增，这样就不均衡了！
那如何处理这个问题呢？
那就是经过 虚拟节点
虚拟节点
虚拟节点 可以理解为是作为实践节点的一个copy，多个虚拟节点映射一个实践节点，因为在哈希环上节点越多就散布的越均匀，即使咱们实际中不会有那么多实在节点。
上图中三个实在节点A、B、C，映射了9个虚拟节点，假如key值经过哈希落到接近A-1、A-2、A-3的虚拟节点，那么最终都将映射到实在节点A，你想假如虚拟节点再多点，是不是就会更均衡了！
假设实在节点A被移除，A对应虚拟节点也会移除，可是多虚拟节点方法可以映射更多实在节点，让剩下的节点更好的承当节点改变的请求压力！
如下图：
这里简单讲解一下，图中实在节点A被移除，那么对应的虚拟节点移除，那么此刻k1的从头映射到C-1、k3从头映射到B-3，也就是说被搬迁到实在节点B和C，由此可见节点被移除会被更均衡的涣散到其他节点上。
图中只简单列举了几个虚拟节点，虚拟节点越多，相对会越均衡。
好了，今天关于共同性哈希算法的介绍就到这了！
欢迎朋友们重视我的公众号：【小许code】，等你哦！
欢迎点赞 、保藏 、重视 三连支撑一下～
知道的越多，不知道的也越多，我是小许，下期见～
