HashSet大小操作

Question

HashSet常量時間操作的大小操作如何？
我讀過包含和大小操作是恆定的時間。
雖然我明白如何包含恆定時間的操作，不會將大小操作與元素數量成比例（不是線性）？

Answer 1

簡短的回答 - 它被緩存了。

較長的答案： HashSet是Set實現，持有HashMap，所有的值是相同的「虛擬價值」。這是size()方法只返回地圖的size()。如果你看看HashMap的實現，你會發現它有一個size成員。將元素添加到地圖（例如，使用put或putAll）可增加size，並從中刪除元素可減少size。這樣，因爲size始終保持最新狀態，所以在調用size()時可以簡單地返回，保證持續執行時間。

Answer 2

HashSet內部存儲它有多少個元素。

wouldnt size operation是否與元素數成比例（非線性）？

如果沒有存儲在現場記錄保存，大小（）將正比於後盾哈希表的大小，而不是元素的數量，因爲你必須在掃描所有的條目，看看是否有東西。除了散列表被分配爲顯着太大或者刪除了很多元素之外，這些往往是相同的（2倍以內）。