一个简单的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个虚拟设备。

最后分布例如以下：

-1561290727=Hash.Cache@10f11b8,

-1083588870=Hash.Cache@10f11b8,

-697149481=Hash.Cache@10f11b8,

-253517545=Hash.Cache@10f11b8,

397383558=Hash.Cache@10f11b8,

1078505027=Hash.Cache@10f11b8,

1810977445=Hash.Cache@10f11b8,

1844081498=Hash.Cache@10f11b8,

2004894833=Hash.Cache@10f11b8,

2051863688=Hash.Cache@10f11b8

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

2051863688=Hash.Cache@10f11b8

结果我们定位到了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流标签