使用動態數組處理散列表中的衝突

Question

環顧一些散列表實現，單獨的鏈接似乎通過鏈接列表或樹來處理。爲什麼不使用動態數組有沒有原因？我會想象有一個動態數組也會有更好的緩存性能。但是，因爲我沒有看到任何這樣的實現，所以我可能錯過了一些東西。

我錯過了什麼？

Answer 1

鏈接列表相對於動態數組的一個優點是重新散列可以更快地完成。不需要製作一堆新的動態數組，然後將舊動態數組中的所有元素複製到新的元素中，鏈接列表中的元素就可以重新分配到新的桶中，而無需執行任何分配。

此外，如果加載因子很小，則使用鏈接列表的空間開銷可能會好於動態數組的空間開銷。使用動態數組時，通常需要存儲指針，長度和容量。這意味着如果你有一個空的動態數組，你最終需要兩個整數和一個指針的空間，再加上任何預分配的空間來存放元素。在一個空的桶中，這個空間開銷很大，與僅爲鏈表存儲空指針相比。另一方面，如果存儲桶中有大量元素，那麼動態數組由於參考的局部性將會更加節省空間並且具有更高的性能。

希望這會有所幫助！

Answer 2

我能想到的一個優點是刪除..加法是在哈希的頭部完成..如果我想刪除哈希值，它將是困難的數組，因爲它可能存在於陣列的中間。