1 00:00:04,986 --> 00:00:10,084 In this video, we're going to implement our own dictionary, using a hash table. 2 00:00:10,084 --> 00:00:14,720 Before I continue, you should know that your computer doesn't understand lists, dictionaries, 3 00:00:14,720 --> 00:00:20,640 tuples or any other kind of data structure. All your computer knows about is its memory. 4 00:00:20,640 --> 00:00:26,640 The closest data structure to your computer's memory is a one-dimensional array. The memory 5 00:00:26,640 --> 00:00:33,780 addresses are similar to indexes into an array. Each memory address can access one memory location. 6 00:00:34,400 --> 00:00:38,960 Anything more complicated than that is implemented by your programming language, and obviously, that's 7 00:00:38,960 --> 00:00:45,840 Python, in our case. Python provides implementations for lists, tuples, sets and dictionaries. These are 8 00:00:45,840 --> 00:00:50,720 the data structures that are built into Python. If the only data structure that a computer 9 00:00:50,720 --> 00:00:56,160 understands is a linear array of memory locations, it should be obvious that any data structure 10 00:00:56,160 --> 00:01:02,659 can be implemented, using an array. At a low level, that's all the computer has to work with. 11 00:01:03,440 --> 00:01:08,852 So we're going to be using fixed size lists, to create a basic dictionary implementation, 12 00:01:08,852 --> 00:01:16,160 using a hash table. A Python list is quite similar to an array, and a fixed-size list is almost identical. 13 00:01:16,160 --> 00:01:19,840 Alright, so we're going to continue on with the atrocious_hash file that we created, 14 00:01:19,840 --> 00:01:24,880 from the previous video. What we're going to need is two lists. One will hold the keys and the other 15 00:01:24,880 --> 00:01:29,440 will hold the values. So I'm going to delete this code here, where we printed it out from line 20, 16 00:01:29,440 --> 00:01:36,080 and replace it with keys is equal to, and in square brackets, two double quotes, 17 00:01:36,080 --> 00:01:45,000 an empty string and asterix 10. Next line, values equals keys.copy. 18 00:01:45,520 --> 00:01:49,200 So on line 20, I've initialized the list to hold 10 items, and all of them 19 00:01:49,200 --> 00:01:53,680 are an empty string. You saw that sequences can be multiplied, earlier in the course. 20 00:01:53,680 --> 00:01:58,240 Here we're multiplying a list, using the asterix containing the single item and empty string, 21 00:01:58,240 --> 00:02:02,400 10 times. If you come across something like that, and you're not sure what it produces, 22 00:02:02,400 --> 00:02:06,880 then just print it out. If you don't want to modify the code you're working on, you can use a Python 23 00:02:06,880 --> 00:02:14,705 console. So as an example, come up here to the Tools menu. We're going to choose Python or Debug Console. 24 00:02:15,974 --> 00:02:20,640 I'll move it up a little bit, so you can see a bit more of it. Now this is the same as typing 25 00:02:20,640 --> 00:02:26,315 Python in a command prompt or terminal, but you can do it without leaving the IDE. 26 00:02:26,880 --> 00:02:33,260 If you see a dialog like this, on Windows, make sure you tick the box to Allow access on Private networks. 27 00:02:33,260 --> 00:02:37,280 Click the Allow Access button after changing the selection to Private networks. 28 00:02:37,280 --> 00:02:42,485 If you don't do that, you'll have to configure the Windows Firewall yourself, and that can be a bit tedious. 29 00:02:42,485 --> 00:02:46,640 So tick the box, to allow the Firewall to be configured automatically, and that's again, 30 00:02:46,640 --> 00:02:52,640 only if it happens to pop up for you. Alright so back to the code. Let's start by testing this out. So square 31 00:02:52,640 --> 00:03:02,880 brackets double quotes, the asterix to multiply by 10, press enter. And you can see there, we did that to 32 00:03:02,880 --> 00:03:07,120 check what it evaluates to, and you can see that we get a list containing 10 items. Each item is 33 00:03:07,120 --> 00:03:12,487 an empty string, and that's fine because we're going to be replacing them with the real keys soon. 34 00:03:12,487 --> 00:03:17,455 So the Python console is a quick way to check expressions, or short snippets of code - very useful indeed. 35 00:03:17,455 --> 00:03:22,099 But for now, what I'm going to do is close it, because we've seen what our lists look like. 36 00:03:22,880 --> 00:03:30,060 Alright, so on line 21, we're creating a copy of the list. We've now got two lists, containing 10 items. 37 00:03:30,060 --> 00:03:35,768 We store our dictionary keys in the list called keys, and the values in the list called values. 38 00:03:35,768 --> 00:03:39,794 Before we write the code, let's have a look at what we're trying to produce. 39 00:03:40,560 --> 00:03:45,920 We saw that our hashing function produced the hash 1 for orange. That means the key orange 40 00:03:45,920 --> 00:03:52,080 goes into the keys table at index position 1. Its value goes into the values table 41 00:03:52,080 --> 00:03:58,000 at the same index position. The same for grape. The string grape hashed to the value 3, so the key 42 00:03:58,000 --> 00:04:03,440 and value go into the tables at index position 3. I've included the index numbers in the leftmost 43 00:04:03,440 --> 00:04:08,226 column of the slide, to make it easier to see what's happening. We don't store the hashes - 44 00:04:08,226 --> 00:04:13,673 we'll calculate them as they're needed. Alright, so that's what we're trying to do to implement a very basic dictionary. 45 00:04:13,673 --> 00:04:18,320 The code isn't complicated. We calculate the hash for the key, then use that to store the 46 00:04:18,320 --> 00:04:25,360 key and value in the appropriate list. I'm gonna start by re-keying some code in again, so for key comma 47 00:04:25,360 --> 00:04:30,480 value in data - probably should have left this code in rather than deleting it earlier. 48 00:04:30,480 --> 00:04:37,952 What we're going to do is type in h equals simple, simple_hash calling our function, key. 49 00:04:38,160 --> 00:04:43,200 And just to be consistent, I'll leave this commented out - this is what we were using 50 00:04:43,200 --> 00:04:50,048 to show the Python version of a hash. I'll leave that there just for clarity. Then we want to print out 51 00:04:50,240 --> 00:04:58,640 key comma h. Okay. So we're now calling our simple_hash function, and I've commented 52 00:04:58,640 --> 00:05:03,281 out the call to the built-in hash function. Well technically, I recreated it and commented it out. 53 00:05:03,281 --> 00:05:09,200 In any event, you can see what we're calling on line 24. And I left line 26 in there, just to remind us 54 00:05:09,200 --> 00:05:14,480 of the hash codes we get for each key. Alright, next what we want to do, is add the keys and 55 00:05:14,480 --> 00:05:21,000 values to the lists. Let's go ahead and do that. So here, after the print, we're going to put keys 56 00:05:21,200 --> 00:05:32,330 h equals key. On the next line, values, h in square brackets again, equals value. 57 00:05:34,400 --> 00:05:42,077 Alright, then let's, down the bottom here, line 30, I'm going to do print keys, print values. 58 00:05:43,440 --> 00:05:50,248 So we're adding our keys and values to the list. We know that h - our hash code - will be a value from 0 to 9, 59 00:05:50,248 --> 00:05:54,640 and that's derived from a call to our simple hash function, on line 24. And we're using that to 60 00:05:54,640 --> 00:06:00,442 index into the lists, replacing the empty strings with the key or value. Alright, the big thing is, 61 00:06:00,442 --> 00:06:07,439 does this work? Let's run the program and see what happens. So looking at the output, 62 00:06:07,439 --> 00:06:15,740 we can see that the first list has orange at position 1, grape at position 3, apple at position 7 and so on. 63 00:06:15,740 --> 00:06:19,578 The second list, which is the values, holds the descriptions of each fruit. 64 00:06:19,578 --> 00:06:24,000 Note that the descriptions are in the same index position as the keys that they describe. 65 00:06:24,000 --> 00:06:31,661 So a sweet, orange citrus fruit is the description for orange, and appears at index position 1. 66 00:06:32,080 --> 00:06:37,724 This is a simplified description of how Python dictionaries are implemented behind the scenes. 67 00:06:37,724 --> 00:06:41,120 Python's implementation is a bit more complicated than this. It doesn't store all 68 00:06:41,120 --> 00:06:46,720 those empty strings, for one thing. But the basic principle is the same. The hash of a key is used 69 00:06:46,720 --> 00:06:51,520 to retrieve the value from the hash table. In the next video, we'll write a get function 70 00:06:51,520 --> 00:06:56,960 to let us retrieve values. See you in the next video.