Hash table

Pollux 中使用的哈希表与 F14 哈希表 类似。 主要区别在于 Pollux 哈希表允许向量化插入和查找，而 F14 则不允许。

Layout

哈希表以桶数组的形式实现。它是一种线性数据结构。 每个桶占用 128 个字节（2 * 64 = 2 个缓存行），包含 16 个槽位。 每个哈希表条目占用一个槽位。哈希表的容量等于槽位总数：桶总数 * 16。哈希表的容量始终是 2 的幂。

每个槽位由两部分组成：一个标签（7 位）和一个指针（6 字节）。 一个桶中总共有 16 个标签和 16 个指针。它们首先存储标签，然后存储指针。每个标签占用 1 个字节（仅使用 7 位）。16 个 标签占用 16 个字节。每个指针占用 6 个字节。16 个指针占用 96 个字节。桶的末尾还有 16 个未使用的字节。 这些字节被称为填充。

哈希表永远不会满。总会有一些空位。Pollux 允许哈希表在调整大小之前填充至 :raw-html:<text style="font-size:1.2em;background-color:none">⅞</text> 的容量。 调整大小时，哈希表的容量会翻倍。

单个存储桶可能完全空、部分填充或已满。存储桶的填充顺序为从左到右。 如果存储桶部分填充，则前 N 个标签和 N 个指针会被填充，其余部分则为空闲 (N < 16)。

Inserting an entry

要插入新条目，我们需要确定将其放入哪个槽位。槽位由桶和桶内的偏移量标识。首先，我们计算条目的哈希值。 然后，我们根据哈希值计算标签和桶号。

我们使用哈希值的 7 位作为标签：第 38-44 位（含）。我们使用哈希值的 N 位作为桶号，

从第 8 位开始。

存储桶使用的位数取决于哈希表的容量。 请记住，容量始终是 2 的幂：2^n。每个存储桶存储 16 个条目，因此，我们需要2^{(n-4)} 个存储桶来存储 2^n 个条目。因此，我们需要使用哈希值的 n-4 位作为存储桶。

假设我们有一个可以存储一百万个条目的哈希表：2^{20} = 1,048,576。其中，n = 20， N = n - 4 = 16。我们将使用 16 位作为存储桶。

给定哈希值：

01011011 11001010 011 <text style="background-color:orange">11100 01</text>101001 10110111

1 <text style="background-color:#ADD8E6">0010100 11111000 1</text> 1001110

我们计算标签为 1 <text style="background-color:orange">1110001</text>，桶偏移量为
1,374,336 (00000000 00000000 00000000 00000000
0 <text style="background-color:#ADD8E6">0010100 11111000 1</text> 0000000)。

存储桶偏移量是距离哈希表开头的字节数。

    bucket offset = bucket number * 128
    bucket number = bucket offset / 128

存储桶偏移量用于定位到存储桶，在本例中是存储桶编号 10737。 候选存储桶可以是空的、部分填充的或满的。

存储桶为空。

在这种情况下，我们只需将条目插入到存储桶的第一个位置即可。 我们只在哈希表中存储标签（哈希值的 7 位）。哈希值本身不存储。 指针指向哈希表外部的内存，完整值存储在该内存中。 这通常是 RowContainer 中的一行。哈希表可以被视为 RowContainer 顶部的索引， 它有助于更快地找到具有匹配键的记录。哈希表本身不存储数据或键。

存储桶已部分填充。

例如，存储桶中有一个槽位已被占用（如上所示）。 在这种情况下，新条目可能与已存储的条目重复。 因此，我们会将新条目的标签与存储桶中已存储的标签进行比较。 如果没有匹配项，则表示该条目不是重复条目，因此我们会将其存储在存储桶中的下一个可用槽位中。

但是，如果一个或多个现有标签与新条目的标签匹配，我们会沿着指针比较键，以确定是否存在匹配项。如果没有匹配项，则插入一个新条目。 否则，则存在重复项。该行将链接到行条目指向的行列表， 并且不会插入新条目。

桶已满。

首先，我们需要检查新条目是否与存储桶中存储的 16 个条目之一重复。 我们比较标签，并在必要时跟踪指针来比较键。 如果匹配，则将该行链接到该行条目指向的行列表， 并且不插入新条目。如果没有匹配，则转到 下一个存储桶并重复该过程。在极少数情况下，我们可能会检查多个存储桶，直到找到 重复的现有条目或新条目的空槽。因此，确保哈希表永不满，并且有足够多的空槽非常重要。

Resizing

如果哈希表的容量超出 :raw-html:<text style="font-size:1.2em;background-color:none">⅞</text> 的上限，则需要调整其大小。每次调整大小都会使容量翻倍。 系统会分配一个新的哈希表，并使用“插入条目”流程插入所有现有条目。 由于我们知道所有条目都是唯一的，因此可以简化“插入条目”流程， 从而省去检查新条目是否与现有条目重复的逻辑。因此，要插入条目， 我们计算哈希值，提取标签和存储桶编号，然后转到存储桶，如果还有空间，则插入条目。如果存储桶已满， 则继续查找下一个存储桶，直到找到一个有空槽的存储桶。我们将新条目插入到该存储桶中。

Use Cases

哈希表的主要用例是 Join <joins.html>_ 和 Aggregation <aggregations.html>_ 运算符。

HashBuild 运算符构建哈希表，用于存储在连接构建端找到的连接键的唯一值。HashProbe 运算符使用来自探测端的连接键在 哈希表中查找条目。HashProbe 运算符不会在哈希表中插入新条目，也不会触发调整大小。哈希表中的指针指向 RowContainer 中的行，该行存储连接构建端的各个行。

HashAggregation 运算符在哈希表中存储唯一的分组键。哈希表中的指针指向 RowContainer 中的行，该行存储分组键以及聚合函数的累加器。

Implementation

哈希表由命名空间kumo::pollux::exec中的HashTable类实现。