bitmap VS bloomfilter

Question

bitmap用一个hash函数分配到bit的0或1

bloomfilter 用K个hash函数指定k个(0或1),只有全是1才抓取过

假如我又M个数据,bitmap使用内存是M个bit,bloomfiter需要KM个bit

可以这么理解吗

Answer 1

bobby 2019-06-24 09:26:31

不能这样简单理解， bitmap的数量肯定是要大于M个bit的，不可能做到刚好m个数据就要m个bit位置，会有一定比例的大于初始化的数据量的，不同的初始化大小的连续bit空间会对错误率有不同的影响的，课程中的bloomfilter会更具你的预计数量和错误率计算出需要的空间大小的