www.876873.xyz

问题： 哈希表由： 数组+链表 组成，但是一个极其致命的工程绝境：“如果一开始建的数组太小，后来表数量暴增，哈希表需要扩容怎么办？难道要把几十 GB 的哈希表锁死，重新申请一块更大的连续内存，然后把几百万个元素一个一个搬过去吗？

如果真这么干，数据库瞬间就会假死几分钟！

为了破解这个物理绝境，PG 内核架构师掏出了终极武器——动态哈希表（Dynamic Hash Table，源码中的 dynahash.c）。我们现在就用严密的逻辑，把这座可以“无限无感扩容”的 3 层立体城堡的物理结构推导出来！

---

第一步破局：抛弃“大平层”，构建“三级立体寻址”

在真实的内存条里，要在高并发下寻找一块连续的、巨大的空闲内存是极其困难的（内存碎片化）。所以，PG 的架构师把哈希表的骨架，从“一个巨大的连续数组”，切碎成了**“目录 $\rightarrow$ 段 $\rightarrow$ 桶”**的三级立体结构。

1. 顶级指挥枢纽：哈希控制块（HTAB）

物理形态：它是整个哈希表的总管家，是一个结构体。

核心内容：它记录了这个哈希表用的是什么 Hash 函数、当前总共有多少个元素、以及一个极其关键的指针——目录指针（Directory Pointer）。

2. 第一级寻址：目录数组（Directory）

物理形态：这是一个非常小的、定长的指针数组（通常有 256 个格子）。

物理推演：它的每一个格子里，不存数据，也不存链表头！它里面存的，是通往下一级“段（Segment）”的内存基地址。有了它，哈希表就不需要一整块几十 GB 的连续内存了，它可以把数据分散在内存的各个角落。

3. 第二级寻址：数据段（Segment）

物理形态：目录数组指引我们来到了“段”。一个段，本质上是一块中等大小的连续内存块。

物理推演：段的作用是“批发空间”。当系统发现空间不够时，不需要动以前的数据，只需要向操作系统再申请一块新的“段”，然后把这个新段的地址登记在“目录数组”的空闲格子里就行了。这就是 “无感极速扩容” 的底层奥秘！

4. 第三级寻址：哈希桶（Bucket / 哈希槽）

物理形态：在一个“段（Segment）”里面，密密麻麻地划分了成千上万个“桶”。

物理推演：这就是我们在前面推导过的、真正发生“哈希碰撞”的地方！桶里面存的依然不是数据实体，而是一条链表的头指针（Head Pointer）。