布隆过滤器与设计 简介 在计算机中集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显着,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。 所以我们可以使用布隆过滤器来过滤掉解决这个问题 布隆过滤器像是一个可以复用基础元素的hash table 通过容忍误判来减少了空间的使用量  原理 ,当一个元素被加入集合时,通过K个 散列函数 将这个元素映射成一个位 数组 中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。 布隆过滤器由长度为M的Bit数组组成 如下图所示…