1 00:00:05,200 --> 00:00:10,800 We've now got an idea of what a hashing function is, but it's all been very theoretical. 2 00:00:10,800 --> 00:00:17,040 In this video, we'll write our own hashing function and see how it can be used in practice. The title 3 00:00:17,040 --> 00:00:22,720 of this video should have made the point that this is going to be a really bad hashing function. 4 00:00:22,720 --> 00:00:26,160 We're going to look at a very simple implementation, and you wouldn't use 5 00:00:26,160 --> 00:00:30,720 anything this simple in your code. But as I've already mentioned in the previous video, 6 00:00:30,720 --> 00:00:35,408 you'll probably never have to write your own hashing function anyway. 7 00:00:35,920 --> 00:00:39,920 Python comes with one built in, and there are modules in the standard library, 8 00:00:39,920 --> 00:00:45,520 that you can also use. So just to be doubly clear, this video is purely for educational 9 00:00:45,520 --> 00:00:51,120 purposes. It's intended to help you understand how hashes are used. It's very definitely 10 00:00:51,120 --> 00:00:58,951 not code that you'd use. Alright, so I'm going to call my new Python file now, atrocious_hash, 11 00:00:58,951 --> 00:01:07,599 just to make it really clear, and remind us that this hashing function really is bad. 12 00:01:12,960 --> 00:01:18,240 Alright, so I'm going to paste in some data for us to work with. 13 00:01:18,240 --> 00:01:22,320 I've done this so that we don't have to keep typing input to our program. It would be a bit 14 00:01:22,320 --> 00:01:27,232 annoying to have to type in the names of the fruit, and the descriptions, every time we ran the program. 15 00:01:27,232 --> 00:01:30,960 We're getting them from this list to save some time. So we've got five strings that we're going 16 00:01:30,960 --> 00:01:39,040 to use, as the keys in our dictionary. That's orange, apple, lemon, grape and melon on lines two to six. 17 00:01:39,040 --> 00:01:42,960 If we're going to create an integer value from these strings, we need some way to get an integer 18 00:01:42,960 --> 00:01:49,600 from each letter. Python has a function to do that - the ord function. I'll demonstrate it quickly here; 19 00:01:49,600 --> 00:01:59,472 print parentheses ord parentheses a. Let's do the same for two other letters - 20 00:01:59,920 --> 00:02:03,120 do the same for b and z. 21 00:02:04,000 --> 00:02:06,032 Let's run it. 22 00:02:07,280 --> 00:02:10,800 We get the value 97 for the character a, 98 for b and so on, 23 00:02:10,800 --> 00:02:16,192 and character z, as you can see there, is represented by 122. 24 00:02:18,000 --> 00:02:22,480 Every character is represented by a number, when it's stored in the computer. In the very early days 25 00:02:22,480 --> 00:02:28,720 of computing, that used to be an ASCII value. ASCII stands for American Standard Code for Information 26 00:02:28,720 --> 00:02:33,440 Interchange, Google for ASCII if you want to know more about it - it's useful to understand 27 00:02:33,440 --> 00:02:37,360 some of the history of computers. But that's not essential for what we're doing here - 28 00:02:37,360 --> 00:02:43,040 all you need to know is that every character is represented by a unique number. These days 29 00:02:43,040 --> 00:02:49,680 we don't use ASCII - we use unicode. ASCII can only represent 127 different characters, and that's not 30 00:02:49,680 --> 00:02:55,920 enough to handle all the languages and character sets that are used throughout the world. Okay, 31 00:02:55,920 --> 00:03:01,120 so now that we've got the ord function to convert a character to a number, we can write our simple 32 00:03:01,120 --> 00:03:08,240 hashing function. I'm going to comment out these three lines that we just used for a test there. 33 00:03:08,720 --> 00:03:16,160 Let's go ahead and add the function now. So def simple_hash parentheses 34 00:03:16,160 --> 00:03:25,168 s colon string, the dash greater than int colon and documentation - 35 00:03:25,600 --> 00:03:31,840 a ridiculously simple hashing function. 36 00:03:36,240 --> 00:03:45,968 I'm going to start with basic_hash is equal to ord parentheses, then s square brackets 0, 37 00:03:45,968 --> 00:03:53,904 return basic_hash percent 10. Obviously we're using the remainder operator there. 38 00:03:53,904 --> 00:03:59,616 Alright, so we're passing a string that's an argument to the function, and it returns an int. 39 00:03:59,616 --> 00:04:05,040 And the implementation is very simple, as the Docstring says. So we start on line 16, with the 40 00:04:05,040 --> 00:04:10,640 ordinal value of the first character of the string. For lowercase letters, that gives us an integer 41 00:04:10,640 --> 00:04:17,680 in the range from 97 to 122. We then take the remainder after dividing by 10, on line17. 42 00:04:17,680 --> 00:04:22,000 That reduces the range to integers from 0 to 9. Before we look at using the hashes 43 00:04:22,000 --> 00:04:26,752 that our function returns, let's check that this works. We're going to type in some code, and loop 44 00:04:26,752 --> 00:04:33,280 through all the keys in the data, and print out the hash for each one. Let's go ahead and do that. 45 00:04:33,680 --> 00:04:42,320 So for key comma value in data colon h equals simple_hash, 46 00:04:42,320 --> 00:04:52,528 and we'll pass key in parentheses. Then we'll print parentheses key comma h. Okay, so let's run that. 47 00:04:52,960 --> 00:04:56,768 As you can see there, we get the strings that we're hashing, and the hash for each one. 48 00:04:56,768 --> 00:05:03,776 The hash codes are an integer, from zero to nine, so we've got one for orange, seven for apple and so on. 49 00:05:04,560 --> 00:05:08,592 In the Wikipedia Overview about hash functions that we looked at in the last video, 50 00:05:08,592 --> 00:05:13,600 there were three bullet points. Let's see how our function satisfies those three points. 51 00:05:13,600 --> 00:05:19,920 One: Convert variable length keys into fixed length - usually machine word length or less - values, 52 00:05:19,920 --> 00:05:26,304 by folding them by words or other units, using a parity-preserved operator like ADD or XOR. 53 00:05:26,304 --> 00:05:32,960 Our simple hash function maps any string into a fixed size value - an integer in the range 0 to 9. 54 00:05:32,960 --> 00:05:39,840 We only use the first character of the string, but a hash function would normally use all characters. 55 00:05:39,840 --> 00:05:44,720 We could add the ordinal values of each character, and use the total of all the ordinal values. 56 00:05:44,720 --> 00:05:49,680 But we're deliberately keeping this simple, and want a small integer value to be produced. 57 00:05:49,680 --> 00:05:54,800 Two: Scramble the bits of the key so that the resulting values are uniformly distributed over 58 00:05:54,800 --> 00:06:01,120 the key space. Our scrambling is very basic. We take the remainder after dividing by 10. More serious 59 00:06:01,120 --> 00:06:09,296 strategies include stripping off all but the low 64 bits of the result - if a 64-bit hash is needed. 60 00:06:09,920 --> 00:06:15,040 And three: Map the key values into ones less than or equal to the size of the table. 61 00:06:15,040 --> 00:06:19,936 We're doing that by only using the last digit. That gives a value in the range 0 to 9. 62 00:06:19,936 --> 00:06:26,560 The length of our table will be 10. In the next video, we're going to use these hashes as indexes 63 00:06:26,560 --> 00:06:31,360 into a hash table. And that's why I've kept this range small - you wouldn't want to examine tables 64 00:06:31,360 --> 00:06:36,800 with thousands of entries, to see how things work. Using a small table with 10 items, makes it a 65 00:06:36,800 --> 00:06:43,520 lot easier to see what's going on. But in practice, the range of possible hashes would be much larger 66 00:06:43,520 --> 00:06:48,480 As an example, let's have a look at what Python's built-in hash function produces. We're going to 67 00:06:48,480 --> 00:06:54,080 comment out the lines that use our simple hash, and call the built-in hash function instead. 68 00:06:54,080 --> 00:07:05,440 Let's have a go at doing that. So h equals hash parentheses key. Let's run this. As you can see, Python's hash 69 00:07:05,440 --> 00:07:11,440 function produces much larger values. On a 64-bit version of Python, you get a 64-bit 70 00:07:11,440 --> 00:07:16,640 integer value. That gives about 1.8 million trillion different hash codes. There are a few 71 00:07:16,640 --> 00:07:23,680 things I should mention about Python's hash codes, because you could be getting confusing results. 72 00:07:23,680 --> 00:07:27,600 First, Python's hash function randomizes the hashes that it produces. 73 00:07:27,600 --> 00:07:31,920 You'll get the same hash for any particular string, while your program's running. 74 00:07:31,920 --> 00:07:38,256 But each time you run the program, the hash codes will be different. This was introduced in Python 3.3 75 00:07:38,256 --> 00:07:44,080 to prevent Denial of Service, or DoS attacks on web servers using Python dictionaries. 76 00:07:44,080 --> 00:07:50,192 So don't be confused if you get different hashes for the strings, each time you run the program. 77 00:07:51,040 --> 00:07:55,080 Second, integers that have their high bit set are interpreted as negative. 78 00:07:55,080 --> 00:08:00,560 That's why some of the hashes, as you can see, print out as negative. Google for two's complement, 79 00:08:00,560 --> 00:08:07,120 if you want to learn more about how negative numbers are stored, in a computer. So finally, you can see 80 00:08:07,120 --> 00:08:12,080 why I've written that very simple hash function. If we try working with tables that can contain 81 00:08:12,080 --> 00:08:17,200 trillions of items, we're going to get into a right mess. Our hashing function is very simple, 82 00:08:17,200 --> 00:08:23,120 but it allows us to work with a very small table - only 10 items - so that we can see what's going on. 83 00:08:23,120 --> 00:08:28,160 Really finally - following on from the last point - don't be worried that Python creates hash tables 84 00:08:28,160 --> 00:08:33,840 with trillions of items, for its dictionaries. It uses techniques such as sparse arrays, 85 00:08:33,840 --> 00:08:39,200 so that only the non-empty values get stored. Alright. So we've got a simple hash function, 86 00:08:39,200 --> 00:08:44,880 and we'll use that to see how looking up values in a hash table is very fast. See you in the next video.