只有存儲不同字符串的高效方法/結構

我目前正在使用大量字符串（+2000）的java應用程序中工作。我想將這些字符串存儲在適當的結構中，所以當我想存儲一個新的字符串時，如果同一個字符串已經存在，我可以快速檢查。如果結構中沒有相同的字符串，我繼續存儲新的（基本上不用重複字符串存儲）。。只有存儲不同字符串的高效方法/結構

//PSEUDOCODE 
private ?????? myCollectionOfStrings; 

public void store_If_Not_Exist(String aNewString){ 
    if (!exist_in_Collection(aNewString)){ //this must be fast. 
     store_in_Collection(aNewString); 
    } 
}

我目前用天真的實現，但我知道這是真的效率低下：

private List<String> myCollectionOfStrings; 

public void store_If_Not_Exist(String aNewString){ 
    boolean existInCollection = false; 

    for (String s: myCollectionOfStrings){ 
     if (s.equals(aNewString)){ 
      existInCollection = true; 
      break; 
     } 
    } 

    if(!existInCollection) 
     store_in_Collection(aNewString); 
}

的問題是：什麼樣的方法/結構/算法可我用來存儲字符串，所以檢查存在可以快速實現？也許一個Trie樹，或者一個HashMap ???。謝謝！

來源

2016-04-22 joradev

使用'Set '。但是通過散列碼查找的任何東西都是相對有效的。 2000年並不是那麼大。當然，我認爲你正在尋找一個直接匹配，而不是詞幹，複數等等。實際上，使用'Set'將允許繞過檢查，因爲只有一個實例存在。 – KevinO

您正在尋找一個Set數據結構。在Java中，'HashSet'。它有一個元素的O（1）查找時間。 –

使用'HashSet'，非常快速 – Bohemian

如果按字母順序維護這些單詞並不重要，那麼只需使用HashSet即可。它允許您檢索O（1）中的任何元素，並且您可以將該單詞添加到該集合中，而無需擔心創建重複項。

哈希集合的唯一問題是，當您迭代它們時，不保持自然順序。換句話說，HashSet不會按字母順序打印您的單詞。

如果順序對您的應用程序至關重要，我的建議是您使用TreeMap或Trie。它們都具有一些特徵和基本結構，但Trie針對字符串進行了優化。

如果您不想過分複雜化，請使用屬於集合框架一部分的TreeMap。但是，如果您想要在效率方面走更多路，那麼您正在尋找的數據結構就是Trie。

https://en.wikipedia.org/wiki/Trie

總之，特里是一個數據結構，它允許你存儲字母順序串。它非常強大，因爲它可以讓你發現一個單詞很快就失蹤了。

想象一下，你想檢查單詞「foo」的存在，如果它不在你的樹中，你想要添加它。

正如您在wikipedia文章中看到的，Trie的根節點包含一個空字符串。確定foo是否在Trie中的第一個操作是檢查根節點是否具有帶字符串「f」的子節點。如果沒有，你已經知道這個詞不在你的Trie中，而你只做了一個操作。

另一方面，如果根節點有一個字符串爲「f」的孩子，那麼你必須檢查這個節點是否有一個字符串爲「fo」的孩子，如果沒有，你的字不在線索中。如果是這樣，最後檢查「fo」節點是否有名爲「foo」的子節點。

總結一下，Trie正是您所需要的，它將允許您在保持自然順序的同時有效地插入和檢查單詞的存在。

在這個論壇帖子中，你可以看到一個trie的實現，所以你不必重新發明輪子。

https://community.oracle.com/thread/2070706

綜上所述：

我不關心保持一個特定的順序：用一個HashSet
我關心維護字母順序的話，我想一個簡單的解決方案，即使它不是最高效的：使用TreeMap
我需要保持字母順序，性能至關重要：使用Trie。

來源

2016-04-22 18:05:19

謝謝!!，這是非常翔實的。我不關心訂單，所以我會使用HashSet。 – joradev

只有存儲不同字符串的高效方法/結構

回答

相關問題