U201915015-杨超平-课程报告1
需积分: 0 118 浏览量
2022-08-08
18:02:39
上传
评论
收藏 121KB DOCX 举报
大数据存储与管理
基于 Bloom Filter 的设计
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二
进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个
集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定
的误识别率和删除困难.
布隆过滤器的主要作用就是 "以更低的空间效率检索一个元素是否
存在其中"
数据结构
关键因子
� bloom filter calculate
� n 是过滤器预期支持的元素个数
� m 是过滤器位数组的大小，即该过滤器总共占用多少 bit 的空间
� c 是每个元素平均占用的空间
� p 是假阳性概率，即 fpp (false positive probability)
� k 哈希函数的个数
计算公式
评论0