## Hash Table - Intro to Computer Science

• 0:00 - 0:03
So now we're ready for a quiz to see if you understand
• 0:03 - 0:06
the goal of the hash table. So the question is if we
• 0:06 - 0:10
have b buckets in our hash table, and we have k keywords,
• 0:10 - 0:12
and we should assume that k is much greater than b, that
• 0:12 - 0:15
there are more keywords than we have buckets. The question is which
• 0:15 - 0:18
the properties should the hash function have? And remember what the hash
• 0:18 - 0:22
function is, is it's a function that takes in a keyword, produces
• 0:22 - 0:26
a number, and what that number does is gives us the position
• 0:26 - 0:28
in the hash table which is the bucket where
• 0:28 - 0:32
that keyword would appear. The first choice is output
• 0:32 - 0:34
a unique number between 0 and k minus 1,
• 0:34 - 0:38
so each keyword maps to its own output number. The
• 0:38 - 0:41
second choice is output a number between 0 and
• 0:41 - 0:45
b minus 1. The number of buckets that we have.
• 0:45 - 0:47
The third choice is that it should map approximately
• 0:47 - 0:51
k divided by b, of the keywords to bucket 0.
• 0:51 - 0:54
That means for that number of keywords, the output of
• 0:54 - 0:57
the hash should be 0. And it should map to
• 0:57 - 1:01
the first bucket. So the fourth choice is map approximately
• 1:01 - 1:05
k divided b of the keywords. To bucket b minus 1.
• 1:05 - 1:08
That's the last bucket. And the final choice is it
• 1:08 - 1:11
should map more of the key words to bucket 0,
• 1:11 - 1:14
than it maps to bucket 1. So check all of
• 1:14 - 1:17
the properties that we would like the hash function to have.
タイトル：
Hash Table - Intro to Computer Science

more » « less
Video Language:
English
Team:
Udacity
プロジェクト：
CS101 - Intro to Computer Science
Duration:
01:18
 Udacity Robot edited 英語(米国) subtitles for 18-19 Hash Table Udacity Robot edited 英語(米国) subtitles for 18-19 Hash Table Udacity Robot edited 英語(米国) subtitles for 18-19 Hash Table Udacity Robot edited 英語(米国) subtitles for 18-19 Hash Table Cogi-Admin edited 英語(米国) subtitles for 18-19 Hash Table

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API