布隆过滤器原理 优缺点有哪些

布隆过滤器原理

今天为网友们详解布隆过滤器原理的方法内容，很不错的方法小知识，建议收藏哦！

位图：int[10]，每个int类型的整数是4*8=32个bit，则int[10]一共有320 bit，每个bit非0即1，初始化时都是0

• 添加数据时，将数据进行hash得到hash值，对应到bit位，将该bit改为1，hash函数可以定义多个，则一个数据添加会将多个（hash函数个数）bit改为1，多个hash函数的目的是减少hash碰撞的概率
• 查询数据：hash函数计算得到hash值，对应到bit中，如果有一个为0，则说明数据不在bit中，如果都为1，则该数据可能在bit中

优点：

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

缺点：

• 误判率，即存在假阳性(False Position)，不能准确判断元素是否在集合中
• 不能获取元素本身
• 一般情况下不能从布隆过滤器中删除元素

上述的关于布隆过滤器原理 以及 优缺点有哪些的全文内容，IT袋网[www.itdai.com]希望对网友有所帮助！