hash - ハッシュの目的

Question

ハッシュ関数を使用するときの目的はランダムではありませんか？rand()では、要素（などhashVal = 37*hashVal + key[i]）に対して操作を行う代わりに関数を使用しないのはなぜですか？

Answer 1

ハッシュ関数を使用するときの目的はランダムではありませんか？

いいえ。技術的には、ハッシュ関数を使用するときの目的は、キーと呼ばれる値の大きなデータセットをハッシュと呼ばれる値のセットにマップすることです。ハッシュ関数は一意ではない可能性があります。つまり、複数のキーが同じハッシュにマップされる可能性があります。ただし、常に特定のキーを同じハッシュにマップする必要があります。

たとえば、hash（ "Hello、world"）= 5の場合、文字列を何度ハッシュしても、常に5でなければなりません。したがって、提案している方法でrand（）を使用すると、毎回同じキーが異なるハッシュにマップされるため、機能しません。

ただし、優れたハッシュ関数は、確率的にそのキーをランダムハッシュにマップしようとします。これは乱数と同じではありません。つまり、平均して、各ハッシュにはほぼ同じ数のプレハッシュがあります。ただし、各キーは、毎回、それ自体のハッシュにマップされます。

バーツの答えもこれを示しています。

Answer 2

ハッシュ関数は、ランダム性の数値ではなくマッピングに使用します。したがって、ハッシュが使用するランダム関数は使用できません。ハッシュ値は、特定の入力で常に一意です。
ハッシュ関数の主な目的は、テーブルルックアップまたはデータ比較タスクを高速化することです。

違い：

key = hash(A valid input)、キーは決定論的出力です

num = random(A valid input)、numは未定の出力です

Answer 3

良い質問。それは、ランダムが何を意味するかによって異なります。

ハッシュは、キーを任意の値にマップします。理想的には、パターンが明らかでない値にマップします。例えば：

'A' => 15
'B' => 97
'C' => 43
'D' => 60
'E' => 41

ただし、ハッシュは常に同じキーを同じ値にマップします。したがって：

"BED"  => [97 41 60]
"BEDE" => [97 41 60 41]

ハッシュにを与えるたびに'E'、それは常に41別の値としてではなく、としてハッシュします。

追記

現在の議論に次ぐ重要なことは、ハッシュが一意の値を提供する必要がないことです。たとえば、これは可能です。

'F' => 41

したがって、ハッシュ値が与えられた場合41、キーがであった'E'か。であったかを判断することはできません'F'。

（これはすべて、当然のことながら、「すばらしい。しかし、ハッシュは何のためにあるのか」という質問を示唆しています。ただし、OPが尋ねた質問ではなく、別の時間の別の質問になります。）

Answer 4

ランダム関数とハッシュ関数の間には類似点があり、どちらもシードが決定されており、値を返します。

ハッシュは、オブジェクトのデータに基づいて数値を返します。そうです、通常は非常に大きな数を提供しますが、その数はオブジェクト自体に基づいています。

ハッシュ関数に応じて、同じデータを持つ同一のオブジェクトは同一の値を返します。このため、「ランダム性」に関する限り、ハッシュは一意の数値を返すのに理想的ではありません。