【架构师训练营】第 5 周作业

发布于: 2020 年 07 月 08 日

用你熟悉的编程语言实现一致性 hash 算法。

编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

package com.ssm.simple.demo.algorithm;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* 一致性哈希
*
* @Author peanutnowing
* @Date 2020/7/8
*/
public class TreeMapConsistentHash {
private TreeMap<Long,String> treeMap = new TreeMap<>();
/**
* 自定义虚拟节点数量
*/
private static final int VIRTUAL_NODE_NUM = 10;
/**
* 增加普通节点
*/
public void add (String key,String value) {
long hash = hash(key);
treeMap.put(hash,value);
}
/**
* 存在虚拟节点
*/
public void addVirtualNode(String key,String value) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
long hash = hash(key + "&&VIR" + i);
treeMap.put(hash, value);
}
treeMap.put(hash(key), value);
}
/**
* 读取节点值
* @param key
* @return
*/
public String getNode(String key) {
long hash = hash(key);
SortedMap<Long, String> sortedMap = treeMap.tailMap(hash);
String value;
if (!sortedMap.isEmpty()) {
value = sortedMap.get(sortedMap.firstKey());
} else {
value = treeMap.firstEntry().getValue();
}
return value;
}
/**
* 使用FNV1_32_HASH
*/
public long hash(String key) {
final int p = 16777619;
int hash = (int)2166136261L;
for(int i = 0; i < key.length(); i++) {
hash = (hash ^ key.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;
}
}
再想想

用户头像

花生无翼

关注

日拱一卒,想到做到 2017.10.29 加入

还未添加个人简介

评论

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