哈希表优化

Question

在几个哈希表实现中，我看到了对桶中的条目使用"transpose“或”Moveto前台“之类的启发式方法。

1. 使用这种启发式方法的优点是什么？我自己搞不清楚，
2. 在哈希表/桶级可以进行哪些其他优化，原因是什么，以及在哪种情况下可以进行优化

请把优化哈希函数放在一边。

Answer 1

如果冲突正在发生，因此桶中有几个项，必须检查这些项，如果通常访问的项在列表的早期就会很方便。

如果有理由假设最近访问的项很可能很快就会再次被访问，那么这些启发式方法是有意义的。当人们考虑诸如新闻故事之类的事情时，很可能会频繁地访问突发新闻。