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

一忘皆空!

  • 累计撰写 22 篇文章
  • 累计创建 15 个标签
  • 累计收到 25 条评论

目 录CONTENT

文章目录

简单记下两种过滤器

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

简单记下两种过滤器

在使用缓存时, 可能会出现的一个问题就是缓存穿透, 就是请求不存在的数据, 没命中缓存, 直接落到数据库.为了解决这个问题, 可以采取的一个措施就是引入过滤器

布隆过滤器

原理

这个应该都比较熟悉, 它是一个bitmap, 通过对key进行多次hash计算出多个hash值, 然后得到不同的哈希桶的下标, 然后将这些下标设置为1.

如果这个key再一次请求过来, 再根据之前的几个hash函数, 得到哈希桶下标, 判断是不是都为1. 如果是, 则表示有可能存在, 如果有一个为0, 则表示一定不存在.

缺点

  1. 无法删除, 布隆过滤器的原理决定了它无法因为删除某个元素而将哈希桶设置为0
  2. 存在误判, 由于哈希碰撞, 不同的元素的哈希桶可能一样
  3. 空间利用率低, 数据量比较大时,哈希碰撞也更严重, 要保证一定的精度的话, 需要更大容量的bitmap, 这样就会存在一些哈希桶空间浪费

布谷过滤器

原理

布谷过滤器也是一个数组构成. 数组中每个元素可以是一个数组byte[4]来容纳多个数据.

同样的对key进行两次哈希函数计算, 得到两个哈希桶坐标, 同时也可以计算出key的指纹, 一般是8bit, 然后判断两个位置是否被占用, 如果没有则将指纹存到其中一个位置. 如果两个位置被占用, 选择一个踢出挤占. 被踢出的那个也同样再根据它的指纹和当前的下标计算它的另一个位置是否被占用, 以此类推

判断是否存在, 布谷过滤器一个哈希桶可以有多个座位, 根据哈希函数计算key的两个下标和指纹, 判断这两个下标里的所有座位, 是否有指纹匹配的, 有则表示可能存在.

布谷过滤器的巧妙之处就是可以通过下标1,和指纹的哈希值异或运算得到下标2的位置

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 异或

和布隆过滤器相比

  1. 在错误率小于3%时, 布谷过滤器的空间性能由于布隆过滤器. 因为它可以通过依次踢出挤占来提高空间利用率
  2. 在查询效率方面高于布隆过滤器, 因为只有2个哈希函数, 即只需要查询访问内存两次就可以判断过滤, 而布隆过滤器需要多个哈希函数计算, 且哈希桶坐标无序, 需要cpu多次寻址. 而布谷过滤器一个哈希桶中的几个座位地址是连续的, 可以利用cpu缓存提高性能
  3. 当数据量大了以后, 还是容易出现循环挤占, 插入时性能降低, 耗费cpu
  4. 和布隆过滤器一样, 删除也同样可能导致误删其他元素
1

评论区