compiler-construction - 哈希表优化

Question

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

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

请先优化散列函数。

Answer 1

如果发生冲突，因此桶中有多个项目，必须检查这些项目，如果经常访问的项目在列表中的前面会很方便。

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