ava实现一致性Hash算法

1. 实现原理

将key映射到 2^32 - 1 的空间中，将这个数字的首尾相连，形成一个环

• 计算节点（使用节点名称、编号、IP地址）的hash值，放置在环上

• 计算key的hash值，放置在环上，顺时针寻找到的第一个节点，就是应选取的节点

例如：p2、p4、p6三个节点，key11、key2、key27按照顺序映射到p2、p4、p6上面，假设新增一个节点p8在p6节点之后，这个时候只需要将key27从p6调整到p8就可以了；也就是说，每次新增删除节点时，只需要重新定位该节点附近的一小部分数据

2. 解决数据倾斜的问题

什么是数据倾斜？

如果服务器的节点过少，容易引起key的倾斜。例如上面的例子中p2、p4、p6分布在环的上半部分，下半部分是空的。那么映射到下半部分的key都会被分配给p2，key过度倾斜到了p2缓存间节点负载不均衡。

解决

为了解决这个问题，引入了虚拟节点的概念，一个真实的节点对应多个虚拟的节点
假设1个真实的节点对应3个虚拟节点，那么p1对应的就是p1-1、p1-2、p1-3

• 计算虚拟节点的Hash值，放置在环上

• 计算key的Hash值，在环上顺时针寻找到对应选取的虚拟节点，例如：p2-1，对应真实的节点p2

 虚拟节点扩充了节点的数量，解决了节点较少的情况下数据倾斜的问题，而且代价非常小，只需要新增一个字典（Map）维护真实的节点与虚拟节点的映射关系就可以了

3. 代码实现

3.1 ConsistentHash

这里使用了泛型的方式来保存数据，可以根据不同的类型，获取到不同的节点存储

public class ConsistentHash<T> {

//自定义hash方法
   private Hash<Object> hashMethod;

//创建hash映射，虚拟节点映射真实节点
   private final Map<Integer, T> hashMap = new ConcurrentHashMap<>();

//将所有的hash保存起来
   private List<Integer> keys = new ArrayList<>();

//默认虚拟节点数量
   private final int replicas;

public ConsistentHash() {
       this(3, Utils::rehash);
   }

public ConsistentHash(int replicas, Hash<Object> hashMethod) {
       this.replicas = replicas;
       this.hashMethod = hashMethod;
   }

@SafeVarargs
   public final void add(T... keys) {
       for (T key : keys) {
           //根据虚拟节点个数来计算虚拟节点
           for (int i = 0; i < this.replicas; i++) {
               //根据函数获取到对应的hash值
               int hash = this.hashMethod.hash(i + ":" + key.toString());
               this.keys.add(hash);
               this.hashMap.put(hash, key);
           }
       }
       //排序，因为是一个环状结构
       Collections.sort(this.keys);
   }

/**
    * 根据对应的key来获取到节点信息
    *
    * @param key
    * @return
    */
   public T get(Object key) {
       Objects.requireNonNull(key, "key不能为空");
       int hash = this.hashMethod.hash(key);
       //获取到对应的节点信息
       int idx = Utils.search(this.keys.size(), h -> this.keys.get(h) >= hash);
       //如果idx == this.keys.size() ，就代表需要取 this.keys.get(0); 因为是环状，所以需要使用 ％ 来进行处理
       return this.hashMap.get(this.keys.get(idx ％ this.keys.size()));
   }
}

3.2 Hash

这里定义了一个函数结构，用于自定计算hash值

@FunctionalInterface
public static interface Hash<T> {
   /**
    * 计算hash值
    *
    * @param t
    * @return int类型
    */
   int hash(T t);
}

3.3 Utils

由于hashcode采用的int类型进行存储，那么就需要考虑，hash是否超过了int最大存储，如果超过了那么存储的数字就是负数，会对获取节点造成影响，所以这里在取hash值时，采用了hashmap中获取到hashcode之后对其进行与操作，可以减少hash冲突，也可以避免负数的产生

public static class Utils {
// int类型的最大数据
       static final int HASH_BITS = 0x7fffffff;

/**
        * 通过二分查找法，定义数组索引位置
        *
        * @param len
        * @param f
        * @return
        */
       public static int search(int len, Function<Integer, Boolean> f) {
           int i = 0, j = len;
           //通过二分查找发来定为索引位置
           while (i < j) {
               //长度除于2
               int h = (i + j) >> 1;
               //调用函数，判断当前的索引值是否大于
               if (f.apply(h)) {
                   //向低半段进行遍历
                   j = h;
               } else {
                   //向高半段进行遍历
                   i = h + 1;
               }
           }
           return i;
       }

/**
        * 将返回的hash能够平均的计算在 int类型之间
        *
        * @param o
        * @return
        */
       public static int rehash(Object o) {
           int h = o.hashCode();
           return (h ^ (h >>> 16)) & HASH_BITS;
       }
   }

3.4 main

下面是main方法进行测试，在后面新增了一个节点之后，只会调整 zs 数据到 109 节点，而且其他两个key的获取不会受到影响

public static void main(String[] args) {
       ConsistentHash<String> consistentHash = new ConsistentHash<>();
       consistentHash.add("192.168.2.106", "192.168.2.107", "192.168.2.108");

Map<String, Object> map = new HashMap<>();
       map.put("zs", "192.168.2.108");
       map.put("999999", "192.168.2.106");
       map.put("233333", "192.168.2.106");

map.forEach((k, v) -> {
           String node = consistentHash.get(k);
           if (!v.equals(node)) {
               throw new IllegalArgumentException("节点获取错误，key：" + k + "，获取到的节点值为：" + node);
           }
       });

consistentHash.add("192.168.2.109");
       map.put("zs", "192.168.2.109");
       map.forEach((k, v) -> {
           String node = consistentHash.get(k);
           if (!v.equals(node)) {
               throw new IllegalArgumentException("节点获取错误，key：" + k + "，获取到的节点值为：" + node);
           }
       });
   }

来源：https://blog.csdn.net/weixin_43915643/article/details/126710021