YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Empty Hash Table Solution - Intro to Computer Science

Get Embed Code
2 Languages

Showing Revision 6 created 07/06/2017 by Dejan Trajkovic.

  1. So here's one way to define make_hashtable. We're going to start by
  2. initializing a variable i = 0. So we're going to start by creating
  3. an empty table and what we want to do is add
  4. n buckets, number of buckets to the table. So we're going to use
  5. a while loop and we're going to loop while i is less
  6. than number of buckets. So each time that I want to go
  7. through the loop what we want to do is add on empty
  8. bucket to our hash table. So we can do that using Append.
  9. That adds a new empty bucket and we need to
  10. remember to increase I to make sure that we don't
  11. keep looping forever. So we're going to go through this
  12. loop nbuckets number of times each time adding an empty bucket
  13. to the table and then we need to return the
  14. table at the end. So let's try that in the Python
  15. interpreter. So here's the code just like we read out
  16. and we'll print out the result of making a hash table.
  17. We'll keep the number of buckets small for printing. For a real
  18. use were going to want to have many more than three buckets. And let's
  19. run that. And we see what we got is a list with
  20. three empty lists as it's elements. So this works okay. It seems like
  21. a lot more code than we need. And it is more code
  22. than we need. There's a better way to write this, which is to
  23. use a four loop. So, the general structure we've seen for four
  24. loops. Alright. We've seen a loop that has, has a structure like this,
  25. where the collection could be a list. It could be
  26. a string. [SOUND] To have a four loop, we need some
  27. set of objects that we're looping through. In this case, what
  28. we want to do is loop through the numbers from 0 to
  29. n buckets minus 1. So we want to create a list
  30. that contains those values. So we, what we would like in
  31. order to be able to define a procedure like make hash
  32. table, is to have a list, which is the numbers from
  33. 0 to n buckets minus 1. Python provides an easy
  34. way to do that, its called range. So range takes
  35. two numbers, as inputs. The start and the stop number.
  36. And what it outputs is a list of all the
  37. numbers from start up to stop minus 1. So this
  38. is what ranges outputs, a list of numbers, starting from
  39. start. Increasing by 1, until we get to stop minus
  40. 1. We'll note that it doesn't include the value passed
  41. in is the second parameter in the list. This turns
  42. out to be useful because oftentimes when we look through
  43. elements, we don't want to include the last element. So
  44. that means if we evaluated something like range 0,10, the
  45. result would be the list 0,1,2, up to 9. So
  46. now that we know about range. We could change our loop
  47. here. Instead of having this while loop, we could do
  48. the for loop. And we prefer this for two reasons. The
  49. first is it's going to make our code shorter. Anytime we
  50. can make code shorter, that's usually a good thing. The second
  51. is, it saves us from the danger of forgetting to increment
  52. the variable. This is a common mistake, and when we forget
  53. to increment the variable, the loop's just going to run forever. So
  54. if we can write our while loops as for loops, that's usually
  55. a good idea. So a better way to define the catch table
  56. is to use the for loop. We're no longer going to need the
  57. variable i. We still need table and now instead of using a
  58. y loop we're going to use a for loop. We're going to leave the
  59. variable name blank for a second, we'll figure out what to put
  60. there later, and what we're looping through. Is from the range from
  61. 0 up to nbuckets. So we want to look through the
  62. elements of the list range to nbuckets. That's going to be the
  63. list of numbers from zero to nbuckets, minus 1. And for
  64. each one of those we want to append, one new bucket to
  65. the table, just like we did before. We don't need
  66. to increment i, there's not i variable now. And at the
  67. end of the loop, we return the table just as before.
  68. For this loop, we didn't actually need a variable here, right?
  69. We never used the variable inside. For this index of the
  70. four loop, well, we still need something here, so I'm just
  71. going to call the variable unused. To make it clear that we
  72. have a name there. We don't actually use it in the body
  73. of the formula. So this makes the code a lot smaller.
  74. It will work the same way as what we had before.
  75. So here's the new code. Several lines shorter than what we
  76. had before. Does exactly the same thing. If you were really clever,
  77. you might have thought of an even shorter way.
  78. To define make hash table, that unfortunately doesn't quite
  79. work. So the shorter way would be to guess,
  80. that the times operator works on list, the same
  81. way it worked on strings. So we could do
  82. this by creating empty list, times nbuckets. This seems
  83. great, it's only one line, really clear and easy
  84. to understand, and it looks like it almost works.
  85. So let's try that in the Python interpreter. And it looks like
  86. it worked, we've got a hash table, a list with three empty
  87. buckets. There's one big problem with this approach, and I'll show you
  88. a hint why it is, and then we'll have a quiz to see
  89. if you can figure out why. So now instead of just printing
  90. out the result. We're going to assign it to a variable called table, and
  91. now we're going to mimic what would happen when we add something to
  92. the hashtable. That means we're going to add something to one of the buckets.
  93. Let's pick bucket one, and let's assume
  94. we're going to add the entry for udacity with
  95. one url. And now we can print out
  96. what's in that bucket. Looks like everything is
  97. okay. What about what's in bucket zero? Now
  98. we get the same result. So, think about
  99. what went wrong. I'm going to ask a quiz to see if you can understand why this
  100. simpler definition of make hash table doesn't actually work correctly.