写点什么

架构师训练营第五周作业

用户头像
听夜雨
关注
发布于: 2020 年 10 月 24 日

一致性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;

}

}



用户头像

听夜雨

关注

还未添加个人签名 2020.08.19 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第五周作业