目录
布隆过滤器（Bloom Filter）
一、思考
如果要经常判断 1 个元素是否存在，你会怎么做？
很容易想到使用哈希表（HashSet、HashMap），将元素作为 key 去查找
时间复杂度：O(1)，但是空间利用率不高，需要占用比较多的内存资源
如果需要编写一个网络爬虫去爬10亿个网站数据，为了避免爬到重复的网站，如何判断某个网站是否爬过？
很显然，HashSet、HashMap 并不是非常好的选择
是否存在时间复杂度低、占用内存较少的方案？
布隆过滤器（Bloom Filter）
二、介绍
1970年由布隆提出
它是一个空间效率高的概率型数据结构，可以用来告诉你：一个元素一定不存在或者可能存在
优缺点
优点：空间效率和查询时间都远远超过一般的算法
缺点：有一定的误判率、删除困难
它实质上是一个很长的二进制向量和一系列随机映射函数（Hash函数）
常见应用
网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题
三、布隆过滤器的原理
假设布隆过滤器由 20位二进制、 3 个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置
添加元素：将每一个哈希函数生成的索引位置都设为 1
查询元素是否存在
✓ 如果有一个哈希函数生成的索引位置不为 1，就代表不存在（100%准确）
✓ 如果每一个哈希函数生成的索引位置都为 1，就代表存在（存在一定的误判率）
添加、查询的时间复杂度都是：O(k) ，k 是哈希函数的个数。空间复杂度是：O(m) ，m 是二进制位的个数
四、布隆过滤器的误判率
误判率 p 受 3 个因素影响：二进制位的个数 m、哈希函数的个数 k、数据规模 n
已知误判率 p、数据规模 n，求二进制位的个数 m、哈希函数的个数 k
代码实现
一、接口定义
@interface LCBloomFilter : NSObject
/// 创建一个布隆过滤器
/// @param n 数据规模
/// @param p 误判率(0,1)
+(instancetype)bloomFilterWithN:(int)n p:(double)p;
/// 添加一个元素。
/// 返回值：是否引起索引值发生变化，true：改变，false:未改变
/// @param value 元素
-(BOOL)put:(id)value;
/// 判断一个元素是否存在
/// @param value 元素
-(BOOL)contains:(id)value;
@end
二、接口实现
@interface LCBloomFilter()
@property(nonatomic,assign)int bitSize; //二进制向量的长度（一个多少个二进制位）
@property(nonatomic,assign)int hashSize; //哈希函数的个数
@property(nonatomic,strong)NSMutableData * bits;//二进制向量
@end
@implementation LCBloomFilter
/// 创建一个布隆过滤器
/// @param n 数据规模
/// @param p 误判率(0,1)
+(instancetype)bloomFilterWithN:(int)n p:(double)p{
if (n <= 0 || p<=0 || p>=1){
NSException * exception = [NSException exceptionWithName:@"wrong n or p"
reason:nil
userInfo:nil];
@throw exception;
}
LCBloomFilter * bf = [[LCBloomFilter alloc] init];
double ln2 = log(2);
//求出二进制向量的长度
bf.bitSize = (int) (- (n * log(p)) / (ln2 * ln2));
// 求出哈希函数的个数
bf.hashSize = (int) (bf.bitSize * ln2 / n);
/**
bits数组的长度
每一页显示100条数据, pageSize
一共有999999条数据, n
请问有多少页 pageCount = (n + pageSize - 1) / pageSize
*/
int byteLength = (bf.bitSize + 8 -1) / 8;
bf.bits = [NSMutableData dataWithLength:byteLength];
return bf;
}
/// 添加一个元素。
/// 返回值：是否引起索引值发生变化，true：改变，false:未改变
/// @param value 元素
-(BOOL)put:(id)value{
[self __nullCheck:value];
NSUInteger hash1 = [value hash];
NSUInteger hash2 = hash1 ^ (hash1 >>32);
NSMutableString * string = [NSMutableString stringWithFormat:@"put[%@]-[",value];
BOOL result = false;
for (int i = 1; i <= self.hashSize; i++) {
//获取一个hash值
unsigned long combinedHash = hash1 + (i*hash2);
// NSLog(@"combineHash = %ld",combinedHash);
//获取一个索引
NSUInteger index = combinedHash % self.bitSize;
[string appendFormat:@" %ld",index];
if ([self __setWithIndex:index]) result = true;
}
[string appendFormat:@"]"];
// NSLog(@"%@",string);
// NSLog(@"self.bits = %@",self.bits);
return result;
}
/// 判断一个元素是否存在
/// @param value 元素
-(BOOL)contains:(id)value{
[self __nullCheck:value];
NSUInteger hash1 = [value hash];
NSUInteger hash2 = hash1 ^ (hash1 >>32);
NSMutableString * string = [NSMutableString stringWithFormat:@"get[%@]-[",value];
for (int i = 1; i <= self.hashSize; i++) {
//获取一个hash值
unsigned long combinedHash = hash1 + (i*hash2);
//获取一个索引
NSUInteger index = combinedHash % self.bitSize;
[string appendFormat:@" %ld",index];
if (![self __getWithIndex:index]){
[string appendFormat:@"]"];
// NSLog(@"%@",string)
return false;
}
}
[string appendFormat:@"]"];
// NSLog(@"%@",string);
return true;
}
#pragma mark - 内部方法
/// 将索引为index的bit位变为1,
/// 索引位置本身就是1返回false,本身为0设置为1返回true
/// @param index bit位索引
-(BOOL)__setWithIndex:(NSUInteger)index{
//取出索引对应的一个字节
NSUInteger byteIndex = index / 8;
NSUInteger bitIndex = index % 8;
Byte bytes[1];
[self.bits getBytes:bytes range:NSMakeRange(byteIndex, 1)];
Byte byte = bytes[0];
//取出对应bit位的值
BOOL bit = (byte&(1<<bitIndex));
//已经为1，没有改变索引位置的值，返回false
if (bit) return false;
//改变字节对应的bit位的值为1，重新写回bits
byte |= (1<<bitIndex);
const Byte bytes2[1] = {byte};
[self.bits replaceBytesInRange:NSMakeRange(byteIndex, 1) withBytes:bytes2];
return true;
}
/// 查看index位置的二进位的值
/// 返回true代表1, false代表0
/// @param index bit位索引
-(BOOL)__getWithIndex:(NSUInteger)index{
//取出索引对应的一个字节
NSUInteger byteIndex = index / 8;
NSUInteger bitIndex = index % 8;
Byte bytes[1];
[self.bits getBytes:bytes range:NSMakeRange(byteIndex, 1)];
Byte byte = bytes[0];
BOOL bit = (byte&(1<<bitIndex));
return bit > 0 ? true : false;
}
-(void)__nullCheck:(id)value{
if (value == nil) {
NSException * exception = [NSException exceptionWithName:@"Value must not be nil"
reason:@""
userInfo:nil];
@throw exception;
}
}
@end
三、使用及误判率验证
1、test1
-(void)test1{
LCBloomFilter * bloomFilter = [LCBloomFilter bloomFilterWithN:3 p:0.01];
BOOL isChange = [bloomFilter put:@"abcde"];
NSLog(@"isChange = %d",isChange);//1
BOOL isContain = [bloomFilter contains:@"abcde"];
NSLog(@"isContain = %d",isContain);//1 可能误判
isChange = [bloomFilter put:@1];
NSLog(@"isChange = %d",isChange);//1
isChange = [bloomFilter put:@1];
NSLog(@"isChange = %d",isChange);//0
isChange = [bloomFilter put:@2];
NSLog(@"isChange = %d",isChange);//1
}
2、test2
-(void)test2{
LCBloomFilter * bloomFilter = [LCBloomFilter bloomFilterWithN:10000 p:0.01];
NSLog(@"开始....");
for (int i = 1; i<= 10000; i++) {
[bloomFilter put:@(i)];
}
int count = 0;
for (int i = 10001; i<= 20000; i++) {
if ([bloomFilter contains:@(i)]) {
count++;
}
}
NSLog(@"count = %d",count);//96 误判率是 96 / 10000
}
3、test3
-(void)test3{
LCBloomFilter * bloomFilter = [LCBloomFilter bloomFilterWithN:10000 p:0.01];
NSLog(@"开始....");
NSMutableArray * urls = [NSMutableArray array];
for (int i = 1; i<= 10000; i++) {
NSString * url = [NSString stringWithFormat:@"https://url%d.com",i];
[urls addObject:url];
}
//网络爬虫模拟 -- 方式一
int count = 0;
for (NSString * url in urls) {
if ([bloomFilter contains:url]) continue;
//爬这个url。。。
count++;
//放进bloomFilter中
[bloomFilter put:url];
}
//9983 有些网站会漏爬 并不会达到10000个 误判率 17/10000
NSLog(@"count = %d",count);
//网络爬虫模拟 -- 方式二
int count2 = 0;
for (NSString * url in urls) {
if ([bloomFilter put:url] == false) continue;
//爬这个url
count2++;
}
//9983 有些网站会漏爬 并不会达到10000个 误判率 17/10000
NSLog(@"count2 = %d",count);
}
行者常至，为者常成！