共通のプレフィックス（ファイルシステムパスに対応しない）を持つ数百万の文字列をメモリ内のSet like構造に格納し、コレクションにクエリを実行してパスが存在するかどうかを確認する必要があります。
例えば
/path
/path/1
/path/2
/path/1/a
/path/1/b
関係するすべての文字列に多くの共通のプレフィックスがあることを考えると、これらを可能な限り効率的に保存したいと思います（メモリ内にあります）。Trieは妥当な候補ですか？
Javaで適切なデータ構造を実装するための推奨事項を探しています。
Trieは、必要な構造のように見えます。同様の構造はRadix Triesで、試行とは異なり、一連の文字を使用してエッジにラベルを付けます。単純な試行では、エッジは単一の文字でラベル付けされています。文字列がかなり多くのプレフィックスを共有している場合、エッジの動作が改善されると確信しています。
も参照してください...
これは良い候補の実装のようです: https://github.com/rkapsi/patricia-trie
提案の前にトレードオフを考えてみましょう。
「何百万もの」パスを保存する必要があると言います。計算が簡単になるので、100 万と仮定します (サーバー上でさえ、100 万を超えるディレクトリは見たことがありません)。
それらのパスの長さはどれくらいですか? 非常に短いパスの例を示したので、それらの百万のパスを格納するためにおそらく 100 メガバイトを検討しています。パスの最大長についての参考文献はありませんが、256 文字が頭に浮かびます。したがって、パスは最大 512 Mb のメモリを必要とします。そんなに記憶あるの？
パス名はどの程度均等に分散されていますか? つまり、パスの 80% がディレクトリの 20% にあるという 80:20 のルールに従っていますか? 私が尋ねる理由は、トライ構造がレベル間に何らかの形式のインデックスを必要とするからです。ディレクトリの下にいくつかのパスしかない多くのディレクトリがある場合、トライを維持するために多くのオーバーヘッドが発生します。
推奨事項: 十分なメモリがあれば、aHashSet<String>を使用して、それで完了します。
大量のメモリがなく、ディレクトリ構造が 80:20 ルール (または、より可能性が高いのは 95:5) に従っていない場合は、HashMap<String,Set<String>>. このマップのキーは、「妥当な」量の重複がある最長の先頭パス文字列であり、値は残りの文字列になります。一致するものが見つかるまで、このマップを徐々に短くする主要コンポーネントでプローブし、次に残りのセットをプローブします。
そのため、「合理的な」複製の問題は未解決のままです。これは、2 ピースのデータ構造のオーバーヘッドが重複の削減によって克服される重複の量です。たとえば、/usr/bin/有効な場合があります (数千のファイルを保持し、それぞれから 9 文字または 18 バイトを節約するため) が、/usr/local/bin/おそらくそうではないでしょう (少なくとも私のシステムでは、単一のファイルしか保持しません)。
私が使用するもの：
ディスク上と同じように、ツリー構造を使用できます。ただし、ツリー構造は、節約できる分だけ多くのメモリをオーバーヘッドで使用できることを覚えておく必要があります。つまり、実際にはメモリを節約するようには設計されていません。
これらのファイルが存在する場合は、おそらくディスク サブシステムのキャッシュを使用できます。それはより速いかもしれません。
JVMに100万個のエントリを非常に快適に保存できるため、これを行う必要があることを確認します。;)
メモリの消費を最小限に抑えたい場合は、メモリ内のデータを圧縮できます。これは他のどのオプションよりもはるかに小さい可能性がありますが、効率的にするのはより複雑です。
パスをそのまま文字列として保存することをお勧めします。メモリを節約しようとするオーバーヘッドは逆になると思います。
もちろん、上記の Tries データ構造に対してベンチマークを行うことで、そうであるかどうかをテストするのは簡単です。