3，一致性哈希的原理： 由于一般的哈希函数返回一个int（32bit）型的hashCode。因此，可以将该哈希函数能够返回的hashCode表示成一个范围为0---（2^32）-1环。 将机器的标识（如：IP地址）作为哈希函数的Key映射到环上。如： hash(Node1) =Key1 hash(Node2) = Key2，借用一张图如下： 同样，数据也通过相同的哈希函数映射到环上。这样，按照顺时针方向，数据存放在它所在的顺时针方向上的那个机器上。这就是一致性哈希算法分配数据的方式！ 4，JAVA实现一致性哈希算法的代码分析： ❶设计哈希函数 这里采用了MD5算法，主要是用来保证平衡性，即能够将机器均衡地映射到环上。貌似用Jdk中String类的hashCode并不能很好的保证平衡性。 1 import java.security.MessageDigest; 2 import java.security.NoSuchAlgorithmException; 3 4 /* 5 * 实现一致性哈希算法中使用的哈希函数,使用MD5算法来保证一致性哈希的平衡性 6 */ 7 public class HashFunction { 8 private MessageDigest md5 = null; 9 10 public long hash(String key) { 11 if (md5 == null) { 12 try { 13 md5 = MessageDigest.getInstance(MD5); 14 } catch (NoSuchAlgorithmException e) { 15 throw new IllegalStateException(no md5 algrithm found); 16 } 17 } 18 19 md5.reset(); 20 md5.update(key.getBytes()); 21 byte[] bKey = md5.digest(); 22 //具体的哈希函数实现细节--每个字节 0xFF 再移位 23 long result = ((long) (bKey[3] 0xFF) 24) 24 ((long) (bKey[2] 0xFF) 16 25 ((long) (bKey[1] 0xFF) 8) (long) (bKey[0] 0xFF)); 26 return result 0xffffffffL; 27 } 28 } ❷实现一致性哈希算法： 为什么要引入虚拟机器节点？它的作用是什么？ 引入虚拟机器节点，其目的就是为了解决数据分配不均衡的问题。因为，在将实际的物理机器映射到环上时，有可能大部分机器都映射到环上的某一个部分(比如左半圆上)，而通过引入虚拟机器节点，在进行机器hash映射时，不是映射具体机器，而是映射虚拟机器，并保证虚拟机器对应的物理机器是均衡的---每台实际的机器对应着相等数目的Virtual nodes。如下图： 如何解决集群中添加或者删除机器上需要迁移大量数据的问题？ 假设采用传统的哈希取模法，设有K台物理机，H(key)=hash(key) mod K即可实现数据分片。但当K变化时（如新增一台机器），所有已经映射好的数据都需要重新再映射。H(key)=hash(key) mod (K+1)。 一致性哈希采用的做法如下：引入一个环的概念，如上面的第一个图。先将机器映射到这个环上，再将数据也通过相同的哈希函数映射到这个环上，数据存储在它顺时针走向的那台机器上。以环为中介，实现了数据与机器数目之间的解藕。这样，当机器的数目变化时，只会影响到增加或删除的那台机器所在的环的邻接机器的数据存储，而其他机器上的数据不受影响。 在具体JAVA实现代码中，定义了一个TreeMapk, V用来保存虚拟机器节点到实际的物理机器的映射。机器以字符串形式来标识，故hash函数的参数为String 1 for (int i = 0; i numberOfReplicas; i++) 2 // 对于一个实际机器节点 node,对应 numberOfReplicas个虚拟节点 3 /* 4 *不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node 5 *虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上 6 */ 7 circle.put(hashFunction.hash(node.toString() + i), node); 而对于数据的存储而言，逻辑上是按顺时针方向存储在虚拟机器节点中，虚拟机器节点通过TreeMap知道它实际需要将数据存储在哪台物理机器上。此外，TreeMap中的Key是有序的，而环也是顺时针有序的，这样才能当数据被映射到两台虚拟机器之间的弧上时，通过TreeMap的 tailMap()来寻找顺时针方向上的下一台虚拟机。 1 if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器 2 SortedMapLong, T tailMap = circle.tailMap(hash); 3 hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); 4 } 1 import java.util.Collection; 2 import java.util.HashSet; 3 import java.util.Iterator; 4 import java.util.Set; 5 import java.util.SortedMap; 6 import java.util.SortedSet; 7 import java.util.TreeMap; 8 import java.util.TreeSet; 9 10 public class ConsistentHashT { 11 private final HashFunction hashFunction; 12 private final int numberOfReplicas;// 节点的复制因子,实际节点个数 * numberOfReplicas = 13 //虚拟节点个数 14 private final SortedMapLong, T circle = new TreeMapLong, T();// 存储虚拟节点的hash值到真实节点的映射 15 16 public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, 17 CollectionT nodes) { 18 this.hashFunction = hashFunction; 19 this.numberOfReplicas = numberOfReplicas; 20 for (T node : nodes) 21 add(node); 22 } 23 24 public void add(T node) { 25 for (int i = 0; i numberOfReplicas; i++) 26 // 对于一个实际机器节点 node,对应 numberOfReplicas个虚拟节点 27 /* 28 *不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node 29 *虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上 30 */ 31 circle.put(hashFunction.hash(node.toString() + i), node); 32 } 33 34 public void remove(T node) { 35 for (int i = 0; i numberOfReplicas; i++) 36 circle.remove(hashFunction.hash(node.toString() + i)); 37 } 38 39 /* 40 * 获得一个最近的顺时针节点,根据给定的key取Hash 41 *然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点 42 *再从实际节点中取得数据 43 */ 44 public T get(Object key) { 45 if (circle.isEmpty()) 46 return null; 47 long hash = hashFunction.hash((String) key);// node用String来表示,获得node在哈希环中的hashCode 48 if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器 49 SortedMapLong, T tailMap = circle.tailMap(hash); 50 hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); 51 } 52 return circle.get(hash); 53 } 54 55 public long getSize() { 56 return circle.size(); 57 } 58 59 /* 60 * 查看MD5算法生成的hashCode值---表示整个哈希环中各个虚拟节点位置 61 */ 62 public void testBalance(){ 63 SetLong sets = circle.keySet();//获得TreeMap中所有的Key 64 SortedSetLong sortedSets= new TreeSetLong(sets);//将获得的Key集合排序 65 for(Long hashCode : sortedSets){ 66 System.out.println(hashCode); 67 } 68 69 System.out.println(---each location 's distance are follows: ---); 70 /* 71 * 查看用MD5算法生成的long hashCode相邻两个hashCode的差值 72 */ 73 IteratorLong it = sortedSets.iterator(); 74 IteratorLong it2 = sortedSets.iterator(); 75 if(it2.hasNext()) 76 it2.next(); 77 long keyPre, keyAfter; 78 while(it.hasNext() it2.hasNext()){ 79 keyPre = it.next(); 80 keyAfter = it2.next(); 81 System.out.println(keyAfter - keyPre); 82 } 83 } 84 85 public static void main(String[] args) { 86 SetString nodes = new HashSetString(); 87 nodes.