一致性（连续性）hash算法（ ）
is athathash tablein a way that theorof one slot does nottheof keys to slots.
一致性哈希算法是分布式系统中常用的算法，为什么要用这个算法？
比如：一个分布式存储系统，要将数据存储到具体的节点（服务器）上，在服务器数量不发生改变的情况下，如果采用普通的hash再对服务器总数量取模的方法（如key%服务器总数量），如果期间有服务器宕机了或者需要增加服务器，问题就出来了 。同一个key经过hash之后，再与服务器总数量取模的结果跟之前的结果会不一样，这就导致了之前保存数据的丢失 。因此，引入了一致性Hash（ ）分布算法
算法的具体原理这里再次贴上：
先构造一个长度为2^32的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2^32-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 2^32-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找 。
这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器 。
image.png
image.png
不带虚拟节点的一致性Hash算法
/*** 不带虚拟节点的一致性Hash算法* @author 五月的仓颉http://www.cnblogs.com/xrq730/**/public class ConsistentHashingWithoutVirtualNode{/*** 待添加入Hash环的服务器列表*/private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111","192.168.0.3:111", "192.168.0.4:111"};/*** key表示服务器的hash值，value表示服务器的名称*/private static SortedMap sortedMap = new TreeMap();/*** 程序初始化，将所有的服务器放入sortedMap中*/static{for (int i = 0; i < servers.length; i++){int hash = getHash(servers[i]);System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);sortedMap.put(hash, servers[i]);}System.out.println();}/*** 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别 */private static int getHash(String str){final int p = 16777619;int hash = (int)2166136261L;for (int i = 0; i < str.length(); i++)hash = (hash ^ str.charAt(i)) * p;hash += hash << 13;hash ^= hash >> 7;hash += hash << 3;hash ^= hash >> 17;hash += hash << 5;// 如果算出来的值为负数则取其绝对值if (hash < 0)hash = Math.abs(hash);return hash;}/*** 得到应当路由到的结点*/private static String getServer(String node){// 得到带路由的结点的Hash值int hash = getHash(node);// 得到大于该Hash值的所有MapSortedMap subMap = sortedMap.tailMap(hash);// 第一个Key就是顺时针过去离node最近的那个结点Integer i = subMap.firstKey();// 返回对应的服务器名称return subMap.get(i);}public static void main(String[] args){String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};for (int i = 0; i < nodes.length; i++)System.out.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");}}
带虚拟节点的一致性Hash算法
/*** 带虚拟节点的一致性Hash算法* @author 五月的仓颉 http://www.cnblogs.com/xrq730/*/public class ConsistentHashingWithVirtualNode{/*** 待添加入Hash环的服务器列表*/private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111","192.168.0.3:111", "192.168.0.4:111"};/*** 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好*/private static List realNodes = new LinkedList();/*** 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称*/private static SortedMap