標準の英字とアンダースコアのみを使用して、ハッシュテーブル/辞書で衝突の可能性を引き起こすことなく、最大で何文字を使用できるか。
したがって、次のような文字列：
blur
Blur
b
Blur_The_Shades_Slightly_With_A_Tint_Of_Blue
..。
5415 次
5 に答える
15
単一の文字間で衝突が発生しないという保証はありません。
おそらくそうしないでしょうが、で使用されるアルゴリズムstring.GetHashCodeは指定されておらず、変更される可能性があります。(特に、.NET 1.1 と .NET 2.0 の間で変更されたため、変更されないと想定していた人々は火傷を負いました。)
ハッシュコードの衝突は、適切に設計されたハッシュテーブルの動作を停止しないことに注意してください.正しい値を取得できるはずです.同じハッシュを持っている場合、等価性を使用して複数のキーをチェックする必要がある可能性があります.コード。
ハッシュコードが一意であることに依存している辞書には、ハッシュコードに関する重要な情報が欠けています.
于 2009-04-09T18:15:36.793 に答える
3
完全なハッシュ関数(他の人が述べたように、通常は使用しない) が与えられた場合、次のように、2 つの文字列が衝突しないことを保証する最大可能文字数を見つけることができます。
利用可能な一意のハッシュ コードの数 = 2 ^ 32 = 4294967296 (ハッシュ コードに 32 ビット整数が使用されると仮定) 文字セットのサイズ = 2 * 26 + 1 = 53 (ラテン アルファベットの大文字として 26 小文字、プラスアンダースコア)
l次に、長さ(またはそれ以下) の文字列には表現の合計があることを考慮する必要があります54 ^ l。基数は 53 ではなく 54 であることに注意してください。これは、文字列が任意の文字の後に終了する可能性があり、文字ごとに追加の可能性が追加されるためです。結果に大きな影響を与えるわけではありません。
いいえを取ります。文字列表現の最大数として一意のハッシュ コードを使用すると、次の簡単な式が得られます。
54 ^ l = 2 ^ 32
そしてそれを解決します：
log2 (54 ^ l) = 32
l * log2 54 = 32
l = 32 / log2 54 = 5.56
(ここで、log2 は底 2 の対数関数です。)
文字列の長さは明らかに小数にはならないため、整数部分を使用して最大長を5にします。確かに非常に短いですが、この制限により、完全なハッシュ関数が与えられた場合、衝突の可能性が最も低くても防ぐことができることに注意してください。
ただし、前述したように、これは主に理論上のものであり、何かの設計上の考慮事項にどの程度使用できるかはわかりません。そうは言っても、理論的な観点から問題を理解するのに役立ち、その上で実際的な考慮事項 (たとえば、不完全なハッシュ関数、分布の不均一性など) を追加できることを願っています。
于 2009-04-09T18:29:10.473 に答える
3
ユニバーサルハッシュ
最適なユニバーサル ハッシュ( 1 ) を想定して、1 文字あたりのビット長から長さビットのハッシュまでの文字S列との衝突の確率を計算するには、サイズ (バケット数) 'N` のハッシュ テーブルに基づいて衝突確率を計算できます。LWH
まず最初に、ハッシュ内のビットを利用可能なバケットに完全に分割する( 3 ) 理想的なハッシュテーブルの実装 ( 2 ) を想定できます。この手段は、 の制限以外では無意味になります。
と 'L' は単に の上限の基礎です。より単純な計算のために、文字列の長さ <は特殊なヌル文字で L に単純に埋め込まれていると仮定します。興味がある場合は、最悪のケースに興味があります。これは 54^ (26*2+'_'+ null) です。明らかに、これはばかげた数字です。実際のエントリ数は、文字セットと長さよりも有用です。それ自体が変数であるかのように単純に動作します。HNHNWSLLS
SアイテムをNバケツに入れようとしています。これは非常によく知られた問題、誕生日のパラドックスになります。
さまざまな確率とバケット数についてこれを解決することは有益ですが、10 億個のバケット (32 ビット システムで約 4GB のメモリ) があると仮定すると、少なくとも 1 つのバケットである可能性が 50% に達する前に、37,000 個のエントリのみが必要になります。衝突。ハッシュテーブル内の衝突を回避しようとすることは、明らかにばかげていることを考えると。
これはすべて、ハッシュ関数の動作を気にする必要がないという意味ではありません。明らかに、これらの数値は理想的な実装を想定しており、どれだけ優れているかの上限です。貧弱なハッシュ関数は、一部の領域ではるかに悪い衝突を引き起こし、可能性のある「スペース」の一部をまったくまたはほとんど使用しないことで浪費する可能性があります。これらすべてにより、ハッシュが最適ではなくなり、リストのように見えるパフォーマンスに低下することさえありますが、はるかに悪い一定の要因があります。
文字列のハッシュ関数の .NET フレームワークの実装は (改善の可能性があるという点で) 優れたものではありませんが、おそらく大多数のユーザーに受け入れられ、かなり効率的に計算できます。
別のアプローチ: 完全ハッシュ
完全なハッシュとして知られるものを生成したい場合、これには事前に入力値の完全な知識が必要ですが、あまり役に立ちません。上記の数学と同様に、完全なハッシュにも限界があることを示すことができます。
Llengthの 54 ^ 文字列の制限を思い出してくださいL。Hただし、約 40 億の異なる数であるビット (32 と仮定します)しかありません。したがって、本当に任意の文字列と任意の数を使用できる場合は、次の条件を満たす必要があります。
54 ^ L <= 2 ^ 32
そしてそれを解決します：
log2 (54 ^ L) <= 32
L * log2 54 <= 32
L <= 32 / log2 54 <= 5.56
文字列の長さは明らかに小数にはならないので、最大長は 5 だけです。実際、非常に短いです。
サイズが 40 億をはるかに下回る文字列のセットしかないことがわかっている場合、完全なハッシュにより の任意の値を処理できますがL、値のセットを制限することは実際には非常に難しく、事前にすべてを知っておく必要があります。または、文字列のデータベースに相当するものに劣化します->ハッシュし、新しい文字列が検出されるとそれに追加します。
この演習では、あらゆる衝突の確率を減らしたいので、ユニバーサル ハッシュが最適です。
ハッシュ (および内部バケット) で最適なジョブを実行するのは非常に難しいことに注意してください。ただし、常に理想的であるとは限らない場合でも、組み込み型が合理的であると期待する必要があります。
この例では、クローズド アドレス指定とオープン アドレス指定の問題を回避しました。これは関連する確率にある程度関係がありますが、有意ではありません
于 2009-04-09T20:23:40.497 に答える
1
ハッシュ アルゴリズムは一意性を保証するものではありません。ハッシュテーブル内の場所よりもはるかに多くの潜在的な文字列 (n の長さに対して 26^n、特殊な文字、スペース、大文字、英語以外の文字などを無視しても) があることを考えると、そのような保証が満たされる方法はありません。 . 適切な配布を保証することだけが想定されています。
于 2009-04-09T18:22:04.033 に答える
0
キーが文字列 (辞書など) の場合は、GetHashCode() が使用されます。これは 32 ビット整数です。Hashtable は、デフォルトで 1 つのキーから値への負荷係数に設定され、その負荷係数を維持するためにバケットの数を増やします。したがって、衝突が見られる場合は、再割り当ての境界付近で発生する傾向があります (再割り当ての直後に減少します)。
于 2009-04-09T18:21:05.190 に答える