2

MIT朗読からの良いハッシュ関数の特性:

  1. 単純な均一ハッシュの仮定を(ほぼ)満たします。各キーは、m個のスロットのいずれかに等しくハッシュされる可能性があります。
  2. ハッシュ関数は特定のスロットに偏ってはいけません。同じスロットに類似のキーをハッシュしないでください(たとえば、コンパイラのシンボルテーブルは変数iとjを同じスロットにハッシュしないでください。これらは、多くの組み合わせで使用されるためです)。
  3. 計算が速く、O(1)ランタイムが必要です
  4. 決定論的です。h(k)は、指定されたkに対して常に同じ値を返す必要があります

誰かがポイント2をさらに説明できますか?変数名はハッシュ関数と何の関係がありますか?

編集:私はJavaを使用しています。したがって、回答にJavaセマンティクスを使用した説明が含まれている場合は、問題ありません。

4

2 に答える 2

3

ハッシュテーブルは、コンパイラが変数名や関数名などのシンボルに関する情報をルックアップするために使用するルックアップテーブルを構築するためによく使用されるため、コンパイラシナリオを使用して#2のポイントを説明します。

著者は、同じプログラムで非常に一般的に見られる変数名のペアを取り、これらの変数の名前を表す文字列、iおよびは同じスロットにハッシュされるべきではないと述べました。ハッシュの衝突を解決することは、速度に最も悪影響を与えるルックアッププロセスの一部であるため、これは理にかなっています。j"i""j"

于 2012-08-17T10:17:53.973 に答える
2

箇条書きは、コンパイラが、変数名からその変数に関する情報へのマッピングであり、ハッシュテーブルとして実装されているシンボルテーブルと呼ばれるものを使用することを示唆しています。

これは多くのコンパイラに当てはまります。

于 2012-08-17T10:15:35.947 に答える