## ← Hash Function - Intro to Computer Science

• 2 Followers
• 56 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=xzQy09kBswM" data-team="udacity"></div> ``` 2 Languages

• English [en] original
• Japanese [ja]

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.