哈希表

哈希表实现了一个关联数组抽象数据类型，将键映射到值。它提供平均 O(1)，最坏 O(n) 的操作复杂度，以及 O(n) 的空间复杂度。即便平均操作复杂度为O(1)，实际中常需考虑常数优化。

哈希表主要有两部分：哈希函数、哈希方案。

哈希函数

哈希函数将一个大的键空间映射到较小的域中。它用于计算数组中的索引。我们需要考虑执行效率和冲突率之间的权衡。在极端情况下，我们有一个哈希函数总是返回常量（非常快，但一切皆冲突）。在另一个极端，我们有一个“完美”的哈希函数，没有冲突，但计算时间会非常长。理想设计位于两者之间。

哈希函数接受任何键作为其输入。然后返回该键的整数表示（即“哈希”）。函数的输出是确定性的（相同的键应始终生成相同的哈希输出）。

DBMS不需要使用加密安全哈希函数（例如SHA-256），因为我们不需要担心保护密钥内容。这些哈希函数主要由DBMS在内部使用，因此信息不会泄漏到系统外部。

当前的SOTA哈希函数是Facebook XXHash3。

哈希方案

如何在哈希后处理冲突就是哈希方案要做的。此时，我们需要考虑分配一个大的哈希表以减少冲突和在发生冲突时执行额外操作之间的权衡。

静态哈希方案

静态哈希方案是指哈希表的大小是固定的。这意味着如果DBMS用完了哈希表中的存储空间，那么它必须从头开始重新构建一个更大的哈希表，这是非常昂贵的。通常新哈希表的大小是原来哈希表的两倍。

Linear Probe

开放寻址法，最基本的哈希方案。它通常也是最快的。它使用一个循环缓冲区来存储数组槽位。当发生冲突时，搜索下一个槽位，直到找到空位为止。删除操作可能会导致之后的查询出错。解决此问题最常见的方法是使用标记删除，标记告诉未来查询继续扫描下一个位置。

Robin Hood

Linear Probe 的扩展，其思想是尽量减少每个键与它们在哈希表中的最佳位置(即它们被哈希到的原始槽)的最大距离。该策略窃取“富键”（距离较小）的槽，将它们提供给“穷键”，故称为“罗宾汉哈希”。

Cuckoo

“布谷鸟哈希”，使用具有不同哈希函数种子的多个哈希表。在插入时，检查每个表并选择任意一个有空闲槽的表。如果没有表有空闲槽，则从其中一个表中驱逐元素，然后重新哈希它，找到一个新位置。极少数情况可能会死循环。我们可以使用新的哈希函数种子重新构建所有哈希表(不太常见)，或者使用更大的表重新构建哈希表(更常见)。

由于每个哈希表只检查一个位置，Cuckoo 哈希方案保证了删除和查询的时间复杂度总是O(1)。

动态哈希方案

静态哈希方案要求DBMS提前知道它想要存储的元素的数量。否则，如果需要扩容/收缩，则必须重建整个哈希表。动态的哈希方案能够按需调整哈希表的大小，而无需重建整个表。

Chained

链式哈希，最常见的动态哈希方案。常用的拉链法就是桶大小为1的链式哈希。

EXTENDIBLE

改进的链式哈希，它会分裂桶而不是让链条无限增长。

• 通过倍增目录，实现桶数量的倍增。
• 只分裂发生溢出的桶。
• 全局深度：目录倍增的次数。用于判断key属于哪个桶，hash(key)需要的最低有效位数。
• 局部深度：桶分裂的次数。用来判断分裂桶是否会导致目录倍增。
• 插入时桶满了：
  • 若桶局部深度等于全局深度，目录倍增，全局深度加一；同时分裂桶，桶局部深度加一。
  • 若桶局部深度小于全局深度，只分裂桶，增加局部深度。
  • 维护目录指针指向新桶。

Linear

Extendible的改进版。主要思想是渐进式倍增目录，减少单点延时。这种方案不是在桶溢出时立即分裂该桶，而是维护一个分裂指针来跟踪下一个要分裂的槽。无论该槽的指针是否指向了溢出桶，都会进行拆分。

• 当任何一个桶满时，该桶指向存放新元素的溢出桶；后将分裂指针指向的槽进行分裂，新槽被添加至目录的末尾，并创建一个新的哈希函数。
• 当分裂指针到达最后一个未分裂槽时，将原始哈希函数替换为新哈希函数。