type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Mar 24, 2024 01:53 AM
Parent item
领域
当一个元素被加入到集合的时候，用
K个Hash函数将元素映射到一个位图中的K个点，并且把这个点的值设置为1，在每次检索的时候我们看一下这个点是不是都是1就知道集合中有没有这个元素了。这样说可能比较抽象，举个例子：
我们假设
K是2，有Hash1和Hash2两个哈希函数然后我们创建一个名叫bitMap长度是20的位图。
这个时候，我们要将7，存入到这个集合中,分别用Hash1和Hash2计算n哈希后的值，得到1，7。我们把bitMap对应的值置为1，从0开始
这样下次我们来查找7在不在这个集合的时候就可以用Hash1和Hash2计算完以后在bitMap集合中查找对应位置是否都是1，如果都是1则一定在集合中。
如果再在集合中插入13分别计算哈希后的值，得到1，5。
设置位图：
这个时候我们发现1被映射到了两次，但是并不影响我们在集合[7, 13]中快速找到7或者13。
bloom过滤器特点
- 位图中有待检查数据的索引，代表可能存在该数据的记录, 因为索引可能和其他数据索引重合；
- 位图中没有待检查数据的索引，代表肯定不存在该数据的记录；
布隆过滤器可能存在的问题
当插入的数据量大幅提升的时候，甚至
bitMap全部被置为1的时候问题就很严重了，误识率就非常高了，这个也是根据不同场景实现布隆过滤器所要考虑的问题。尽管有这样的问题，但是仍然不能掩盖布隆过滤器的
空间利用率和查询时间远超其他算法，插入数据和查询数据的时间复杂度都是O(k)以太坊中的bloom过滤器是2048位长度的位图。
支持删除么
传统的布隆过滤器并不支持删除操作。
布隆过滤器应用
在实际工作中，布隆过滤器常见的应用场景如下：
- 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
- Google Chrome 使用布隆过滤器识别恶意 URL；
- Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。
- 解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。
缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
- 在 leveldb 中有应用，提升查询未命中的效率。在从磁盘加载数据前，先从布隆过滤器中判断数据是否存在。如果不存在，就直接返回。这样可以减少磁盘访问，提升响应速度。