精品课件
Hash函数
假设hash表的大小为9（即有9个槽），hash(k) = k mod 9，现在要把 一串数据存到表里：5,28,19,15,20,33,12,17,10
hash(5)=5, hash(28)=1，hash(19)=1， 01 234 567 8
28
5
n个关键字映射到k个槽中，n只要大于k，一定至少有一个槽放了多于1个元 素，所以不能完全避免碰撞（冲突） 。
位图法
比如一个公司有8个员工，现在需要记录公司的考勤记录，传统 的方案是记录下每天正常考勤的员工的ID列表，比如2012-0101:[1,2,3,4,5,6,7,8]。
假如员工ID采用byte数据类型，则保存每天的考勤记录需要N个byte ，其中N是当天考勤的总人数。 1 2 3 4 5 67 8
精品课件
位图法
位图法就是Bitmap的缩写。就是用每一位来存放某种状态，适用于 大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存 不存在的。
位图法可以理解为通过一个bit数组来存储特定数据的一种数据结构；由 于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间。
精品课件
s'1 = F'1 = s1 s'2 = F'2 s'3 = F'3 = s2 s'4 = F'4 = s3 s'5 = F'5 = s4 s'6 = F'6 = s5 s'7 = F'7 = s6 s'8 = F'8 = s7
布隆过滤器
算法描述
精品课件
Bloom Filter
布隆过滤器（Bloom Filter）是一种概率空间高效的数据 结构。用于检索一个元素是否在一个集合中。
存在“在集合内（可能错误）”和“不在集合内（绝对不 在集合内）”两种情况。
精品课件
温故知新
精品课件
核心思想
核心思想就是利用多个不同的Hash函数来解决“冲突”。 如何判断某元素x是否在一个集合中？
X
X1,X2,X3.. ..Xn
R
精品课件
算法原理
Bloom Filter需要一个位数组(和位图类似)和K个映射函数(和Hash 表类似)。包含两种操作：插入和查询 1.初始化：将所有位置0 2. 集合R={r1,r2...rn},通过k个相互独立的映射函数{h1,h2,......hk}，将集 合R中的每个元素rj(1<=j<=n)映射为K个值 3.将位数组中相对应的array[h1]，array[h2]，array[h3]......array[hk]置 为1
删除操作： 不允许删除一个元素，会导致false negative。 false negative：把属于这个集合的元素误认为不属于这个集合。
精品课件
添加地址
1亿
邮箱
16亿二进 制
0
0
0
0
0
0
0
0
0
0
abc123@gmail.co m
abc456@gmail.co m
随机数生成器 F1-8
随机数生成器 G
01110011
这样可以每天采用恒定的1个byte即可保存当天的考勤记录。
精品课件
布隆过滤器
布隆过滤器（Bloom Filter），它结合了位图和Hash 表两者的优点.
位图的优点是节省空间，但是只能处理整型值一类的问题 ，无法处理字符串一类的问题.
而Hash表却恰巧解决了位图无法解决的问题，然而Hash 太浪费空间。
精品课件
算法原理
精品课件
算法原理
精品课件
算法原理
4.将待查询元素映射到位数组中，若对应每位都是1，则在集合中； 否则，不在。 注：会出现两种情况：（1）没有发生误判（2）发生了误判（false positive） false positive：有可能会把不属于这个集合的元素误认为属于这个 集合。
1
01
1
1
1
1
1
1
1
0
g1 g' g' 2 1
g2 g8 g3 g4 g5 g6 g7
精品课件
查询地址
1
1
1
t1 t'2 t2
abc123@gmail.co m
BCD123@gmail.co m
16亿二进 制
1
0
t8 t3 t4 t5 t6 t7
随机数生成器 F1-8
信息指 纹
s1 = F1 s2 = F2 s3 = F3 s4 = F4 s5 = F5 s6 = F6 s7 = F7 s8 = F8
布隆过滤器
信息安全课程报告
Bloom filter -------- The course report of Information security
组长：
汇报人：
精品课件
CONTENTS
目 录
1 背景介绍 2 算法描述 3 误判概率证明和计算 4 优劣详解 5 布隆过滤器改进方案 6 布隆过滤器设计和应用
Hash函数
一般来讲，计算机中的集合是用哈希表（hash table）来存储的。 Hash函数作用就是把要存的数据映射成hash表中的一个位置，这个位置 就是你要存放该数据的地方。一般把hash表的每个位置都叫做“槽（slot） ”。 它的好处是快速准确，缺点是浪费存储空间。当集合比较小时，这个问题 不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来 了。
信息指 纹
f1 = F1 f‘1 = F‘1 = f1 f2 = F2 f’2 = F’2 f3 = F3 f‘3 = F’3 = m2 f4 = F4 f’4 = F‘4 = m3 f5 = F5 f‘5 = F’5 = m4 f6 = F6 f’6 = F‘6 = m5 f7 = F7 f‘7 = F’7 = m6 f8 = F8 f’8 = F‘8 = m7
精品课件
The background of Bloom filter
布隆过滤器
背景介绍
精品课件
背景介绍
比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它 是否在已知的字典中）； 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上； 在网络爬虫里，一个网址是否被访问过等等。
精品课件
精品课件
计数布隆过滤器
计数布隆过滤器是对基本布隆过滤器的改进，使布隆过滤器可以支 持删除成员。 因为布隆过滤器的基本单位是1个bit，只能表达2种状态， 即存在、不存在。 如果把基本单位1bit拓展成多个bit，这样就能增加更 多信息，表达出多种状态。
精品课件
The description of it's core algorithm