2

説明

私はかなり大きなセット（文字列、文字列、文字列）の一意のタプルを持っています（約40mlnですが、大きくなる可能性があります）。タプルごとに、単一のunsignedint値を計算します。これらの値をどこかに保存して、生成後に再利用できるようにしたいと思います（アプリケーションがダウンした後でも、メモリストレージは問題外であり、データベースも問題外です）。

最初はそれらをタプル（文字列、文字列、文字列、値）としてファイルに保存しましたが、40mlnレコードの読み取りには時間がかかります（ほぼ瞬時に必要になります）。

最初に各（文字列、文字列、文字列）タプルのハッシュ値を計算し、次にそれを[0、n]（nは値の数）に正規化し、値のみをソートされた順序でバイナリファイルに格納することにしました。 （正規化されたハッシュ値でソート）。その後、このファイルをmmap（）して、mmap [normalize（hash（string、string、string））]で値を取得できます。

私のハッシュ関数は非常に単純ですが高速で、私の場合は機能します（衝突に気づきませんでした）：

concatenatedString = s1+"."+s2+"."+s3
unsigned int hash = 31;
for(int i = 0; i < concatenatedString.length(); i++) {
  hash = hash * 101 + (unsigned int) concatenatedString[i];
}

正規化と同じ（簡単）：

((long) n * hash) / max_value

n-正規化された範囲の上限（約40mln、lowe_bound = 0であるため、nは（n-lower_bound）ではありません）

max_value-古いセットの最大値（私の場合はUINT_MAX、min_value = 0なので、方程式には含めません）

問題

私のハッシュ関数は、0から4,294,967,295（unsigned int）の範囲で均一に分散された値を生成しません（それがどのように実行できるかはわかりません）。このため、正規化後、かなりの数の衝突が発生し、データが失われます（同じ配列インデックスの下で値が上書きされます）。

私がやりたいことを、それらの衝突なしで行うための賢い方法はありますか？

衝突が発生する可能性があることを十分に承知しています。私のアプローチでは、それらはあまりにも頻繁に発生する傾向があります。私のハッシュ範囲は要素の数の100倍なので、これを行う方法があるかもしれないと思いますが、その方法はまだわかりません。

解決策 最終的に、ハッシュをMurmurhashに変更し、正規化メソッドを単純な「モジュロnewRange」に変更し、ファイルの形式を変更しました（すべてのデータを保存します（文字列文字列文字列値））-ファイルはかなり大きくなりましたしかし、そのおかげで、単純な衝突検出メカニズム（ダブルハッシュ）を実装することができました。

4

4 に答える 4

4

ハッシュ値の範囲を正規化する前に衝突が発生していないことに実際は驚いています。正規化されていない範囲[0,2^32）を使用しているようです。ここで誕生日の問題のグラフを見ると、4 * 10 ^ 7の要素との衝突の確率は75％より高いはずです。いずれにせよ、要素のセットのサイズに等しい範囲にハッシュ出力を正規化することは、衝突の重要な数を実質的に保証します。ハッシュ値にカウンターを使用する意思がない限り、それを回避する方法がわかりません。

編集：あなたの編集を見ました。要素数の100倍（約4 * 10 * 9）の範囲であっても、多くの衝突が発生する可能性があります。上に示したように、1回以上の衝突の確率は75％をはるかに超えています。

私が提案する2つのことがあります：

別のハッシュ関数を選択してください

お気づきのとおり、ハッシュ関数は高速ですが、[0,2 ^ 32）の範囲の値をランダムに分散することはありません。そこにはいくつかのハッシュ関数があり、それらは高速であり、ハッシュ関数の範囲全体にハッシュ値をより適切に分散します。私が過去に使用したものの1つはMurmurHashです。

より広い範囲を使用する

より広い範囲を使用すると、衝突のリスクを減らすことができます。ここでもう一度グラフを見ると、衝突のリスクを10^-6未満に減らすには64ビットで十分であるように見えます。この場合、MurmurHash64AおよびMurmurHash64Bバリアントが役立ちます。

于 2013-02-20T07:33:49.013 に答える
1

ハッシュを一意の[0..n]値に正規化できるとは限りません。

私はあなたに2つのアプローチを提案することができます：

  1. ファイルを並べ替えて、マップの代わりにバイナリ検索を使用します。（LogNの複雑さ）
  2. インデックスを使用して2番目のファイルに折り目を付け、範囲[0..5n]のハッシュテーブルを実装します（5nは、nより大きい他の数値で変更される可能性があります）。
于 2013-02-20T06:53:11.383 に答える
1

これを正規化に使用していると言っています。

((unsigned int) n * hash) / max_value

そしてあなたはそれmax_valueがUINT_MAX：であると言います

「max_value-古いセットの最大値（UINT_MAX」

そして、hashとして宣言されunsigned intます。

さて、ご存知のとおり、上記では値0と1しか生成できません。これにより、衝突が保証されます。

C ++の整数除算と浮動小数点除算の違いを知っていますか？

そうでない場合は、 C++の教科書を入手することをお勧めします。

ちなみに、「（unsigned int）blah」のようなキャストは、バグを作成する確実な方法です。彼らはコンパイラーに、起こりうる問題についてあなたに話さないように、シャットダウンするように指示します。なぜなら、あなたがそれを言っているので、あなたはもっとよく知っているからです。しかし、あなたはしません。

于 2013-02-20T08:03:01.287 に答える
0

私が理解している限り、一意のハッシュが必要です（これは実際には不可能です:)）：

Javaでは、String.hashCode（）は32ビットのハッシュコードを提供します。

（たとえば）64ビットのハッシュコードが必要な場合は、自分で簡単に実装できます。

文字列の暗号化ハッシュが必要な場合、Java暗号化ライブラリにはMD5、SHA-1などの実装が含まれています。通常、文字列をバイト配列に変換してから、ハッシュジェネレーター/ダイジェストジェネレーターにフィードする必要があります。たとえば、@BorisPavlovićの回答を参照してください。

一意のハッシュコードが必要な場合は、運が悪いです。ハッシュとハッシュコードは一意ではありません。

長さNのJava文字列には65536^Nの可能な状態があり、すべての可能な値を表すには16*Nビットの整数が必要です。より狭い範囲（たとえば、16 * Nビット未満）の​​整数を生成するハッシュ関数を作成すると、最終的に、複数の文字列が同じ整数にハッシュされる場合があります。つまり、ハッシュコードを一意にすることはできません。これは鳩の巣原理と呼ばれ、簡単な数学的証明があります。（数学と戦って勝つことはできません！）

于 2013-02-20T07:53:36.167 に答える