我听说当数据限制存储在磁盘而不是主内存上时，尝试执行查找的效率低于哈希表。为什么会出现这种情况？
最佳答案
在磁盘上，随机访问速度很慢，因为为了读取特定位置的字节，硬盘驱动器必须物理旋转以将这些字节放在读取磁头下。磁盘上随机访问的成本可能比 RAM 上的类似访问慢数百万倍。
最重要的是，每当您从磁盘读取数据时，都会从磁盘读取称为页面的内存块，而不仅仅是您请求的字节。这意味着，如果您从磁盘读取一些数据，访问该字节附近的字节可能会非常快，因为该数据将从同一页读取并加载到 RAM 中。这意味着磁盘上的数组中的顺序访问将很快，因为在第一次(慢速)读取以获取要读取的第一个数组元素的字节之后，下一个数组元素的字节可能已经被加载并可用。/p>
考虑一下这对于尝试与线性探测哈希表意味着什么。 trie 是一种树结构，其中查找需要跟踪大量指向内存中不按特定顺序排列的节点的指针。这意味着 trie 查找的成本可能是字符串中每个字符读取一次磁盘，这是非常低效的。另一方面，如果您有一个使用线性探测的哈希表，则查找的成本将(大致)是一次磁盘读取的成本，因为在表中找到值应为数组的初始位置后，读取应该不需要将来的磁盘读取。
请注意，并非所有尝试和所有哈希表都具有此属性。高速缓存忽略尝试是专门为最大限度地减少磁盘读取而构建的尝试，并且在外部内存中速度非常快。许多哈希表，例如链式哈希表或双哈希表，具有更分散的查找模式，因此会产生更多的磁盘读取。
希望这有帮助!
关于performance - 当存储在磁盘上时，为什么尝试比哈希表慢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20708727/