哈希表：从「按值找」到 O(1) 映射¶
覆盖：哈希表的历史渊源、抽象问题、与数组/树/链表的对比、冲突处理、典型模式 适用：Day 2 专题深读，或面试前快速回顾哈希相关技巧 方法：5W1H（为什么学、学什么、何时用、在哪用、谁在用、怎么用）
← 返回 数据结构与算法总览 | 数组专题 | 树专题 | 7 天冲刺 Day 2
读前须知：这篇在讲什么？¶
如果你之前「知道 HashMap、看过 API，还是懵」，通常卡在四个地方：
- 哈希表：听起来像
Map，和「发明」有什么关系？ - 抽象问题：它到底在解决哪一类题？为什么两数之和、分组、计数都爱用它？
- 性能：别的结构也能查，哈希表是不是又费空间又容易冲突，其实很差？
- 和数组：底层是不是就是数组？算不算数组的变型？
下面按 先建立直觉 → 再讲历史与抽象问题 → 再对比其他结构 → 手把手推演 → 最后对照业务 的顺序写。
你可以先只看 §0 直觉 和 §三 里的「手把手推演」，回头再读历史。
今日收工写这里 → 学习打卡 · 笔记 3 条 + 30 秒版（mystar 出题模板 可对照主问/下钻）
§0 先用生活例子建立直觉（不看代码也能懂）¶
0.1 哈希表是什么？¶
把内存想成 一排带门牌号的储物柜（这点和数组一样），但多了一道 「翻译规则」：
你手里拿的是「名字」或「学号」（key），不是「第几格」（下标）
key = "张三" ──哈希函数──→ 门牌号 7 ──→ 打开 7 号柜，取出 value
key = "李四" ──哈希函数──→ 门牌号 2 ──→ 打开 2 号柜
- 数组：你知道「第 i 个」，直接
arr[i]，O(1) - 哈希表：你知道「某个 key」，先算它该去几号柜，再 O(1) 读写
- 核心差别：访问依据是 key（键），不是 下标 index
没有哈希表时：要在 100 万条用户记录里按手机号找人，只能从头扫到尾，最坏 100 万次比较。
0.2 它解决的是哪一类抽象问题？（一句话）¶
关联映射（Associative Mapping）：给定 key，快速得到 value；或快速判断「在不在」「出现过几次」「该归到哪一组」。
在 数据结构与算法总览 的问题分类里，它主要对应：
| 抽象问题 | 典型问法 | 哈希表扮演的角色 |
|---|---|---|
| 键值 / 映射 | key → value | Map<K,V> 本体 |
| 按值查找 | 某数在不在、某字符上次出现在哪 | Set / Map 做 O(1) 查询 |
| 计数 / 频次 | 每个元素出现几次 | Map<T, Integer> 计数 |
| 分组 | 相同特征放一堆 | key 是「特征」，value 是列表 |
| 去重 | 见过没有 | Set |
不是哈希表主场的情况：
- 要 有序遍历、范围查询（第 10 小～第 100 小）→ 用树（BST、B+ 树）
- 要 按下标访问第 k 个、连续区间求和 → 用数组 + 前缀和
- 数据 已排序 且问 两数之和 → 双指针 O(n)，不必哈希
0.3 暴力 vs 哈希：差在哪？（用数字感受）¶
假设有 n = 100 万 条记录，要查 10 万次「这个 key 在不在」：
| 做法 | 单次查找 | 10 万次总代价 | 体感 |
|---|---|---|---|
| 无序数组线性扫 | O(n) | ≈ 10¹¹ 次比较 | 不可用 |
| 排序 + 二分 | O(log n) | ≈ 10⁷ 次比较 | 可用，但插入/重排贵 |
| 哈希表（平均） | O(1) | ≈ 10⁵ 次 | 通常首选 |
所以：在「按 key 查」这类问题上，哈希表不是性能差，而是往往最快——代价是额外空间、无序、最坏情况可能退化。
0.4 它是不是数组的变型？¶
半是半不是，要分两层说：
| 层面 | 说法 |
|---|---|
| 实现（Implementation） | 绝大多数哈希表 底层用数组存桶（bucket）；冲突时桶里再接链表、红黑树或开放寻址 |
| 抽象（Abstraction） | 对外是 关联容器（Associative Container），不是「按下标 0…n-1 顺序访问的序列」 |
┌─────────────────────────────────────┐
│ 哈希表（你用的 Map / dict / HashMap） │
│ 接口：put(key) / get(key) / contains │
└─────────────────────────────────────┘
│
┌─────────────┼─────────────┐
▼ ▼ ▼
哈希函数 数组（桶） 冲突处理
key → index 存槽位 链表 / 开放寻址
一句话：哈希表 借用了数组 O(1) 随机访问的能力，但加了一层 哈希函数 + 冲突策略，解决的是 「按 key 找」 而不是 「按位置 i 找」——所以它是 数组之上的新抽象，不是「另一种数组下标」。
一、哈希表是怎么来的？（展开版）¶
1.1 为什么需要哈希表？（Why）¶
矛盾：现实里大量问题是 按名字、按 ID、按账号查记录（符号表、电话簿、用户会话），而数组天然擅长的是 按下标访问。
| 结构 | 按 key 查找 | 按下标访问 | 插入（平均） |
|---|---|---|---|
| 无序数组 | O(n) | O(1) | O(1) 尾插 |
| 有序数组 + 二分 | O(log n) | O(1) | O(n) 要挪动 |
| 链表 | O(n) | O(n) | O(1) 已知位置 |
| 哈希表 | O(1) 平均 | ❌ 不支持 | O(1) 平均 |
数组/链表的困境：元素一多，「找某个 key」只能遍历比较。
哈希表的突破：用哈希函数把 key 直接映射到槽位，跳过逐个比较。
// 理想情况（无冲突）：
int index = hash("张三") % bucketSize;
bucket[index] = value; // 一次定位
1.2 谁发明的？第一次用在哪里？（What）¶
重要前提：没有像灯泡那样「一个人某天发明哈希表」。是 信息检索需求 → 散列思想 → 语言内置字典 逐步成熟。
第一步：早期「散列」思想——把名字变成数字¶
- 1953 年，IBM 的 H. P. Luhn 在内部备忘录里提出用 哈希编码（hash coding） 加速信息检索（常被引为现代哈希思想源头之一）。
- 1958 年，Arnold Dumey 讨论 开放寻址（open addressing） 处理冲突。
核心想法一致：用 key 算出一个整数，再映射到有限槽位。
第二步：编译器与符号表——第一次大规模「非数值」刚需¶
1960 年代起，高级语言编译器要为每个 变量名、函数名 建 符号表（symbol table）：
源代码里写 userName → 编译器要查：这个名字定义过吗？类型是什么？
变量名是字符串，不是 0、1、2 下标。若每次定义/引用都扫整张表，编译大文件会慢到无法接受。
哈希表成为符号表的标准实现——这是哈希表在工业界最早、最硬的需求之一。
→ 符号表含义见 QA · Q1。
第三步：理论定型——Knuth 与教材¶
Donald Knuth 在《计算机程序设计艺术》里系统分析散列函数、冲突处理、装载因子，把哈希从「工程技巧」变成 可分析的数据结构。
第四步：语言标准库——程序员日常可用的 Map / dict¶
| 时间 | 谁 / 什么 | 贡献 |
|---|---|---|
| 1960s | 编译器符号表 | 按名字 O(1) 查找的工程刚需 |
| 1970s | Knuth / 教材 | 冲突、装载因子、期望复杂度 |
| 1990s+ | Java HashMap、Python dict、C++ unordered_map |
内置关联容器 |
| 今天 | Redis、Memcached、数据库 Hash Join | 分布式缓存、查询优化 |
第一次真正「用哈希表干活」的场景：
| 场景 | 在干什么 | 为什么适合哈希 |
|---|---|---|
| 编译器符号表 | 变量名 → 类型、地址 | 名字是无穷集合，不能当下标 |
| 数据库 Hash Join | 小表建哈希，大表探测 | 等值连接避免嵌套循环 |
| 缓存（Redis） | URL / sessionId → 页面片段 | 读多写多，要 O(1) get/set |
| 密码学校验和 | 文件 → 固定长度摘要 | 快速比对是否篡改（密码学哈希另有安全要求） |
当时没有哈希表会怎样？ 符号表、电话簿式检索、用户会话都要 线性扫描 或 维护复杂索引树；数据上百万后，交互式系统会明显卡顿。
一句话：哈希表 = 散列函数 + 数组槽位 + 冲突处理；最早大规模用于 编译器按名字查符号；今天无处不在于 Map、缓存、Join。
→ 「散列 / 哈希」见 QA · Q2。
1.3 When — 什么时候该用哈希表？¶
✅ 适合哈希表：
- 大量「按 key 查 value」「在不在」「出现几次」
- 需要 O(1) 平均的插入、查找、删除
- 不要求 key 有序、不要求范围查询
- 愿意用额外空间换时间（空间换时间）
❌ 不适合哈希表（考虑排序数组、树、堆等）：
- 需要有序遍历、第 K 小、区间 [a,b] 内所有 key → 树 / 堆
- 需要按下标访问、连续子数组 → 数组
- 内存极度紧张且 n 很小 → 线性扫可能更简单
- 恶意构造 key 导致哈希退化（需安全哈希或树化桶）
1.4 Where — 哈希表在现实中的位置¶
即使你不写算法题，哈希表也无处不在：
- Java HashMap / Python dict / JS Map：语言内置关联容器
- Redis / Memcached：key-value 缓存
- 数据库：Hash Join、哈希聚合
- 编译器 / JVM：符号表、字符串驻留（intern）
- 负载均衡：一致性哈希把请求映射到机器
- Git：对象按 SHA-1（哈希）寻址
- 布隆过滤器：基于哈希的「可能存在」判定
1.5 Who — 谁在用？¶
- 后端：Session 存储、接口幂等 token、限流计数器
- 数据工程：Spark map-side combine、维表 Hash Join
- 前端：用对象/Map 做组件状态索引、路由表
- 安全：密码存储用慢哈希（bcrypt），与数据结构哈希不同但同源思想
- 游戏：实体 ID → 组件、资源路径 → 句柄
二、和其他结构比：解决「同样问题」时性能很差吗？¶
结论先说：不是。 在 「按 key 等值查找 / 插入 / 删除」 这一类问题上，哈希表 平均性能通常是最好的；差的是 别的维度（有序性、最坏情况、空间）。
2.1 同一道题，不同结构怎么选？¶
以 「给定数组，多次问：某数在不在」 为例，n = 10⁶，查询 m = 10⁵ 次：
| 结构 | 预处理 | 单次查询 | 总查询 | 有序？ | 备注 |
|---|---|---|---|---|---|
| 无序数组 | 无 | O(n) | O(nm) | ❌ | 仅 n、m 都极小时 |
| 排序 + 二分 | O(n log n) | O(log n) | O(m log n) | ✅ | 静态数据、要顺序 |
| BST / 平衡树 | O(n log n) 建树 | O(log n) | O(m log n) | ✅ | 要范围查询 |
| 哈希 Set | O(n) 建表 | O(1) 平均 | O(n + m) | ❌ | 动态增删查首选 |
以 LeetCode 1 两数之和（无序数组，找两数之和为 target）：
| 做法 | 时间 | 空间 | 前提 |
|---|---|---|---|
| 暴力两重循环 | O(n²) | O(1) | 无 |
| 排序 + 双指针 | O(n log n) | O(1) | 要下标则还需额外处理 |
| 哈希一边扫一边查 | O(n) | O(n) | 无序数组经典解 |
2.2 哈希表「输」在哪里？¶
| 劣势 | 含义 | 典型替代 |
|---|---|---|
| 无序 | 不能 for (key : map) 得到排序顺序 |
TreeMap、排序数组 |
| 无范围查询 | 不能「所有 > 100 的 key」 | BST、B+ 树 |
| 空间开销 | 桶数组 + 指针，装载因子常 < 1 | 位图、排序紧凑数组 |
| 最坏 O(n) | 冲突极端或恶意 key | 树化桶、安全哈希 |
| 不支持「第 k 个」 | 没有自然下标语义 | 数组、堆 |
2.3 和数组的关系（再强调一次）¶
| 问题类型 | 数组 | 哈希表 |
|---|---|---|
访问 第 i 个元素 |
✅ O(1) | ❌ 无此概念 |
访问 key 为 K 的元素 |
❌ O(n) 扫描 | ✅ O(1) 平均 |
| 连续内存、缓存友好 | ✅ | 桶内可能跳跃 |
| 实现底层 | 就是连续内存 | 常用数组当桶 |
数组 解决的是 「位置 → 值」；哈希表 解决的是 「键 → 值」。底层共享「随机访问槽位」的思想，但 抽象问题不同，不能互相替代。
三、哈希表常见模式 + 手把手推演¶
3.1 四种套路（背表）¶
| 模式 | 存什么 | 典型题 | 一句话 |
|---|---|---|---|
| 补数 / 配对 | 见过什么 → 下标或值 | LC 1 两数之和 | 遍历时查 target - x 在不在 |
| 计数 | 元素 → 次数 | LC 347 前 K 高频 | map.merge(c, 1, Integer::sum) |
| 分组 | 特征 key → 列表 | LC 49 异位词分组 | 排序串或频次串当 key |
| 枚举状态 | 前缀和 / 差值 → 次数 | LC 560 和为 K 子数组 | 问「之前有没有某个前缀和」 |
3.2 手把手推演：两数之和（LeetCode 1）¶
nums = [2, 7, 11, 15], target = 9
暴力：每个 i 再扫 j → O(n²)。
哈希：seen 存「值 → 下标」，走到 nums[i] 时查 target - nums[i] 是否见过。
i=0, nums[0]=2, 需要 7, seen 空 → seen={2:0}
i=1, nums[1]=7, 需要 2, seen 有 2@0 → 答案 [0,1]
每个元素最多进表、查表各一次 → O(n)。
业务对应：支付对账里「两笔流水金额之和是否等于某结算单」；库存里「两件 SKU 价格组合是否等于促销价」。
3.3 手把手推演：字母异位词分组（LeetCode 49）¶
strs = ["eat","tea","tan","ate","nat","bat"]
特征 key：把每个字符串排序 → "eat"、"tea"、"ate" 都是 "aet"。
key "aet" → [eat, tea, ate]
key "ant" → [tan, nat]
key "abt" → [bat]
哈希表把 O(n²) 两两比较是否异位词 变成 O(n · k log k)（k 为串长），分组一次到位。
3.4 手把手推演：和为 K 的子数组（LeetCode 560）¶
数组 [1, 2, 3]，和为 3 的连续子数组个数。
前缀和 + 哈希：prefix[j] - prefix[i] = k ⇔ 之前出现过 prefix[i] = prefix[j] - k。
遍历时维护 prefix 和 map：前缀和 → 出现次数
遇到 prefix - k 在 map 里出现过几次，就加上几种合法起点
业务对应：滑动时间窗口内「净流量是否为 K」的片段计数。
3.5 冲突怎么处理？（知道即可）¶
两种主流方式，面试常问原理：
| 方式 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 链地址法 | 同一桶挂链表（Java 8+ 过长变红黑树） | 简单、删除方便 | 指针额外空间 |
| 开放寻址 | 槽位满了就探下一个空位 | 缓存友好 | 删除、装载因子敏感 |
装载因子（load factor）：元素个数 / 桶数。太高冲突多，太低浪费空间；Java HashMap 默认 0.75 扩容翻倍。
学习打卡 · 笔记 3 条 + 30 秒版¶
何时填： 读完 §0 + §三 后（daily 2606 块 A 交付物写这里）。
出题模板（主问/下钻/过关勾选）： mystar · 哈希表示例
笔记 3 条（各一句，自己能复述）¶
- 解决的是o1点查问题，不适合做范围查询、排序
- key --哈希函数-> index -> arr[index] ，另外加一个冲突处理
- 历史上最先是编译器的符号表第一个采用的
30 秒版（闭卷口述用，≤80 字）¶
哈希表解决 O1增删改查的 问题；和数组的差别是，在实现上多了哈希函数、冲突处理，在逻辑上是多容器的结构；
今天推演的题 §3.2 两数之和还没推演，下次补 seen 表。
填完示例（可删改）：
哈希表解决「按 key 查 value / 在不在」；和数组的差别是访问依据是 key 不是下标；
两数之和；遍历时查 target-x 是否在 seen 里。
过关勾选¶
- 笔记 3 条已写
- 30 秒版能口述（不看稿）
- 出题模板 · 主问+下钻① 能答
- 两数之和：□ 纸上推演 □ AC
日期： 2026-06-03 · 低电量日： ☑ 是（只保本节 + 30 秒版）· 切换收工 见 2606 收工切换
四、刷题时怎么选？（决策树）¶
拿到题
│
├─ 问「某 key / 某值在不在」「出现过几次」？
│ └─ 是 → 【哈希 Set / Map 计数】
│
├─ 问「两数/三数之和」且数组无序？
│ └─ 是 → 【哈希补数】或排序+双指针
│
├─ 问「按某特征分组」？
│ └─ 是 → 【哈希分组】key=特征
│
├─ 问「子数组和为 K」？
│ └─ 是 → 【前缀和 + 哈希】
│
├─ 需要有序 / 第 K 小 / 范围查询？
│ └─ 否 → 别用纯哈希，考虑 【树 / 堆】
│
└─ 需要 O(1) 查 + O(1) 淘汰最久未用？
└─ 【哈希 + 双向链表】LRU
| 技巧 | 一句话 | 典型前提 | 代表题 |
|---|---|---|---|
| 补数哈希 | 遍历时查「还差谁」 | 无序、配对 | 1, 15 |
| 计数哈希 | 频次、最后出现位置 | 统计、窗口 | 347, 3 |
| 分组哈希 | 特征 → 桶 | 异位词、归类 | 49 |
| 前缀和+哈希 | 区间和转化差值 | 子数组和 | 560 |
┌─────────────────────────────────┐
│ 关联映射（按 key 操作） │
└─────────────────────────────────┘
│
┌───────────────────────────┼───────────────────────────┐
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ 哈希表 │ │ 平衡 BST │ │ 排序+二分 │
│ O(1) 均值的 │ │ O(log n) │ │ O(log n) 查 │
│ 等值查找 │ │ 有序+范围 │ │ 静态有序数据 │
└─────────────┘ └─────────────┘ └─────────────┘
│
▼
底层常用【数组】存桶 + 哈希函数 + 冲突链
五、核心模板（Java）¶
import java.util.*;
// ============ 1. 补数模式：两数之和 ============
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) {
return new int[]{seen.get(need), i};
}
seen.put(nums[i], i);
}
return new int[]{};
}
// ============ 2. 分组模式：异位词分组 ============
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
// ============ 3. 计数模式 ============
public int singleNumber(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) {
count.merge(x, 1, Integer::sum);
}
for (Map.Entry<Integer, Integer> e : count.entrySet()) {
if (e.getValue() == 1) return e.getKey();
}
return -1;
}
// ============ 4. 前缀和 + 哈希：和为 K 的子数组 ============
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += prefixCount.getOrDefault(sum - k, 0);
prefixCount.merge(sum, 1, Integer::sum);
}
return ans;
}
// ============ 5. 集合：在不在 / 去重 ============
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue; // 只从序列起点扩展
int len = 1;
while (set.contains(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
六、必刷题目（15 题）¶
| # | 题目 | 难度 | 技巧 | 优先级 |
|---|---|---|---|---|
| 1 | 两数之和 | Easy | 补数哈希 | ⭐⭐⭐ |
| 49 | 字母异位词分组 | Medium | 分组哈希 | ⭐⭐⭐ |
| 128 | 最长连续序列 | Medium | 哈希集合 | ⭐⭐⭐ |
| 560 | 和为K的子数组 | Medium | 前缀和+哈希 | ⭐⭐⭐ |
| 347 | 前K个高频元素 | Medium | 计数+堆 | ⭐⭐⭐ |
| 146 | LRU缓存 | Medium | 哈希+双向链表 | ⭐⭐⭐ |
| 242 | 有效的字母异位词 | Easy | 计数 | ⭐⭐ |
| 219 | 存在重复元素 II | Easy | 哈希记录下标 | ⭐⭐ |
| 380 | O(1) 时间插入、删除和获取随机元素 | Medium | 哈希+动态数组 | ⭐⭐ |
| 454 | 四数相加 II | Medium | 两表哈希 | ⭐⭐ |
| 36 | 有效的数独 | Medium | 行列宫集合 | ⭐⭐ |
| 138 | 随机链表的复制 | Medium | 旧节点→新节点映射 | ⭐⭐ |
| 202 | 快乐数 | Easy | 环检测 Set | ⭐⭐ |
| 349 | 两个数组的交集 | Easy | Set 交集 | ⭐⭐ |
| 705 | 设计哈希集合 | Easy | 理解实现 | ⭐ |
七、小结（背这几句就够）¶
| 主题 | 记住这一句 |
|---|---|
| 为什么有哈希表 | 数组按下标快，但 按 key 找 要 O(n)；散列把 key 映射到槽位 → 平均 O(1) |
| 诞生背景 | 1950s 散列思想 → 1960s 编译器符号表 → Knuth 理论 → 今日 Map/Redis/Hash Join |
| 抽象问题 | 关联映射：查、存、计数、分组、在不在；不是区间、不是有序遍历 |
| 性能 | 在「等值 key」问题上 通常最快；输在无序、最坏冲突、范围查询 |
| 和数组 | 底层常用数组当桶，但接口是 key→value，不是数组变型，是 数组之上的关联容器 |
刷题口诀：
- 无序 + 配对 / 在不在 → 哈希
- 要分组 → 特征当 key
- 子数组和 → 前缀和 + 哈希
- 要顺序 / 范围 → 树，别硬上哈希
若仍懵：回到 §0.2、§0.4 和 §三 3.2，对着 [2,7,11,15] 和 target=9 在纸上画 seen 表的变化。
QA 疑问解答¶
读的过程中：只往 📥 待解答 里 追加，不打断阅读。
读完后：整段复制给 Cursor，一次问完。
答完后：把条目从「待解答」挪到下方，补全 ✅ 纠正（格式同 DDIA 框架 QA）。
📥 待解答（批量问 Cursor）¶
复制本小节 到下一个
---之前 的全部内容即可。
（暂无 — 按下面格式追加）
待解答条目格式（读的时候照抄）：
### Qn：一句话问题（YYYY-MM-DD）
**关联**：§1.2 / 行号 …
**❓ 我的疑问（原话即可）**
- …
**🤔 我目前的理解（可选，错也写）**
- …
（已解答条目从「待解答」移到这里，并补 ✅ 纠正）
Q1：符号表是啥？和「编译器把变量名转成指令」是一回事吗？（2026-06-03）¶
❌ 我的理解（错 / 不完整）
- 符号表 = 编译器已经把变量名 翻译成了机器指令。
✅ 纠正
- 符号表（symbol table） = 编译期的一张 「名字登记册」：
变量名/函数名→{ 类型、作用域、栈偏移或地址、是否已定义… }。 - 编译流水线（极简）：
- 读源码
int userName = 1; - 查/写符号表：
userName是int、在哪一层作用域、占哪块栈 - 再 生成汇编/机器码：
mov …（这一步才是「转成指令」） - 所以：符号表解决 「这个名字是谁、合法吗」；指令生成解决 「在 CPU 上怎么跑」。哈希表加速的是 第 2 步按名字查表，不是代替第 3 步。
- 类比：电话簿（符号表）≠ 你拨出去的那通电话（机器码）。
Q2：「散列」和「哈希」是啥意思？为啥这么叫？（2026-06-03）¶
关联：§1.2 第一步 / 一句话 · §1.2 末尾
❌ 我的理解（错 / 不完整）
- 把 key 放进「有限空间」= 应该很 集中；不理解为啥叫 散列。
✅ 纠正
| 词 | 英文 | 本意 |
|---|---|---|
| 散列 | hash（动词） | 把 任意长度 key「搅碎」成 固定范围的整数（像把食材切成碎块 hash 成肉馅） |
| 哈希 | hash | 同一概念的 音译（港台常译哈希，大陆教材两词混用） |
| 哈希表 | hash table | 用上面算出的下标，在 桶数组 里存 value |
- 「散」在哪：算出来的下标在
0 … bucketSize-1里 伪随机分布，不同 key 散开 到不同槽，不是按字典序紧挨着——所以中文叫 散列（分散到各槽），不是「聚集」。 - 「有限空间」：桶只有
m个；n个 key 要 映射进 m 格，必然 多对一（冲突）→ 才要链表/开放寻址。 - 一句话：散列/哈希 = 把 key 打散成槽位编号；哈希表 = 散列 + 数组桶 + 冲突处理。