🧭
🧭
🧭
🧭
区块链技术指南
搜索文档…
🧭
🧭
🧭
🧭
区块链技术指南
前言
修订记录
如何贡献
区块链的诞生
核心技术概览
典型应用场景
分布式系统核心技术
密码学与安全技术
密码学简史
Hash 算法与数字摘要
加解密算法
消息认证码与数字签名
数字证书
PKI 体系
Merkle 树结构
Bloom Filter 结构
同态加密
其它技术
本章小结
比特币 —— 初露锋芒的区块链
以太坊 —— 挣脱加密货币的枷锁
超级账本 —— 面向企业的分布式账本
Fabric 安装与部署
智能合约开发
Fabric 架构与设计
区块链服务平台设计
性能与评测
附录
由
GitBook
提供支持
Bloom Filter 结构
布隆过滤器(Bloom Filter)是在 1970 年由 Burton Howard Bloom 在论文《Space/Time Trade-offs in Hash Coding with Allowable Errors》提出的。布隆过滤器是一种基于 Hash 的高效查找结构,能够快速(常数时间内)回答“某个元素是否在一个集合内”的问题。
该结构因为具有高效性而广泛应用到网络和安全领域,例如信息检索(BigTable 和 HBase)、垃圾邮件规则、注册管理等。
基于 Hash 的快速查找
在介绍布隆过滤器之前,先来看看基于 Hash 的快速查找算法。在前面的讲解中,我们提到,Hash 可以将任意内容映射到一个固定长度的字符串,而且不同内容映射到相同串的概率很低。因此,这就构成了一个很好的“内容 -> 索引”的生成关系。
试想,如果给定一个内容和存储数组,通过构造 Hash 函数,让映射后的 Hash 值总不超过数组的大小,则可以实现快速的基于内容的查找。例如,内容 “hello world” 的 Hash 值如果是 “100”,则存放到数组的第 100 个单元上去。如果需要快速查找任意内容,如 “hello world” 字符串是否在存储系统中,只需要将其在常数时间内计算 Hash 值,并用 Hash 值查看系统中对应元素即可。该系统“完美地”实现了常数时间内的查找。
然而,令人遗憾的是,当映射后的值限制在一定范围(如总数组的大小)内时,会发现 Hash 冲突的概率会变高,而且范围越小,冲突概率越大。很多时候,存储系统的大小又不能无限扩展,这就造成算法效率的下降。为了提高空间利用率,后来人们基于 Hash 算法的思想设计出了布隆过滤器结构。
更高效的布隆过滤器
布隆过滤器
布隆过滤器采用了多个 Hash 函数来提高空间利用率。
对同一个给定输入来说,多个 Hash 函数计算出多个地址,分别在位串的这些地址上标记为 1。在查找时,进行同样的计算过程,并查看对应元素,如果都为 1,则说明较大概率是存在该输入。
布隆过滤器与单个 Hash 算法查找相比,大大提高了空间利用率,可以使用较少的空间来表示较大集合的存在关系。
实际上,无论是 Hash 还是布隆过滤器,基本思想是一致的,都是基于内容的编址。Hash 函数存在冲突,布隆过滤器也存在冲突,即这两种方法都存在着误报(False Positive)的情况,但绝对不会漏报(False Negative)。
布隆过滤器在应用中误报率往往很低,例如,在使用 7 个不同 Hash 函数的情况下,记录 100 万个数据,采用 2 MB 大小的位串,整体的误判率将低于 1%。而传统的 Hash 查找算法的误报率将接近 10%。
以前
Merkle 树结构
下一个
同态加密
最近更新
5mo ago
复制链接
在 GitHub 上编辑
大纲
基于 Hash 的快速查找
更高效的布隆过滤器