English subtitles

← Hash Function - Intro to Computer Science

Get Embed Code
2 Languages

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

  1. So let's try to define a hash function
  2. that has these properties. And what we want the
  3. hash function to do is to take a string
  4. as its input, we'll call the hash function hash_string,
  5. and it'll produce as output a number between 0
  6. and b. So, we also need another input to
  7. our hash string, which is going to be the size
  8. of the hash table. So that'll be the second
  9. input is the size of the hash table, the
  10. number of buckets. What we haven't seen yet, that
  11. we're going to need for this function, is a way
  12. to turn a string into a number. Python provides an
  13. operation to do that. It's called ord as an
  14. ordinal, and what ord takes as it's input is
  15. a one letter string and produces as it's output
  16. a number. And actual mapping between strings and numbers is
  17. not so important. We just want something
  18. that is going to map different string to
  19. different numbers. There's another operator that goes in
  20. the opposite direction that takes in a number,
  21. and outputs the one-letter string that corresponds to
  22. that number. And the property these functions have
  23. is their inverses. That if we take the
  24. character corresponding to the ordinal corresponding to any
  25. one-letter string. We'll call that alpha. What we get as a result is the same
  26. alpha that we passed in. So let's try
  27. a few examples in the python interpreter to
  28. see how ord and chr work. So we'll print ord of a, and
  29. when we run that we see we get the number 97. If we try print ord of capital A.
  30. That's different. We get 65. And if we print ord of B,
  31. we get 66. So, the numbers are sort of sensible.
  32. B is higher than A. The lower case letters have
  33. different ordinals than the upper case. So, if we try
  34. a lower case b, we should expect to get 98.
  35. And that is indeed what we get. And these are
  36. the numbers based on the ASCII enchar, character encoding, what
  37. the actual numbers are, are not very important for us,
  38. other than that we get different number for different letters.
  39. So we'll be able to use the results
  40. of ord to make different strings hash to different
  41. values. And just to show that there are inter, inverses. If we do ord of u, and
  42. then chart of that, what we get back
  43. is the single letter string u that we started
  44. with. The limit of ord is it only works
  45. on one-letter strings. If it provided a mapping from
  46. any string to a number that would be useful for a
  47. hash table. Well, then we'd be done. But it doesn't do that.
  48. If we try running it on a multi-letter string, we get
  49. an error. It says that ord expects a single character, but it
  50. got a string of length 7. So we're going to need to
  51. use ord only on single letter strings. So with ord, we have
  52. a way of converting strings to numbers. Converting single character strengths
  53. to numbers. The other property we need our hash function to have,
  54. is that our output number is always between 0 and B minus 1. We need it to be in
  55. that range, because we're going to use that to index
  56. the list, to find the bucket where that string belongs.