架构师训练营第五周作业

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

package test;

import java.util.LinkedList;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;

/**

* 一次性哈希算法

* @author cypei

* @since 2021-01-31

*/

public class HashAlgorithmMain {

public static void main(String[] args) {

//初始化

initialize();

String[] keys = {"地址 A", "地址 B", "地址 C","地址 D"};

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

System.out.println("[" + keys[i] + "]的 hash 值为" + getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]");

}

}

private static void initialize() {

int size = servers.length;

for (int i = 0 ; i < size ; i++) {

realNodes.add(servers[i]);

}

for (String str : realNodes){

for(int i = 0 ; i < VIRTUAL_NODES ; i++){

String virtualNodeName = str + "&&VN" + String.valueOf(i);

int hash = getHash(virtualNodeName);

System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash 值为" + hash);

virtualNodes.put(hash, virtualNodeName);

}

}

}

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);

return hash;

}

private static String getServer(String key){

int hash = getHash(key);

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

String virtualNode;

if(subMap.isEmpty()){

Integer i = virtualNodes.firstKey();

virtualNode = virtualNodes.get(i);

}

else{

Integer i = subMap.firstKey();

virtualNode = subMap.get(i);

}

if(virtualNode != null && virtualNode.length() > 0){

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

}

return null;

}

//服务器列表

private static String[] servers = {"10.8.0.1:8080", "10.8.0.3:8080", "10.8.0.5:8080","10.8.0.7:8080", "10.8.0.11:8080"};

//真实结点列表

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

//虚拟结点列表

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

//一个真实结点对应多少个虚拟结点

private static final int VIRTUAL_NODES = 150;

}