So now we're ready for a quiz to see if you understand
the goal of the hash table. So the question is if we
have b buckets in our hash table, and we have k keywords,
and we should assume that k is much greater than b, that
there are more keywords than we have buckets. The question is which
the properties should the hash function have? And remember what the hash
function is, is it's a function that takes in a keyword, produces
a number, and what that number does is gives us the position
in the hash table which is the bucket where
that keyword would appear. The first choice is output
a unique number between 0 and k minus 1,
so each keyword maps to its own output number. The
second choice is output a number between 0 and
b minus 1. The number of buckets that we have.
The third choice is that it should map approximately
k divided by b, of the keywords to bucket 0.
That means for that number of keywords, the output of
the hash should be 0. And it should map to
the first bucket. So the fourth choice is map approximately
k divided b of the keywords. To bucket b minus 1.
That's the last bucket. And the final choice is it
should map more of the key words to bucket 0,
than it maps to bucket 1. So check all of
the properties that we would like the hash function to have.
それではハッシュテーブルの目的を理解できているか 確認の小テストを行いましょう
bのバケットとkのキーワードがある場合
kはbよりはるかに大きいと仮定します
バケットにあるよりもさらにキーワードがあります
ハッシュ関数にあるのはどのプロパティでしょう？
キーワードを用い数値を生成する関数だということを 忘れないでください
その数値によってハッシュテーブルの位置が分かります
それはキーワードが含まれているバケットになります 1つ目の選択肢は
ゼロとkー1間の一意の数値を出力する
つまり各キーワードが自らの出力数値に対応づける
2つ目の選択肢はゼロとbー1の数値を出力する
持っているバケットの数ですね
3つ目はキーワードのおおよそk割るbを バケットゼロに対応づける
つまりキーワードのその数値ではハッシュ関数の出力が ゼロになり1つ目のバケットに対応づけられます
4つ目の選択肢はキーワードの おおよそk割るbをバケットbー1に対応づける
これが最後のバケットです そして最後の選択肢は
キーワードをバケット1に対応づけるよりも バケットゼロに対応づける
ハッシュ関数が持つと思うプロパティを すべて選んでください