ハッシュ関数 - 2つの異なる意味ですか？

Question

我々はハッシュ関数を言うとき、私はそれはあなたがhash_tableを実装する場合しかし、それがどのように見えるthis

を参照してください例えば、ほとんどの記事に32ビットにするキーのシーケンスバイトまたは64ビットの符号なし整数に変換する意味を見つけますそのハッシュ関数は、非常に大きな整数をより小さい内部配列インデックスに変換することを意味し、このドメインでは、上記の「ハッシュ関数」の意味は、のハッシュ値に変更されます。

1. 私の理解は正しいですか？
2. 誰かが小さな整数の内部インデックスに変換する大規模整数に関するいくつかの洞察やリンクや論文を提供できますか？

おかげ

Answer 1

hash functionは単に小さなデータセットに大きなデータセットからのマッピングです。 hash tableの場合は、バケットのルックアップキーとして、より小さいデータセット（多くの場合、整数を指します）が使用されます。

例の記事では、これらのすべてのハッシュ関数出力がすべての整数がハッシュテーブルのルックアップインデックスとして使用されます。

Answer 2

「ハッシュ関数」を理解することは、集合Aから集合{0,1,2、...、n}までの任意の関数です.nは負でない自然数です。それ以外は、本質的には「ハッシュ関数」であることを意味します。あなたの例と他の多くの例の両方は、物事を非負の整数の部分集合に写像するので、「ハッシュ関数」になっています。 「ハッシュ関数」が問題に適用される方法も、定義の一部ではありません。

私は本当にドメインがcodomainよりも大きくなければならないとは思っていませんが、間違っているかもしれません。私はcodomainが無限になるとは思わないが、私は間違っているかもしれない。

Answer 3

「ハッシング」という用語は、一般的に上記の両方の意味をカバーしています。他の回答が指摘しているように、操作は似ています。また、2つのプロセスは、一般的に並行して使用されます。

ハッシュシステムを探したり設計したりするとき、フィディーパートはよく分散された32/64ビット整数（実際の「ハッシュ関数」）を生成しています。最初のハッシュ値が良いと、結果が最終的なインデックスに均等に分散されている限り、出力を使用する正確な方法は重要ではありません。

最終的なインデックス（固定サイズのハッシュテーブルに適しています）を生成する明白な方法は、モジュロハッシュ値を取ることです。このアルゴリズムは、インデックスの数ただし、ハッシュ値の使用方法はアプリケーションによって異なります（たとえば、動的サイズのハッシュテーブルはおそらく固定サイズのテーブルとは異なる処理を行います）。