Java中contains（）的最快數據結構？

Java中對contains（）有最快操作的數據結構是什麼？Java中contains（）的最快數據結構？

例如我有一組數字{1，7，12，14，20 ...}

給定另一個任意數字x，生成布爾值是否包含在x中的最快方式（平均）是否設置？！contains（）的概率大約高出5倍。

所有的地圖結構都提供o（1）操作嗎？ HashSet是最快的方法嗎？

來源

2010-07-16 codechobo

102

查看set（Hashset，enumset）和hash（HashMap，linkedhash ...，idnetityhash ..）的實現。他們有O（1）for contains（）

This cheatsheet有很大的幫助。

來源

2010-07-16 17:57:43

對於什麼是值得的，當散列衝突發生時（通常情況下，如果一次只有很少的情況下它們會發生），散列映射通常不是O（1）查找。最壞的情況是O（n）查找。 – Blindy 2010-07-17 07:27:05

我同意Blindy。基於散列的收集性能受散列函數性能的限制。 – sbidwai 2010-07-17 07:42:33

我最近去的時候，網站已經關閉了。如果發生這種情況，您可以使用此[鏈接]（http://web.archive.org/web/20120105103844/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2。 pdf） – EasilyBaffled 2013-04-28 18:17:01

-2

散列（哈希集合）是最好的一個用O（1）

來源

2010-07-16 18:07:10 Satish

答案與Pangea之間有8分鐘的時間。你的增加沒有額外的價值，爲什麼張貼它？ – 2010-07-16 18:12:04

@bart真實緩慢的互聯網連接 – Will 2010-07-16 18:49:35

@也許會。如果是這樣，那麼@Satish現在有足夠的時間去除他/她多餘的答案。然而，他/她選擇讓它垂涎。也許希望收集一些觀點？也許這是開始的意圖，誰知道？ – 2010-07-16 18:52:55

對於數字的你的具體情況具有相對高密度的我會使用一個位集合，它會比一個哈希更快，更小組。

來源

2010-07-16 22:15:20 starblue

唯一比HashSet更快的數據結構可能是來自Trove4J的TIntHashSet。這使用基元來避免使用整數對象。

如果整數的數量很少，您可以創建一個布爾值[]，其中每個存在的值都變爲「true」。這將是O（1）。注意：HashSet不保證是O（1），更可能是O（log（log（N）））。

你只會得到一個理想的散列分佈的O（1）。但是，您更有可能會碰到散列桶，並且有些查找需要檢查多個值。

來源

2010-07-17 07:23:45

Java中contains（）的最快數據結構？

回答

相關問題