【CMU 15-445】06 哈希表

Slides
Notes

Tips

大部分内容就是数据结构中哈希表的内容，结合数据结构和数据库的实现好理解很多。

1. 数据结构

DBMS对系统内部的许多不同部分使用各种数据结构：

• Internal Meta-Data（内部元数据）：跟踪有关数据库和系统状态的信息。
• Core Data Storage （核心数据存储）：可用作数据库中元组的基本存储。
• Temporary Data Structures（临时数据结构）：DBMS可以在处理查询时动态构建数据结构，以加快执行速度(例如，用于 joins 的哈希表)。
• Table Indexes（表索引）：辅助数据结构，使查找特定元组更容易。

设计决策：

• 数据组织：我们如何布局内存以及在数据结构中存储哪些信息。
• 并发性：如何让多线程不出问题地访问数据结构。

2. 哈希表

哈希表实现了将 key 映射到 value 的关联数组抽象数据类型。它提供了平均O(1)的计算复杂度（时间）和O(n)的存储复杂度（空间）。

哈希表实现由两部分组成：

• 哈希函数：如何将大的密钥空间映射到较小的域中。它用于计算存储桶或槽数组的索引。需要考虑快速执行和冲突率之间的权衡。
• 哈希方案：如何处理散列后的密钥冲突。需要考虑分配大型哈希表以减少冲突与执行额外指令以查找/插入键之间的权衡。

3. 哈希函数

哈希函数接受任何 key 作为其输入。然后，它返回该 key 的整数表示(即,“hash”)。函数的输出是确定性的(即，相同的键应该始终生成相同的散列输出)。

DBMS不想使用密码散列函数(例如，SHA-256)，因为我们不需要担心保护密钥的内容。这些散列函数主要由DBMS内部使用，因此信息不会泄漏到系统之外。对于本课，我们只关心散列函数的速度和冲突率。目前最先进的散列函数是Facebook XXHash3。

Tips1:

加密常见Hash:

• SHA-256
• MD5(2004年被山大王小云老师破解)

数据库常见Hash：

• CRC-64(1975)
• MurmurHash(2008)
• Google CityHash(2011)
• Facebook XXHash(2012)
• Google FarmHash(2014)

Tips2:

不要自己写哈希，浪费时间，直接拿来用

4. 静态（Static）哈希方案

静态哈希方案是其中哈希表的大小是固定的方案。这意味着如果DBMS耗尽了哈希表中的存储空间，则它必须使用更大的表从头开始重建它。通常，新哈希表的大小是原始哈希表的2倍。（我们已知哈希表的大小，且不动态增长。）

为了减少浪费比较的次数，重要的是要避免碰撞×散列key。这需要具有两倍于预期元素数量的段数的哈希表。

4.1. Linear Probe Hashing

线性探针哈希，这是最基本的 hashing 方案。它通常也是最快的。它使用单一的槽表。哈希函数允许DBMS快速跳转到 slots 并查找所需的 key 。（其实就是开放地址法）

• 通过线性搜索表中的下一个空闲插槽来解决冲突；
• 要查看值是否存在，请使用散列转到 slot ，并扫描 key 。如果找到所需的 key 或遇到空 slot ，扫描将停止。

  删除时添加⼀个tombstone(墓碑)标记

4.2. Robin Hood Hashing

这是线性探测散列的扩展，它寻求减少每个 key 从它们在哈希表中的最佳位置的最大距离。允许线程从“rich”keys 中窃取slot，并将它们分配给“poor”keys。

• 每个 key 跟踪它们在表中从其最佳位置开始的位置的数量。
• 插入时，如果第一个 key 比第二个 key 离其最佳位置的距离更远，则一个 key 将占据另一个 key 的槽。然后，必须将删除的 key 重新插入到表中。

4.3. Cuckoo Hashing

这种方法不是使用单个哈希表，而是使用不同的哈希函数维护多个哈希表。哈希函数是相同的算法(例如，XXHash、CityHash)；它们通过使用不同的 seeds 为相同的 key 生成不同的哈希。

• 在插入时，检查每一张表，并挑选任何有空位的 slot 。
• 如果没有表有空闲的 slot ，则从其中一个表中取出元素，并对其进行重新 hash 以找到新的位置。
• 如果我们找到一个循环，那么我们可以用新的hash函数 seeds 重建所有hash表(不太常见)，或者使用更大的表重建hash表(更常见)。

5. 动态（Dynamic）哈希方案

静态散列方案要求DBMS知道它想要存储的元素的数量n。否则，如果需要增大/缩小大小，它将重新构建该表。

动态哈希方案能够按需调整哈希表的大小，而无需重新构建整个表。这些方案以不同的方式执行调整大小的操作，这些方式可以最大化读取或写入。

5.1. 链式哈希 Chained Hashing

这是最常见的动态散列方案。DBMS为哈希表中的每个 slot 维护 桶buckets 的链接列表。

• 通过将具有相同hash key 的元素放入同一 buckets 来解决冲突。
• 如果 buckets 已满，则向链中添加另一个buckets 。哈希表可以无限增长，因为DBMS不断添加新的 buckets 。

5.2. 可扩展哈希 Extendible Hashing

链式散列的改进变体，它拆分 buckets ，而不是让链永远增长。该方法允许哈希表中的多个槽位置指向相同的桶链。

重新平衡哈希表背后的核心思想是在拆分时移动 buckets 条目，并增加要检查以在哈希表中查找条目的 bits 数。这意味着DBMS只需在拆分链的 buckets 内移动数据；所有其他 buckets 保持不变。

• DBMS维护全局和局部深度 bit 计数，以确定在槽数组中查找桶所需的 bit 数。
• 当 buckets 满时，DBMS拆分 buckets 并重新洗牌其元素。如果拆分 buckets 的局部深度小于全局深度，则新buckets 只是添加到现有槽数组中。否则，DBMS会将槽数组的大小增加一倍以容纳新的 buckets ，并递增全局深度计数器。

5.3. 线性哈希 Linear Hashing

该方案不是在桶溢出时立即拆分桶，而是维护一个拆分指针来跟踪下一个要拆分的桶。无论该指针是否指向溢出的桶，DBMS总是拆分。溢出标准由实现决定。

• 当任何桶溢出时，通过添加新的槽条目在指针位置拆分桶，并创建新的散列函数。
• 如果散列函数映射到先前由指针指向的槽，则应用新的散列函数。
• 当指针到达最后一个槽时，删除原有的散列函数，代之以新的散列函数。