CMU::15-445/645::Hash Tables 笔记

散列表

数据结构

DBMS 为系统内部的许多不同部分使用各种数据结构。一些例子包括。

• 内部元数据。这是对数据库和系统状态信息进行跟踪的数据。
• 核心数据存储。数据结构被用来作为数据库中 Tuple 的基础存储。
• 临时数据结构。DBMS 可以在处理查询的过程中即时建立数据结构，以加快执行速度（例如，用于连接的哈希表）。
• 表索引。可以使用辅助数据结构来使其更容易找到特定的 Tuple 。

在实现 DBMS 的数据结构时，有两个主要的设计决定需要考虑。

• 数据组织。我们需要弄清楚如何布局内存，以及在数据结构内存储哪些信息以支持有效的访问。
• 并发。我们还需要考虑如何使多个线程访问数据结构而不造成问题。

散列表 Hash Tables

哈希表实现了一个关联数组的抽象数据类型，它将键映射到值。它提供了平均 O(1) 的操作复杂度（最坏情况下为 O(n)）和 O(n)的存储复杂度。请注意，即使平均操作复杂度为 O(1)，也有一些常数系数的优化这在现实实践中需要考虑，这些很重要的。

哈希函数

这告诉我们如何将一个大的键空间映射到一个较小的领域。它被用来计算进入一个桶或槽阵列的索引。我们需要考虑快速执行和碰撞率之间的权衡。在一个极端，我们有一个总是返回一个常数的哈希函数（非常快，但一切都会发生碰撞）。在另一个极端，我们有一个"完美"的散列函数，其中没有碰撞，但需要极长的时间来计算。理想的设计是介于两者之间。

散列方案

这告诉我们如何处理散列后的键值冲突。在这里，我们需要考虑分配一个大的哈希表以减少碰撞和在发生碰撞时必须执行额外的指令之间的权衡。

散列函数

散列函数接受任何键作为其输入。然后它返回该键的整数表示（即"哈希"）。该函数的输出是确定的（即，相同的键值应该总是产生相同的哈希输出）。

DBMS 不需要使用加密安全的哈希函数（例如 SHA-256），因为我们不需要担心保护键值的内容。这些哈希函数主要由 DBMS 内部使用，因此信息不会被泄露。

一般来说，我们只关心哈希函数的速度和碰撞率。 目前最先进的哈希函数是 Facebook XXHash3。

静态散列方案

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

为了减少浪费的比较次数，避免哈希键的碰撞很重要。通常情况下，我们使用两倍于预期元素数量的槽位。

以下假设在现实中通常是不成立的。

• 元素的数量是提前知道的。
• 键值是唯一的。
• 存在一个完美的哈希函数。

因此，我们需要适当地选择散列函数和散列模式。

线性探测散列

这是最基本的散列方案。它通常也是最快的。它使用一个数组槽的循环缓冲区。 散列函数将键映射到槽。当发生碰撞时，我们线性地搜索相邻的槽，直到找到一个开放的槽。对于查找，我们可以检查键的哈希值，然后线性搜索，直到找到所需的条目（或一个空槽，在这种情况下，键不在表中）。请注意，这意味着我们必须在槽中存储密钥，以便我们能够检查一个条目是否是所需的。删除是比较棘手的。我们必须小心翼翼地从槽中删除条目，因为这可能会阻止未来的查询找到被放在现在空槽下面的条目。这个问题有两个解决方案。

• 最常见的方法是使用 “墓碑”。我们不删除这个条目，而是用一个 “墓碑 “条目取代它，告诉未来的查找要继续扫描。
• 另一种方法是在删除一个条目后移动相邻的数据以填补现在的空槽。然而，我们必须注意只移动最初被移位的条目。

非唯一键。在同一个键可能与多个不同的值或 Tuple 相关的情况下，有两种方法。

• 单独的链表。我们不将数值与键一起存储，而是将一个指针指向一个单独的存储区域，该区域包含所有数值的链接列表。
• 冗余的键。更常见的方法是简单地在表中多次存储相同的键。即使我们这样做，所有具有线性探测功能的东西仍然可以工作。

插入

有 A B C D E F 六个值和一个缓冲区

计算 A 的散列值，落在第三个槽

计算 B 的散列值，落在第一个槽

计算 C 的散列值，落在第 3 个槽，被占用，向下继续寻找找到第一个空闲的槽插入

计算 D 的散列值，落在第三个槽，已经被占用，向下寻找第四个槽，也被占用，继续向下找，找到空闲的，插入

E F 的散列冲突以此类推，如果，对应位置后面的槽都被占用，那么从头开始找，缓冲区是环形的。

删除

把第四个槽的数据删除后出现了一个空位

一个做法是把那个位置标记为“墓碑”，当后面的散列值对应到这个位置的时候，就会继续向后寻找。

另一个做法是，把删除位后面的数据往前移动一格。

罗宾霍德散列

这是线性探测散列的一个扩展，旨在减少每个键值在散列表中的最佳位置（即它们被散列到的原始槽）的最大距离。这种策略从 “富 “键中窃取槽位，并把它们给 “穷 “键。 在这个变体中，每个条目也记录了它们与最佳位置的 “距离”。然后，在每次插入时，如果被插入的钥匙与它们在当前槽的最佳位置的距离比当前条目的距离更远，我们就替换当前条目，并继续尝试在表中更远的位置插入旧条目。

插入

插入 A 在第三个槽

插入 B 在第一个槽

插入 C 到第三个槽，此时与 A 冲突，往后一个，记录最佳位置的距离为 1

插入 D 到第四个槽，与 C 冲突，比较两个的最佳距离都是 1，D 继续往后，插入，记录最佳距离为 1。

插入 E 到第三个槽，冲突，往后继续，到第五个槽，此时最佳位置 2，比 D 的最佳位置更大，E 插入到第五个槽，记录最佳位置 2，D 往后移动一个位置，记录最佳位置 2

Cuckoo 散列

这种方法不是使用单一的哈希表，而是用不同的哈希函数维护多个哈希表。 这些哈希函数是相同的算法（例如，XXHash，CityHash）；它们通过使用不同的种子值为同一个键生成不同的哈希值。 当我们插入时，我们检查每一个表，并选择一个有空闲槽的表（如果多个表都有空闲槽，我们可以比较诸如负载率之类的东西，或者更常见的，只是选择一个随机表）。如果没有表有空闲的槽，我们就选择（通常是随机的）并驱逐旧条目。然后，我们将旧的条目重新洗牌到一个不同的表中。在极少数情况下，我们可能会在一个循环中结束。如果发生这种情况，我们可以用新的哈希函数种子重建所有的哈希表（不太常见）或者用更大的表重建哈希表（更常见）。 Cuckoo 散列保证了 O（1）的查找和删除，但插入可能更昂贵。

动态散列方案

静态散列方案要求 DBMS 知道它要存储的元素的数量。否则，如果需要增加/缩小表的大小，它就必须重建表。

动态散列方案能够根据需要调整散列表的大小，而不需要重建整个表。这些方案以不同的方式执行这种大小调整，可以最大限度地提高读取或写入。

链式散列

这是最常见的动态散列方案。DBMS 为哈希表中的每个槽维护一个桶的链接列表。对同一槽位进行散列的键被简单地插入到该槽位的链表中。

可扩展散列

链式散列的改进版本，它将桶拆分，而不是让链永远增长。这种方法允许哈希表中的多个槽位指向同一个桶链。

重新平衡哈希表的核心思想是在分割时移动桶的条目，并增加检查的位数来寻找哈希表中的条目。这意味着 DBMS 只需要在分割链的桶内移动数据，其他所有的桶都不需要动。

• DBMS 维护着一个全局和局部的深度位数，决定了在槽阵列中寻找桶所需的位数。
• 当一个 bucket 满了，DBMS 会分割 bucket 并重新排列其元素。如果分割后的水桶的本地深度小于全局深度，那么新的 bucket 就只是添加到现有的槽阵列中。否则，DBMS 将槽阵列的大小增加一倍以容纳新的槽，并增加全局深度计数器。

线性散列

当一个桶溢出时，这个方案并不立即分割，而是保持一个分割指针，跟踪下一个要分割的桶。无论这个指针是否指向一个溢出的桶，DBMS 都会进行分割。溢出的标准是由实现者决定的。

• 当任何一个桶溢出时，通过添加一个新的槽项来分割指针位置的桶，并创建一个新的哈希函数。
• 如果哈希函数映射到以前被指针指向的槽，则应用新的哈希函数。
• 当指针到达最后一个槽时，删除原来的哈希函数，用新的哈希函数替换它。

查找 6，hash1 计算结果是 2，对应找到 2 指向的阵列

插入 17，hash1 计算结果是 1，插入到 1 指向的阵列，此时，1 的阵列满了，所以 17 通过溢出的方式跟在后面，并看是否需要分裂指针指向的阵列

对于被分类的阵列，在哈希表的键值部分生成一个 n+1 的键值，然后把这个陈列的值用 hash2 重新分布

当我们要查找 20 的时候，首先用 hash1 计算出结果，发现落到了 0，0 此时在指针指向的分割线上面，所以要应用 hash2，再次查找，当指针遍历完第一轮之后，删除 hash1 函数