www.876873.xyz

这是一个直接触及计算机科学（CS）数据结构灵魂的硬核追问！

在人类的直觉里，找东西最快的方法是“按顺序找”或者“翻目录”。但在多核 CPU 面对每秒几十万次极速并发的内存寻址时，任何带有“遍历”性质的动作都是不可原谅的物理拖累。

为了实现绝对的 $O(1)$ 极速寻址，内核架构师没有选择普通的数组（Array），也没有选择树（Tree），而是祭出了计算机科学中最伟大的空间换时间魔法——哈希表（Hash Table）。

我们现在彻底抛开晦涩的代码，完全按照“如果我是内核架构师，遇到性能绝境时我会怎么设计”的物理逻辑，把哈希表的真实内存结构一步步推导出来！

---

第一步绝境：寻找 $O(1)$ 的物理载体（为什么不用纯数组？）

【架构师的痛点】

假设现在内存里有 10 万个 LOCK 结构体，分别代表 10 万张不同的表。

来了一个业务请求：“我要给 OID 为 16384 的表加锁”。

CPU 怎么瞬间找到代表 16384 的那个结构体？

1. 链表（Linked List）：从头跑到尾，一个个问“你是 16384 吗？”。时间复杂度 $O(N)$，太慢，直接毙掉。
2. 纯数组（Array）：数组拥有完美的 $O(1)$ 物理特性（通过首地址 + 偏移量直接定位）。
   • 致命缺陷：如果用 OID 作为数组下标，我们需要建一个超级巨大的数组（比如下标从 0 到 42 亿）。但这 42 亿个格子里，绝大多数是空的，极其浪费极其珍贵的内存！

推导结论：我们需要数组的 $O(1)$ 极速，但不能容忍数组的无限巨大。

---

第二步破局：数学绞肉机（Hash Function）的诞生

既然不能建 42 亿个格子，那我们只在内存里建 1024 个格子（桶 Bucket） 组成的固定数组。

【降维映射】

架构师引入了一个极其暴力的数学函数（Hash Function）。这个函数就像一台“数字绞肉机”。

• 它的输入：是任意长度、任意乱序的数据（比如表的 OID 16384，或者字符串 “users_table”）。
• 它的输出：经过复杂的位移和异或运算后，必定输出一个 0 到 1023 之间的绝对固定整数。

【物理运转】

1. 进程拿着表的身份牌 LOCKTAG（里面写着 16384）。
2. 扔进 Hash 绞肉机：Hash(16384)。
3. 瞬间吐出一个数字：5。
4. CPU 直接访问数组的第 5 号格子（Bucket 5）。寻址结束，耗时 1 纳秒！

---

第三步灾难：不可避免的物理车祸（Hash Collision 哈希冲突）

数学规律决定了（鸽巢原理），把无限多的表 OID，硬塞进只有 1024 个格子的数组里，绝对会发生重复！

【车祸现场】

1. 业务 A 查表 16384，Hash(16384) = 5，它走向了第 5 号格子。
2. 业务 B 查表 99999，经过 Hash 绞肉机计算，极其倒霉地得出 Hash(99999) = 5。它也走向了第 5 号格子！

这就是大名鼎鼎的哈希冲突（Hash Collision）。如果两个表抢同一个格子，难道把前一个人的锁结构体给覆盖掉（写花）吗？绝对不行！

---

第四步终极形态：数组 + 链表（拉链法 Separate Chaining）

为了完美解决冲突，哈希表的终极内存物理结构诞生了：它根本不是用来直接存数据的，它是一个“存指针的指针柜”！

【哈希表的真实结构图纸】

1. 主干（数组/桶数组）：内存中一段连续的空间（比如 1024 个格子）。但格子里不存哪怕一个 LOCK 结构体！格子里存的，只有 8 个字节的内存地址指针。
2. 分支（链表）：当找到具体格子后，顺着指针拉出来的一条链表。

【动态推演：哈希表是如何化解车祸的】

1. 业务 A 带着表 16384 来到第 5 号格子。
   • 格子里是指针 NULL（空）。
   • 业务 A 在别处的内存 malloc 了一个 LOCK 结构体（代表表 16384），然后把第 5 号格子的指针指向自己。
2. 业务 B 带着表 99999 也来到了第 5 号格子（发生冲突！）。
   • 业务 B 发现格子不是空的，顺着指针看到了业务 A 的 LOCK 结构体。
   • 业务 B 问：“你是表 99999 吗？” A 回答：“不是，我是 16384。”
   • 破局：业务 B 自己也在别处建了一个 LOCK 结构体（代表表 99999），然后用一根链表指针（next），把自己挂在业务 A 的屁股后面！

---

架构师的全局收网（PostgreSQL 的终极哈希网）

现在，你脑海里的 LockMethodLockHash 不再是一个抽象的名词了。它是一座气势恢宏的微观立交桥：

1. 横向的骨架（数组）：提供了 $O(1)$ 的极速降落能力。10 万个进程通过 Hash 绞肉机，瞬间被精准分发到不同的槽位里，打散了全局冲突。
2. 纵向的藤蔓（链表）：在同一个槽位里，用链表把那些因为“哈希冲突”而挤在一起的、不同表的 LOCK 结构体串联起来。
3. 顶层的保安（LWLock 分区锁）：为了防止多核 CPU 同时在一个槽位里修改链表指针导致断裂（写花），架构师把这几万个槽位切分成 16 个区，每个区派一把 LWLock 死死守住。

这就是为什么数据库能在毫秒级时间内，从几百万把锁中精准定位到你要的那一把的终极物理奥秘。数组的极速 + 链表的无限延伸 + 绞肉机的均匀打散 = 工业级哈希表！