CMU15-445 数据库系统播客：适用于数据库的经典哈希结构与设计权衡

速度与碰撞的数适用权衡 (Trade-off between Speed and Collision Rate)

不使用加密哈希函数，我们只关注 速度快 和 碰撞率低 的据库据库计权哈希函数。

常数因子很重要 (Constant Factors Matter) ：在处理大量数据时，系统希结即使O(1)操作的播客常数因子差异也会导致巨大的性能差距和金钱成本。

• 静态哈希方案 (Static Hashing Schemes)：静态哈希方案的于数哈希表大小是固定的。如果存储空间不足，经典哈DBMS必须从头开始重建一个更大的构设哈希表（通常是原大小的两倍），这会 非常昂贵 。数适用

线性探测哈希 (Linear Probe Hashing)

实现原理/方法 ：哈希函数计算出槽位后，据库据库计权如果该槽位已被占用，系统希结则 线性扫描 到下一个空闲槽位进行插入。播客查找时，于数也从哈希到的经典哈槽位开始线性扫描，直到找到目标键或遇到空槽。构设为了进行验证，数适用每个槽位必须存储原始键。

• 优点 ： 最基本也通常是最快 的哈希方案，因为它具有良好的缓存局部性，且分支预测失败较少。

• 代价 ：删除操作很复杂。源码下载如果直接删除，会中断后续键的查找链； 墓碑标记 (Tombstone) 复杂，在删除的槽位放置一个“墓碑”标记，表示该槽位逻辑上为空但物理上占用，查找时会跳过此标记继续扫描。浪费空间，需要后续垃圾回收。将后续的键向前移动以填充空位，代价是移动后的键可能不再位于其最佳哈希位置的下游，导致查找失败。

罗宾汉哈希 (Robin Hood Hashing)

实现原理/方法 ：线性探测哈希的一种变体。每个键都会记录它 距离其理想哈希位置的“跳跃”次数 （即贫富程度）。在插入时，如果新键比当前占据该槽位的键“更贫穷”（即距离其理想位置更远），新键会 “偷走” 这个槽位，而被“偷走”的键则会被重新插入到哈希表中。

• 优点 ：旨在 平衡整个哈希表中键的距离 ，最小化任何键距离其理想位置的最大距离。

• 代价 ： 写入/插入更昂贵 ，在实践中，对于内存中的云服务器数据结构，通常 比线性探测哈希慢 。

布谷鸟哈希 (Cuckoo Hashing)

实现原理/方法 ：使用 多个哈希表 （通常是两个）和 不同的哈希函数种子 。插入时，尝试在每个哈希表中找到一个空闲槽位。如果所有可能的槽位都被占用，则 驱逐 其中一个哈希表中的现有元素，并将其重新哈希以找到新位置，这可能导致连锁驱逐（像布谷鸟占巢）。

• 优点 ： 查找和删除总是O(1) ，因为只需检查每个哈希表中的一个特定位置。

• 代价 ： 插入可能昂贵 ，可能导致“乒乓”效应或连锁驱逐，甚至陷入 循环 （无限循环）；如果检测到循环或哈希表变得太满，就需要 重建所有哈希表 ，使用新的哈希函数种子或更大的表。

• 动态哈希方案 (Dynamic Hashing Schemes)，能够在需要时 按需调整大小 ，而无需重建整个哈希表。

链式哈希 (Chained Hashing / Bucket Hashing)

实现原理/方法 ：每个主槽位都维护一个 桶（bucket）的链表 。所有哈希到同一个槽位的键都放在该链表的桶中。当桶满时，源码库就 分配并链接一个新的桶 。

• 优点 ：实现简单，且通过不断添加新桶可以“无限”增长。易于实现线程安全，只需对槽位或单个页面进行加锁。

• 代价 ：如果所有键都映射到同一个桶链，哈希表可能会退化为 O(n)的线性搜索 ，性能显著下降；可能存在空间浪费，尤其是有许多短链时。

可扩展哈希 (Extendible Hashing)

实现原理/方法 ：链式哈希的改进变体，它会 分裂桶 而不是让链无限增长。维护一个 全局计数器（global depth） ，指示哈希值需要检查的位数，以确定在槽数组中的位置。

每个桶也有一个 局部计数器（local depth） 。

当桶溢出时，会触发分裂。如果局部深度小于全局深度，则重新分配桶中的元素到新的桶中。如果局部深度等于全局深度，则 全局深度会增加，槽数组的大小会加倍 （这个操作是廉价的，因为只是指针数组），然后重新分配桶中的元素。

• 优点 ： 数据移动被局部化 到溢出的桶链，其他桶不受影响。槽数组的加倍操作相对廉价，因为它只涉及指针数组的更新，不涉及数据的物理移动。

• 代价 ：槽数组加倍时，需要对整个槽数组 获取全局锁 ，这可能成为并发访问的瓶颈；删除操作比较复杂，可能需要合并桶并逆向分裂过程

线性哈希 (Linear Hashing)

实现原理/方法 ：维护一个 分裂指针 (split pointer) ，它跟踪下一个要分裂的桶，而不管哪个桶实际溢出。使用 多个哈希函数 （例如 key % n 和 key % 2n）。

当任何桶溢出时， 分裂指针指向的桶 会被分裂（即使它不是溢出的那个），将其内容重新分配到新的槽位，并添加一个新的哈希函数（key % 2n）。

查询时，首先使用第一个哈希函数。如果映射到的槽位在分裂指针 之上 （即已被分裂），则需要使用第二个哈希函数来找到实际位置。

• 优点 ：将 调整大小的操作局部化 到分裂指针所指向的桶，避免了对整个哈希表进行全局加锁，从而减少了并发瓶颈。

• 代价 ：由于分裂的桶不一定是溢出的桶，这可能导致 临时出现更多的溢出链 ；删除操作很复杂，可能涉及分裂指针的逆向移动和内存回收。

• 线性探测哈希 (Linear Probe Hashing)

本文地址：http://www.bhae.cn/html/116b9899785.html