用Java写一个一致性哈希算法
时间: 2024-03-21 16:39:05 浏览: 25
好的,以下是用Java实现一致性哈希算法的代码:
```java
import java.util.*;
public class ConsistentHashing {
private SortedMap<Integer, String> circle = new TreeMap<>(); // 使用TreeMap存储哈希环
private int replicas; // 副本数
private HashFunction hashFunction; // 哈希函数
public ConsistentHashing(int replicas, HashFunction hashFunction) {
this.replicas = replicas;
this.hashFunction = hashFunction;
}
public void addNode(String node) { // 添加节点
for (int i = 0; i < replicas; i++) { // 对节点进行多次哈希,增加其在哈希环上的复制
int hash = hashFunction.hash(node + i);
circle.put(hash, node);
}
}
public void removeNode(String node) { // 移除节点
for (int i = 0; i < replicas; i++) { // 对节点进行多次哈希,移除其在哈希环上的复制
int hash = hashFunction.hash(node + i);
circle.remove(hash);
}
}
public String getNode(String key) { // 获取节点
if (circle.isEmpty()) { // 如果哈希环为空,返回null
return null;
}
int hash = hashFunction.hash(key); // 对关键字进行哈希
if (!circle.containsKey(hash)) { // 如果哈希环中不存在该哈希值,返回大于该哈希值的最小哈希值对应的节点
SortedMap<Integer, String> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash); // 返回对应的节点
}
public static void main(String[] args) {
ConsistentHashing ch = new ConsistentHashing(3, new HashFunction()); // 创建一致性哈希对象
ch.addNode("192.168.0.1"); // 添加节点
ch.addNode("192.168.0.2");
ch.addNode("192.168.0.3");
System.out.println(ch.getNode("key1")); // 获取节点
System.out.println(ch.getNode("key2"));
ch.removeNode("192.168.0.2"); // 移除节点
System.out.println(ch.getNode("key1")); // 再次获取节点
System.out.println(ch.getNode("key2"));
}
}
class HashFunction { // 哈希函数
public int hash(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;
return hash;
}
}
```
以上代码实现了一致性哈希算法,并提供了添加节点、移除节点和获取节点的方法。可以根据需求调用相应的方法即可。