Java集幷包含

HashSet爲基本操作（添加，刪除，包含和大小）提供恆定的時間表現。

這裏'包含'是真的嗎？儘管篩選桶是一個容量時間表現 - 沒有發現桶內的元素是一個o（n）操作嗎？

我誤解了什麼嗎？

2013-03-29 IUnknown

你需要看看應對衝突的主要散列策略：列表鏈和開放尋址。瞭解他們如何工作，你會明白爲什麼「包含」在平均不變的時間內工作。例如，請參閱：http://en.wikipedia.org/wiki/Hash_table#Separate_chaining。如果你想要一些正式的東西，你總是可以閱讀Knuth的「計算機編程的藝術，第3卷'排序和搜索'」。 – naitoon

爲了回答所有這些問題和類似的問題，我在[Java的HashSet的內部生活]上有教程（http://volodial.blogspot.com/2013/07/internal-life-of-hashset-in-java.html） –

n in o（n）表示散列中元素的數量，而不是存儲桶中的元素數量。並且由於桶內的元素數量不隨着集合的大小線性增長而受到限制，因此可能需要一個恆定的最大時間。並且常數不會影響符號。至少如果你有一個完美的哈希函數，這完全是另一個問題。

來源

2013-03-29 05:44:58 fdreger

現在我明白了 - 所以'恆定時間'並不意味着ao（1）就像添加或刪除一樣。 – IUnknown

HashSet使用hasing功能來定位元素。評估它是O（1）。

例如，如果我們有一個存儲僱員姓名的哈希表中，我們將使用功能ASCII字符在它的總和：

f(name) = sum(ascii chars)

和 F（艾哈邁德·'）=' a'+'h'+'m'+'e'+'d'= 97 + 104 + 109 + 101 + 100 = 511. 因此，'ahmed'將被存儲在位置511. 然而，函數非常糟糕，當使用產生相同總和的名稱進行評估時會導致很多衝突。因此，在散列表實現中尋找一個好的散列函數是非常關鍵的目標。

有關更多信息，請參閱Hash Table數據結構。

來源

2013-03-29 05:29:30

是的，它是finding the elements within the bucket a o(n) operation。
contains操作性能爲O（n）。它將目標對象與HashSet中的所有其他對象對齊。

來源

2013-03-29 05:35:37

隨着documentation說，

這個類提供了固定的時間表現爲基本操作（添加，刪除，包含和大小），假定哈希函數將適當分散的元素桶之間

檢查上面的假設部分。如果所有元素都在一個桶中結束，那麼包含就是o（n），這將是世界上最差的散列函數之一。 HashSet內部使用HashMap。

來源

2013-03-29 05:39:20 Adi

顧名思義HashSet通過hasing技術實現。所以這意味着查找對象的複雜度是O（1）。這就是爲什麼contains需要O（1）次。但在最壞的情況下，如果所有對象都放在同一個桶中，那麼複雜度將爲O（n）。

如果此集合包含指定的元素，則返回true。更正式地說，當且僅當這個集合包含一個使得（o == null？e == null：o.equals（e））的元素e時才返回true。

public boolean contains(Object o) { 
    return map.containsKey(o); 
}

以上是含有來自HashSet的類的方法。請注意，它使用地圖來存儲對象。

來源

2013-03-29 05:47:35

找不到桶內的元素一個o（n）操作？

這真的取決於。如果有很多散列衝突算法必須通過每個值並檢索您感興趣的算法，則最壞情況下的時間爲o（n）。但是，它根本就不是一個好的散列函數。一個好的散列函數在整個範圍內均勻分配散列值。

如果您始終返回相同的hashCode，這也可能發生，這也不是一個好兆頭。無論該集合的基數如何，這會給你相同的散列值。

來源

2013-03-29 05:52:59

回答

相關問題