基础数据结构

哈希表的原理与实现

它做的事：把 key 变成下标

数组按下标访问是 O(1)。哈希表想让任意 key 也享受这个待遇， 办法是找一个函数把 key 映射成下标：

下标 = hash(key) % 桶数组长度

于是查找、插入、删除都变成「算一次 hash，直接访问那个格子」—— 平均 O(1)。

⭐ 所以哈希表的性能完全取决于两件事：hash 算得快不快， 以及不同的 key 会不会撞到同一个格子。

哈希冲突：两种解法

不同的 key 算出同一个下标，叫哈希冲突。这是必然的 —— key 的空间通常远大于桶的数量（鸽笼原理）。

拉链法：每个桶挂一条链表，冲突的元素串起来。

桶[0] → nodeA → nodeD
桶[1] → nodeB
桶[2] → (空)
桶[3] → nodeC

开放寻址（线性探查）：撞了就往后找下一个空位。

拉链法 开放寻址
冲突处理 挂链上 顺延到下一个空桶
删除 简单 麻烦（要留墓碑标记，否则查找链会断）
内存 每个节点多一个指针 无额外指针，但要求负载因子低
缓存友好 差（链表节点分散） 好（都在连续数组里）

📌 Java 的 HashMap 用拉链法（链太长会转红黑树）， Python 的 dict 用开放寻址。面试问「怎么解决冲突」，答这两个名字 + 各自的删除代价。

负载因子与扩容

负载因子 = 元素个数 / 桶数量。它越大，冲突越频繁，O(1) 越名不副实。

所以哈希表会在负载因子超过阈值时扩容（Java 默认 0.75）： 申请一个更大的桶数组，把所有元素重新 hash 一遍搬过去。

🚨 注意是「重新 hash」而不是「照搬」——因为下标是 hash % 桶数， 桶数变了，每个元素该去的格子也变了。

⚠️ 单次扩容是 O(n)，但和动态数组一样按倍数扩， 所以均摊仍是 O(1)。这也解释了为什么哈希表的最坏单次操作是 O(n) —— 面试里问「哈希表一定是 O(1) 吗」，这是标准答案的一半； 另一半是「所有 key 都冲突时退化到 O(n)」。

🚨 但**「退化到 O(n)」这半句要看语言**，别对着 Java 说。从 JDK 里把常量读出来：

HashMap.DEFAULT_LOAD_FACTOR   = 0.75      ← 扩容阈值
HashMap.TREEIFY_THRESHOLD     = 8         ← 单链长度到 8 就考虑转红黑树
HashMap.MIN_TREEIFY_CAPACITY  = 64        ← 但桶数组不足 64 时改为扩容
HashMap.UNTREEIFY_THRESHOLD   = 6         ← 缩回 6 以下再退回链表

⭐ 所以 Java 8+ 全冲突时是 O(log n) 不是 O(n)，而且要两个条件同时满足才转树： 链长 ≥ 8 且 桶数组 ≥ 64。桶少的时候它优先扩容，因为那种冲突多半是桶太少导致的。 📌 本篇下面手写的那个版本没有转树，它才是真的 O(n) —— 说「退化到 O(n)」时 先说清楚在说哪个实现。

🚨 遍历顺序：一条被广泛误传的说法

「哈希表的遍历顺序不确定，不要依赖它」—— 这句话在 Java、C++ 里对， 但在 JavaScript 里不完全对，而且不对的方式很微妙。

实测三种容器：

const m = new Map();  [3,1,2].forEach(k => m.set(k, k));  m.set('b',1);  m.set('a',1);
const o = {};         [3,1,2].forEach(k => o[k] = k);     o.b = 1;       o.a = 1;
const s = new Set([3, 1, 2]);
Map      插入 3,1,2,b,a  →  3,1,2,b,a     ✅ 严格保持插入顺序
Object   插入 3,1,2,b,a  →  1,2,3,b,a     🚨 数字键被重排了！
Set      插入 3,1,2      →  3,1,2         ✅ 保持插入顺序

⭐ Map 和 Set 的插入顺序是写进 ECMAScript 规范的，可以放心依赖。

同一组数据在另外两门语言里实跑，结论比「JS 是特例」复杂：

JS     Map      3,1,2,b,a      ✅ 保序（规范保证）
JS     Set      3,1,2          ✅ 保序（规范保证）
JS     Object   1,2,3,b,a      🚨 整数键被重排

Java   HashMap        1,a,2,b,3   🚨 彻底乱序
Java   LinkedHashMap  3,1,2,b,a   ✅ 保序

Python dict     3,1,2,b,a      ✅ 保序（3.7 起是语言保证）
Python set      1,2,3          🚨 不保序

🚨 注意 Java 的 HashMap 用拉链法却乱序，Python 的 dict 用开放寻址却保序 —— 冲突解法和保不保序是两回事，别从「它用什么解决冲突」推断遍历顺序。 （Python 的 dict 靠一个额外的紧凑条目数组记录插入次序，与寻址方式无关。）

⭐ 真正的分界不是语言，是容器：同一门语言里 Map/LinkedHashMap/dict 保序， Object/HashMap/set 不保序。查文档看你手上那个容器怎么说，别记「某某语言不保证」。

🚨 但普通对象不是。 它的规则是： 「整数样式」的键先按数值升序排，然后才是字符串键按插入顺序排。

const o = {}; o.z = 1; o[10] = 1; o.a = 1; o[2] = 1;
Object.keys(o)   // → ['2', '10', 'z', 'a']

⚠️ 而「整数样式」的判据比看上去窄 —— 规范认的是数组索引（0 ~ 2³²-2 的规范整数串）。 以下这些都不算，一律当普通字符串键、排在数值区后面并保持插入顺序：

const t = {};
t.z = 1; t[-1] = 1; t[1.5] = 1; t['4294967295'] = 1; t['4294967294'] = 1; t[10] = 1; t[2] = 1; t['01'] = 1;

Object.keys(t)
// → ['2', '10', '4294967294',   'z', '-1', '1.5', '4294967295', '01']
//    └──── 数值区，升序 ────┘   └──────── 字符串区，插入顺序 ────────┘

⭐ 负数、小数、带前导零的 '01'、以及恰好是 2³²-1 的那一个都掉进字符串区； 2³²-2 还在数值区。所以「整数键会被重排」这句话对负数下标是不成立的。

⚠️ 这个坑在算法题里真实存在：拿 {} 当计数器统计数字出现次数， 然后遍历输出 —— 你以为是插入顺序，实际被排序了。

📌 有个说法是「大多数时候碰巧也对」。要分清「对」指的是什么： 很多题不关心顺序，所以能过 —— 但顺序本身几乎从来不对。 随机数字序列灌进 {} 再遍历，与「首次出现顺序」不一致的比例：

元素个数    值域 0~9   值域 0~99   值域 0~999
     3        73.3%       82.7%       83.2%
     5        93.7%       98.8%       99.1%
    10        99.7%      100.0%      100.0%
    20       100.0%      100.0%      100.0%

🚨 三个元素就已经七八成不对，十个元素基本必错。 同样的场景换成 Map， 20000 组一次都没错过。所以别指望「小数据先蒙混过去」——它一开始就是错的， 只是题目没问而已。

📌 结论很简单：算法题里一律用 Map，不要用 {} 当哈希表。 除了顺序保证，Map 还能用任意类型当 key（对象、数组）， 而对象的 key 会被强制转成字符串 —— o[1] 和 o['1'] 是同一个键。

手写一个最简哈希表

面试偶尔会要求手写。拉链法版本二十行：

class SimpleHashMap {
  constructor(buckets = 16) {
    this.buckets = Array.from({ length: buckets }, () => []);
    this.count = 0;
  }

  _hash(key) {
    const s = String(key);
    let h = 0;
    for (let i = 0; i < s.length; i++) {
      h = (h * 31 + s.charCodeAt(i)) | 0;   // 31 是常用的乘子
    }
    return ((h % this.buckets.length) + this.buckets.length) % this.buckets.length;
  }

  set(key, val) {
    const b = this.buckets[this._hash(key)];
    const hit = b.find((e) => e[0] === key);
    if (hit) { hit[1] = val; return; }
    b.push([key, val]);
    this.count++;
  }

  get(key) {
    const hit = this.buckets[this._hash(key)].find((e) => e[0] === key);
    return hit ? hit[1] : undefined;
  }
}

🚨 _hash 里那个双取模不是多余的。h = (h * 31 + c) | 0 用 | 0 截成 32 位有符号整数，会产生负数；负数取余在 JS 里仍是负数 （同环形数组那条）， 直接拿去索引会得到 undefined。

🚨 「短 key 没事、长 key 才崩」——不是这样，它是一道悬崖

这个错法的暴露规律不是渐变的。穷举全部小写串（不是抽样）：

key 长度      1       2       3       4       5       6       7       8      20
负数比例   0.00%   0.00%   0.00%   0.00%   0.00%  100.0%   52.5%   49.3%   50.1%
           └──── 穷举，一个负数都没有 ────┘    └── 抽样 20000 个/档 ──┘

⭐ 长度 5 是 0%，长度 6 是 100%。 中间没有过渡。而且这个数能算出来：

6 个小写字母的 h 取值区间
  最小 "aaaaaa" = 2,869,595,232
  最大 "zzzzzz" = 3,609,181,632
  2^31          = 2,147,483,648     2^32 = 4,294,967,296

整个区间夹在 2^31 与 2^32 之间  →  | 0 之后无一例外全变负

长度 5 的最大值 "zzzzz" = 116,425,210  <  2^31  →  必为正

🚨 六个字母根本不算「长 key」。 "orange"、"string"、"banana" 全中：

"orange"  h = -1008851410      "apple"  h =  93029210
"string"  h =  -891985903      "hello"  h =  99162322
"banana"  h = -1396355227

⚠️ 所以真实的盲区窄得多：只有 1~5 个字符的 key 才安全。 拿 "a"、"key"、"abcd" 自测会全绿，换成任何一个六字母单词立刻 undefined。 把 key 长度混起来（1~10）测，约 27.9% 会落到负下标。

📌 交叉验证：这个 _hash 就是 Java 的 String.hashCode。同样五个词在 JDK 17 里跑， "orange".hashCode() 也是 -1008851410，五个值逐位相同 —— 说明上面这套「六字母必为负」在 Java 里同样成立，只是 Java 的下标计算做了处理。

📌 乘子为什么取 31

历史惯例（Java 的 String.hashCode 就用它）：它是质数， 且 31 * h 可以被编译器优化成 (h << 5) - h。

⚠️ 但这个改写在 JavaScript 里不能裸写。<< 先把结果截成 32 位， 而 - 是双精度浮点运算，两者从 h = 2²⁶ 开始就分家：

h = 67,108,864 (2^26)   裸写 (h<<5)-h = -2214592512    (31*h)|0 = 2080374784   🚨
h = 2,147,483,647       裸写 (h<<5)-h = -2147483679    (31*h)|0 = 2147483617   🚨

⭐ 包进 | 0 就恒等了：((h << 5) - h + c) | 0 与 (h * 31 + c) | 0 在 20 万组随机 int32 上完全一致。改写本身没错，错的是漏掉那个 | 0。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。