範囲0の計算ハッシュ関数

私は文字列の配列を持っています。配列の長さはnです。どのように各文字列のハッシュキーを計算するので、各キーは0..nの範囲の数値になりますか？）範囲0の計算ハッシュ関数

2011-12-07 Kornel William

アレイの内容を最初に調べることなく、ハッシュ関数を選択することはできません。ハッシュ関数を選択し、配列を選択させるとしましょう。 2n文字列を生成し、ハッシュ関数を適用し、結果をソートします。 2n個の文字列とn個の可能な値だけが衝突する必要があるので、たくさんの衝突を含むn個の文字列を選択し、それらをハッシュして衝突を観察するために戻します。

ハッシュ関数を選択するために、事前に文字列を分析する準備ができている場合、開始点の1つまたは検索語のソースは、http://en.wikipedia.org/wiki/Perfect_hash_functionの「最小完全ハッシュ関数」になります。

また、これが本当に必要なものであるかどうか、あまり完全でないハッシュ関数の使用を検討できるかどうかを検討することもできます。私はhttp://en.wikipedia.org/wiki/Cuckoo_hashingの外観が好きです。

出典

2011-12-07 20:56:45 mcdowella

なぜハッシュキーとして配列のインデックスを使用しない、それは私を助けるために誰かに助けになる場合

UPDATE

アレイの項目は、文字列が、数値ではないだろうか？

出典

2011-12-07 20:29:12 buddhabrot

を、私は異なる位置に2つの同じ文字列を持っている場合はどう？それらのハッシュは文字列が等しい間に異なっているでしょう。 –

配列をソートするだけで、一意の要素のみを使用します。 – buddhabrot

彼は 'O（log（N））'プローブをリストに入れたくないかもしれません。ハッシュ関数は定数wrt 'N'（キーの長さだけではありません）です。 – phs

はモジュロNを試してみてください。

int N = array.Length; 
int hashMaxN = strings[i].GetHashCode() % N;

これは、異なるインデックスの一意のハッシュを保証するものではありません。しかし、ハッシュコードは一意ではありません。

リスト内の各文字列に割り当てられた固有のIDが必要な場合は、anothe Rの答えからの提案を使用します。個別の文字列

int itemHash = myList.Distinct().OrderBy(s => s).IndexOf(item);

これは、プロパティを持っていますがソートされた配列内の文字列のインデックスを選びますリストがどのように順序付けされているかにかかわらず同じ文字列に対して同じであることを示します。しかし文字列をリストに追加すると、アイテムのハッシュコードが変更されます。

出典

2011-12-07 20:29:24

ハッシュを構築するアルゴリズムが必要です。しかし、モジュロでのあなたのアプローチでさえ、うまくいきません - 例えば31％3 = 1と13％3 = 1のように、結果のハッシュの一意性を保証しません。 –

私の答えを編集しました。通常、ハッシュコードは、一意である必要はありません（ただし、ハッシュテーブルでのパフォーマンスのためにできるだけ少ない数のコリジョンを持つようにしようとします）。 –

ゲームでは遅くなっていますが、このトピックは最近これまでに見たものよりnicer solutionで再び現れました。

は例えば、CRC32ハッシュを取り、所望の範囲内の数を取得するために剰余を使用：

crc32(str) % 5 // returns either 0, 1, 2, 3, 4

出典

2012-11-16 10:43:04

範囲0の計算ハッシュ関数

答えて

関連する問題