使用填充的ArrayList初始化HashSet的時間複雜度是多少？

我在線閱讀HashSet使用HashMap作爲其基礎數據結構。使用填充的ArrayList初始化HashSet的時間複雜度是多少？

而且HashMap使用ArrayList作爲其底層的數據結構與每個項目在列表是LinkedList或tree的對象。

什麼時間複雜度，當你初始化HashSet這種方式？它可以是O（1）？如果不是，爲什麼？

List<Integer> list = new ArrayList<>(); 
list.add(1); 
list.add(3); 
list.add(2); 
list.add(6); 
list.add(0); 
HashSet<Integer> set = new HashSet<>(list);

來源

2017-05-23 Tech Guy

你的標題說'HashMap'，但你的代碼演示初始化'HashSet'。 –

感謝您指出。我已經更新了這個問題。 –

HashMap不使用ArrayList作爲其底層的數據結構。

HashMap維護一個構建在原始數組之外的散列表，並使用鏈表或樹的混合策略來處理衝突。你可以通過檢查source code for java.util.HashMap來看到這一點。

因爲，建立一個哈希表，你需要調用每個條目的哈希函數來確定哈希的位置，勢必最小爲O（N）。最壞的情況是病理分佈的密鑰（例如，每個密鑰都是碰撞），這將比O（N）嚴重得多。由於Java 8實現在最壞的情況下降級爲平衡樹而不是鏈表，所以最壞情況下的運行時間爲O（N log N）。（在使用線性探測的Java以前的版本中，我認爲最糟糕的情況應該是O（N ²））。

來源

2017-05-23 20:15:33

java8中的默認實現不使用探測，它使用小型桶（最多8個項）的鏈接列表和更大桶的樹。 –

@ k5_：就這樣。看起來Java 8的實現比Java 7或更早的版本要複雜得多。我已更新我的答案，謝謝。 –

@DanielPryden，感謝您的解釋。我將研究源代碼。 –

您的List可以包含n可能全部重複或全部唯一或混合的對象數。

HashSet集合的屬性是它不包含重複的對象。

因此，時間複雜度遍歷List並添加每個對象到HashSet將O(n)

來源

2017-05-23 20:16:24

使用填充的ArrayList初始化HashSet的時間複雜度是多少？

回答

相關問題