English subtitles

← Keywords and Buckets Solution - Intro to Computer Science

Get Embed Code
2 Languages

Showing Revision 6 created 05/24/2016 by Udacity Robot.

  1. So there are two correct answers, the third one, and
  2. the fifth one. And this is why a hash table is such a great
  3. advance over the linear index, is that we can double the number of keywords, and
  4. double the number of buckets, and the look up
  5. time stays the same. With the linear index, if we
  6. double the number of keywords for each look up, we
  7. need to go through the loop once for each keyword.
  8. If the keyword was near the end or one that wasn't
  9. in the table, the time to look up the keyword would
  10. double as we double the number of keywords. With a hash
  11. table if we also double the number of buckets when we double
  12. the number of keywords, well then the number of keywords in
  13. each bucket stays the same. We're dividing the keywords evenly between
  14. buckets. So this is the number, the number of keywords per
  15. bucket is the number of keywords divided by the number of buckets.
  16. Of we double both, that number stays approximately the same. The
  17. time to look up only depends on the number of keywords per
  18. bucket. The time to find the bucket is very fast, right? We
  19. just need to run the hash function, find that element of the
  20. list. Both of those don't depend on the size of the
  21. list, how long it takes to do that. And then we have
  22. to look through the bucket, the size of the bucket, we have
  23. to look though each element in the bucket one at a time.
  24. So if we keep the number of key words per bucket
  25. the same, the look up time stays essentially the same. So that's
  26. the great property that hash tables have. If we double the
  27. number of buckets, as we double the number of keywords, the expected
  28. look up time doesn't change. For the other possibilities, well if
  29. we double the number of keywords and keep the same number of
  30. buckets, that's going to get slower because the number of keywords
  31. per bucket will approximately double. So it's going to take about twice
  32. as long for each look up. If we keep the same
  33. number of keywords, but double the number of buckets, well then it's
  34. going to actually get faster. We'll have the same number of keywords, double
  35. the number of buckets. So, this value will be approximately half of
  36. what it was before. The expected lookup time will be about
  37. half of what is before we doubled the number of buckets. If
  38. we have the number of keywords keeping the same number of buckets,
  39. well that has essentially the same affect. The average number of keywords
  40. per bucket will be half of what it
  41. was before, so the expected lookup time will be
  42. about half of what it was. And finally
  43. if we have both, well that's going to keep
  44. the ratio the same so the expected look
  45. up time will be about the same. So that's
  46. why these two are the correct answers, that those
  47. are expected to leave the lookup time essentially unchanged.