架构师训练营第五周作业

一致性hash算法思路：

使用list存储真实的节点；使用sortedMap存储虚拟节点，使用虚拟节点的hash值进行排序

获取缓存节点时：通过计算str的hash值，取右侧节点的前缀，从真实节点的list中获取真实的节点。

import java.util.LinkedList;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;



public class ConsistentHashing {

//真实的缓存节点

private List<String> realNodes = new LinkedList<String>();

//虚拟节点，使用sortedmap 进行存储排序

private SortedMap<Integer, String> sortedVirutalNodesMap = new TreeMap<Integer, String>();

//虚拟节点数量

private int virtualNum = 0;

public ConsistentHashing(List<String> nodes, int virtualNum) {

realNodes.addAll(nodes);

this.virtualNum = virtualNum;

initVirtualNodes();

}

//初始化虚拟节点

public void initVirtualNodes() {

sortedVirutalNodesMap.clear();

for (String node : realNodes) {

String realNode = node + "_0";

sortedVirutalNodesMap.put((int) HashUtils.getHash(realNode), realNode);

for (int i = 1; i <= virtualNum; i++) {

String virtualNode = node + "_" + String.valueOf(i);

sortedVirutalNodesMap.put( (int) HashUtils.getHash(virtualNode), virtualNode);

}

}

}

//根据右边虚拟节点的前缀，获取真实节点的名称

public String getRealServer(String str) {

int hash = (int) HashUtils.getHash(str);

SortedMap<Integer, String> subMap = sortedVirutalNodesMap.tailMap(hash);

if(!subMap.isEmpty()) {

String virtualNode = subMap.get(subMap.firstKey());

return virtualNode.substring(0, virtualNode.indexOf("_"));

}

return realNodes.get(0);

}

public int getVirtualNum() {

return virtualNum;

}

public void setVirtualNum(int virtualNum) {

this.virtualNum = virtualNum;

}

public List<String> getRealNodes() {

return realNodes;

}

public void addNode(String node) {

realNodes.add(node);

}

public void removeNode(String node) {

realNodes.remove(node);

}

}



class HashUtils {

private static final long PSART = 16777619L;

private static final long PMULT = 2166136261L;

public static long getHash(String str) {

long p = PSART;

long hash = PMULT;

for (int i = 0; i < str.length(); i++)

hash = (hash ^ str.charAt(i)) * p;

hash += hash << 13;

hash ^= hash >> 7;

hash += hash << 3;

hash ^= hash >> 17;

hash += hash << 5;

if (hash < 0)

hash = Math.abs(hash);

return hash;

}

}