問題タブ [hashset]

上記のプログラム出力が 3 なのはなぜですか?

編集

以下のコメントを見て、質問を拡張しています：

System.out.println (s1 == s2);

s1 と s2 は同じオブジェクトを参照していますか? 上記のステートメントは true を出力するはずですが、その出力は false です。

ハッシュコードに関しては似ていますが、それでも違いますか?

現在、ハッシュセットに問題があります。不変で1つのアイテムしか含まないクラスがあります。同じデータを持つ2つの異なるクラスをハッシュセットに追加すると、両方がセットに含まれます。基本クラスとスーパークラスの両方でEqualsとGetHashCodeをオーバーロードしたため、これは奇妙です。

そして、継承するクラス：

ご覧のとおり、実際の作業はすべて、IDであるBigIntegerに延期されます。これは.netクラスであり、BigIntegerをハッシュセットに追加するだけで重複しないことを確認しました。

明確にするために：

値の重複を許可しないという事実を除けば、とHashSetの違いは何ですか?HashMapHashSet

私は賢明な実装を意味しますか？どちらもハッシュ テーブルを使用して値を格納するため、少しあいまいです。

このコードの実行:

値 100 を出力します。

なぜこの値を出力するのですか?

免責事項：この質問に対する完全に明白な答えはHashSet<string>. それはとてつもなく速く、順序付けられておらず、その値は一意です。

しかし、私はちょうど疑問に思っています.なぜならHashSet<T>、それは変更可能なクラスなので、、、AddなどがありますRemove; したがって、これらの操作を可能にする基礎となるデータ構造が、読み取り操作に関して特定のパフォーマンスを犠牲にするかどうかはわかりません。特に、Contains.

基本的に、 type のオブジェクトのメソッドを提供できる、存在する絶対的に最速のデータ構造は何だろうと思っています。.NET フレームワーク自体の内外。Containsstring

制限に関係なく、あらゆる種類の答えに興味があります。たとえば、ある構造が特定の長さの文字列に制限されたり、問題の領域 (たとえば、可能な入力値の範囲) に応じて最適化されたりする可能性があると想像できます。存在する場合は、それについて聞きたいです。

最後に 1 つ: これを読み取り専用のデータ構造に限定しているわけではありません。明らかに、読み取り/書き込みデータ構造は、読み取り専用ラッパー内に埋め込むことができます。「読み取り専用」という言葉に言及した唯一の理由は、データ構造に追加、削除などを許可する必要がないからです。ただし、それらの機能があれば文句は言いません。

更新：

モロンの答えは、私が探している種類のものの優れた例です。Trie *は、次の理由から間違いなく大きな可能性のように思えます: someHashSet<T>.Containsの機能に依存します。これは、私が知る限り、.NET ではデフォルトで O(n)** です。つまり、文字列内のすべての文字を調べて、 またはを返す必要があります。a の場合、 の戻り値のみが O(n) を使用して決定されます。の戻り値は、はるかに迅速に返される可能性があります。GetHashCodeIEqualityComparer<string>HashSet<string>.Containstrue falseTrietruefalse

これはもちろん仮説です。HashSet<string>これまでのところ、a at に勝る .NET の Trie 実装を書いたり、見つけたりしたことはありませんContains(ただし、自分で書いた実装は、アルファベット 'a' から 'z' に非常に近いものでした)。私はただ言っている、それは可能だと思われる.

_{*ちなみに、そのリンクは、別の興味深い/同様の可能性にもつながりました: DAWG .
**ここで「n」は文字列の長さを指しています。}

さて、私はしばしばある種のセットを返すメソッドを持っています。このようなメソッドの単体テストの問題は、セットに対する反復が常に同じ順序でアイテムを返すという保証がないことです。

セットを検証するための好ましい方法はありますか？

ピーター

Dictionary<Key, Value>に変換する最短の方法を提案してくださいHashset<Value>

IEnumerables用の組み込みのToHashset（） LINQ拡張機能はありますか？

前もって感謝します！

データベースから (Hibernate を使用して) レコードをフェッチし、Vector. 操作のパフォーマンスに問題があったため、 を にVector置き換えてテストを行いましたHashSet。300000 レコードの場合、スピードの向上は計り知れません - 45 分から 2 分!

私の質問は、この大きな違いの原因は何ですか? のすべてのメソッドが同期されているという点だけですか、それとも配列Vectorを内部的に使用しているのに使用していないという点ですか? または、他の何か？VectorHashSet

コードはシングル スレッドで実行されます。

EDIT : コードはVector(およびその他の場合はHashSet) に値を挿入するだけです。

ネストされたハッシュセット内でサブセットの複数の組み合わせを見つけなければならないという問題があります。基本的に、「マスター」のネストされたHashSetがあり、「可能な」ネストされたHashSetのコレクションから、「マスター」の同時サブセットである可能性のある「可能性」をプログラムで見つける必要があります。

私が次のものを持っているとしましょう：

アルゴリズムから取得する必要がある出力は次のようになります。

すべての可能な組み合わせサブセット:

私はこれにアプローチする最善の方法を見つけようとしています。もちろん、力ずくのオプションもありますが、できればそれを避けようとしています。

私の質問が十分に明確であることを願っています。

編集

サブセットを構成するものをさらに詳しく説明するために、マスター {{"A","B","C"},{"C","D","E",F"},{ "X","Y","Z"}} :

• {{"A","B"}{"C","D"}} は、
• {{"A","B","C"},{"X","Y"}} はサブセットになります
• {{"A","B"},{"A","B"}} はサブセットではありません
• {{"A","B","C","D"}} はサブセットではありません
• {{"A","B","C"},{"C","D","X"}} はサブセットではありません

基本的に、各子セットは、マスター内の対応する子のサブセットである必要があります。

解決策が見つからない問題が発生しました。値を格納するために HashSet を使用しています。私が保存する値はカスタムタイプのCyclesであり、HashCodeとequalsを次のようにオーバーライドして、パフォーマンスの低下がhascodeまたはequalメソッドによって引き起こされていないことを確認しますまた、ハッシュセットの初期容量を10.000に設定しました.000

(HashSet クラスの add メソッドを使用して) 新しい値を追加しようとすると、最初の 1.500.000 の最初の値の後、プログラムは非常に遅くなります。最終的に、格納された値が 1.600.000 に達する前に、Java のメモリ不足例外 (スレッド "Thread-0" java.lang.OutOfMemoryError: Java ヒープ領域の例外) が発生します。

私が使用するIDEはEclipseです。したがって、次のステップは、JVM ヒープ サイズをデフォルト値から 1 ギガに増やすことでした (コマンド Xmx1000M および Xms1000M を使用)。これで、楕円が 10 倍のメモリを使用して開始されます (右下で合計ヒープ サイズが表示されていることがわかります)。メモリと使用済みメモリが表示されます）が、以前と同じ「遅い」パフォーマンスと同じ値のメモリ不足エラー（1.500.000の後と1.600.000の前）があり、非常に奇妙です。

誰がそれが問題である可能性があるか考えていますか?

前もって感謝します