布隆过滤器之误识别率FPP公式的推导

在《什么是布隆过滤器(Bloom Filter)?》一文中,多次提到了误识别率(FPP,false positive probabilistic)。

那么误识别率到底是多大,应该如何计算呢?

假设布隆过滤器大小为m比特,存储了n个元素,使用k次散列函数来计算元素的存储位置。 … [阅读文章]

什么是布隆过滤器(Bloom Filter)?

在日常工作中,有一个比较常见的需求,就是需要判断一个元素是否在集合中。

例如以下场景:

给定一个IP黑名单库,检查指定IP是否在黑名单中? 在接收邮件的时候,判断一个邮箱地址是否为垃圾邮件? 在文字处理软件中,检查一个英文单词是否拼写正确?

遇到这种问题,通常直觉会告诉我们,应该使用集合这种数据结构来实现。例如,先将IP黑名单库的所有IP全部存储到一个集合中,然后再拿指定的IP到该集合中检查是否存在,如果存在则说明该IP命中黑名单。 … [阅读文章]

不用加减乘除做加法

一. 十进制计算

计算十进制 13+9:

1.计算不进位的和。十位 1 不变,个位 3 加 9 等于 2,结果为 12 ;

2.计算进位。十位没进位,个位进位为 1,结果为 10。

再计算十进制 12+10:

1.计算不进位的和。十位 1 加 1 等于 2,个位 2 加 0 等于 2,结果为 22 ; … [阅读文章]

Times 33 哈希算法

一个好的散列函数通常倾向于“为不相等的对象产生不相等的散列码”。理想情况下,散列函数应该把集合中不相等的实例均匀地分布到所有可能的散列值上。要想完全达到这种理想的情形是非常困难的。幸运的是,相对接近这种理想情形则并不太困难。

由Daniel J. … [阅读文章]

一篇总结二叉树的4种遍历方式(含模板)

万丈高楼平地起,正所谓地基打得好,百年不会倒。

计算机程序如同高楼的建造,也是要先打好地基,再一层层往上盖。

程序是由数据结构和算法组成的,核心是数据结构和算法。

本篇我们要总结的,是二叉树这种数据结构的遍历方式,提供一些基本的模板,以便随时查阅与套用,快速的搭建程序。 … [阅读文章]