Bitget App
Trade smarter
行情交易合约跟单策略理财Web3

布隆过滤器

高级
share

布隆过滤器是一种概率数据结构,旨在有效地测试某个元素是否在一个集合中。它由伯顿·霍华德·布隆(Burton Howard Bloom)于1970年发明,能够以最小的内存消耗管理大型数据集,因为成为计算机科学领域的基本工具。与哈希表或二叉搜索树等传统数据结构不同,当某个元素不在集合中时,布隆过滤器可以提供确定的答案,但当某个元素在集合中时,它只能提供概率答案。这意味着虽然可能出现假阳性,但不会出现假阴性。

布隆过滤器的核心概念围绕着一个位数组和一系列哈希函数展开,位数组初始化均为0。当一个元素被添加到布隆过滤器时,它会通过每个哈希函数在位数组中产生多个位置。然后将这些位置上的比特位设置为1。要检查某个元素是否在集合中,需要再次使用相同的函数对其进行散列,并检查相应的比特位。如果这些位置上的所有比特位都是1,则认为该元素有可能出现在集合中;如果任何一位都是0,则该元素肯定不在集合中。

布隆过滤器的一个显著优势是空间效率高。与执行相同任务的其他数据结构相比,它们所需的内存要少得多,当元素数量增加时尤其如此。例如,无论集合中的元素数量多少,要达到1%的误报概率,每个元素所需的比特数少于10比特。因此,对于网络路由器、数据库系统和分布式系统等内存使用率至关重要的应用来说,布隆过滤器尤为有用。

不过,布隆过滤器也有一定的局限性。最主要的缺点就是无法从集合中删除元素,因为清除被多个元素设置的比特位会带来假阴性。为了解决这个问题,我们开发了计数式布隆过滤器(counting bloom filter)等变体,通过对每个比特位被设置的次数进行计数来删除元素。此外,随着元素的增加,误报率也会增加,这意味着必须根据预期的元素数量和可接受的误报率来谨慎选择比特数组的大小和哈希函数的数量。

在实际应用中,布隆过滤器在各个领域得到了广泛使用。例如,在比特币中,它们被用于增强简化支付验证(SPV)客户端的隐私性,允许用户在不暴露地址的情况下查询交易。Akamai 等内容分发网络使用布隆过滤器来有效管理缓存存储,通过避免不必要的数据检索来减少服务器的工作量。尽管布隆过滤器具有一定的概率和局限性,但它仍然是设计高效且可扩展系统的宝贵工具。

下载 App
下载 App