主要涉及了哈希表结构以及如何处理哈希冲突的方案。
Background
哈希表以无序数组实现，其中存储键值对映射。哈希表依赖哈希函数计算键在哈希表中的偏移量/位置，因此：
- 时间复杂度：平均为
O(1)，最差情况下为O(n); - 空间复杂度：
O(n)
一个理想的哈希表如图所示，遵循如下假设：
- 元素的数量固定且提前可知；
- 每个key都是唯一的；
- 存在能够使所有键的哈希值都不冲突的哈希函数。
上述假设在实际系统运行时往往很难达成。
hash table的设计主要在如下两个方面考虑：
- hash function：设计一个将大量key映射到一个较小范围的映射函数，且需要在碰撞率和速度之间权衡。例如最快的hash函数直接返回常量，但这样会带来100%的碰撞率。
- hashing scheme：在映射之后如何解决哈希冲突，此时需要在分配一个较大的哈希表降低冲突可能性或者引入额外指示之间权衡。
Hash Functions
对于给定的key，返回32/64位整数表示。
Static Hashing Schemes
Open Addressing，开放寻址
每次相同的key存入hash表时的位置未必完全相同。
1. Linear Probe Hashing，线性探测
哈希表被构建为一个固定大小的数组，线性探测将使用线性扫描寻找下一个空闲可用的槽位或者当前key已经存在的槽位：
- key到达，经过哈希函数得到哈希值，该哈希值映射到数组中的一个槽位作为起点；
- 若映射所得槽位空闲，直接插入即可；
- 若映射所得槽位非空，且其中存储元素和当前key不等，则继续向下扫描，直到找到一个空闲槽位/和当前key相等的槽位。
哈希表中还存在称为负载因子的元数据，例如设置负载因子为0.7，当元素数量占比达到哈希表大小的70%时，则应当对哈希表进行扩容。
扩容后，原哈希表中的元素应当重新映射并写入新的哈希表中。
扩容操作是比较耗时的，最坏的实现下，扩容时将阻塞所有读写线程，优先进行哈希表扩容。因此实际实现会尽量避免扩容操作，比较容易的方式是通过预估哈希表中的元素数量来避免扩容，pg在hash join构建哈希表时会这样做。
关于键值对entry存储
对于固定长度键值对：
- 可以将value内联在hash table中，因为每个元素都将拥有固定的长度（size(key) + size(value)）
- 在某些情况下，例如key是128位的字符串，也可以额外存储key的哈希值，便于快速比较该槽位是否可能存储这个key，加快查找速度。
对于变长键值对：
- 可以将键值真实数据存储在另一个独立临时表中；
- 在哈希表中，存储哈希值为key，record id为value，其中record id指向实际的键值对在临时表中的位置。
关于线性探测的严重问题：删除
假设哈希表：
删除条目C：
删除条目D：现在我们移动到D原先被映射到的位置，由于C和D之间存在哈希冲突，导致D的位置下移；而我们上一步中删除了条目C，导致现在槽位为空。因此我们跳转到D本应被映射的槽位时，检测器为空，我们认为D不在此哈希表中，虽然实际上它就在下面一个位置。
解决方案：
- 每次删除元素后，所有之后的元组都重新哈希并移动，但这样做开销太大；
- 逻辑删除：删除元素时，仅对元素做逻辑上已删除的标记。那么删除条目C之后，会存在一个逻辑删除的标记，删除条目D时在C的位置读到这里曾有过数据，也就是原数据可能和D存在冲突，从而向下继续扫描D。
非单一key处理
对于同一key映射至不同值的情况：
- 可以使用链表：
优化方向
- 根据key的类型和大小使用不同的哈希表，例如为不同大小的string，维护不同的哈希表，当字符串size很小的时候（小于32位）我们可以直接在哈希表中存储原始值，字符串长度过大时存储哈希值。
- 维护额外的元数据，例如bitmap跟踪hash table某槽位是否为空。
- 使用哈希表和槽位版本号，例如某个槽位版本号和当前table版本号不匹配，则视为空槽位。
2. Cuckoo Hashing
使用多个hash函数而非线性探测来寻找下一个空闲/可用的槽位：
- 对于当前key，通过多个hash函数得到多个槽位，若其中有空闲/可用，则插入/修改；
- 如果没有可用槽位，则从候选槽位中驱逐原有数据并插入，将原有数据hash到新的位置。
Dynamic Hashing Schemes
无需为哈希表进行扩容，哈希表会随着元素插入动态扩展。
Chained Hashing
哈希冲突的元素将被组织为一个链表。
优化方向：可以在链表头节点中维护一个类似布隆过滤器，用于快速判断元素是否在当前链表中。
Extendible Hashing
极端情况下，数据倾斜严重时，chain hashing中会出现链过长，查找退化为O（n）复杂度。
Extendible Hashing：
- 使用 哈希值的前几位(bit prefix) 来定位桶
- 使用一个 目录（directory） 指向桶
- directory：存在一个全局变量g，取hash(key)的前g位，目录的大小为$$2^g$$，每个条目都指向一个bucket。
- bucket：持有局部深度local depth，表明当前桶使用的哈希前缀位数。
桶满时：
此时会触发：global位数++，overflow的桶按照新的global位数进行分裂：
Linear Hashing
与extendible hashing不同的地方在于：
- extendible hashing分割容量溢出的bucket；
- linear hashing采用分割指针，分割指向的bucket，但该桶未必溢出。
分割指针：指向下一个要被分裂的桶，设桶的数量为n，那么分裂的顺序按照 0-1-2-…-n-1，不会产生跳跃。
初始状态下，我们使用一个哈希函数并对n取模，得到相应的桶号，这一切过程和前述chain没有区别。
桶分裂：
- 若插入操作导致目标桶溢出
- 触发分裂，分裂当前分割指针指向的bucket
- 注意到我们新增了一个哈希值的获取方式，即对2n进行取模，接下来的进行的插入/查找操作：
- 若对n取模的结果大于分割指针，则按照该结果指向的桶号进行操作；
- 若对n取模的结果小于分割指针，则按照2n取模结果指向的桶号操作。
- 向下移动分割指针
删除操作也可能涉及分割指针的向上移动。