ハッシュ関数と余り演算子

Question

私はしばらく私を混乱させていた私の心の中で立ち往生した簡単な質問を持っていました。私の教授は単純にハッシュ関数がキー配列％であると言っていました。これはすべてのハッシュテーブルでこのようにする必要がありますか、それとも私たちが決定するものですか？私たちが実際に作成するハッシュテーブルごとにハッシュ関数を記述していますか？単純に、ハッシュ関数=キーと言うことができます。

Answer 1

一般に、ハッシュ関数のドメインは、その範囲よりもはるかに大きくなります。例えば、ハッシュは「2^64文字以下のすべてのUnicode文字列」を受け入れ、「16ビット数」を出力するかもしれません。

はい、いくつかのアプリケーションでは、ハッシュテーブルが通常の配列と非常によく似ていますが、ハッシュ関数としてID関数を使用することは意味があります。

一般にハッシュテーブルの場合、モジュロ（%）が良い選択です。計算が簡単で、通常のケースで十分に広がります。しかし、それは暗号的に強力ではなく、多くのアプリケーションでそれが必要です。

Answer 2

インデックスで参照される固定サイズの結果を格納する配列があります（質問の場合、0からarray_size-1までの数値を生成するindex = key％array_size）。インデックスが配列のサイズより大きくなると、問題が発生します。それが常に少ない場合、スペースが無駄になり、ハッシュの最終段階は、それが適合しなければならない配列のサイズのモジュロになる傾向があります。

もちろん、これは必ずしも均等に広がるわけではありませんしたがって、のキーを変更して、のモジュロをインデックスとして使用することができます。