14.2 一致性Hash算法
面试重要程度：⭐⭐⭐⭐⭐
常见提问方式： "设计分布式缓存" "解决数据倾斜问题" "一致性Hash的优缺点"
预计阅读时间：35分钟
🎯 一致性Hash基本原理
传统Hash的问题
在分布式系统中，传统的Hash算法存在以下问题：
/**
* 传统Hash分片的问题演示
*/
public class TraditionalHashProblems {
/**
* 传统Hash分片
*/
public static int traditionalHash(String key, int serverCount) {
return Math.abs(key.hashCode()) % serverCount;
}
/**
* 演示节点变化对数据分布的影响
*/
public static void demonstrateProblem() {
String[] keys = {"user1", "user2", "user3", "user4", "user5"};
System.out.println("=== 3台服务器时的分布 ===");
for (String key : keys) {
int server = traditionalHash(key, 3);
System.out.println(key + " -> Server " + server);
}
System.out.println("\n=== 增加1台服务器后的分布 ===");
for (String key : keys) {
int server = traditionalHash(key, 4);
System.out.println(key + " -> Server " + server);
}
// 结果：大部分数据需要重新分布
}
}
问题分析：
- 当服务器数量变化时，几乎所有数据都需要重新分布
- 造成大量的数据迁移和缓存失效
- 系统扩容或缩容成本极高
一致性Hash解决方案
一致性Hash通过构建Hash环来解决数据重分布问题。
🔄 一致性Hash实现
基础实现
/**
* 一致性Hash算法实现
*/
public class ConsistentHash {
/**
* 虚拟节点数量
*/
private static final int VIRTUAL_NODES = 150;
/**
* Hash环，使用TreeMap保证有序
*/
private final TreeMap<Long, String> hashRing = new TreeMap<>();
/**
* 物理节点集合
*/
private final Set<String> physicalNodes = new HashSet<>();
/**
* 添加节点
*/
public void addNode(String node) {
physicalNodes.add(node);
// 为每个物理节点创建虚拟节点
for (int i = 0; i < VIRTUAL_NODES; i++) {
String virtualNode = node + "#" + i;
long hash = hash(virtualNode);
hashRing.put(hash, node);
}
System.out.println("Added node: " + node + " with " + VIRTUAL_NODES + " virtual nodes");
}
/**
* 移除节点
*/
public void removeNode(String node) {
physicalNodes.remove(node);
// 移除所有虚拟节点
for (int i = 0; i < VIRTUAL_NODES; i++) {
String virtualNode = node + "#" + i;
long hash = hash(virtualNode);
hashRing.remove(hash);
}
System.out.println("Removed node: " + node);
}
/**
* 获取数据应该存储的节点
*/
public String getNode(String key) {
if (hashRing.isEmpty()) {
return null;
}
long hash = hash(key);
// 查找第一个大于等于该hash值的节点
Map.Entry<Long, String> entry = hashRing.ceilingEntry(hash);
// 如果没找到，说明应该存储在第一个节点（环形结构）
if (entry == null) {
entry = hashRing.firstEntry();
}
return entry.getValue();
}
/**
* Hash函数（使用FNV1a算法）
*/
private long hash(String key) {
final long FNV_64_INIT = 0xcbf29ce484222325L;
final long FNV_64_PRIME = 0x100000001b3L;
long hash = FNV_64_INIT;
for (byte b : key.getBytes()) {
hash ^= b;
hash *= FNV_64_PRIME;
}
return hash;
}
/**
* 获取所有物理节点
*/
public Set<String> getPhysicalNodes() {
return new HashSet<>(physicalNodes);
}
/**
* 获取Hash环状态
*/
public void printRingStatus() {
System.out.println("=== Hash Ring Status ===");
System.out.println("Physical nodes: " + physicalNodes.size());
System.out.println("Virtual nodes: " + hashRing.size());
// 统计每个物理节点的虚拟节点分布
Map<String, Integer> distribution = new HashMap<>();
for (String node : hashRing.values()) {
distribution.put(node, distribution.getOrDefault(node, 0) + 1);
}
System.out.println("Virtual nodes distribution:");
for (Map.Entry<String, Integer> entry : distribution.entrySet()) {
System.out.println(" " + entry.getKey() + ": " + entry.getValue());
}
}
}
高级实现（支持权重）
/**
* 支持权重的一致性Hash实现
*/
public class WeightedConsistentHash {
private final TreeMap<Long, String> hashRing = new TreeMap<>();
private final Map<String, Integer> nodeWeights = new HashMap<>();
private final Set<String> physicalNodes = new HashSet<>();
/**
* 添加带权重的节点
*/
public void addNode(String node, int weight) {
physicalNodes.add(node);
nodeWeights.put(node, weight);
// 根据权重计算虚拟节点数量
int virtualNodes = weight * 40; // 基础虚拟节点数 * 权重
for (int i = 0; i < virtualNodes; i++) {
String virtualNode = node + "#" + i;
long hash = hash(virtualNode);
hashRing.put(hash, node);
}
System.out.println("Added weighted node: " + node +
" (weight=" + weight + ", virtual_nodes=" + virtualNodes + ")");
}
/**
* 移除节点
*/
public void removeNode(String node) {
Integer weight = nodeWeights.remove(node);
if (weight == null) {
return;
}
physicalNodes.remove(node);
// 移除所有虚拟节点
int virtualNodes = weight * 40;
for (int i = 0; i < virtualNodes; i++) {
String virtualNode = node + "#" + i;
long hash = hash(virtualNode);
hashRing.remove(hash);
}
System.out.println("Removed weighted node: " + node);
}
/**
* 获取节点
*/
public String getNode(String key) {
if (hashRing.isEmpty()) {
return null;
}
long hash = hash(key);
Map.Entry<Long, String> entry = hashRing.ceilingEntry(hash);
if (entry == null) {
entry = hashRing.firstEntry();
}
return entry.getValue();
}
/**
* 分析数据分布
*/
public void analyzeDistribution(String[] testKeys) {
Map<String, Integer> distribution = new HashMap<>();
for (String key : testKeys) {
String node = getNode(key);
distribution.put(node, distribution.getOrDefault(node, 0) + 1);
}
System.out.println("=== Data Distribution Analysis ===");
System.out.println("Total keys: " + testKeys.length);
for (Map.Entry<String, Integer> entry : distribution.entrySet()) {
String node = entry.getKey();
int count = entry.getValue();
double percentage = (count * 100.0) / testKeys.length;
int weight = nodeWeights.getOrDefault(node, 1);
System.out.printf("Node %s (weight=%d): %d keys (%.2f%%)\n",
node, weight, count, percentage);
}
}
private long hash(String key) {
final long FNV_64_INIT = 0xcbf29ce484222325L;
final long FNV_64_PRIME = 0x100000001b3L;
long hash = FNV_64_INIT;
for (byte b : key.getBytes()) {
hash ^= b;
hash *= FNV_64_PRIME;
}
return hash;
}
}
🔧 实际应用场景
分布式缓存实现
/**
* 基于一致性Hash的分布式缓存
*/
public class DistributedCache {
private final ConsistentHash consistentHash;
private final Map<String, CacheNode> cacheNodes;
public DistributedCache() {
this.consistentHash = new ConsistentHash();
this.cacheNodes = new HashMap<>();
}
/**
* 缓存节点
*/
static class CacheNode {
private final String nodeId;
private final Map<String, Object> cache;
public CacheNode(String nodeId) {
this.nodeId = nodeId;
this.cache = new ConcurrentHashMap<>();
}
public void put(String key, Object value) {
cache.put(key, value);
System.out.println("Node " + nodeId + " stored: " + key);
}
public Object get(String key) {
Object value = cache.get(key);
System.out.println("Node " + nodeId + " retrieved: " + key +
" -> " + (value != null ? "HIT" : "MISS"));
return value;
}
public void remove(String key) {
cache.remove(key);
System.out.println("Node " + nodeId + " removed: " + key);
}
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
Java面试圣经 文章被收录于专栏
Java面试圣经，带你练透java圣经
SHEIN希音公司福利 370人发布