HashCode与布隆过滤器一致性Hash

设计一种结构，具有如下三种功能，insert(Key)，将某个Key加入到该结构中，做到不重复加入。delete(Key)将该结构中的某个Key删除，getRamdom()随机等概率返回该结构中的任何一个Key，

时间复杂度都为O(1)。

思路：创建两张Hash表，一张存储Key和一个int值，一张存储int值和Key

HashMap keyValue = new HashMap();
HashMap valueKey= new HashMap();

想该结构中插入Key时，先判断keyVaule中是否有该Key，没有则进行插入，插入时需要像两张表中都插入，插入完成后int值加一对应有多少个Key。

随机返回时利用Math类获取从0到int值的随机数，然后从valueKey表获取K。

删除时先将KeyValue表中的Key对应的int值拿到，然后在用Key的个数减一到表ValueKey中拿到最后一哥对应的Key，最后更新keyValue表和valueKey表对应的数据，最后删除Key和最后一个int值。

    HashMap keyValue = new HashMap();
    HashMap valueKey = new HashMap();
    int size = 0;

    public void delete(K k) {

        if (keyValue.containsKey(k)) {
            int value = keyValue.get(k);
            int lastIndex = --size; //获取最后一个元素，size时Hash中的元素个数
            K k = valueKey.get(lastIndex);
            keyValue.put(k, value);
            valueKey.put(value, k);
            keyValue.remove(k);
            valueKey.remove(lastIndex);
        }
    }

布隆过滤器具有一定的失误率，可能将不在该集合中的元素作为是该集合的元素，（宁可错杀三千，部放过一个）bit类型的数组。每一个位置是一个bit，不是0就是1。如何创建一个bit类型的数组，可以用int，double，long等，列如：int []a = new int[1000]; 一个int有4个字节32位，所以该数组可以表示32000个bit。

public static void main(String[] args) {

        int hashCode =30000;
        int[] a = new int[1000];//320000位
        int index = hashCode / 32;//获得索引a[index]
        int bit = hashCode % 32;//获得该索引多少位描黑
        a[index] = (a[index] | (1 << bit));//将a[index]的bit位描黑

    }

布隆过滤器是准备K个Hash函数，在每次经过Hash数算出的位置进行描黑（0改为1）。如果数组太短，那么失误率将会升高（与长度成反比），因为数组太短Hash可能算出的位置都是描黑的。

hash所开空间大小 bit， n：样本量 1000亿，P：失误率 1/1000

K：Hash函数个数

真实失误率：

一致性Hash结构可以把负载均衡和数据迁移的代价将到很低。如有三台机器组成的环，当需要添加数据时，根据该数据的Hash值将其存放到距离它顺时针最近的位置。如果向环中加入一台机器，那么只迁移该机器到其顺时针方向相邻机器上的数据单该机器上即可。减机器时，就将被减机器上的数据迁移到其顺时针方向相邻机器上即可。

问题：由于该结构中有可能相邻机器的间距不同，不能保证均分，导致有的机器利用率低，有的高。

HashCode与布隆过滤器一致性Hash

Java相关栏目本月热门文章