bitSet,布隆过滤器等

bitSet

java bitSet类是一种特殊类型的数组,用于存储位值,提供的方法本质上是位运算,所以对于一些数据的处理特别快。

应用场景

示例

// 数据准备
int i = 0;
List<Apple> apples = new ArrayList<>();
while (i < 10000000) {
    Apple apple = new Apple();
    if (i % 4 == 0) {
        apple.setCountry("china");
    }
    if (i % 6 == 0) {
        apple.setWight(10);
    }
    apple.setSeqNo(i);
    apples.add(apple);
    i++;
}

BitSet chinaBitSet = new BitSet();
for (Apple apple : apples) {
    if ("china".equals(apple.getCountry())) {
        chinaBitSet.set(apple.getSeqNo());
    }
}

BitSet wightSet = new BitSet();
for (Apple apple : apples) {
    if (Integer.valueOf(10).equals(apple.getWight())) {
        wightSet.set(apple.getSeqNo());
    }
}

// bitset求交集
long startTimeOfBitSet = System.currentTimeMillis();
wightSet.and(chinaBitSet);
long endTimeOfBitSet = System.currentTimeMillis();
System.out.println("bitset method cost time---" + (endTimeOfBitSet - startTimeOfBitSet));

// 正常求交集
long startTimeOfNormal = System.currentTimeMillis();
apples = apples.stream().filter(a -> "china".equals(a.getCountry()) && Integer.valueOf(10).equals(a.getWight())).collect(Collectors.toList());
long endTimeOfNormal = System.currentTimeMillis();
System.out.println("normal method cost time---" + (endTimeOfNormal - startTimeOfNormal));

bitSet局限性

数字分布不均匀很浪费空间 只能表示正整数 不容纳冲突

布隆过滤器

对于不同字符串问题,通过hash后得到的hash值可能一样,那么就无法判断这个字符串是否存在。布隆过滤器使用多个hash函数对该 字符串进行hash得到不同hash值存入数组中,表示为1。如果下次判断这个字符串是否存入时,同时判断多个hash后得到的值是否都为1, 如果有其中一个为0,则这个字符串一定不存在;如果全为1,这个字符串不一定存在。最大限度的避免了hash冲突

应用场景

  1. 判断某个key是否存在,如:黑名单,邮件过滤,URL访问

布隆过滤器局限性

有一定的误判性,取决于hash函数的质量和数量。跟过滤性能在一定程度上成反比。

未完待续….