这个散列 table 优化的名称是什么？

Question

在使用开放寻址实现自定义散列 table 时，我发现对于我的应用程序，如果我将一排填充槽中的探测元素与第一个探测位置中的元素交换，它有助于提高性能。 （优化 table 以更快地生成经常访问的元素）

这个优化有名字吗？

Answer 1

这种优化最通用的术语可能是self-organization。

Answer 2

您的问题与list update problem from the field of online-competitive algorithms非常相似。

您使用的解决方案称为 MTF (move to front)。众所周知，该解决方案是 2 竞争的，这意味着它的表现最多是预先知道未来的假想对手的两倍。

请注意，您可以比 bit algorithm 做得稍微好一点，后者需要另一位 + 随机操作，但具有 7-4 的竞争力。