English subtitles

← Update Solution - Intro to Computer Science

Get Embed Code
2 Languages

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

  1. So update's going to be pretty similar to look
  2. up. So let's start by copying that code and
  3. seeing how we need to change it. So we
  4. have lookup. We're going to change it to be update.
  5. Now instead of taking a key as its input, it's going to take a key and a value.
  6. But it's not going to return anything, so we're going to get rid
  7. of the returns. Right. remember all update is doing is modifying the
  8. value of entry. So now we still have what we had for
  9. lookup, we're still getting the bucket and we want to do that.
  10. We want to make sure that we update the value in the
  11. right bucket. We still need to look through the entries in the
  12. bucket, to find if one matches. If we find one that matches,
  13. well what we did in lookup, was just return it. And update,
  14. what we want to do is change the value associated with
  15. that key. So we are going to have an assignment that replaces
  16. whatever value is there before with a new value. And now
  17. instead of returning the value, we want to stop going through the
  18. loop, and we actually are done with update, so we can
  19. return here. We found the entry, we updated the value. We
  20. also need to deal with a case where we didn't find
  21. the entry. So now we've gone through the loop enough times.
  22. When it was a look-up we just returned none. When it's
  23. an update what we want to do when the key is not
  24. already in the table, is add it. So now we're going
  25. to use, append, to add a new entry to bucket, that has
  26. the key and the value. So that's how we defined update.
  27. There's certainly lots of other ways to do it, and one
  28. thing you should be thinking about is, well this is actually
  29. very similar to look up, right. We duplicated a lot of code.
  30. Maybe there's a way to define update and lookup so
  31. we don't have to have two copies of the code,
  32. that scans through the bucket to find the right entry.
  33. We'll leave that as a homework question for this unit.
  34. For now we're going to be happy that we've got correct
  35. implementations of both lookup and update. And, let's test them.
  36. So, what we did before, we're going to replace the adds
  37. with updates, and now, the second time, what happened with
  38. the add was we added an entry, but we could
  39. never reach that entry because it had the same keyword.
  40. Now we're used update, the second time we should be
  41. updating that value, and we'll see that the lookup now produces
  42. the value 27, for the second lookup. That's good, right,
  43. the first time the value was 23. We did the update,
  44. we got 27, and we can see that the bucket
  45. only contains one entry. So this is great, we finished our
  46. implementation of the hash table. We can do updates that will
  47. either add new values to the hash table, if they don't
  48. already exist, or change the value of ones that exist. And
  49. we can do lookups and lookup will know where to look, which
  50. bucket to look in to find that key, if it exists.
  51. So this has the great property that as the number of keys
  52. increase. As long as we increase the numbers of buckets accordingly,
  53. the time to do both an update and a lookup is constant.
  54. This means the time doesn't increase even as the number of keywords increases,
  55. as long as we increase the number of buckets. So, this size of
  56. each bucket stays the same size, because the expensive cost of this is
  57. going through the elements in the bucket looking for the key that matches.