散列表大小對訪問速度的影響

Question

我在面試論壇上閱讀了這個問題&我不確定答案。請幫助我。在訪問速度方面有多個小哈希表或一個大哈希表是否更好（假設兩者都適合RAM）？我認爲答案應該是;兩者的性能都與訪問時間相同。但我對多個小哈希表感到困惑。

Answer 1

這樣的問題取決於很多因素，如哈希函數的實現以及如何選擇哪個表。

一般來說，如果兩者都適合內存，速度應該是可比的。哈希表需要一個鍵，將其轉換爲數字，然後查找該值。對於多個小表，您必須選擇哪個哈希表，以便添加額外的圖層。另一方面，現代計算機體系結構在RAM中具有多級緩存，所以一個小的散列表可能在緩存中，使訪問更快。