3

同じ要素を含む順序付けられていないシーケンスに対して同じ結果を生成するハッシュ関数を探しています。

例えば：

Array_1: [a, b, c]
Array_2: [b, a, c]
Array_3: [c, b, a]

ハッシュ関数は、これらの配列のそれぞれに対して同じ結果を返す必要があります。

これを達成する方法は？

最も一般的な答えは、要素を何らかのルールでソートし、連結してからハッシュを取得することです。

他の方法はありますか？

4

2 に答える 2

1

a、b、c が数値の場合、合計して、その合計に対してハッシュを作成できます。あなたも増えるかもしれません。ただし、ゼロには注意してください。XOR-ing数値もアプローチです。

非常に小さい数値の場合は、数値でインデックス付けされたビットを設定することを検討できます。これは、ハッシュの入力として long (64 ビット) を構築すると、0 ～ 63 の範囲の要素番号のみが許可されることを意味します。

要素が多いほど、衝突が多くなります。最後に、 mビットのn要素(結果として 2^(m*n) の範囲) をkビットのハッシュ値にマップします。通常、m と k は定数ですが、n は変化します。

ハッシュによるアクセスには、正しい要素を取得するかどうかのテストが必要であることに注意してください。一般に、ハッシュは一意ではありません。

それ以外の場合は、要素を並べ替えてから、提案どおりにハッシュを実行します

CodesInChaos からのコメントについて:

テストを省略できるようにするために、ハッシュのビット数は要素ビットの合計よりもはるかに大きくする必要があります。少なくとも 64 ビット以上と言います。一般に、この状況は与えられません。

安全なハッシュ/一意の ID の一般的なケースの 1 つは GUID です。これは事実上 128 ビットを意味します。テキスト char のランダムなシーケンスは、20 ～ 25 文字以内でこのビット数に達します。テキストが長いと、衝突が発生する可能性が非常に高くなります。これが許容できるかどうかは、ユースケースによって異なります。

于 2012-12-12T20:30:07.513 に答える
0 
XOR | Sum | Sum of squares | ...

ここで| concatを示します。

また

XOR of hash of elements
于 2012-12-15T16:17:27.713 に答える