1 00:00:05,120 --> 00:00:10,240 The function to get values from our simple dictionary is quite straightforward. We calculate 2 00:00:10,240 --> 00:00:15,600 the hash of the key, and use that to index into the values list. So let's add that function, 3 00:00:15,600 --> 00:00:19,845 after our simple_hash function, with two blank lines before it. 4 00:00:19,845 --> 00:00:28,080 So I'm going to type def get parentheses k colon string, and dash greater than sign str colon. 5 00:00:28,080 --> 00:00:32,420 We'll add a doc string there, return the value for a key, 6 00:00:33,760 --> 00:00:40,752 or none, if the key does not exist. Fix that up as well 7 00:00:41,280 --> 00:00:45,120 Alright, so in terms of the code; hash_code 8 00:00:45,120 --> 00:00:50,237 is equal to simple_hash, and in parentheses, k. 9 00:00:50,479 --> 00:00:56,614 If values square bracket hash_code colon 10 00:00:56,614 --> 00:01:05,894 return values hash_code square brackets else colon return None. 11 00:01:08,640 --> 00:01:15,520 Now you may get a warning like I'm getting, on line 26 here; Expected type str got None instead. 12 00:01:15,520 --> 00:01:19,280 That's okay - we can ignore that for now. It's appearing because we've annotated the function as returning 13 00:01:19,280 --> 00:01:25,177 a string, on line 20. If the key isn't in the dictionary, we're returning None instead. 14 00:01:25,177 --> 00:01:29,440 There is a way to deal with this situation, and we'll look at how to write the correct annotation later, 15 00:01:29,440 --> 00:01:34,160 when we revisit Functions. Okay though, let's test the function. I'm going to do that, I'm going to 16 00:01:34,160 --> 00:01:40,678 come down to the end of our code, down here. Add an empty print there - print with just parentheses. 17 00:01:40,678 --> 00:01:46,793 Then we're going to do a lookup, so value equals get parentheses double quotes lemon. 18 00:01:46,960 --> 00:01:53,840 So I'm retrieving the value for lemon. Let's print out value as well. Alright, so let's run this. 19 00:01:55,120 --> 00:01:59,920 And you can see the output. We get the correct value for lemon - a sour, yellow citrus fruit 20 00:01:59,920 --> 00:02:04,720 So test the function with different keys. I'm going to come down here and change it to grape, 21 00:02:04,720 --> 00:02:11,600 just to make sure it's working okay. That's working fine as well. When testing, make sure 22 00:02:11,600 --> 00:02:16,000 you don't use an empty string. The simple_hash function will crash if you pass 23 00:02:16,000 --> 00:02:22,701 an empty string to it. As I said, we're using this to demonstrate how a dictionary uses a hash table. 24 00:02:24,240 --> 00:02:29,067 This definitely isn't production quality code, and we didn't include any error handling in the function. 25 00:02:29,067 --> 00:02:36,598 If the key doesn't exist, we should get None. So let's actually try that. We'll try it with tomato. 26 00:02:39,680 --> 00:02:43,280 The key tomato doesn't exist and we get None printed out. So our get function's 27 00:02:43,280 --> 00:02:46,668 behaving very much like the dictionary get method. 28 00:02:47,840 --> 00:02:51,920 We haven't written a complete implementation of a dictionary, but this code does demonstrate 29 00:02:51,920 --> 00:02:56,560 how Python's dictionaries work. The real implementation works very similar to this. 30 00:02:56,560 --> 00:03:00,960 It uses a hash table, to allow keys to be accessed very quickly. 31 00:03:00,960 --> 00:03:05,927 Hashes of the keys are used as the indexes into the hash function. 32 00:03:06,480 --> 00:03:11,680 Unfortunately though, our implementation is broken. We saw that hashes can have collisions - that's when 33 00:03:11,680 --> 00:03:17,360 two different keys have the same hash. With a serious hash function, collisions will be rare, 34 00:03:17,360 --> 00:03:23,217 and the Python dict contains code to handle collisions. Our dictionary doesn't handle collisions. 35 00:03:23,217 --> 00:03:27,440 It also uses a really bad hashing function, that results in over half of the 36 00:03:27,440 --> 00:03:34,490 keys producing the same hash. So let's see what happens when we try to get the value for banana. 37 00:03:38,640 --> 00:03:46,080 Run this, and you can see that the result is, the value for lemon being printed out. The hash for b 38 00:03:46,080 --> 00:03:50,800 is the same as the hash for l, and we get the wrong value. Now that's not good, and we can 39 00:03:50,800 --> 00:03:55,760 see why I've repeatedly said that this isn't production quality code. What we've produced 40 00:03:55,760 --> 00:04:02,371 is just for educational purposes. You now understand how a dictionary uses hash tables. 41 00:04:03,280 --> 00:04:08,400 Retrieving a value for a key is very fast. Importantly, it's fast no matter how many 42 00:04:08,400 --> 00:04:14,000 items are in the dictionary. We calculate an index position, and can go directly to that position to 43 00:04:14,000 --> 00:04:19,279 retrieve a value. Compare that to finding an item in an unsorted list. You'd check the 44 00:04:19,279 --> 00:04:23,040 first value, to see if it's the one you want. You'd then do the same with the next value, 45 00:04:23,040 --> 00:04:28,632 and so on, until you either find what you're looking for, or you reach the end of the list. 46 00:04:29,200 --> 00:04:33,680 As the list gets larger, the number of checks you'll need also get larger. On average, you 47 00:04:33,680 --> 00:04:38,000 need to check more and more values to find the one you want. Getting a value from a dictionary 48 00:04:38,000 --> 00:04:43,328 takes the same amount of time, no matter how many items are in the dictionary. That's called constant time, 49 00:04:43,328 --> 00:04:48,000 or O1. We'll see what that means, later in the course, when we learn about Big O notation. 50 00:04:48,000 --> 00:04:52,160 I don't want to digress to talk about Big O notation just yet, because we're focusing 51 00:04:52,160 --> 00:04:57,490 on dictionaries and how they work. But as we're discussing hash functions, I'm going to digress slightly. 52 00:04:57,490 --> 00:05:01,520 We'll be looking at hash functions as they relate to finding values in a dictionary. 53 00:05:01,520 --> 00:05:07,120 They have other uses, and one of those is security. We'll have a quick look at that, in the next video.