布隆过滤器

位图

位图中的每一个槽只占1 bit的内存，所以即便面对10亿数据也只占用119多M的内存

适用场景

1
在面临大数据的情况下，判断一个数是否存在

原理

1
2
将判断的值分多个hash函数进行计算，如果其中有一个hash函数的值不等于1，则可以判定这个数不存在；
反之大概率存在

优点

  • 占用内存小

  • 增加和查询的时间复杂度为：O(K)，K为哈希函数的个数

  • 哈希函数相互之间没有关系，方便硬件并行运算

  • 布隆过滤器本身不存储元素本身，在某些对保密要求比较严格的场合有很大优势

  • 数据量很大时，布隆过滤器可以表示全集

  • 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

  • 缺点

  • 存在误判率

  • 不能获取元素本身

  • 一般情况下不能从布隆过滤器删除元素

Redis原理

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！