位图（BitMap）

定义

位图（BitMap）是一种用二进制位（bit）来表示状态的数据结构，每个 bit 对应一个元素的存在状态（1 表示存在，0 表示不存在）。

核心优势

  • 空间效率极高：相比布尔数组（1 byte/元素），位图仅用 1 bit/元素，节省 7/8 的空间
  • 适合超大规模数据：如判断 10 亿个整数中是否存在某个数，仅需 ~120MB 空间

局限性

  • 仅支持整数类型的数据
  • 无法处理字符串等其他类型
  • 布隆过滤器是其扩展，支持更多数据类型 → 布隆过滤器

相关概念

  • 哈希表：位图可作为哈希表的简化替代（仅判断存在性）
  • 布隆过滤器：基于位图的扩展
  • 数组：底层用位数组（bit array）实现

Link to this note

布隆过滤器

type: concept tags:布隆过滤器概率型数据结构空间优化哈希 created: 2026-05-03 updated: 2026-05-03布隆过滤器（Bloom Filter）定义布隆过滤器（Bloom Filter）是一种概率型数据结构，用于在超大规模数据集中快速判断一个元素是否存在，仅使用少量内存空间，且具备数据隐私性。核心原理布隆过滤器不存储具体数据，而仅仅存储数据指纹（哈希值），通过多个哈希函数将数据映射到位图（bitmap） 中的多个位置，通过比对指纹来判断数据是否存在。基本操作：添加元素：用 k 个哈希函数计算哈希值，将位图中对应的 k 个位置设为 1查询元素：用同样的 k 个哈希函数计算哈希值，检查位图中对应的 k 个位置：如果任意一位为 0 → 元素一定不存在（无假阴性）如果所有位都为 1 → 元素可能存在（有假阳性）特性| 特性 | 说明 | |------|------| | 空间效率 | 极高，仅存储哈希值，不存储实际数据 | | 查询时间 | $O(k)$，k 为哈希函数个数，通常为常数 | | 假阴性（False Negative） | 不存在（如果查询说不存在，就一定不存在） | |

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

log

Harness Engineering - 操作日志本页面记录所有 Claude 的操作记录，仅追加，不修改历史记录[2026-05-02] init | 初始化仓库结构创建 raw/ 目录结构（articles, papers, images）创建 wiki/ 目录结构（entities, concepts, summaries, comparison）创建 wiki/index.md 索引页创建 wiki/log.md 操作日志仓库初始化完成[2026-05-02] ingest | 时间空间复杂度入门保存原始内容到 raw/articles/复杂度分析基础.md创建摘要页 wiki/summaries/2026-05-02 时间空间复杂度入门.md侧重：复杂度分析的实用方法（Big O 简化估算技巧）更新 wiki/index.md：摘要页数量 0→1注意：labuladong 实体和复杂度概念首次出现，暂不创建独立页（需 ≥2 篇来源）[2026-05-02] ingest | 数组基础（labuladong）提取网页内容（defuddle）并创建摘要页 wiki/summaries/2026-05-02 数组基础.md创建实体页

位图-总结

type: summary tags: [位图, 数据结构, 空间优化, bitmap] created: 2026-05-02 updated: 2026-05-02位图（BitMap）基础[[raw/articles/2026/05/位图]]一句话总结位图（BitMap）是一种极致节省空间的数据结构，用 1 个比特位（bit）的 0/1 来标记元素是否存在，相比布尔数组节省 7/8 的内存空间，适用于超大规模数据场景。核心原理问题背景在算法题中，常用 boolean[] visited 布尔数组记录元素访问状态：boolean[] visited = new boolean[nums.length]; visited[10] = true;空间浪费问题：布尔类型只需 1 bit（0/1）即可表示但大部分编程语言中，一个 boolean 占用 1 字节（8 bits） 内存布尔数组实际浪费了 7/8 的存储空间位图设计位图直接用 1 个 bit 表示一种状态：0 表示元素不存在 / 未访问1

布隆过滤器-总结

type: summary tags: [布隆过滤器, 数据结构, 概率型数据结构, 空间优化] created: 2026-05-03 updated: 2026-05-03布隆过滤器（Bloom Filter）[[raw/articles/2026/05/布隆过滤器]]⚠️ 内容不完整提示：原文使用 JavaScript 动态加载，仅获取到 35 行简介，核心原理、实现代码、详细分析等内容缺失。一句话总结布隆过滤器的核心能力是：在超大规模的数据集中，仅使用少量内存空间，即可快速判断一个元素是否存在。具备数据隐私性。即，可以在不暴露具体数据的情况下，判断一个元素是否存在。它的核心原理是，不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。核心原理布隆过滤器不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。与哈希集合的对比：| 特性 | 哈希集合 | 布隆过滤器 | |------|---------|------------| | 空间复杂度 | $O(N)$ | 远低于 $O(N)$ | | 数据存储 | 存储实际数据 | 仅存储哈希值（指纹） | | 数据隐私性 | 无（暴露实际数据） | 有（不存储实际数据） | | 查询时间

Interactive Graph