type
status
date
slug
summary
tags
category
icon
password
overview
许多人都有过这样的经历：注册新的社交平台或是游戏账号时，需要输入一个独一无二的名字，可输入了很多。却发现系统总返回类似user name has existed这样的信息；注册过的用户可能有成百上千万，应用是如何快速判断我们输入的username是否已经被注册过了呢？
让我们将问题进一步陈述：如何在一堆数据中快速判断某一个数据是否存在？
大多数人的第一反应是二分法，二分法也确实可以用来处理这个需求，但是二分法logn的时间复杂度使得应用判断的依旧不够快。
于此，我们引入了今天的主角—bloom filter（布隆过滤器）
WHAT
bloom filter是一种高效的数据筛选结构，可以用来快速判断某一个数据是否存在于一个数据集中；这里讲的高效，是时间与空间两方面的。
HOW
bloom filter主要涉及存储与查找两个过程；
其实现机制主要依靠两个东西：哈希函数与byte数组；
byte数组所有元素初始值均为0，其后存入的元素按照一定的映射规则，将对应的元素置为1，其后判断是否存在该元素时，按照相同的映射规则，找到对应的元素，看其是否为1；
以下是存储过程的大致流程：
- 我们要有一个byte数组，其所有元素为0，方便起见，假设数组大小为10；
- 准备一组哈希函数，这里方便起见，假设为三个：h1，h2，h3；
- 定义一组映射规则，用于将哈希后的结果映射到byte数组下标，比如：
h1（imput）%10=3
- 传入input，假定input为lover，以下是映射过程：
h1(”lover”)%10=1
h2(”lover”)%10=7
h3(”lover”)%10=9
- 将以上映射出来的index所对应的元素置1；
至此，我们实现了存储的过程；
查找的过程便是判断对应下标的元素是否为1，假如有一个不为1，我们就认为这个元素不存在，否则认为它存在；
Note
bloom filter判断元素是否存在的功能十分强大，但是它有一个缺陷，有时会把不存在的数据判断为存在，这个缺陷本质是因为哈希碰撞，导致两个input映射之后的元素相同，我们可以通过增大byte数组的大小来降低这种概率；（注意：存在的数据是绝对不会被判断为不存在的！）
Implement
下面是Go语言bloom filter的简单实现：
Application
bloom filter的应用十分广泛，除了上面说过的用户名判断，还包括但不限于：
防短信邮件轰炸，以太坊收据树中用于快速查询，防止缓存击穿…
- 作者:Alex
- 链接:https://nextme.one/wureny.eth/article/bloomfilter
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章