Java版一致性哈希

昨天听一个在找工作的朋友讲，他面试的时候被问到一致性哈希，问我到底什么是一致性哈希，我第一感觉就是，面试官应该问的是memcache或redis之类的分布式应用，一致性哈希主要思想是闭环，场景一般是降低因节点变化而导致缓存命中率降低的问题。其实这个问题老生常谈，网上很多，只是他没有遇到过罢了，我好像记得memcache或是redis都是单点的服务器，集群都是在客户端做的，不多说了，贴代码。

import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * 
 * @author <a href="mailto:yankai913@gmail.com">yankai</a>
 * @date 2013-7-6
 */
public class ConsistentHash {
	
	final SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
	
	final int virtualMappingNo = 10;
	
	final List<String> realNodes;
	
	public ConsistentHash(List<String> realNodes) {
		this.realNodes = realNodes;
		for (String node : this.realNodes) {
			addNode(node);
		}
	}
	
	int hash(String key) {
		return key.hashCode();
	}
	
	void addNode(String node) {
		for (int i = 0; i < virtualMappingNo; i++) {
			virtualNodes.put(hash(node + i), node);
		}
		realNodes.add(node);
	}
	
	void removeNode(String node) {
		for (int i = 0; i < virtualMappingNo; i++) {
			virtualNodes.remove(hash(node + i));
		}
		realNodes.remove(node);
	}
	
	String get(String key) {
		int hash = hash(key);
		if (virtualNodes.containsKey(hash)) {
			return virtualNodes.get(hash);
		}
		SortedMap<Integer, String> tail = virtualNodes.tailMap(hash);
		if (tail.isEmpty()) {
			return virtualNodes.get(virtualNodes.firstKey());
		}
		return tail.get(tail.firstKey());
	}
	
}