15

特定の範囲（通常は0から約1000）の番号があります。アルゴリズムは、この範囲からいくつかの数値を選択します（約3から10の数値）。この選択は非常に頻繁に行われるため、選択した数値の順列がすでに選択されているかどうかを確認する必要があります。

たとえば、1つのステップが選択[1, 10, 3, 18]され、別のステップが選択されると[10, 18, 3, 1]、2番目の選択は順列であるため破棄できます。

このチェックを非常に速く行う必要があります。今、私はすべての配列をハッシュマップに入れ、カスタムハッシュ関数を使用しています。つまり、すべての要素を合計するだけなので、1 + 10 + 3 + 18 = 32、さらに10 + 18 + 3 + 1=32です。等しい場合は、ビットセットを使用して、要素が両方のセットにあるかどうかをすばやく確認します（ビットセットを使用する場合は並べ替えは必要ありませんが、数値の範囲がわかっていて大きすぎない場合にのみ機能します）。

これは問題なく機能しますが、多くの衝突を生成する可能性があるため、equals（）メソッドが頻繁に呼び出されます。順列をチェックするより速い方法があるかどうか疑問に思いましたか？

順列に適したハッシュ関数はありますか？

アップデート

私は少しベンチマークを行いました：0から6の範囲の数値のすべての組み合わせ、および配列の長さ1から9を生成します。3003の可能な順列があり、この多くの異なるハッシュの近くで適切なハッシュを生成する必要があります（32ビットの数値を使用します）ハッシュの場合）：

  • 追加するだけの41の異なるハッシュ（したがって、衝突がたくさんあります）
  • 値を一緒にXORするための8つの異なるハッシュ
  • 乗算用の286の異なるハッシュ
  • （R + 2e）の3003の異なるハッシュと、abcが示唆しているように乗算（Rに1779033703を使用）

したがって、abcのハッシュは非常に高速に計算でき、他のすべてのハッシュよりもはるかに優れています。ありがとう！

PS：遅くなりすぎるので、必要のないときに値を並べ替えたくありません。

4

7 に答える 7

7

有力な候補の1つがこれかもしれません。奇数の整数 R を修正します。ハッシュする各要素 e について、係数 (R + 2*e) を計算します。次に、これらすべての因数の積を計算します。最後に積を 2 で割り、ハッシュを取得します。

(R + 2e) の因数 2 は、すべての因数が奇数であることを保証するため、積が 0 になることを回避します。最後に 2 で除算するのは、積が常に奇数になるためです。したがって、除算は定数ビットを削除するだけです。 .

たとえば、R = 1779033703 を選択します。これは任意の選択です。いくつかの実験を行うと、与えられた R が良いか悪いかがわかります。値が [1, 10, 3, 18] であると仮定します。積 (32 ビット整数を使用して計算) は

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311

したがって、ハッシュは次のようになります

3376724311/2 = 1688362155。

于 2009-10-08T11:22:51.153 に答える
5

要素を合計することは、すでに実行できる最も単純なことの 1 つです。しかし、疑似ランダム性に関して特に優れたハッシュ関数だとは思いません。

配列を保存したりハッシュを計算したりする前に配列を並べ替えると、すべての適切なハッシュ関数が実行されます。

速度に関する場合: ボトルネックがどこにあるかを測定しましたか? ハッシュ関数が多くの衝突を引き起こし、ほとんどの時間を配列のビットごとの比較に費やさなければならない場合、ハッシュ関数は明らかに本来の目的を達成できていません。Sorting + Better Hash が解決策になるかもしれません。

于 2009-10-08T08:28:59.193 に答える
3

あなたの質問を正しく理解できれば、アイテムが注文されていないセット間の同等性をテストしたいと考えています。これはまさにブルーム フィルターが行うことです。少数の誤検知を犠牲にして (その場合、ブルート フォース セット比較を呼び出す必要があります)、ブルーム フィルター ハッシュが等しいかどうかを確認することで、そのようなセットを比較できます。

これが成立する代数的な理由は、OR 演算が交換可能であることです。これは他のセミリングにも当てはまります。

于 2011-03-31T05:48:05.977 に答える
0

私はこれを提案します：1。順列の長さが同じであるかどうかを確認します（そうでない場合-それらは等しくありません）

  1. 1つの配列のみを並べ替えます。別の配列を並べ替える代わりに、1番目の配列の要素を反復処理し、2番目の配列内の各要素の存在を検索します（2番目の配列の要素が小さい場合にのみ比較してください。配列全体を反復処理しないでください）。

注：順列に同じ番号（[1,2,2,10]など）を含めることができる場合は、最初の配列のメンバーと一致するときに、2番目の配列から要素を削除する必要があります。

擬似コード：

if length(arr1) <> length(arr2) return false;
sort(arr2);
for i=1 to length(arr1) {
elem=arr1[i];
j=1;
while (j<=length(arr2) and elem<arr2[j]) j=j+1;
if elem <> arr2[j] return false;
}
return true;

別の配列を並べ替える代わりに、並べ替えられた配列内のすべての要素を一致させようとすることができます。

于 2009-10-08T09:51:42.773 に答える
0

文字列のデフォルトのハッシュ コード (Java、C# は他の言語については不明) を使用するのが好きで、かなりユニークなハッシュ コードが生成されます。したがって、最初に配列をソートしてから、区切り文字を使用して一意の文字列を生成するとします。

したがって、次のことができます（Java）：

    int[] arr = selectRandomNumbers();
    Arrays.sort(arr);
    int hash = (arr[0] + "," + arr[1] + "," + arr[2] + "," + arr[3]).hashCode();

パフォーマンスが問題になる場合は、提案された非効率的な文字列連結を変更して、StringBuilder または String.format を使用できます。

   String.format("{0},{1},{2},{3}", arr[0],arr[1],arr[2],arr[3]);

もちろん、文字列ハッシュ コードは、2 つの異なる文字列が異なるハッシュを持つことを保証するものではありませんが、この推奨される形式を考慮すると、衝突は非常にまれです。

于 2009-10-08T09:07:04.873 に答える
0

積と項の合計を使用することで、おそらく衝突を大幅に減らすことができます。

1*10*3*18=540 および 10*18*3*1=540

したがって、和積ハッシュは [32,540] になります。

ただし、衝突が発生した場合は、衝突について何かをする必要があります

于 2009-10-08T10:58:11.427 に答える
0

衝突が多いかどうかに応じて (つまり、同じハッシュであり、順列ではない)、ハッシュ中に配列を事前に並べ替えることができます。その場合、数値を合計するだけでなく、それにビットマジックを追加して、まったく異なるハッシュを取得する、より積極的な種類のハッシュを実行できます。

これは、現在実行しているハッシュが貧弱すぎて不要な衝突が大量に発生する場合にのみ有益です。衝突がほとんどない場合、使用している方法は問題ないようです

于 2009-10-08T08:31:58.837 に答える