Return to Video

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

English subtitles

改訂 Compare revisions