一致性哈希算法（consistent hashing）例子+测试。 .

一个简单的consistent hashing的例子，很容易理解。

首先有一个设备类，定义了机器名和ip：

[java]  view plain copy print ?

1. public class Cache  
2. {  
3.     public String name;  
4.     public String ipAddress;  
5. }  

然后是主要的实现：

[java]  view plain copy print ?

1. public class Shard<T> {   
2.     //hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，   
3.     //所以增加虚拟节点   
4.     private TreeMap<Long, T> nodes;  
5.     private List<T> shards; //节点碎片   
6.     private final int NODE_NUM = 10; // 每个机器节点关联的虚拟节点个数   
7.   
8.     public Shard(List<T> shards) {  
9.         this.shards = shards;  
10.         init();  
11.     }  
12.   
13.     private void init() {   
14.         nodes = new TreeMap<Long, T>();  
15.         for (int i = 0; i < shards.size(); i++)   
16.         { // 遍历真实节点   
17.             final T shardInfo = shards.get(i);  
18.               
19.             for (int n = 0; n < NODE_NUM; n++)  
20.             {  
21.                 // 真实节点关联虚拟节点，真实节点是VALUE；   
22.                 nodes.put((long) Hash("SHARD-" + i + "-NODE-" + n), shardInfo);  
23.             }  
24.             System.out.println(shardInfo);  
25.         }  
26.     }  
27.   
28.     public T getShardInfo(String key) {  
29.         SortedMap<Long, T> tail = nodes.tailMap((long) Hash(key));   
30.         if (tail.size() == 0) {  
31.             return nodes.get(nodes.firstKey());  
32.         }  
33.         //找到最近的虚拟节点   
34.         return tail.get(tail.firstKey());  
35.     }  
36.       
37.     /** 
38.      * 改进的32位FNV算法，高离散 
39.      *  
40.      * @param string 
41.      *            字符串 
42.      * @return int值 
43.      */  
44.     public static int Hash(String str)   
45.     {  
46.         final int p = 16777619;  
47.         int hash = (int) 2166136261L;  
48.         for (byte b : str.getBytes())  
49.             hash = (hash ^ b) * p;  
50.         hash += hash << 13;  
51.         hash ^= hash >> 7;  
52.         hash += hash << 3;  
53.         hash ^= hash >> 17;  
54.         hash += hash << 5;  
55.         return hash;  
56.     }  
57.   
58. }  

到这里就完了，是不是很简单，下面来测试下：

[java]  view plain copy print ?

1. public class Test  
2. {  
3.   
4.     /** 
5.      * @param args 
6.      */  
7.     public static void main(String[] args)  
8.     {  
9.         List<Cache> myCaches=new ArrayList<Cache>();  
10.         Cache cache1=new Cache();  
11.         cache1.name="COMPUTER1";  
12.         Cache cache2=new Cache();  
13.         cache2.name="COMPUTER2";  
14.         myCaches.add(cache1);  
15.         myCaches.add(cache2);  
16.           
17.           
18.         Shard<Cache> myShard=new Shard<Cache>(myCaches);  
19.           
20.         Cache currentCache=myShard.getShardInfo("info1");  
21.         System.out.println(currentCache.name);  
22.           
23. //      for(int i=0;i<20;i++)   
24. //      {   
25. //          String object=getRandomString(20);//产生20位长度的随机字符串   
26. //          Cache currentCache=myShard.getShardInfo(object);   
27. //          System.out.println(currentCache.name);   
28. //      }   
29.           
30.           
31.     }  
32.       
33.     public static String getRandomString(int length) { //length表示生成字符串的长度   
34.         String base = "abcdefghijklmnopqrstuvwxyz0123456789";     
35.         Random random = new Random();     
36.         StringBuffer sb = new StringBuffer();     
37.         for (int i = 0; i < length; i++) {     
38.             int number = random.nextInt(base.length());     
39.             sb.append(base.charAt(number));     
40.         }     
41.         return sb.toString();     
42.      }     
43.   
44. }  

我们有两台设备，computer1和computer2，第一次初始化要构建一个2的32次方的环，并往上面放设备。这个环由改进的FNV算法实现。位置也由hash算法确定。

但我们只有两台设备，很明显在环上会分布不均匀（这个就不解释了，网上很多资料）。于是我们每台设备增加10个虚拟设备。

最后分布如下：

[html]  view plain copy print ?

1. <SPAN style="COLOR: #003300">-1561290727=Hash.Cache@10f11b8,  
2. -1083588870=Hash.Cache@10f11b8,  
3. -697149481=Hash.Cache@10f11b8,  
4. -253517545=Hash.Cache@10f11b8,  
5. 397383558=Hash.Cache@10f11b8,  
6. 1078505027=Hash.Cache@10f11b8,  
7. 1810977445=Hash.Cache@10f11b8,  
8. 1844081498=Hash.Cache@10f11b8,  
9. 2004894833=Hash.Cache@10f11b8,  
10. 2051863688=Hash.Cache@10f11b8</SPAN>  

-2147483648到2147483647之间是不是比较均匀，这是java的，如果是c#的就是0~2的32次方。我们hash计算出KEY值为2049553054，然后顺时针找到最近的位置，即为

结果我们定位到了COMPUTER1

最好我们要看看平衡性如何：取消上面注释的代码，循环20次，得到结果如下：

COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER1
COMPUTER1
COMPUTER2
COMPUTER2
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER1
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2

大家可以自己取试试，

FNV哈希算法是一种高离散性的哈希算法，特别适用于哈希非常相似的字符串，例如：URL，IP，主机名，文件名等。

以下服务使用了FNV:
1、calc
2、DNS
3、mdbm key/value查询函数
4、数据库索引hash
5、主流web查询/索引引擎
6、高性能email服务
7、基于消息ID查询函数
8、auti-spam反垃圾邮件过滤器
9、NFS实现（比如freebsd 4.3, linux NFS v4）
10、Cohesia MASS project 
11、Ada 95的spellchecker
12、开源x86汇编器：flatassembler   user-defined symbol hashtree
13、PowerBASIC
14、PS2、XBOX上的文本资源
15、非加密图形文件指纹
16、FRET
17、Symbian DASM
18、VC++ 2005的hash_map实现
19、memcache中的libketama
20、 PHP 5.x 
21、twitter中用于改进cache碎片
22、BSD IDE project
23、deliantra game server
24、 Leprechaun
25、IPv6流标签