什麼是確定值是否在Java中的一組值中的最快方法？

這可能是您JAVA專家的一個簡單問題，但我比較新，所以我想我會問。我需要測試字符串X是否存在於一個集合中。我不需要任何關聯的值或索引，我不需要任何訂單。我只需要知道它是否存在。我知道這可以使用HashMap或ArrayList來實現，但這些看起來過度。該怎麼辦？只是一個列表？還是有更基本的東西可以達到同樣的目的。測試給定集合中是否存在某個字符串X的最快方法是什麼？什麼是確定值是否在Java中的一組值中的最快方法？

來源

2012-02-17 meesterguyperson

集合有多大？如果不用真實的數據進行基準測試，您無法確定最快的解決方案。 – DNA 2012-02-17 22:14:26

聽起來像是你想有一個HashSet<String>：

Set<String> set = new HashSet<String>(); 
set.add("foo"); 
set.add("bar"); 

boolean no = set.contains("baz"); 
boolean yes = set.contains("foo");

還有其他Set實現可用，當然，但HashSet可能是最合適的位置。

來源

2012-02-17 21:51:36

我們實際上使用了幾乎相同的字符串名稱;） – Jack 2012-02-17 21:53:41

您不只有ArrayList和HashMap，JDK帶有很多種類，您可以在其中找到您要查找的內容：集合。

其中之一例如是HashSet，其中有您正在尋找有關功能..

Set<String> set = new HashSet<String>(); 

set.add("foo"); 
set.add("bar"); 

boolean b = set.contains("foo");

來源

2012-02-17 21:53:18 Jack

import java.util.Arrays; 

... 

if (Arrays.asList("foo", "bar", "baz").contains(myString)) { 
    ... 
}

來源

2012-02-17 21:54:44 gpeche

這樣做效率不高，因爲與HashSet（常量O（1））或TreeSet（我猜O（logn ）如果我沒有記錯的話） – Jack 2012-02-17 21:55:50

@Jack對於非常小的集合（比如<5），它將會高效並且更容易編寫。當然，這不是一個通用的解決方案，但提問者認爲一般的解決方案無論如何都是「矯枉過正」。 – gpeche 2012-02-17 22:02:00

你們都是對的 - 但是OP需要用適當大小的套件進行基準測試！ – DNA 2012-02-17 22:16:09

我知道，這可以用一個HashMap或ArrayList的實現，但這些似乎矯枉過正。

究竟什麼是「大材小用」關於使用被設計做的正是你想要的一個內置類，並做到這一點非常快？因爲這就是HashMap是。 HashSet在它的接口（未映射的值）中會更加基本一些，但實際上它通過具有空值的HashMap來實現。

來源

2012-02-17 21:56:00

好吧，'HashMap'被設計爲將鍵映射到值，這比OP想要的更多*因爲他只需要「存在」。另一方面，'HashSet' – 2012-02-17 21:59:34

幾個答案建議HashSet，其他人指出，簡單的集合可能會更快的小集 - 你沒有說什麼大小的集合。

字符串的大小也是相關的，因爲HashSet等將使用字符串的哈希碼，它是從字符串的整個內容（然後緩存）計算出來的。這可能需要一點時間 - 但另一方面，它可能已經被計算，取決於你的代碼，所以不會產生額外的成本。

在某些情況下，您可以通過字符串的大小或通過檢查前幾個字符來排除字符串 - 它取決於您的數據和字符串集。數據結構（如Trie）在這裏可能很有用 - （但您想要一個簡單的解決方案）。

如果性能至關重要，那麼您需要在現實條件下仔細對所有建議的解決方案進行基準測試。請參閱How do I write a correct micro-benchmark in Java?

如果您確實需要快速解決方案（這對您的應用程序實際上是否至關重要？），那麼您可能需要忍受「矯枉過正」！

來源

2012-02-17 22:24:57 DNA

不要使用含有使用Collections.binarySearch（列表，對象）

不要忘了排序使用此方法集合之前。排序（列表）

來源

2012-02-17 22:46:02 Ramu

什麼是確定值是否在Java中的一組值中的最快方法？

回答

相關問題