哈希表优化

Question

在几个哈希表实现中，我看到了对存储桶中的项目使用“转置”或“移到前面”等启发式方法。

1. 使用这种启发式方法有什么优点？我自己也想不通。
2. 在哈希表/桶级别还可以进行哪些其他优化，为什么以及在什么情况下？

请先优化哈希函数。

Answer 1

如果发生冲突，因此存储桶中有多个项目，则必须对其进行检查，如果常用访问的项目位于列表的前面，将会很方便。

如果有理由假设最近访问的项目可能很快会再次被访问，那么这些启发式方法就有意义。当人们考虑新闻报道等内容时，很可能会经常访问突发新闻。