August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
112
｜
第
5
章
在图
5-5
中，假设两个值
u
和
v
存在于位数组
B
中。在图的上半部分我们使用
k
= 3
个
散列函数来计算哪些位应该被置
1
。可以看到，
布隆过滤器
可以很快地认为一个元素
w
并不在
B
中，因为有一个位的值是
0
（这里是第
6
个比特）。但是查找
x
的时候，它会
错误地返回存在，因为所有
k
个比特都是
1
。
࿋ຕፇ
C
图 5-5：布隆过滤器例子
5.4.1 输入 / 输出
布隆过滤器
的输入和
散列搜索
基本上大同小异。它需要一个
m
bits
的数组并且初始化为
0
。
而且还需要
k
个散列函数来计算元素插入时的散列值，并且映射到这个位数组中去。
布隆过滤器
在能确定目标元素还未插入位数组时返回
false
，即它能够判断元素不在集
中
C
当中。不过在元素还没有插入位数组之前，算法有可能会返回
true
，即
误报
。
5.4.2 使用环境
虽然
布隆过滤器
的内存使用非常高效，不过它也只有在误报可以被容忍的情况下才显得
有用。
布隆过滤器
可以通过过滤一些必然失败的条件来减少昂贵搜索的次数，例如，借
助布隆过滤器来确认是否在基于磁盘的存储上进行昂贵的搜索。
5.4.3 解决方案
布隆过滤器
需要
m
bits
的存储空间。例
5-10
是它的
Python
实现，并且使用了
bignum
库。
例
5-10
：布隆过滤器的
Python
实现
class bloomFilter:
def __init__(self, size=1000, hashFunctions=None):
"""
创建一个
size bits(
默认
1000)
的布隆过滤器
,
并且提供相应的散列函数
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.