3
34 布隆过滤器
source link: https://segmentfault.com/a/1190000040401077
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
什么是布隆过滤器
一种检测元素是否在给定大集合中的数据结构。是一个位数组。元素只能是1或0。性能好，但不容易删除，有一定错误率，集合越大错误率越高。
如何使用布隆过滤器
布隆过滤器有多个哈希函数，将元素放入过滤器时，用这几个哈希函数求元素hash值，然后将对应的位置为1,。
检测元素是否存在时，用这几个哈希函数对元素求哈希值，然后检测对应的位置是否为1。
因此布隆过滤器说某个元素存在，可能会误判，但说某个元素不在，那肯定不在。
布隆过滤器应用场景
- 判断元素是否存在与海量数据集里/去重
- 防缓存穿透
将数据制成布隆过滤器，如果缓存里没有请求数据，先看看布隆过滤器里是否有请求数据，如果没有就不用请求数据库直接返回，如果有可以先把数据放到缓存里，也不用请求数据库。 - 垃圾邮件过滤和黑名单
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK