15445-07-HashTables

Mindmap

可扩展哈希和线性哈希详解

一、数据结构

数据库管理系统（DBMS）在系统的不同部分使用多种数据结构。常见示例包括：

• 内部元数据：用于跟踪数据库信息及系统状态。
  例如：页表（Page Tables）、页目录（Page Directories）

• 核心数据存储：数据结构存储数据库中的实际元组（记录）。

• 临时数据结构：DBMS 在查询执行时可以动态构建临时结构以加速处理。
  例如：用于连接操作的哈希表。

• 表索引：辅助数据结构，用于高效定位特定元组。

实现这些数据结构时，需要考虑两项关键设计决策：

1. 数据组织：布局会影响性能。例如，内存访问效率差的结构在磁盘型 DBMS 中可能更优。
2. 并发性：需保证多线程同时访问时数据一致性与正确性。

---

二、哈希表（Hash Table）

哈希表实现了一个将“键”映射到“值”的关联数组（associative array）。
其平均操作复杂度为 O(1)（最坏为 O(n)），存储复杂度为 O(n)。

即使平均复杂度为常数，也需注意常数因子的性能优化。哈希表不保证键的顺序性，因此无法顺序遍历。

哈希表由两部分组成：

1. 哈希函数（Hash Function）：将大的键空间映射到较小的索引空间（桶/槽）。

   • 需在速度与冲突概率之间权衡。
   • 极端情况：
     • 恒定输出哈希函数 → 快速但冲突严重
     • 完美哈希函数 → 无冲突但计算昂贵
   • 理想方案在两者之间平衡。

2. 哈希方案（Hashing Scheme）：定义冲突处理机制。
   需权衡空间浪费与冲突时的额外操作代价。

---

三、哈希函数（Hash Functions）

哈希函数接受任意键作为输入，输出其整数表示（哈希值）。
输出必须确定性（deterministic）：相同键必须生成相同哈希。

• DBMS 无需使用加密安全哈希（如 SHA-256），因为其内部用途不涉及安全风险。
• 主要关注速度与冲突率。

当前最先进的哈希函数是 Facebook 的 XXHash3。

---

四、静态哈希方案（Static Hashing Schemes）

静态哈希方案的哈希表大小在创建前固定。若空间耗尽，必须整体重建更大表（通常扩容为原来的两倍），代价高昂。

为减少冲突，应预留充足空间（常取预期元素数量的两倍槽位）。

常见的错误假设包括：

1. 元素数量固定且已知；
2. 键唯一；
3. 完美哈希函数无冲突。

因此，必须合理选择哈希函数与方案。

---

（一）线性探测哈希（Linear Probe Hashing）

最基本且通常最快的方案。
其原理是使用**环形缓冲区（circular buffer）**存储槽位。

• 插入（Insert）：若发生冲突，则线性向后查找直至找到空槽，必要时循环回数组开头。
• 查找（Lookup）：从目标槽开始线性扫描，若遇空槽或遍历完则表示键不存在。
  因此需在槽中存储键与值以便比对。
• 删除（Delete）：若直接清除会破坏查找链，可采用两种方案：
  1. 使用**墓碑标记（Tombstone）**代替删除，表示该槽曾被占用；
  2. 或者移动相邻条目填补空槽（代价高，实际较少使用）。

键/值存储方式

• 固定长度键值：直接存储于哈希页，可选存储哈希值以加速比较。
• 可变长度键值：键值存于独立临时表，哈希表中仅存哈希与记录ID。

非唯一键处理

• 分离链表：存储指向包含所有值的链表指针。
• 冗余键：重复存储同一键（线性探测仍有效）。

优化技巧

• 针对不同数据类型或键长度的专用实现。
• 元数据（如空槽、墓碑信息）可存于单独数组或位图中。
• 使用版本控制机制避免重复初始化（通过版本号判断槽是否有效）。

实例： Google 的 absl::flat_hash_map 是线性探测哈希的先进实现。

---

（二）布谷鸟哈希（Cuckoo Hashing）

通过多个哈希函数将键映射到不同槽（通常位于同一个表中）。
哈希函数算法相同，但使用不同种子以生成不同哈希值。

• 插入：若目标表无空槽，则随机选择一表逐出旧条目，并将其重新哈希至另一表。
  若出现循环，则需：
  • 重建所有表（使用新种子），或
  • 扩大表容量。
• 特性：
  • 查找与删除操作保证 O(1)；
  • 插入代价较高。

教授注：布谷鸟哈希的本质是利用多个哈希函数映射到不同槽。
实际实现中，这些槽通常位于单个哈希表中。

---

五、动态哈希方案（Dynamic Hashing Schemes）

静态哈希表需要预知元素数量，否则需整体重建。
动态哈希方案能按需调整大小，无需重建全部数据。其扩展方式可偏向读或写优化。

---

（一）链式哈希（Chained Hashing）

最常见的动态方案。
每个槽对应一个桶链表，所有哈希到同一槽的键插入同一链表。

查找时，哈希到桶后遍历链表即可。

---

（二）可扩展哈希（Extendible Hashing）

链式哈希的改进版本，通过拆分桶而非无限延长链表。
支持多个槽指向同一桶链，从而减少重组开销。

关键机制：

• DBMS 维护全局深度（global depth）与局部深度（local depth），用于决定索引位数。
• 当桶满：
  • 若局部深度 < 全局深度 → 在槽数组中新增桶。
  • 否则 → 扩展槽数组（大小翻倍）并增加全局深度。

---

（三）线性哈希（Linear Hashing）

维护一个分裂指针（split pointer），记录下一个待分裂的桶。
当任意桶溢出时，总是分裂指针所指桶。分裂规则灵活。

操作流程：

1. 当桶溢出 → 在指针位置拆分桶，新增槽位与哈希函数，并重新哈希拆分桶的键。
2. 若原哈希映射到已拆分槽位 → 应用新哈希函数重新定位。
3. 当指针到达最后一个槽位 → 删除旧哈希函数并回到起点。
4. 若指针下方桶为空，可反向移动指针以缩小表。

优势：
线性哈希能逐步扩展或收缩表，避免整体重建的高成本。

---

Notes