1 00:00:00,220 --> 00:00:02,980 So now we're ready for a quiz to see if you understand 2 00:00:02,980 --> 00:00:05,530 the goal of the hash table. So the question is if we 3 00:00:05,530 --> 00:00:09,650 have b buckets in our hash table, and we have k keywords, 4 00:00:09,650 --> 00:00:12,100 and we should assume that k is much greater than b, that 5 00:00:12,100 --> 00:00:14,844 there are more keywords than we have buckets. The question is which 6 00:00:14,844 --> 00:00:17,660 the properties should the hash function have? And remember what the hash 7 00:00:17,660 --> 00:00:21,910 function is, is it's a function that takes in a keyword, produces 8 00:00:21,910 --> 00:00:25,670 a number, and what that number does is gives us the position 9 00:00:25,670 --> 00:00:28,070 in the hash table which is the bucket where 10 00:00:28,070 --> 00:00:31,600 that keyword would appear. The first choice is output 11 00:00:31,600 --> 00:00:34,350 a unique number between 0 and k minus 1, 12 00:00:34,350 --> 00:00:38,140 so each keyword maps to its own output number. The 13 00:00:38,140 --> 00:00:41,120 second choice is output a number between 0 and 14 00:00:41,120 --> 00:00:45,150 b minus 1. The number of buckets that we have. 15 00:00:45,150 --> 00:00:47,370 The third choice is that it should map approximately 16 00:00:47,370 --> 00:00:51,370 k divided by b, of the keywords to bucket 0. 17 00:00:51,370 --> 00:00:54,385 That means for that number of keywords, the output of 18 00:00:54,385 --> 00:00:57,140 the hash should be 0. And it should map to 19 00:00:57,140 --> 00:01:01,160 the first bucket. So the fourth choice is map approximately 20 00:01:01,160 --> 00:01:04,640 k divided b of the keywords. To bucket b minus 1. 21 00:01:04,640 --> 00:01:07,850 That's the last bucket. And the final choice is it 22 00:01:07,850 --> 00:01:10,890 should map more of the key words to bucket 0, 23 00:01:10,890 --> 00:01:13,570 than it maps to bucket 1. So check all of 24 00:01:13,570 --> 00:01:16,670 the properties that we would like the hash function to have.