使用guava 实现java的一致性hash

    一致性hash算法,顾名思义,尽量让hash结果能一致。可以应用在分布式、集群环境中的请求分发,分布式缓存等场景之中。为了在集群节点的动态调整的时候,不会在rehash的时候导致大量的前后hash运算结果不同问题,这就是要解决的hash一致性问题,而hash一致性算法要解决的就是这种动态调整hash容器大小这后保证尽可能小的影响到hash结果。关于这个问题的一些基本概念可以参考 http://en.wikipedia.org/wiki/Consistent_hashing 上的解释,本文介绍一种源自guava中的实现,看了代码后,整体思路特别简单,和大家分享一下。

    通过guava实现consistent hash特别的简单,如下代码就可以了,为了方便测试,我将guava的实现源码一并粘贴如下:

final public class Hashing {
    public static int consistentHash(long input, int buckets) {
        LinearCongruentialGenerator generator = 
            new LinearCongruentialGenerator(input);
        int candidate = 0;
        int next;
        while (true) {
            next = (int) ((candidate + 1) / generator.nextDouble());
            if (next >= 0 && next < buckets) {
                candidate = next;
            } else {
                return candidate;
            }
        }
    }
    public static void main(String[] args) {
        int bucket = 5;
        {
            Multimap map = ArrayListMultimap.create();
            for (int i = 0; i < 20; i++) {
                map.put(consistentHash(i, bucket), i);
            }
            System.out.println(bucket + ":" + map);
        }
        bucket = 3;
        {
            Multimap map = ArrayListMultimap.create();
            for (int i = 0; i < 20; i++) {
                map.put(consistentHash(i, bucket), i);
            }
            System.out.println(bucket + ":" + map);
        }
        bucket = 4;
        {
            Multimap map = ArrayListMultimap.create();
            for (int i = 0; i < 20; i++) {
                map.put(consistentHash(i, bucket), i);
            }
            System.out.println(bucket + ":" + map);
        }
    }
    private static class LinearCongruentialGenerator {
        private long state;
        public LinearCongruentialGenerator(long seed) {
            this.state = seed;
        }
        public double nextDouble() {
            state = 2862933555777941757L * state + 1;
            return ((double) ((int) (state >>> 33) + 1)) / (0x1.0p31);
        }
    }
}

    如果上述的解决办法不是很符合你的需求,可以参考java.net上的这篇博文。另外,关于hash 一致性的描述,我觉得csdn上的这篇文章解释的比较不错,有兴趣的话可以去看看。