異なる文字列のみを格納する効率的な方法/構造

Question

現在、多くの文字列（+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？ありがとう！

Answer 1

アルファベット順に単語を維持することは重要ではない場合は、単にHashSetを使用してください。それはあなたがO（1）の任意の要素を取得することを可能にし、重複を作成することを心配することなく、単語をセットに追加することができます。

ハッシュコレクションの唯一の問題は、それらを反復処理するとき自然な順序を維持しないことです。言い換えれば、HashSetは単語をアルファベット順に出力しません。

ご注文がアプリケーションにとって重大なものである場合は、TreeMapまたはTrieを使用することをお勧めします。それらは両方ともいくつかの特性と基本構造を共有しますが、Trieは文字列に最適化されています。

複雑すぎることを避けたい場合は、コレクションフレームワークの一部であるTreeMapを使用します。

しかし、あなたのパスの効率を上げるためには、探しているデータ構造がTrieである必要があります。要約すると

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

、トライはあなたがアルファベット順に文字列を格納することを可能にするデータ構造です。単語が非常に迅速に見つからないことを検出できるので、非常に強力です。

"foo"という単語が存在するかどうかを確認したい場合は、ツリーにない場合は追加します。

ウィキペディアの記事からわかるように、Trieのルートノードには空のStringが含まれています。 fooという単語がTrieにあるかどうかを判断する最初のアクションは、ルートノードに文字列 "f"を持つ子ノードがあるかどうかをチェックすることです。そうでない場合は、その単語があなたのトライに含まれていないことをすでに知っており、操作を行っただけです。

一方、ルートノードに文字列 "f"を持つ子がある場合は、このノードに文字列 "fo"の子があるかどうかをチェックする必要がありますトライにはありません。そうであれば、最終的に "fo"ノードに "foo"という名前の子があるかどうかを確認します。

要約すると、Trieはあなたが探しているものであり、自然な順序を維持しながら単語の存在を効率的に挿入して確認することができます。

このフォーラムの投稿では、トライの実装を見ることができますので、ホイールを再開発する必要はありません。

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

まとめると：

• を私は特定の順序を維持することを気にしない：私はアルファベット順に単語を維持することを気にして私が欲しいのHashSet
• を使用シンプルなソリューションでも、最も効率的ではない場合でも：TreeMapを使用してください。
• アルファベット順を維持する必要があります。パフォーマンスは重要です.Trieを使用してください。