HashSet中填充比率或負載因子概念的需求

Question

正如我研究過HashSet類，它使用填充比率的概念，它表示如果HashSet如果填充到此限制將創建更大的HashSet和複製值到它。爲什麼我們不讓HashSet充滿對象，然後創建一個新的HashSet？爲什麼要爲HashSet派生一個新概念？

Answer 1

ArrayList和Vector都通過位置索引訪問，所以沒有衝突，訪問總是O（1）。

基於哈希的數據結構被哈希值訪問，哈希值可能會碰撞並降級爲訪問第二級「溢出」數據結構（列表或樹）。如果你沒有這種衝突，訪問是O（1），但是如果你有很多衝突，它可能會更糟糕。你可以通過分配更多的內存來控制這一點（以便有更多的桶和希望更少的衝突）。

因此，不需要將ArrayList增長到超過需要存儲所有元素的容量，但在HashSet的情況下「浪費」一點（或很多）確實有意義。該參數被公開以允許程序員選擇對於其應用最適合的東西。

Answer 2

正如Jonny Henly所描述的那樣。這是因爲存儲數據的方式。

ArrayList是線性數據結構，而HashSet不是。在HashSet中，數據基於哈希碼存儲在底層數組中。在某種程度上，HashSet的性能與多少個桶被填充以及這些桶之間的數據分配有多好有關。一旦這種數據分佈超出了某個水平（稱爲加載因子），則重新哈希完成。

Answer 3

HashSet主要用於確保在恆定時間內執行基本操作（例如添加，讀取，修改和刪除），無論存儲在HashSet中的條目數量如何。

雖然設計良好的哈希函數可以實現這一點，但設計一個可能需要時間。因此，如果性能是應用程序的關鍵要求，那麼我們可以使用負載因數來確保操作在不變的時間內執行。我認爲我們可以將這兩者都稱爲冗餘（負載因子和散列函數）。

我同意這可能不是一個完美的解釋，但我希望它確實爲這個問題帶來了一些清晰。