开放寻址法

哈希表

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-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: [哈希表, 拉链法, 链地址法, 数据结构, 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 | | 数组大小