English subtitles

← Hash Table - Intro to Computer Science

Get Embed Code
2 Languages

Showing Revision 5 created 05/25/2016 by Udacity Robot.

  1. So now we're ready for a quiz to see if you understand
  2. the goal of the hash table. So the question is if we
  3. have b buckets in our hash table, and we have k keywords,
  4. and we should assume that k is much greater than b, that
  5. there are more keywords than we have buckets. The question is which
  6. the properties should the hash function have? And remember what the hash
  7. function is, is it's a function that takes in a keyword, produces
  8. a number, and what that number does is gives us the position
  9. in the hash table which is the bucket where
  10. that keyword would appear. The first choice is output
  11. a unique number between 0 and k minus 1,
  12. so each keyword maps to its own output number. The
  13. second choice is output a number between 0 and
  14. b minus 1. The number of buckets that we have.
  15. The third choice is that it should map approximately
  16. k divided by b, of the keywords to bucket 0.
  17. That means for that number of keywords, the output of
  18. the hash should be 0. And it should map to
  19. the first bucket. So the fourth choice is map approximately
  20. k divided b of the keywords. To bucket b minus 1.
  21. That's the last bucket. And the final choice is it
  22. should map more of the key words to bucket 0,
  23. than it maps to bucket 1. So check all of
  24. the properties that we would like the hash function to have.