Java 大数据算法 布隆过滤器的简单实现
【摘要】 布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,布隆过滤器可以用于检索一个元素是否在一个集合中,因此它是一个空间效率极高的概率型算法;它实际上是一个很长的二进制向量和一系列随机映射函数;优缺点仅仅保留数据的指纹信息,空间效率极高;查询效率极高,时间复杂度为:O(n);信息安全性较高;存在一定的误判;(默认大概3% 的错误率,可牺牲时间和空间,使错误率无限趋向于零)数据删...
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,布隆过滤器可以用于检索一个元素是否在一个集合中,因此它是一个空间效率极高的概率型算法;它实际上是一个很长的二进制向量和一系列随机映射函数;
优缺点
仅仅保留数据的指纹信息,空间效率极高;
查询效率极高,时间复杂度为:O(n);
信息安全性较高;
存在一定的误判;(默认大概3% 的错误率,可牺牲时间和空间,使错误率无限趋向于零)
数据删除困难;
public class BloomFilterDemo {
private static final int insertions = 1000000;//100w
@Test
public void bfTest(){
//初始化一个存储string数据的布隆过滤器,初始化大小100w
BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.001);
//初始化一个存储string数据的set,初始化大小100w
Set<String> sets = new HashSet<>(insertions);
//初始化一个存储string数据的set,初始化大小100w
List<String> lists = new ArrayList<String>(insertions);
//向三个容器初始化100万个随机并且唯一的字符串,100万个uuid 34M多
for (int i = 0; i < insertions; i++) {
String uuid = UUID.randomUUID().toString();
bf.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
int wrong = 0;//布隆过滤器错误判断的次数
int right =0;//布隆过滤器正确判断的次数
//在大街上找10000个人
for (int i = 0; i < 10000; i++) {
String test = i % 100 == 0 ? lists.get(i/100):UUID.randomUUID().toString();//按照一定比例选择bf中肯定存在的值
if(bf.mightContain(test)){
if(sets.contains(test)){
right ++;
}else{
wrong ++;
}
}
}
System.out.println("================right==============="+right);
System.out.println("================wrong==============="+wrong);
}
//720万长度的bit数组 容量约为0.86M
//1400万长度的bit数组容量约为1.67M
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)