4

整数のセットに値を割り当てる辞書が必要です。

たとえば、特定の値がありkeyます[1 2 3]。value

問題は[3 2 1]、私の場合は同じように扱う必要があるため、ハッシュアプ​​ローチを使用する場合は、ハッシュが等しくなる必要があるということです。

セットには2〜10個のアイテムが含まれます。

アイテムの合計は通常固定されているため、合計に従ってハッシュコードを作成することはできません。これは、ここでの最初の自然なアイデアです。

宿題ではなく、実際に私のコードでこの問題に直面しています。

このセットは基本的IEnumerable<int>にC＃であるため、どのデータ構造でも保存できます。

助けていただければ幸いです。ここでもパフォーマンスは非常に重要です。

すぐに考えてみてください。要約するitems^2と、すでに何らかの優れたハッシュを取得できますが、それでもいくつかの考えを聞きたいと思います。

編集：うーん、本当に申し訳ありませんが、誰もが注文を提案していますが、実際に注文とハッシュが現在使用しているソリューションであり、より高速な代替案を検討していると言う必要があるとは思いませんでした。

4

9 に答える 9

5

基本的に、ここでのアプローチはすべて同じテンプレートのインスタンス化です。x 1 , …, x nを f(x 1 ) op … op f(x n ) にマップします。ここで、op は集合 X に対する可換結合操作であり、f はアイテムから X へのマップです。このテンプレートが使用されています。証明できるほど良い方法で数回。

  • [1, p - 1] 内のランダムな大きな素数 p とランダムな留数 b を選択します。f(x) = b x mod p とし、op を加算とします。基本的に、集合を多項式として解釈し、シュワルツ・ジッペルの補題を使用して衝突の確率 (= ゼロでない多項式が p を法とする根として b を持つ確率) を制限します。

  • op を XOR とし、f をランダムに選択されたテーブルとします。これはZobrist ハッシングであり、単純な線形代数引数によって予想される衝突の数を最小限に抑えます。

累乗剰余は遅いので、使用しないでください。Zobrist ハッシュに関しては、300 万の項目があるため、テーブル f はおそらく L2 に収まりませんが、1 回のメイン メモリ アクセスの上限が設定されます。

代わりに、出発点として Zobrist ハッシュを使用し、ランダム関数のように動作する安価な関数 f を探します。これは基本的に、非暗号化疑似乱数ジェネレーターの仕事内容です。高速な PRG に x をシードして 1 つの値を生成することで、f を計算してみます。

編集: セットがすべて同じ合計を持っていることを考えると、f を 1 次多項式 (たとえば、線形合同ジェネレーターのステップ関数) に選択しないでください。

于 2011-11-18T22:03:28.857 に答える
2

を返すHashSet<T>and を使用します。HashSet<T>.CreateSetComparer()IEqualityComparer<HashSet<T>>

于 2011-11-18T20:50:09.960 に答える
2

この論文で言及されていることは間違いなく役立つと思います：

http://people.csail.mit.edu/devadas/pubs/mhashes.pdf

増分マルチセット ハッシュ関数とそのメモリ整合性チェックへの応用

要約: 新しい暗号化ツールであるマルチセット ハッシュ関数を紹介します。文字列を入力として受け取る標準​​のハッシュ関数とは異なり、マルチセット ハッシュ関数はマルチセット (またはセット) で動作します。これらは、任意の有限サイズのマルチセットを固定長の文字列 (ハッシュ) にマップします。それらは、新しいメンバーがマルチセットに追加されると、変更に比例して時間内にハッシュを更新できるという点で増分的です。関数は、同じハッシュを生成する 2 つのマルチセットを見つけるのが難しいという点でマルチセット衝突耐性があるか、または同じハッシュを生成するセットとマルチセットを見つけるのが難しいという点でセット衝突耐性があります。

于 2011-11-18T20:56:23.890 に答える
1

あなたの二乗のアイデアは正しい方向に進んでいると思いますが、機能の選択は不十分です。私は PRNG 関数のようなものを試したり、単に大きな素数を乗算したり、結果のすべての値の XOR を実行したりします。

于 2011-11-18T20:59:31.237 に答える
0

1 つの可能性: リスト内のアイテムを並べ替えてから、それをハッシュします。

于 2011-11-18T20:48:43.990 に答える
0

数値を並べ替えて、所定のインデックスからサンプルを選択し、現在の値の数値が少ない場合は残りをゼロのままにすることができます。または、それらをxorすることもできます。

于 2011-11-18T20:50:32.473 に答える
0

なぜ次のようなものではないのですか

public int GetOrderIndependantHashCode(IEnumerable<int> source)
{
    return (source.Select(x => x*x).Sum()
            + source.Select(x => x*x*x).Sum()
            + source.Select(x => x*x*x*x).Sum()) & 0x7FFFFF;
}
于 2011-11-18T21:43:18.930 に答える
-1

を実装する独自の型を作成しますIEnumerable<T>。

オーバーライドしGetHashCodeます。その中で、コレクションをソートし、 を呼び出して返しToArray().GetHashCode()ます。

于 2011-11-18T20:48:37.963 に答える