
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.