[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.22,0:00:02.98,Default,,0000,0000,0000,,So now we're ready for a quiz to see if you understand
Dialogue: 0,0:00:02.98,0:00:05.53,Default,,0000,0000,0000,,the goal of the hash table. So the question is if we
Dialogue: 0,0:00:05.53,0:00:09.65,Default,,0000,0000,0000,,have b buckets in our hash table, and we have k keywords,
Dialogue: 0,0:00:09.65,0:00:12.10,Default,,0000,0000,0000,,and we should assume that k is much greater than b, that
Dialogue: 0,0:00:12.10,0:00:14.84,Default,,0000,0000,0000,,there are more keywords than we have buckets. The question is which
Dialogue: 0,0:00:14.84,0:00:17.66,Default,,0000,0000,0000,,the properties should the hash function have? And remember what the hash
Dialogue: 0,0:00:17.66,0:00:21.91,Default,,0000,0000,0000,,function is, is it's a function that takes in a keyword, produces
Dialogue: 0,0:00:21.91,0:00:25.67,Default,,0000,0000,0000,,a number, and what that number does is gives us the position
Dialogue: 0,0:00:25.67,0:00:28.07,Default,,0000,0000,0000,,in the hash table which is the bucket where
Dialogue: 0,0:00:28.07,0:00:31.60,Default,,0000,0000,0000,,that keyword would appear. The first choice is output
Dialogue: 0,0:00:31.60,0:00:34.35,Default,,0000,0000,0000,,a unique number between 0 and k minus 1,
Dialogue: 0,0:00:34.35,0:00:38.14,Default,,0000,0000,0000,,so each keyword maps to its own output number. The
Dialogue: 0,0:00:38.14,0:00:41.12,Default,,0000,0000,0000,,second choice is output a number between 0 and
Dialogue: 0,0:00:41.12,0:00:45.15,Default,,0000,0000,0000,,b minus 1. The number of buckets that we have.
Dialogue: 0,0:00:45.15,0:00:47.37,Default,,0000,0000,0000,,The third choice is that it should map approximately
Dialogue: 0,0:00:47.37,0:00:51.37,Default,,0000,0000,0000,,k divided by b, of the keywords to bucket 0.
Dialogue: 0,0:00:51.37,0:00:54.38,Default,,0000,0000,0000,,That means for that number of keywords, the output of
Dialogue: 0,0:00:54.38,0:00:57.14,Default,,0000,0000,0000,,the hash should be 0. And it should map to
Dialogue: 0,0:00:57.14,0:01:01.16,Default,,0000,0000,0000,,the first bucket. So the fourth choice is map approximately
Dialogue: 0,0:01:01.16,0:01:04.64,Default,,0000,0000,0000,,k divided b of the keywords. To bucket b minus 1.
Dialogue: 0,0:01:04.64,0:01:07.85,Default,,0000,0000,0000,,That's the last bucket. And the final choice is it
Dialogue: 0,0:01:07.85,0:01:10.89,Default,,0000,0000,0000,,should map more of the key words to bucket 0,
Dialogue: 0,0:01:10.89,0:01:13.57,Default,,0000,0000,0000,,than it maps to bucket 1. So check all of
Dialogue: 0,0:01:13.57,0:01:16.67,Default,,0000,0000,0000,,the properties that we would like the hash function to have.