Hopscotch Hashing
这篇讲的是Hopscotch Hashing，一种旨在显著提升查询速度的开放地址哈希方法。作者直接点明，传统思路（如链地址法或其它开放寻址方式）在哈希表负载较高时，性能会急剧下降，查询复杂度难以维持。 文章的核心方案围绕一个巧妙的插入时调整策略展开：通过在插入数据时主动将其“路由”到目标桶的邻近区域，让每个桶的“邻居”形成一个高效的数据簇。这个过程有点像精心规划交通，确保前往某个目的地（桶）时，所有相关的车辆（数据）都停在旁边的几个固定停车位里，而不是散落在整个停车场的各个角落。 这种设计带来的关键差异和结论是，它能在最坏情况下也保证查询操作的时间复杂度为一个常数，这是很多传统哈希方法难以做到的。无论哈希表装得多满，你查找任何一个键的耗时基本都是确定的，这对于需要稳定低延迟的应用场景非常有价值。 文章没有停留在理论层面，而是清晰地阐述了这种算法如何通过“预见性布局”来克服开放寻址哈希的经典痛点，真正承诺了性能的稳定可预测。