哈希冲突

哈希函数

type: concept tags: [哈希表, 数据结构, 哈希函数] created: 2026-05-04 updated: 2026-05-04哈希函数定义哈希函数是将任意长度的输入（键）映射为固定长度输出（哈希值）的函数，是哈希表的核心组件。理想的哈希函数应满足：计算速度快哈希值分布均匀（减少冲突）相同的键必须产生相同的哈希值常见哈希函数除法哈希法：h(k) = k mod m（m 为哈希表大小）乘法哈希法：h(k) = floor(m * (kA mod 1))（A 为常数）全域哈希：随机选择哈希函数族中的函数，避免最坏情况相关概念[[哈希表]]：哈希函数的应用场景[[哈希冲突]]：哈希函数不均匀会导致冲突[[拉链法]]：冲突解决方法[[线性探查法]]：另一种冲突解决方法

哈希表

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-04 updated: 2026-05-04开放寻址法定义开放寻址法是一种哈希冲突解决方法：所有元素都存储在哈希表数组本身中，冲突时按照某种探测序列寻找下一个可用的空位。与链地址法不同，不需要额外的链表结构。常见探测方法线性探查法：冲突时依次检查下一个位置（d_i = i）→ [[线性探查法]]二次探查法：冲突时检查 d_i = i² 的位置双重哈希法：使用第二个哈希函数计算步长优缺点优点：所有数据在连续数组中，缓存友好缺点：存在聚集现象（线性探查尤其明显），删除操作复杂相关概念[[哈希表]]：应用场景[[哈希冲突]]：要解决的问题[[线性探查法]]：最常用的开放寻址法[[拉链法]]：对比方法（链地址法）

拉链法

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.

负载因子

type: concept tags: [哈希表, 负载因子, 性能指标, 哈希冲突] created: 2026-05-06 updated: 2026-05-06负载因子（Load Factor）负载因子衡量哈希表的装满程度，是决定哈希冲突概率和扩容时机的关键指标。定义负载因子（Load Factor）是哈希表中已存储元素数量与数组容量的比值：负载因子 = 已存储元素数量 / 数组容量 λ = n / m其中：n = 已存储的元素数量m = 数组的容量（桶的数量）核心特性| 特性 | 说明 | |------|------| | 取值范围 | λ ≥ 0，通常在实际使用中 λ ≤ 1（开放寻址法）或 λ 可 > 1（拉链法） | | 冲突概率

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 | | 数组大小