哈希函数

哈希冲突

type: concept tags: [哈希表, 数据结构, 哈希冲突] created: 2026-05-04 updated: 2026-05-04哈希冲突定义哈希冲突是指两个不同的键通过哈希函数计算后得到相同的哈希值的现象。由于哈希表的大小有限，而键的空间可能无限，冲突是不可避免的。冲突解决方法链地址法（拉链法）每个哈希桶维护一个链表，冲突的元素追加到链表末尾 → [[拉链法]]开放寻址法冲突时按照某种探测序列寻找下一个空位，包括：线性探查法 → [[线性探查法]]二次探查法双重哈希法相关概念[[哈希表]]：冲突发生的场景[[哈希函数]]：均匀的哈希函数可减少冲突负载因子：负载因子过高会加剧冲突

哈希表

type: concept tags:哈希表数据结构HashMap键值对哈希函数 created: 2026-05-03 updated: 2026-05-03哈希表（Hash Table）定义哈希表（Hash Table，也称散列表）是一种基于哈希函数实现的数据结构，能够在平均 O(1) 时间内完成插入、删除和查找操作。核心思想：通过哈希函数将键（key）映射到数组的某个索引位置，直接访问该位置获取数据。基本原理键值对 (key, value) │ ▼ 哈希函数 hash(key) → 数组索引 index │ ▼ 数组 table[index] = value伪码表示put(key, value): index = hash(key)

哈希集合

type: concept tags:数据结构哈希表集合 created: 2026-05-06 updated: 2026-05-06哈希集合（HashSet）基于哈希表实现的集合数据结构，提供 O(1) 平均时间复杂度的插入、删除和查找操作。定义哈希集合（HashSet） 是一种基于哈希表实现的集合数据结构，它存储不重复的元素。与哈希表（HashMap）存储键值对不同，哈希集合只存储元素本身。核心特性| 特性 | 说明 | |------|------| | 元素唯一性 | 集合中不包含重复元素 | | 无序性 | 元素存储顺序不保证（除非使用 LinkedHashSet） | | 允许 null | 大多数实现允许存储一个 null 元素 | | 基于哈希表 | 底层使用哈希表实现，依赖 hashCode() 和 equals() |基本原理哈希集合的工作原理与哈希表类似：调用元素的 hashCode() 方法计算哈希值根据哈希值确定元素在底层数组中的存储位置如果该位置已有元素（哈希冲突），使用链表或红黑树解决冲突插入前检查元素是否已存在（使用 equals() 方法比较）插入元素 e: 1. hash

布隆过滤器

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） | 不存在（如果查询说不存在，就一定不存在） | |

拉链法

type: concept tags:哈希表数据结构冲突解决拉链法链地址法 created: 2026-05-03 updated: 2026-05-03拉链法（链地址法）定义拉链法（Separate Chaining，也称链地址法）是解决哈希冲突的一种方法。其核心思想是：哈希表的每个数组位置不直接存储键值对，而是存储一个链表（或其他容器）。所有哈希到同一索引的键值对都放入该位置的链表中。基本原理索引: 0 1 2 3 4

线性探查法

type: concept tags:哈希表数据结构开放寻址法哈希冲突解决算法原理 created: 2026-05-03 updated: 2026-05-09线性探查法（Linear Probing）定义线性探查法（Linear Probing）是一种开放寻址（Open Addressing）的哈希冲突解决方法。核心思想：当发生哈希冲突时，从冲突位置开始线性向后探查（index+1, +2, +3, ...），直到找到空位或目标 key。基本原理冲突处理流程插入键值对 (key, value): 1. 计算初始索引：index = hash(key) 2. 若 table[index] 为空 → 直接插入 3. 若 table[index] 不为空： - 若 key 相同 → 更新值 - 若 key 不同 → index++，继续探查 4.

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: [哈希表, HashMap, 数据结构, Java, 哈希函数, 负载因子, 哈希冲突, 拉链法, 线性探查法] created: 2026-05-03 updated: 2026-05-03哈希表基础[[raw/articles/2026/05/哈希表基础]]核心要点1. 哈希表 vs MapMap 是接口，仅声明操作方法（get/put/remove），未指定实现方式HashMap 是 Map 的一种实现，底层使用哈希表，增删查改复杂度 O(1)其他实现如 TreeMap（红黑树，O(logN)）、LinkedHashMap（保持插入顺序）不能假设所有键值对操作都是 O(1)，需看具体实现的数据结构2. 哈希表基本原理哈希表 = 加强版数组核心机制：通过哈希函数将 key 映射到数组索引，实现 O(1) 访问伪码逻辑：put(key, value): table[hash(key)] = value get(key): return table[hash(key)] remove(key): table[hash(key)] = null3. 哈希函数设计作用：将任意类型

哈希表链地址法

type: summary tags: [哈希表, 拉链法, 链地址法, 数据结构, Java, 哈希冲突, 开放寻址法] created: 2026-05-03 updated: 2026-05-03哈希表链地址法（拉链法）实现[[raw/articles/2026/05/哈希表链地址法]]⚠️ 注意：原文使用 JavaScript 动态加载内容，未能获取完整正文（仅获取到29行简介）。以下为基于现有内容的摘要，待补充完整内容。核心要点前置知识本文建立于以下基础知识之上：[[哈希表基础]][[链表]]哈希冲突解决方法回顾文章回顾了两种主流哈希冲突解决方法：| 方法 | 别名 | 原理 | |------|------|------| | 拉链法 | 链地址法 | 数组每个位置存储链表，冲突元素追加到链表 | | 开放寻址法 | 线性探查法 | 冲突时往后找空位（index+1, +2, ...） |![[images/hash-collision.jpeg]]拉链法简化版实现假设为了便于理解，文章采用以下简化：类型限制：仅支持 key 类型为 int，value 类型为 int，key 不存在时返回

线性探查法的两个难点

type: summary tags: [哈希表, 线性探查法, 开放寻址法, 数据结构, 算法原理, 哈希冲突] created: 2026-05-03 updated: 2026-05-03线性探查法的两个难点[[raw/articles/2026/05/线性探查法的两个难点]]⚠️ 注意：原文使用 JavaScript 动态加载内容，未能获取完整正文（仅获取到"简化场景"部分，缺少"两个难点"的核心内容）。以下为基于现有内容的摘要，待补充完整内容。核心要点（侧重算法原理理解）前置知识本文建立于以下基础知识之上：[[哈希表基础]]哈希冲突解决方法对比| 方法 | 别名 | 基本原理 | 特点 | |------|------|---------|------| | 拉链法 | 链地址法 | 数组每个位置存储链表，冲突元素追加到链表 | 实现简单，每个桶独立 | | 线性探查法 | 开放寻址法 | 冲突时往后找空位（index+1, +2, ...） | 所有元素存在数组中，缓存友好 |![[images/hash-collision.jpeg]]线性探查法基本原理核心思想：当发生哈希冲突时，从冲突位置开始，线性向后探查，直到找到：相同的 key（更新值）空位（插入新键值对）到达数组末尾（探查失败，需特殊处理）算法特性：所有数据存储在同一个数组中（不像拉链法需要额外链表）探查序列：hash(key),

线性探测哈希表实现

type: summary tags: [哈希表, 线性探测, 代码实现, 数据结构] created: 2026-05-03 updated: 2026-05-03线性探测哈希表实现[[raw/articles/2026/05/线性探测哈希表实现]][!warning] 内容不完整 本文原始页面使用 JavaScript 动态加载，仅获取到静态部分（19行）。核心代码实现部分缺失。文章要点（基于静态内容）本文目标提供线性探查法（Linear Probing）的完整代码实现，包括：简化实现（帮助理解增删查改过程）完整实现（生产级代码）简化实现的假设为聚焦核心逻辑，作者做了以下简化：| 简化项 | 说明 | |--------|------| | key 类型 | 仅支持 int | | value 类型 | 仅支持 int，key 不存在时返回 -1 | | 哈希函数 | 简单取模 hash(key) = key % table.length | | 数组大小