首页 > 其他分享 >2020-11-09:谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点?

2020-11-09:谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点?

时间:2023-05-12 10:31:51浏览次数:52  
标签:11 函数 布谷鸟 09 布隆 哈希 过滤器


福哥答案2020-11-09:

相同点:
都是过滤器。

不同点:
算法:布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。
能否删除:布隆过滤器无法删除元素。布谷鸟过滤器可以删除元素,有误删可能。
空间是否2的指数:布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。
空间利用率:相同误判下,布谷鸟空间节省40%多。
查询性能:布隆过滤器查询性能弱,原因是使用了多个hash函数,内存跨度大,缓存行命中率低。布谷鸟过滤器访问内存次数低,效率相对高。
哈希相关:布隆过滤器的多个函数函数之间没关系。布谷鸟过滤器的两个哈希函数可互相推导,两者有关系,用到了【空间是2的指数】和【按位与】。
重复插入相同元素:布隆过滤器天然自带重复过滤。布谷鸟过滤器会发生挤兑循环问题。


Redis布隆Bloom过滤器布隆过滤器过时了,未来属于布谷鸟过滤器?【Redis 第七篇】面试加分项:缓存穿透,布隆过滤器-计数过滤器-布谷鸟过滤器(好文005)


标签:11,函数,布谷鸟,09,布隆,哈希,过滤器
From: https://blog.51cto.com/u_14891145/6269418

相关文章

  • 基于28335实现的旋变软解码 1、在0-360°的范围内,与TI方案的偏差非常小,平均偏差最大为
    基于28335实现的旋变软解码1、在0-360°的范围内,与TI方案的偏差非常小,平均偏差最大为0.0009弧度左右,最大偏差0.0016弧度左右。2、与1205最大偏差在±3个弧分以内,考虑到AD2S1205的精度为±11个弧分,可以认为这个偏差没有任何问题。3、对179°输入的响应如图所示,可以看到179°输入......
  • SSO2.0 3-20230511
         ......
  • 5.11
    一.问题描述pta多态实验:1.定义一个整数加法器类Adder,对其重载运算符“+”、“++”,main(void)函数完成对其的测试。#include<iostream>usingnamespacestd;/*请在这里填写答案*///主函数intmain(void){intx;Addera1,a2(a1);cin>>x;(a1++).show()......
  • day70(2023.5.11)
    1.计算机网络通信 2.TCP/IP协议群 3.TCP协议传输特点 4.服务端口 5.数据包与处理流程 6.HTTP协议简介 7.HTTP协议特点 8.HTTP协议发展和版本     9.HTTP协议中URI、URL、URN10.HTTP协议的......
  • 5.11打卡
     二、思路设计 三、代码实现#include<bits/stdc++.h>usingnamespacestd;#defineTAXBASE3500;typedefstruct{longstart;longend;doubletaxrate;}TAXTABLE;TAXTABLETaxTable[]={{0,1500,0.03},{1500,4500,0.10},{4500,9000,0.20}......
  • ORA-01172 ORA-01151 故障恢复---惜分飞
    联系:手机/微信(+8617813235971)QQ(107644445)标题:ORA-01172ORA-01151故障恢复作者:惜分飞©版权所有[未经本人同意,不得以任何形式转载,否则有进一步追究法律责任的权利.]节点2报Error:Controlfilesequencenumberinfileheaderisdifferentfromtheoneinmemory,导......
  • C/C++折半查找与哈希查找[2023-05-11]
    C/C++折半查找与哈希查找[2023-05-11]4、折半查找与哈希查找(难度等级A)[问题描述]查找是通过在查找表中做比较来完成的操作。折半查找与哈希查找都是利用数组实现的查找算法。通过本题,可以观察两种查找算法的性能。一般我们用平均查找长度ASL来表示一种查找算法的性能。ASL......
  • 2023.5.11
    1//例6-162#include<iostream>3usingnamespacestd;4classPoint5{6public:7Point():x(0),y(0)8{9cout<<"DefaultConstructorcalled."<<endl;10}11Point(intx,inty):x(x),y......
  • 音视频八股文(11)-- ffmpeg 音频重采样
    1重采样1.1什么是重采样所谓的重采样,就是改变⾳频的采样率、sampleformat、声道数等参数,使之按照我们期望的参数输出。1.2为什么要重采样为什么要重采样?当然是原有的⾳频参数不满⾜我们的需求,⽐如在FFmpeg解码⾳频的时候,不同的⾳源有不同的格式,采样率等,在解码后的数据中的这些参......
  • 音视频八股文(11)-- ffmpeg 音频重采样
    1重采样1.1什么是重采样所谓的重采样,就是改变⾳频的采样率、sampleformat、声道数等参数,使之按照我们期望的参数输出。1.2为什么要重采样为什么要重采样?当然是原有的⾳频参数不满⾜我们的需求,⽐如在FFmpeg解码⾳频的时候,不同的⾳源有不同的格式,采样率等,在解码后的数据中的这些参......