我正在使用 murmur hash 在哈希表中存储 150,000 个单词 我正在使用线性探测来解决程序中的冲突。我想如果我的hashtable的size很大，那么就会有大量的空闲空间，不用我去探查半天。但是奇怪的事情发生了。当哈希表的大小为 250,000 时，我获得了最快的运行时间。之后运行时间增加。为什么会这样？
最佳答案
虽然 Robert 涵盖了一般性问题(局部性)，但问题可能是空间局部性。
当你有一个较小的哈希表时，它适合缓存。当您有一个非常大的哈希表时，每次查找都存在页面错误的高风险。如果您出现页面错误，那么您的操作系统需要暂停执行，直到内存管理单元可以将 block 从较慢的访问内存复制到更靠近 CPU 的缓存。
在极端情况下，较慢的访问内存甚至可能是操作系统提供的磁盘资源。
关于c - 为什么我的程序在增加哈希表的大小时变慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25272071/