布隆过滤器

位图

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

适用场景

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

原理

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

反之大概率存在

优点

• 占用内存小
• 增加和查询的时间复杂度为：O(K)，K为哈希函数的个数
• 哈希函数相互之间没有关系，方便硬件并行运算
• 布隆过滤器本身不存储元素本身，在某些对保密要求比较严格的场合有很大优势
• 数据量很大时，布隆过滤器可以表示全集
• 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点

• 存在误判率
• 不能获取元素本身
• 一般情况下不能从布隆过滤器删除元素