侧边栏壁纸
博主头像
Lang博主等级

十七岁想打职业。

  • 累计撰写 10 篇文章
  • 累计创建 11 个标签
  • 累计收到 1 条评论
隐藏侧边栏

布隆过滤器? 为什么不直接用HashMap?

Lang
2022-02-10 / 0 评论 / 0 点赞 / 252 阅读 / 645 字
温馨提示:
本文最后更新于 2022-02-10,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

什么是布隆过滤器:

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

布隆过滤器应用场景:

为了解决redis缓存穿透问题(大量请求的 key 根本不存在于缓存中,导致请求直接到了数据库上)通常的一种解决方案就是布隆过滤器。

我们只需要在布隆过滤器上判断该元素是否存在,如果不存在则直接返回,如果判断存在则查询缓存和数据库,尽管有误判率的影响,但是也能够大大减少数据库的负担,同时也能够阻挡大部分的非法请求。

于是我就想为啥不直接用HashMap? 这样就不会有布隆过滤器无法删除以及误判的缺点。我把问题抛入群里,于是引发了以下对话。





总结一下:

  1. 布隆过滤器主要是解决redis缓存穿透问题。
  2. HashMap与布隆过滤器应用场景不同,布隆过滤器的使用场景是判断指定值是否存在,hashmap不仅判断是否存在,而且存储了完整的数据。
  3. 布隆过滤器的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
0

评论