一致性哈希算法的范例

源码：

public class HashTest {
	private static TreeMap<Long, Node> vNodes; //虚拟节点集合   
    private static List<Node> rNodes; //真实节点集合
    private static final int REAL_NODE_NUM = 5; //真实节点数
    private static final int VIRTUAL_NODE_NUM = 100; //虚拟节点数
    
	public static void main(String[] args) {
		//物理节点
		rNodes = new ArrayList<Node>();
		for(int i=0; i<REAL_NODE_NUM; i++){
			Node node = new Node("192.168.1." + (i+1), (1000+i), "");
			rNodes.add(node);
		}
		
		init();
		
		//生成随机数，验证测试数据在真实机器上的数量分布情况
		Map<String, Long> map = new HashMap<String, Long>();
		for(int i=0; i<1000; i++){
			Node node = getNode("key"+i);
			if(map.containsKey(node.getIp())){
				map.put(node.getIp(), new Long(map.get(node.getIp()).longValue() + 1));
			}else{
				map.put(node.getIp(), new Long(1));
			}
		}
		
		//显示数据分布情况
		for(Iterator<String> it = map.keySet().iterator(); it.hasNext();){
			String ip = it.next();
			System.out.println(ip + ": " + map.get(ip));
		}
	}
	
	/**
	 * 初始化真实节点和虚拟节点之间的映射关系
	 */
	private static void init() { 
        vNodes = new TreeMap<Long, Node>();  
        for(int i=0; i<rNodes.size(); i++){   
            final Node node = rNodes.get(i);
            for(int j=0; j<VIRTUAL_NODE_NUM; j++){  
            	String hashKey = node.getIp() + "-V-" + j;
            	node.setHashKey(hashKey);
                vNodes.put(hash(hashKey), node); 
            }
        }
    }  
	
	/**
	 * 获取对应的真实节点对象
	 * @param key
	 * @return
	 */
	public static Node getNode(String key) {  
		Node node = null;
        SortedMap<Long, Node> tail = vNodes.tailMap(hash(key)); 
        if(tail.size() == 0){  
        	node = vNodes.get(vNodes.firstKey());  
        }else{
        	node = tail.get(tail.firstKey());
        }
        node.setData(key);
        return node;
    }
	
	/**
	 * 一致性hash算法
	 * @param key
	 * @return
	 */
	private static Long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());  
        int seed = 0x1234ABCD;  
          
        ByteOrder byteOrder = buf.order();  
        buf.order(ByteOrder.LITTLE_ENDIAN);  
  
        long m = 0xc6a4a7935bd1e995L;  
        int r = 47;  
  
        long h = seed ^ (buf.remaining() * m);  
  
        long k;  
        while (buf.remaining() >= 8) {  
            k = buf.getLong();  
  
            k *= m;  
            k ^= k >>> r;  
            k *= m;  
  
            h ^= k;  
            h *= m;  
        }  
  
        if (buf.remaining() > 0) {  
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);  
            // for big-endian version, do this first:   
            // finish.position(8-buf.remaining());   
            finish.put(buf).rewind();  
            h ^= finish.getLong();  
            h *= m;  
        }  
  
        h ^= h >>> r;  
        h *= m;  
        h ^= h >>> r;  
  
        buf.order(byteOrder);  
        return h;  
    }  
	
}