7

非常に多数の文字列があるとします (それぞれ 50 文字以下の文字列が 100 億個あるとします)。文字列を正確に 10 個のバケットに分散したいと考えています。各バケットには、文字列の約 10% を保持する必要があります。ハッシュ関数 h() を使用すると、次のことができます。

int bucket_for_s = h(s) % 10

ただし、これは分布の均一性を保証するものではありません。すべての文字列に対して上記を実行すると、30% がバケット 1 に移動し、5% がバケット 2 に移動する、というようになります。私の質問は：

h() 分布が与えられた場合、文字列をより均等に分散する新しいハッシュ関数 h2() を生成する方法はありますか?

または、一連のハッシュ関数 h2()、h3()... を生成できるプロセスがあるので、1: 各ハッシュ関数は前のハッシュ関数よりも優れており、2: 妥当な数のハッシュのみを生成する必要があります。機能？

残念ながら、入力が複数のマシンに分散しているため、入力を単純に 10 の部分に分割することはできません。各マシンに個別に適用して同じ結果を得ることができる決定論的なソリューションを探しています（そのため、最終的に「こんにちは」は、どのマシンに保存されていても、バケット x に移動します）。

4

4 に答える 4

7

暗号学的に堅固なハッシュ関数は、ハッシュ出力のすべてのビットにわたって非常に均等に分散されているはずです。

Javaのようなものを使用している場合、hashCode()私は次のように見えると信じています

s[0]*31^(n-1) + s 1 *31^(n-2) + ... + s[n-1]

理想的とは言えないハッシュ分布が表示される可能性があります。

SHA-256 などの暗号化ハッシュをベースとして使用してみてください。

Google のCity HashはSHA-256ほど分散されていませんが、はるかに高速です。これにより、より少ない計算コストで十分な分散が提供される場合があります。

于 2012-08-24T00:28:59.787 に答える
6

ハッシュ関数を連鎖させたり、一連のハッシュ関数を生成したりすると、計算コストが不必要に高くなります。必要なプロパティをすぐに使用できるハッシュ関数を使用する必要があります。

有力候補

あなたが説明したことから、ハッシュ関数は決定論的である必要があります（「こんにちは」の例）-これはすべてのハッシュ関数に当てはまり、均等な分布を生成する必要があります。

SHA-256などの暗号化ハッシュは、"hello" と "hallo" などのわずかに異なる入力に対しても完全に異なるハッシュを出力するため、要件を満たす必要があります。ハッシュに対してモジュロ (%) 演算を使用することで、必要な数のバケットを使用できます (もちろん、ハッシュの数を超えてはなりません)。

ただし、暗号化ハッシュ関数はセキュリティとチェックサムのために構築されており、複雑な計算が必要です。あなたの場合、それらが提供する強力なセキュリティ関連のプロパティは必要ない可能性が非常に高いです。

むしろ、プロパティが緩和され、ルックアップ用に設計されている、いわゆる「非暗号化ハッシュ関数」を探すことをお勧めします。これにより、速度が最適化されます。Java のhashCode()、MurmurHash、および前述の CityHash ( Google の発表) は良い出発点かもしれません。

ハッシュ関数の決定論的性質とハッシュの均等な分布

つまり、ハッシュ関数は入力に関して決定論的であるため、ハッシュ関数を複数回呼び出しても、「hello」としての特定の入力のハッシュは常に同じになります。データ セットに完全に重複する要素が多数含まれている場合 (たとえば、"a" と "the" は通常、トークン化されたテキストの疑いがあります)、使用するハッシュ関数に関係なく、バケットのサイズが不均一になる可能性があります。

ワークロードの均等な分散のためにハッシュの均等な分散を使用したいと仮定すると、これは次の戦略を使用して克服できます。各バケットは、使用可能な任意のマシンで処理できる作業パッケージまたはジョブと考えてください。マシンより多くの作業パッケージがある場合 (10 台のマシンに対して 20 または 30 個のパッケージとしましょう)、柔軟なスケジューリングが可能である限り、ワークロードを均等に分散できます。マシン A が特大パッケージの 1 つを取得し、その処理に時間がかかる場合、マシン B は 2 つの小または中サイズのパッケージを同時に処理できるため、特大パッケージの全体的なパフォーマンスへの影響が軽減されます。

于 2012-08-24T14:20:13.723 に答える
0

ハッシュ関数は、均一な分布を生成するように設計されています。これがあなたのデータに当てはまらない場合、あなたのデータはどういうわけかその特定のハッシュ関数の「部分的に」逆であり、別のデータを選択すると問題は解決するはずです。

これが理論的な問題であることを考えると、1 つのアプローチは次のようになります。

ホワイトニングカラードノイズ

で遊ぶことができますint bucket_for_s

int bucket_for_s = put_in_bucket(s)

put_in_bucket:
    x = h(s) % 10 + 10*((h(s)/10)%10)
    if(0<=x<=2) return 0
    if(3<=x<=5) return 1
    if(6<=x<=9) return 2
    #The previous bucket_1 (30%) is now split into 3 buckets
    if(10<=x<=27) return 0
    #The previous bucket_2 (5%) is now enlarged
    #to incorporate more of the small old buckets (or parts of buckets)
    #This bucket is now bucket_4
    #... more of the same 
    if(83<=x<=99) return 9

「解決策」に満足するまで、このアイデアをさらに1桁拡張できます。

からロジックを取り出して、それをusingput_in_bucketに入れることができます。h2(s)h1(s)

このアプローチは、ホワイト ノイズに色を付ける (または、この場合のように色付きノイズを白くする) ために使用されるため、この名前が付けられました。

于 2016-04-18T12:00:24.283 に答える
0

それを解決する方法の指示は、10 または N ではなく 2 つのバケットに単純化されました。

バケット1 とh()バケット2、そしてもちろん.pqp + q = 1

ここでの目標は、与えられたバケット 1 がチャンスを使用し、与えられたバケット 2 がチャンスを使用h2()するパラメーターを使用して、そのような分布を見つけることです。p1, q1, p2, q2p1, q1 (p1+q1=1)p2, q2 (p2+q2=1)

         h()          h2()

                 / bucket1 p*p1 
      bucket1 p -
    /            \ bucket2 p*q1 
 x -
    \            / bucket1 q*p2 
      bucket2 q -
                 \ bucket2 q*q2

ここでの目標は、2 つのバケットすべてのチャンスを均等にすることです。

p*q1 + q*p2 = 1/2  (total chances for bucket 1 after h2())
p*q2 + q*q2 = 1/2  (total chances for bucket 2 after h2())

そして前と同じように：

p1 + q1 = 1
p2 + q2 = 1

p1,q1,p2,q2これは、4 つの変数 (分布のパラメーター) を持つ 4 つの方程式の線形システムですh2()。

注: バケットが 10 個ある場合はh()、p1, p2, ..., p10whereを使用しp1 + p2 + ... + p10 = 1ます。バケット数 > 2 の場合、方程式は未知数よりも少なくなります:p1のコンポーネントを取得するような割り当てごとh2()にp11+p12+...+p1_10=1)。したがって、10 個のバケットの場合、100 個の未知のパラメーターh2()とわずか 20 個の方程式があります。h2()これは、残りのパラメーターの方程式を解く前に、いくつかの任意の (ただし実行可能な) 値を の 80 個のパラメーターに与えることができることを意味します。きれいではありませんが、それでも解決策です。

于 2012-08-24T12:53:22.627 に答える