データ構造に数百の文字列を格納する必要があります。すべての文字列には、単語の意味とその起源など、2 つのフィールドが関連付けられています。並べ替え、逆並べ替えなど、任意の方法で単語を保存できます。
ディクショナリ内の文字列をできるだけ早く検索し、関連する 2 つのフィールドをフェッチするだけです。可能であれば、バイナリ検索よりも優れた検索を行いたいと思っています。
私はJavaを使用しています。どちらを使用する必要がありますdata structureかCollection Class?
注：これでデータベースを使用したくありません。
を使用できますHashMap<String,MyDataObject>- 使用するのが最も速く、最も簡単です。
平均シーク時間は ですO(|S|)。ここ|S|で、 は文字列の長さです。
トライまたは基数ツリーを試して使用することもできますが、HashMap作業を開始する前に、ソリューションのプロファイリングを行って時間を確保するようにしてください。
明白な答えは「を使用するHashMap」ですが、警告がないわけではありません。検索するすべての文字列のハッシュコードを計算する必要があります。毎回新しいオブジェクトを使用する場合、毎回 O( s ) (この場合はsは文字列の長さ) に加えて、小切手に O( sequals ) を支払います。
これを回避する 1 つの方法はintern、検索に使用するすべての文字列を対象にすることです。これにより、一度計算されたハッシュコードが確実に再利用され、その後のequalsチェックも省略されます。
もう 1 つのオプションは、triを使用することです。その利点は、最大で O( s ) を支払うことですが、通常はそれより少なくなります。プレフィックス ベースの検索であるため、プレフィックスが一意であるポイントまでたどるとすぐに結果が得られます。
結論として、interned文字列を再利用できる場合は、ハッシュコード ベースのソリューションが最適です。そうでない場合は、試行が優れた選択肢です。
その他の一般的なオプションは、スキップ リスト (Lucene で使用) と B-tree (データベース インデックスで一般的) です。
Trieデータ構造を使用することをお勧めします。私はこれに似た課題を行いました。このリンクは、Trie DS の実装に役立ちます。
HashTableまたは_HashMap
構造は次のようになりますHashMap<String,Bookcontent>
BookContent属性単語の意味と起源を持つクラスはどこですか