一致性哈希一般用来做分布式缓存
将各服务器的哈希值映射到一个圆环上(一般用0~2^32-1)，缓存寻址时，将缓存的键取哈希值放到圆环上，然后顺时针寻找第一个服务器节点，用找到的这个节点做缓存服务器
有缓存服务器5台，缓存键30个，分别对每个缓存键在服务器上寻址
Java代码
package bj;
import lombok.RequiredArgsConstructor;
import org.apache.commons.codec.digest.DigestUtils;
import org.junit.Test;
import java.nio.ByteBuffer;
import java.util.TreeSet;
import java.util.stream.IntStream;
/**
* Created by BaiJiFeiLong@gmail.com at 2018/12/6 下午2:11
*/
public class LinearHashingTest {
@RequiredArgsConstructor
static class Node implements Comparable<Node> {
private final String name;
long digest() {
byte[] digest = DigestUtils.md5(name);
return Integer.toUnsignedLong(ByteBuffer.wrap(digest, 0, 4).getInt());
}
@Override
public int compareTo(Node o) {
return Long.compare(this.digest(), o.digest());
}
@Override
public String toString() {
return String.format("Node(name=%s, digest=%d)", name, digest());
}
}
@Test
public void testAlpha() {
TreeSet<Node> set = new TreeSet<>();
for (int i : new int[]{1, 2, 3, 4, 5}) {
set.add(new Node("server" + i));
}
System.out.println("Server nodes:");
for (Node node : set) {
System.out.println(node);
}
System.out.println("Routing...");
IntStream.rangeClosed(1, 20).forEach(i -> {
long hash = new Node("key" + i).digest();
System.out.printf("key%d\t%d\t => %s\n", i, hash, route(set, hash));
});
IntStream.rangeClosed(1, 20).forEach(i -> {
set.add(new Node("key" + i));
});
System.out.println("All nodes:");
for (Node node : set) {
System.out.println(node);
}
}
private Node route(TreeSet<Node> nodes, long code) {
for (Node node : nodes) {
if (node.digest() > code) {
return node;
}
}
return nodes.first();
}
}
``
控制台输出:
```log
Node(name=server3, digest=232443701)
Node(name=server2, digest=424647047)
Node(name=server4, digest=648772546)
Node(name=server5, digest=1375127456)
Node(name=server1, digest=2822999463)
Routing...
key1 3266172564 => Node(name=server3, digest=232443701)
key2 2029528490 => Node(name=server1, digest=2822999463)
key3 909203333 => Node(name=server5, digest=1375127456)
key4 3405308747 => Node(name=server3, digest=232443701)
key5 1034591130 => Node(name=server5, digest=1375127456)
key6 1684928417 => Node(name=server1, digest=2822999463)
key7 4187051213 => Node(name=server3, digest=232443701)
key8 1564577213 => Node(name=server1, digest=2822999463)
key9 215402731 => Node(name=server3, digest=232443701)
key10 4045919512 => Node(name=server3, digest=232443701)
key11 3930184853 => Node(name=server3, digest=232443701)
key12 3610429654 => Node(name=server3, digest=232443701)
key13 4149020260 => Node(name=server3, digest=232443701)
key14 2302410740 => Node(name=server1, digest=2822999463)
key15 1605175883 => Node(name=server1, digest=2822999463)
key16 4248449615 => Node(name=server3, digest=232443701)
key17 3126975152 => Node(name=server3, digest=232443701)
key18 533962436 => Node(name=server4, digest=648772546)
key19 1425581655 => Node(name=server1, digest=2822999463)
key20 180948674 => Node(name=server3, digest=232443701)
All nodes:
Node(name=key20, digest=180948674)
Node(name=key9, digest=215402731)
Node(name=server3, digest=232443701)
Node(name=server2, digest=424647047)
Node(name=key18, digest=533962436)
Node(name=server4, digest=648772546)
Node(name=key3, digest=909203333)
Node(name=key5, digest=1034591130)
Node(name=server5, digest=1375127456)
Node(name=key19, digest=1425581655)
Node(name=key8, digest=1564577213)
Node(name=key15, digest=1605175883)
Node(name=key6, digest=1684928417)
Node(name=key2, digest=2029528490)
Node(name=key14, digest=2302410740)
Node(name=server1, digest=2822999463)
Node(name=key17, digest=3126975152)
Node(name=key1, digest=3266172564)
Node(name=key4, digest=3405308747)
Node(name=key12, digest=3610429654)
Node(name=key11, digest=3930184853)
Node(name=key10, digest=4045919512)
Node(name=key13, digest=4149020260)
Node(name=key7, digest=4187051213)
Node(name=key16, digest=4248449615)