数据结构与算法 - 一致性哈希
前言
前面我们学过了哈希算法、哈希表、布隆过滤器，尤其是布隆过滤器，它的基本思想是需要一个大的位数组，然后把需要处理的数据进行哈希算法得到哈希值，然后模位数组的大小，然后置为1。缺点很明显，那就是当我们要进行复制的时候，我们就需要把之前所有的数据再次进行取模运算，这样很费时间，那么如何保证迁移的时候达到
-
（1）数据的均匀分布，尤其是当我们的机器比较少的时候，哈希函数可能不会均匀的分布
-
（2）当要增加删除机器的数量的时候，我们怎么保证每个机器的原先的数据不会再次运算，保证迁移的代价比较低。
一致性哈希
-
与之前不同的是，一致性哈希不再对位数组取模，而是按照一定的规则比如机器的IP地址经过哈希函数处理过得到哈希值，这个哈希值再对整个哈希地址取模得到一个位置，比如哈希码的构成是0 ~ 9 + a ~ f ，一共十六位，那么一共的哈希地址个数就是16^16 = 2 ^ 64个，这样就组成一个哈希环范围是 0 ~ 2 ^ 64 - 1。
-
现在前言的说的两点问题还是会出现，比如最开始只有三台机器，无法保证平分整个哈希环，即使平分了，想要增加一个还是会出现，地址分的不均匀，有的机器流量多，有的少，那么我们再引入一个东西—虚拟节点，本质上就是把机器的数量变多了，这样分布的就均匀了，举一个例子：现在有三台机器，分别为 m1, m2, m3 ，每个节点分配1000个虚拟节点m1: m1-1, m1-2, m1-3…m2:m2-1, m2-2…以此类推，这样在计算哪个节点属于哪个哈希环的位置的时候，就用这个虚拟节点，我们还需要一个路由表，保存的是哪个虚拟节点是哪个物理节点，这样就保证了机器数量很少的情况下依然会均分流量，现在再增加一个机器m4,那么也是再增加1000个虚拟节点，经过哈希函数计算后，如果碰到重叠的了，那么就把原先的节点数据归为第四个机器处理，这样就保证了迁移的代价，不用把原先所有的数据迁移。
应长场景
在应对负载均衡的情况下使用。