一緻性雜湊演算法（consistent hashing）樣例+測試。

一個簡單的consistent hashing的樣例，非常easy了解。

首先有一個裝置類，定義了機器名和ip：

public class Cache
{
	public String name;
	public String ipAddress;
}
           

然後是基本的實作：

public class Shard<T> { 
	//hash 算法并非保證絕對的平衡，假設 cache 較少的話，對象并不能被均勻的映射到 cache 上，
	//是以添加虛拟節點
	private TreeMap<Long, T> nodes;
	private List<T> shards; //節點碎片
	private final int NODE_NUM = 10; // 每一個機器節點關聯的虛拟節點個數

	public Shard(List<T> shards) {
		this.shards = shards;
		init();
	}

	private void init() { 
		nodes = new TreeMap<Long, T>();
		for (int i = 0; i < shards.size(); i++) 
		{ // 周遊真實節點
			final T shardInfo = shards.get(i);
			
			for (int n = 0; n < NODE_NUM; n++)
			{
				// 真實節點關聯虛拟節點，真實節點是VALUE；
				nodes.put((long) Hash("SHARD-" + i + "-NODE-" + n), shardInfo);
			}
			System.out.println(shardInfo);
		}
	}

	public T getShardInfo(String key) {
		SortedMap<Long, T> tail = nodes.tailMap((long) Hash(key)); 
		if (tail.size() == 0) {
			return nodes.get(nodes.firstKey());
		}
		//找到近期的虛拟節點
		return tail.get(tail.firstKey());
	}
	
	/**
     * 改進的32位FNV算法，高離散
     * 
     * @param string
     *            字元串
     * @return int值
     */
    public static int Hash(String str) 
    {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (byte b : str.getBytes())
            hash = (hash ^ b) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }

}
           

到這裡就完了，是不是非常easy，以下來測試下：

public class Test
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		List<Cache> myCaches=new ArrayList<Cache>();
		Cache cache1=new Cache();
		cache1.name="COMPUTER1";
		Cache cache2=new Cache();
		cache2.name="COMPUTER2";
		myCaches.add(cache1);
		myCaches.add(cache2);
		
		
		Shard<Cache> myShard=new Shard<Cache>(myCaches);
		
		Cache currentCache=myShard.getShardInfo("info1");
		System.out.println(currentCache.name);
		
//		for(int i=0;i<20;i++)
//		{
//			String object=getRandomString(20);//産生20位長度的随機字元串
//			Cache currentCache=myShard.getShardInfo(object);
//			System.out.println(currentCache.name);
//		}
		
		
	}
	
	public static String getRandomString(int length) { //length表示生成字元串的長度
	    String base = "abcdefghijklmnopqrstuvwxyz0123456789";   
	    Random random = new Random();   
	    StringBuffer sb = new StringBuffer();   
	    for (int i = 0; i < length; i++) {   
	        int number = random.nextInt(base.length());   
	        sb.append(base.charAt(number));   
	    }   
	    return sb.toString();   
	 }   

}
           

我們有兩台裝置，computer1和computer2，第一次初始化要建構一個2的32次方的環，并往上面放裝置。這個環由改進的FNV算法實作。位置也由hash算法确定。

但我們僅僅有兩台裝置，非常明顯在環上會分布不均勻（這個就不解釋了，網上非常多資料）。于是我們每台裝置添加10個虛拟裝置。

最後分布例如以下：

[email protected],
[email protected],
[email protected],
[email protected],
[email protected],
[email protected],
[email protected],
[email protected],
[email protected],
[email protected]
           

-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流标簽