CMU15445-lecture7
第七课：哈希表
1 数据结构
DBMS 对系统内部的许多不同部分使用各种数据结构。一些例子包括：
- 内部元数据：这是跟踪有关数据库和系统状态的信息的数据。比如：页表，页目录
- 核心数据存储：数据结构用作数据库中元组的基础存储。
- 临时数据结构：DBMS 可以在处理查询时动态构建临时数据结构以加速执行（例如，用于连接的哈希表）。
- 表索引：辅助数据结构可用于更轻松地查找特定元组。
在实现DBMS的数据结构时，需要考虑两个主要的设计决策：
- 数据组织：我们需要弄清楚如何布局存储以及在数据结构内存储哪些信息以支持高效访问。
- 并发性：我们还需要思考如何让多个线程访问数据结构而不引起问题，确保数据保持正确和健全。
2 哈希表
哈希表实现了将键映射到值的关联数据抽象数据类型。它平均提供O（1）操作复杂度（最坏情况下为O（n））和O（n）存储复杂度。请注意，即使平均操作复杂度为O（1），在现实世界中也存在需要考虑的常数因子优化。
哈希表实现由两个方面组成：
- 哈希函数：这告诉我们如何将大的密钥空间映射到更小的域中。它用于计算存储桶或槽数组的索引。我们需要考虑快速执行和冲突率之间的权衡。在一个极端，我们有一个哈希函数，它总是返回一个常量（非常快，但一切都是冲突）。在另一个极端，我们有一个“完美”的哈希函数，没有冲突，但需要很长时间才能计算。理想的设计是介于两者之间。
- 哈希方案：这告诉我们如何处理哈希后的密钥冲突。在这里，我们需要考虑分配一个大的哈希表以减少冲突和在发生冲突时必须执行额外的指令之间的权衡
3 哈希函数
哈希函数接受任何键作为其输入。然后它返回该键的整数表示（即“哈希”）。该函数的输出是确定性的（即相同的密钥应始终生成相同的哈希输出）。
DBMS 不需要使用加密安全哈希函数（例如 SHA-256），因为我们不需要担心保护密钥内容。这些哈希函数主要由 DBMS 内部使用，因此信息不会泄漏到系统外部。一般来说，我们只关心哈希函数的速度和碰撞率。
目前最先进的哈希函数是 Facebook XXHash3。
4 静态哈希方案
静态哈希方案是哈希表大小固定的一种方案。这意味着如果DBMS耗尽了哈希表中的存储空间，那么它必须从头开始重建更大的哈希表，这是非常昂贵的。通常新哈希表的大小是原始哈希表的两倍。
为了减少浪费的比较次数，避免散列密钥的冲突很重要。通常，我们使用的槽数是预期元素数的两倍。
以下假设在现实中通常不成立：
- 提前知道元素的数量
- 键是不唯一的
- 存在完美的哈希函数
因此，我们需要适当选择哈希函数和哈希模式。
4.1 线性探查哈希
这是最基本的哈希方案。它通常也是最快的。它使用数组槽的循环缓冲区。哈希函数将键映射到槽。当发生冲突时，我们线性搜索相邻的槽，直到找到一个开放的槽。对于查找，我们可以检查键散列到的槽，并线性搜索，直到找到所需的条目。如果我们到达一个空槽或迭代哈希表中的每个槽，则该键不在表中。请注意，这意味着我们必须将键和值都存储在槽中，以便我们可以检查条目是否是所需的条目。删除则更加棘手。我们必须小心从槽中删除条目，因为这可能会阻止将来的查找找到已放在现在空槽下方的条目。这个问题有两种解决方案：
- 最常见的方法是使用“墓碑”。我们没有删除该条目，而是将其替换为“逻辑删除”条目，该条目告诉未来的查找继续扫描。
- 另一种选择是在删除条目后移动相邻数据以填充现在的空槽。但是，我们必须小心，只移动最初移动的条目。这在实践中很少实现，因为当我们拥有大量密钥时，它的成本非常高。
非唯一键：在同一键可能与多个不同值或元组关联的情况下，有两种方法。
- 单独的链表：我们不存储带有键的值，而是存储一个指向单独存储区域的指针，该存储区域包含所有值的链表，这可能会溢出到多个页面。
- 冗余键：更常见的方法是简单地在表中多次存储相同的键。即使我们这样做，所有线性探测仍然有效。
优化：
有多种方法可以进一步优化此哈希方案：
- 基于数据类型或键大小的专用哈希表实现：它们存储数据、执行拆分等的方式可能有所不同。例如，如果我们有字符串键，我们可以在原始哈希表中存储较小的字符串，而对于较大的字符串仅存储指针或哈希。
- 将元数据存储在单独的数组中：一个示例是将空槽/逻辑删除信息存储在打包位图中作为页头的一部分或存储在单独的哈希表中，这将帮助我们避免查找已删除的键。
- 维护哈希表及其槽的版本：由于为哈希表分配内存非常昂贵，因此我们可能希望重复重用相同的内存。要清除表并使其条目无效，我们可以增加表的版本计数器，而不是将每个槽标记为已删除/空。如果槽版本与表版本不匹配，则槽可以被视为空。
Google的absl::flat_hash_map是线性探针哈希的最先进的实现。
4.2 Cuckoo哈希
这种方法不再使用一个单一的哈希表，而是维护多个具有不同哈希函数的哈希表。这些哈希函数使用相同的算法（例如XXHash、CityHash），通过使用不同的种子值为相同的键生成不同的哈希值。
当我们插入时，我们会检查每个表并选择一个具有空闲插槽的表（如果有多个表都有一个插槽，可以比较负载因子，或者更常见的，随机选择一个表）。如果没有表有空闲插槽，我们会选择（通常是随机选择一个）并驱逐旧条目。然后我们将旧条目重新哈希到另一个表中。在极少数情况下，我们可能会陷入一个循环。如果发生这种情况，我们可以使用新的哈希函数种子重建所有哈希表（不太常见）或使用更大的表重建哈希表（更常见）。
Cuckoo 哈希保证 O(1) 查找和删除，但插入可能更昂贵。
教授注：Cuckoo哈希的本质是多个哈希函数将一个键映射到不同的槽。在实践中，Cuckoo哈希是通过多个哈希函数来实现的，这些函数将一个键映射到单个哈希表中的不同槽。此外，由于散列可能并不总是 O(1)，Cuckoo散列查找和删除的成本可能超过 O(1)。
5 动态哈希方案
静态散列方案要求 DBMS 知道它想要存储的元素数量。否则，如果需要增大/缩小表的大小，则必须重建表。
动态哈希方案能够根据需要调整哈希表的大小，而无需重建整个表。这些方案以不同的方式执行大小调整，可以最大化读取或写入。
5.1 链式哈希
这是最常见的动态哈希方案。 DBMS 为哈希表中的每个槽维护一个存储桶的链表。散列到同一槽的键被简单地插入到该槽的链表中。
为了查找一个元素，我们散列到它的存储桶，然后扫描它。这可以通过在存储桶指针列表中额外存储布隆过滤器来优化，这会告诉我们链表中是否不存在某个键，并帮助我们避免在这种情况下进行查找。
5.2 可扩展哈希
链式哈希的改进变体，它分割存储桶而不是让链永远增长。这种方法允许哈希表中的多个槽位置指向同一个桶链。
重新平衡哈希表背后的核心思想是在拆分时移动存储桶条目，并增加要检查的位数以查找哈希表中的条目。这意味着 DBMS 只需要在分割链的桶内移动数据；所有其他桶保持不变。
- DBMS 维护全局和局部深度位计数，确定在槽数组中查找存储桶所需的位数
- 当存储桶已满时，DBMS 会拆分存储桶并重新排列其元素。如果分割桶的局部深度小于全局深度，则新的桶将被添加到现有的槽数组中。否则，DBMS 将槽数组的大小加倍以容纳新的存储桶，并增加全局深度计数器。
5.3 线性哈希
该方案不会在桶溢出时立即拆分桶，而是维护一个 split 指针来跟踪下一个要拆分的桶。无论这个指针是否指向溢出的桶，DBMS 总是会分裂。溢出标准由实现决定。
- 当任何桶溢出时，在指针位置分裂桶。添加新的槽条目和新的哈希函数，并应用此函数对拆分存储桶中的键进行重新哈希。
- 如果原始哈希函数映射到先前已被分割指针指向的槽，则应用新的哈希函数来确定键的实际位置。
- 当指针到达最后一个槽时，删除原来的哈希函数并将指针移回到开头。
如果split指针下面的最高bucket是空的，我们还可以删除该bucket，并将split指针反向移动，从而缩小哈希表的大小。