写点什么

第 5 周作业

用户头像
Steven
关注
发布于: 2020 年 11 月 22 日

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

预设5台服务器,每台服务器预设150个虚拟结点。

如下代码仅实现基础功能,仅实现初始化及获取服务器功能。

java自带的hash算法具有局限性,因此采用了FNV1_32_HASH算法。

package hash;

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash {

private static String[] servers = { "192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5" };

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

private static final int VIRTUAL_NODE_NUMBER = 150;
private static final String VIRUTAL_NODE_SPIT_STRING = "#";

static {
for (int i = 0; i < servers.length; i++) {
String server = servers[i];

for (int j = 0; j < VIRTUAL_NODE_NUMBER; j++) {
String virtualNode = server + VIRUTAL_NODE_SPIT_STRING + j;
int hashCode = getHash(virtualNode);

virtualNodes.put(hashCode, virtualNode);// server);
}
}
}

// FNV1_32_HASH
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
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);
hash = hash & Integer.MAX_VALUE;
return hash;
}

public static String getServer(String key) {
int hashCode = getHash(key);

SortedMap<Integer, String> tailMap = virtualNodes.tailMap(hashCode);
String virtualNode;

if (!tailMap.isEmpty()) {
virtualNode = tailMap.get(tailMap.firstKey());
} else {
virtualNode = virtualNodes.get(virtualNodes.firstKey());
}

if (virtualNode != null && !virtualNode.isEmpty()) {
String server = virtualNode.substring(0, virtualNode.indexOf(VIRUTAL_NODE_SPIT_STRING));
return server;
}
return null;

}

}



用户头像

Steven

关注

还未添加个人签名 2008.07.18 加入

还未添加个人简介

评论

发布
暂无评论
第 5 周作业