使用社交账号登录
以大规模网页爬虫为例,在针对特定关键词的大规模网页爬虫中,待抓取的 URL 数量可能达到数亿,重复 URL 不仅浪费爬取资源,还可能导致爬虫陷入死循环或无效抓取,严重影响抓取效率和数据质量
考虑到 URL 爬虫去重允许误判,大数据量的情况下小部分数据误判完全允许
布隆过滤器(Bloom Filter)是一种基于位图(Bit Array)的概率型数据结构,它能够高效地检测一个元素"可能存在"或者"绝对不存在"。
初始化布隆过滤器

image.png|500
image.png|500
查询:绝对不存在及可能存在
绝对不存在:查询并插入 Z
Z 在查询时发现只有一个 bit 是 1,另一位 bit 是 0,可证明绝对不存在

image.png|500
image.png|500
image.png|500
参数含义
推导公式
参数预估 已知待插入数 及 误判率
增、查,无删 很明显布隆过滤器无法支持删除操作,因为多个元素可能哈希到一个布隆过滤器的同一个位置,参考上方布隆过滤器示意图
占用空间 百亿 URL 内存占用估算,$1%$ 的假阳率
实际项目中通常使用 Google 提供的 Guava 库中的布隆过滤器 Guava 的 Maven 仓库
引入 Guava 依赖
Guava 库的布隆过滤器核心方法
put():插入元素mightContain():判断元素是否可能存在示例案例
插入 的数据,判断 个数据,误判 次
封装了布隆过滤器的核心逻辑,如添加、查询元素、初始化参数计算(如位图大小、哈希函数数量)等
工厂创建 BloomFilter
核心方法
Funnel 接口
Funnel 接口的主要职责是将一个对象的状态“注入”到一个 PrimitiveSink 中,从而产生连续的字节序列,如此才可以对自定义结构使用布隆过滤器
Guava 自带有原生 Funnel,如 integerFunnel()、stringFunnel(Charset)、byteArrayFunnel() 等
案例
Goods
PojoBloomFilter
Funnel 作用
Strategy 接口定义了布隆过滤器的哈希策略、元素插入以及查询具体操作 默认使用 MURMUR128MITZ64
可以发现并没有真的使用 个哈希函数,并且实现中使用了一次 Hash,并分割成两个字段 《Less Hashing, Same Performance: Building a Better Bloom Filter》提出优化算法,只需计算两个独立哈希函数即可构造出等价于使用多个哈希函数的布隆过滤器 $$gi(x)=h1(x)+i·h_2(x)$$
策略传入 BitArray 的 index = (combinedHash & Long.MAX_VALUE) % bitSize),目的是让 combinedHash 为正,否则无法对 bitSize 取模(负索引异常)
BitArray 是布隆过滤器底层实现的核心,负责位数组的存储与管理
Bloomfilter

image.png|500
image.png|500

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>32.1.2-jre</version>
</dependency>
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample
{
private static Integer expectedInsertions = 10000000;
private static Double fpp = 0.01;
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
public static void main(String[] args)
{
for (int i = 0; i < expectedInsertions; i++)
{
bloomFilter.put(i);
}
int count = 0;
for (int i = expectedInsertions; i < expectedInsertions * 2; i++)
{
if (bloomFilter.mightContain(i))
{
count++;
}
}
System.out.println("一共误判了:" + count);
}
}
public static <T extends @Nullable Object> BloomFilter<T> create(
Funnel<? super T> funnel, int expectedInsertions, double fpp) {
return create(funnel, (long) expectedInsertions, fpp);
}
public static <T extends @Nullable Object> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp) {
return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}
public boolean put(@ParametricNullness T object) {
return strategy.put(object, funnel, numHashFunctions, bits);
}
public boolean mightContain(@ParametricNullness T object) {
return strategy.mightContain(object, funnel, numHashFunctions, bits);
}
static int optimalNumOfHashFunctions(long n, long m) {
// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
public interface Funnel<T> {
void funnel(T from, PrimitiveSink into);
}
@Data
@AllArgsConstructor
public class Goods {
private final int id;
private final String name;
}
public static void main(String[] args)
{
// 预计插入10000个Person对象,误判率设为0.01
BloomFilter<Goods> personBloomFilter = BloomFilter.create(
PersonFunnel.INSTANCE,
10000,
0.01
);
// 创建并插入一个Goods对象
Goods apple = new Goods(1, "apple");
personBloomFilter.put(apple);
// 查询某个对象是否可能存在
Goods queryGoods1 = new Goods(1, "apple");
if (personBloomFilter.mightContain(queryGoods1))
{
System.out.println(queryGoods1 + "可能存在于布隆过滤器中");
}
else
{
System.out.println(queryGoods1 + "肯定不存在于布隆过滤器中");
}
Goods queryGoods2 = new Goods(2, "banana");
if (personBloomFilter.mightContain(queryGoods2))
{
System.out.println(queryGoods2 + "可能存在于布隆过滤器中");
}
else
{
System.out.println(queryGoods2 + "肯定不存在于布隆过滤器中");
}
}
public <T extends @Nullable Object> boolean put(
@ParametricNullness T object,
Funnel<? super T> funnel,
int numHashFunctions,
LockFreeBitArray bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
boolean bitsChanged = false;
long combinedHash = hash1;
for (int i = 0; i < numHashFunctions; i++) {
// Make the combined hash positive and indexable
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
combinedHash += hash2;
}
return bitsChanged;
}
static final class LockFreeBitArray {
private static final int LONG_ADDRESSABLE_BITS = 6;
final AtomicLongArray data;
private final LongAddable bitCount;
LockFreeBitArray(long bits) {
checkArgument(bits > 0, "data length is zero!");
// Avoid delegating to this(long[]), since AtomicLongArray(long[]) will clone its input and
// thus double memory usage.
this.data = new AtomicLongArray(Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING)));
this.bitCount = LongAddables.create();
}
boolean set(long bitIndex) {
if (get(bitIndex)) {
return false;
}
int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex
long oldValue;
long newValue;
do {
oldValue = data.get(longIndex);
newValue = oldValue | mask;
if (oldValue == newValue) {
return false;
}
} while (!data.compareAndSet(longIndex, oldValue, newValue));
// We turned the bit on, so increment bitCount.
bitCount.increment();
return true;
}
boolean get(long bitIndex) {
return (data.get((int) (bitIndex >>> LONG_ADDRESSABLE_BITS)) & (1L << bitIndex)) != 0;
}
}