一 算法内容

以下是线性同余的一致性 Hash 算法的全部代码。

输入参数分别是 64 位的 key 和桶的数量（一般对于服务节点的数量），输出一个桶的编号（从0开始）。

1 代码

package consistenthash;

/**
* @className: JumpConsistentHash
* @description: 利用线性同余的一致性 Hash 算法
* @date: 2022/2/1
* @author: 贝医
*/
public class JumpConsistentHash {
    private static final long UNSIGNED_MASK = 0x7fffffffffffffffL;

    private static final long JUMP = 1L << 31;

    private static final long CONSTANT = Long
            .parseUnsignedLong("2862933555777941757");

    private JumpConsistentHash() {
        throw new AssertionError(
                "No com.github.ssedano.hash.JumpConsistentHash instances for you!");
    }

    /**
     * @param o       对象
     * @param buckets 桶的个数
     * @return int 节点
     */
    public static int jumpConsistentHash(final Object o, final int buckets) {
        return jumpConsistentHash(o.hashCode(), buckets);
    }

    /**
     * @param key     键
     * @param buckets 桶的个数
     * @return the hash of the key
     * @throws IllegalArgumentException if buckets is less than 0
     */
    public static int jumpConsistentHash(final long key, final int buckets) {
        checkBuckets(buckets);
        long k = key;
        long b = -1;
        long j = 0;

        while (j < buckets) {
            b = j;
            k = k * CONSTANT + 1L;

            j = (long) ((b + 1L) * (JUMP / toDouble((k >>> 33) + 1L)));
        }
        return (int) b;
    }

    private static void checkBuckets(final int buckets) {
        if (buckets < 0) {
            throw new IllegalArgumentException("Buckets cannot be less than 0");
        }
    }

    private static double toDouble(final long n) {
        double d = n & UNSIGNED_MASK;
        if (n < 0) {
            d += 0x1.0p63;
        }
        return d;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 35; i++) {
            int node = jumpConsistentHash(i, 7);
            System.out.println("选中节点为" + node);
        }
    }
}

2 测试

选中节点为：0
选中节点为：6
选中节点为：6
选中节点为：3
选中节点为：1
选中节点为：4
选中节点为：5
选中节点为：0
选中节点为：4
选中节点为：2
选中节点为：6
选中节点为：5
选中节点为：1
选中节点为：0
选中节点为：5
选中节点为：4
选中节点为：2
选中节点为：4
选中节点为：4
选中节点为：6
选中节点为：0
选中节点为：3
选中节点为：6
选中节点为：3
选中节点为：1
选中节点为：5
选中节点为：0
选中节点为：6
选中节点为：2
选中节点为：5
选中节点为：3
选中节点为：6
选中节点为：1
选中节点为：0
选中节点为：6

Process finished with exit code 0

二 适用场景

该算法适用于分布式存储产品，而不太适合用于缓存类型的产品。因为当有节点不可用时， jump consistent hash 算法用存活节点分担不可用节点能力不强，当有节点失效要把数据迁移到其他节点时，会造成大量的数据被移动。但在分布式存储产品中，主节点不可用时会把访问主节点的请求路由到备节点，key 的分布不会有变化。

该算法适合用在分布式系统中根据 key 来选择被分配到的服务的场景。每次新增服务节点时，只有 1/n 的 key 会变动，不会因为扩容或缩容的瞬间造成大部分缓存失效。

三 缺点

和其他一致性 Hash 算法相比，如果中间的桶失效，则该算法是不能像其他一致性算法一样把失效的数据均匀分配到其他节点的，只能找到一个新的节点替换。

四 优点

不用存储过多节点信息，计算量小，运行快速、代码短，易于实现。

五 参考

一致性哈希算法（三）- 跳跃一致性哈希法 | 春水煎茶 - 王超的个人博客

GitHub - ssedano/jump-consistent-hash: Java implementation of the jump consistent hash