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.