🧭
区块链技术指南
  • 前言
  • 修订记录
  • 如何贡献
  • 区块链的诞生
    • 记账科技的千年演化
    • 分布式记账与区块链
    • 集大成者的比特币
    • 区块链的商业价值
    • 本章小结
  • 核心技术概览
    • 定义与原理
    • 技术的演化与分类
    • 关键问题和挑战
    • 趋势与展望
    • 认识上的误区
    • 本章小结
  • 典型应用场景
    • 应用场景概览
    • 金融服务
    • 征信管理
    • 权属管理与溯源
    • 资源共享
    • 物流与供应链
    • 物联网
    • 数字艺术品和 NFT
    • 其它场景
    • 本章小结
  • 分布式系统核心技术
    • 一致性问题
    • 共识算法
    • FLP 不可能原理
    • CAP 原理
    • ACID 原则与多阶段提交
    • Paxos 算法与 Raft 算法
    • 拜占庭问题与算法
    • 可靠性指标
    • 本章小结
  • 密码学与安全技术
    • 密码学简史
    • Hash 算法与数字摘要
    • 加解密算法
    • 消息认证码与数字签名
    • 数字证书
    • PKI 体系
    • Merkle 树结构
    • Bloom Filter 结构
    • 同态加密
    • 其它技术
    • 本章小结
  • 比特币 —— 初露锋芒的区块链
    • 比特币项目简介
    • 比特币诞生背景
    • 工作原理
    • 挖矿过程
    • 共识机制
    • 闪电网络
    • 侧链
    • 热门问题
    • 相关工具
    • 本章小结
  • 以太坊 —— 挣脱加密货币的枷锁
    • 以太坊项目简介
    • 核心概念
    • 主要设计
    • 相关工具
    • 安装客户端
    • 使用智能合约
    • 智能合约案例:投票
    • 本章小结
  • 超级账本 —— 面向企业的分布式账本
    • 超级账本项目简介
    • 社区组织结构
    • 顶级项目介绍
    • 开发必备工具
    • 贡献代码
    • 本章小结
  • Fabric 安装与部署
    • 简介
    • 本地编译组件
    • 容器方式获取
    • 本地方式启动 Fabric 网络
    • 容器方式启动 Fabric 网络
    • 本章小结
  • 管理 Fabric 网络
    • 简介
    • 使用通道
    • 管理节点
    • 管理链上代码
    • 监听网络事件
    • 自动发现网络信息
    • 使用运维服务
    • 如何升级网络版本
    • 使用 SDK
    • 注意事项与最佳实践
    • 本章小结
  • 智能合约开发
    • 简介
    • 链码概念与结构
    • 示例一:信息公证
    • 示例二:交易资产
    • 示例三:数字货币发行与管理
    • 示例四:学历认证
    • 示例五:社区能源共享
    • 小结
  • Fabric 架构与设计
    • 简介
    • 架构设计
    • 消息协议
    • 小结
  • 区块链服务平台设计
    • 简介
    • IBM Bluemix 云区块链服务
    • 微软 Azure 云区块链服务
    • 使用超级账本 Cello 搭建区块链服务
    • 本章小结
  • 性能与评测
    • 简介
    • Hyperledger Fabric v0.6
    • 小结
  • 附录
    • 术语
    • 常见问题
    • Go 语言开发相关
      • 安装与配置 Golang 环境
      • 编辑器与 IDE
      • 高效开发工具
      • 依赖管理
    • ProtoBuf 与 gRPC
    • 参考资源链接
由 GitBook 提供支持
在本页
  • 基于 Hash 的快速查找
  • 更高效的布隆过滤器

这有帮助吗?

在GitHub上编辑
  1. 密码学与安全技术

Bloom Filter 结构

上一页Merkle 树结构下一页同态加密

最后更新于3年前

这有帮助吗?

布隆过滤器(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%。

布隆过滤器