跳房子哈希(Hopscotch Hashing)

跳房子哈希是一种基于开放寻址的哈希表冲突处理方案。它的核心约束是:任何键都必须存放在其理想桶之后的一个固定大小邻域内,从而把查找范围限制在连续的少量槽位上,获得优秀的缓存友好性。

概述

跳房子哈希由莫里斯·赫利希(Maurice Herlihy)、尼尔·沙维特与莫兰·蒂利等人于2008年提出。它结合了线性探测的缓存优势与布谷鸟哈希的邻域搬迁思想。每个桶维护一个位图,标记其邻域内哪些槽位存放着本应属于该桶的键,查找时只需扫描这个小邻域。

核心原理

• 邻域约束:定义一个常数邻域长度H,某桶的所有元素必须位于该桶起始的连续H个槽内。
• 插入搬迁:若目标邻域已满,则通过一系列跳跃式搬迁,把某个空槽逐步挪进目标邻域。
• 位图导航:每个桶用一个比特掩码记录邻域占用情况,使查找几乎只访问一个缓存行。
• 并发友好:邻域局部性使得加锁范围小,便于设计高效的并发哈希表。

应用场景

跳房子哈希适合对查找延迟敏感、负载因子较高的内存哈希表,尤其在多核并发环境下表现突出。它被用于并发哈希表库、内存数据库索引以及需要稳定尾延迟的高性能系统组件中。

常见问题

问:跳房子哈希相比线性探测好在哪?答:线性探测在高负载下会出现长探测序列导致性能骤降,而跳房子把每个键限制在固定邻域内,查找步数有上界,尾延迟更可控。

问:插入一定能成功吗?答:当无法把空槽搬进目标邻域时插入会失败,此时需要触发扩容重建,这与其他开放寻址表类似。