爲什麼在存儲在磁盤上時嘗試比散列表慢？

Question

我聽說當數據限制存儲在磁盤而不是主內存時，嘗試比散列表效率低。爲什麼會這樣呢？

Answer 1

在磁盤上，隨機存取速度很慢，因爲要讀取特定位置的字節，硬盤驅動器必須物理旋轉才能將這些字節放在讀取頭下。磁盤上隨機訪問的成本可能比同等訪問RAM慢數百萬倍。

最重要的是，無論何時從磁盤讀取數據，都會從磁盤中讀取稱爲頁的內存塊，而不僅僅是要求的字節。這意味着如果您從磁盤讀取一些數據，訪問該字節附近的字節可能會非常快，因爲該數據將從同一頁面讀取並加載到RAM中。這意味着磁盤陣列中的順序存取速度會很快，因爲在第一次（緩慢）讀取以獲取讀取第一個數組元素的字節後，下一個數組元素的字節可能已經被加載並可用。

想想這對於嘗試與線性探測哈希表意味着什麼。一個trie是一個樹結構，在這個結構中，查找需要很多指向內存中沒有特定順序的節點的指針。這意味着查詢字典查找的成本可能是字符串的每個字符讀取的一個磁盤，這非常低效。另一方面，如果你有一個使用線性探測的散列表，查找的代價將（大致）成爲一個磁盤讀取的成本，因爲在查找表中的初始位置後，數組應該是數組讀取的位置不需要將來的磁盤讀取。

請注意，並非所有嘗試和所有散列表都具有此屬性。緩存遺忘嘗試是特別構建的嘗試，以最大限度地減少磁盤讀取，並且在外部存儲器中可以非常快速。許多散列表（如鏈式散列表或雙散列表）具有更分散的查找模式，因此會導致更多的磁盤讀取。

希望這會有所幫助！