Robin hood hashing
Robin hood hashing
复制标题
罗宾汉哈希
DOI：
10.1109/sfcs.1985.48
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
J. Munro
中科院分区：
文献类型：
--
作者：
P. Celis;P. Larson;J. Munro
本文论述了通过开放寻址解决冲突的哈希表。最初的贡献是一个非常简单的插入过程，与标准方法相比，它极大地降低了搜索所需探测次数的方差。这引出了一种新的搜索过程，即使对于填满的表，平均也只需要常数次探测。最后，对这些方法的扩展产生了一种执行删除和后续插入的新的简单方法。实验结果有力地表明搜索时间几乎没有退化。特别是删除和成功搜索似乎需要常数时间（远小于2.57次探测），而插入和不成功搜索需要O(logn)时间。
This paper deals with hash tables in which conflicts are resolved by open addressing. The initial contribution is a very simple insertion procedure which (in comparison to the standard approach) has the effect of dramatically reducing the variance of the number of probes required for a search. This leads to a new search procedure which requires only a constant number of probes, on average, even for full tables. Finally, an extension to these methods yields a new, simple way of performing deletions and subsequent insertions. Experimental results strongly indicate little degeneration in search time. In particular deletions and successful searches appear to require constant time (≪ 2.57 probes) and insertions and unsuccessful searches, O(logn).