1 00:00:05,360 --> 00:00:10,640 Back in the lecture The dict documentation, we saw a major restriction on what you can use for 2 00:00:10,640 --> 00:00:16,320 a key in a dictionary. Objects that we use as keys must be hashable. Now it's time to find out 3 00:00:16,320 --> 00:00:22,293 what that means. We saw the Python definition of hashable in the glossary, and I've got that on screen now. 4 00:00:22,293 --> 00:00:26,880 The link is in the resources section. You can see here that it says An object is hashable 5 00:00:26,880 --> 00:00:31,440 if it has a hash value which never changes during its lifetime. In this video, we'll see what a 6 00:00:31,440 --> 00:00:36,720 hash value is, and how a hash function is used to calculate it. Alright, so let's have a look at 7 00:00:36,720 --> 00:00:43,840 what Wikipedia has to say about hash functions. So a bit of googling will get you to this page. 8 00:00:45,040 --> 00:00:50,640 So it starts off by saying that a hash function is any function that can be used to map data of 9 00:00:50,640 --> 00:00:56,934 arbitrary size to fixed-size values. That's important, but may not make much sense. 10 00:00:56,934 --> 00:01:02,160 When it talks about size, it's referring to the size when stored in a computer's memory. 11 00:01:02,160 --> 00:01:06,891 We use this image to explain why it's important to have a fixed-size hash. 12 00:01:07,920 --> 00:01:12,080 We've got four strings that we want to use as keys. As you can see, the names have different 13 00:01:12,080 --> 00:01:18,960 numbers of characters. Sam Doe contains seven characters including the space. Sandra Dee contains 14 00:01:18,960 --> 00:01:24,160 10 characters. When we pass those names to this hash function, we get an integer in the range 15 00:01:24,160 --> 00:01:30,690 of 0 to 15, inclusive. All those integers are the same size. Now I know that might sound strange - 16 00:01:30,690 --> 00:01:38,080 15 is obviously larger than 0 - but in the computer's memory, all those values can be stored using 4 bits. 17 00:01:38,080 --> 00:01:44,560 They'll certainly fit in a single memory location, on a 32 or 64-bit computer. We don't know exactly 18 00:01:44,560 --> 00:01:50,129 what that hash function is doing, but we know that we can pass strings of variable lengths to it. 19 00:01:50,129 --> 00:01:54,861 The output will always be an integer - hash functions will often return integer values. 20 00:01:54,861 --> 00:01:59,520 But be aware that they don't have to - it's not a requirement that the hash codes be unique. 21 00:01:59,520 --> 00:02:05,680 In this diagram, the hash function produces the same hash code for John Smith and Sandra Dee. 22 00:02:05,680 --> 00:02:11,360 The hash code for both those strings is the value 2. That's called a collision. Data structures that use 23 00:02:11,360 --> 00:02:17,243 hashes need some way to handle collisions, because two or more keys could produce the same hash code. 24 00:02:17,243 --> 00:02:21,280 Now that's more detail than I want to get into at this stage. We're not going to discuss strategies 25 00:02:21,280 --> 00:02:25,600 for handling collisions. We're learning how to use dictionaries - we're not learning how to write the 26 00:02:25,600 --> 00:02:30,400 code to implement them. But it's interesting to see how all this is used in practice, so we're 27 00:02:30,400 --> 00:02:36,593 going to write a very basic dictionary structure in the next lecture. Before then, though, I'm going to close this image, 28 00:02:36,593 --> 00:02:40,960 and we'll see what else Wikipedia has to say about hashes and hash functions. 29 00:02:40,960 --> 00:02:46,160 The second sentence gives some terminology. Those values are referred to by various names. 30 00:02:46,160 --> 00:02:51,900 I've called them hash codes up to now, but from now on, I'm just going to refer to them as hashes. 31 00:02:51,900 --> 00:02:58,789 So the next sentence in that first paragraph, explains that hashes are used to index into a fixed-size table, 32 00:02:58,789 --> 00:03:04,800 called a hash table. One example is a Python list. You could use a list as a hash table if you 33 00:03:04,800 --> 00:03:09,440 initialize it to the size you need, and that's what we'll do in the next video. Looking at the image 34 00:03:09,440 --> 00:03:16,668 on the right again, we can see that the hashes could be used as indexes into a list of length 16. 35 00:03:16,668 --> 00:03:22,985 If you wanted to find Sam Doe, you'd calculate its hash and go straight to index position four. 36 00:03:24,240 --> 00:03:28,160 And that's a very important point. If you can calculate a hash, 37 00:03:28,160 --> 00:03:34,480 and use it to go directly to an entry in a hash table, then accessing the data becomes very fast. 38 00:03:34,480 --> 00:03:38,355 If we assume a perfect hash function - one that produces no collisions - 39 00:03:38,355 --> 00:03:41,920 then we can retrieve values from a table containing millions of entries, 40 00:03:41,920 --> 00:03:46,480 in the same time as a table containing only a handful of entries. It doesn't matter how many 41 00:03:46,480 --> 00:03:52,899 items are in the hash table, we calculate the hash, and retrieve the value with a single operation. 42 00:03:54,320 --> 00:03:58,000 So that's why we're retrieving a value from a dictionary, using its key, 43 00:03:58,000 --> 00:04:03,200 is so fast. The speed doesn't depend on how many items are in the dictionary, it depends on 44 00:04:03,200 --> 00:04:09,503 how fast the hashing function can calculate the hash. Accessing an item in a dictionary 45 00:04:09,503 --> 00:04:14,560 will be slightly slower than indexing a list, because of the time taken to calculate the hash. 46 00:04:14,560 --> 00:04:19,386 But it's largely independent of the number of items you've stored in the dictionary. 47 00:04:19,386 --> 00:04:25,000 The hash functions, that most dictionaries use, have been designed to execute quickly. 48 00:04:25,000 --> 00:04:30,960 Alright, so I'm going to close this window down again. Just scroll down to the Overview function, down here. 49 00:04:30,960 --> 00:04:35,440 You saw that was just after the table of contents. Now it's worth reading through this, and also the 50 00:04:35,440 --> 00:04:40,884 first part of the hashes table section - you can see that towards the bottom of the screen. 51 00:04:40,884 --> 00:04:46,240 We will be looking at each of those bullet points in an Overview, when we write our own hash function, next. 52 00:04:46,240 --> 00:04:50,400 If you want to skim through the whole article, you'll learn all sorts of interesting things. 53 00:04:50,400 --> 00:04:54,080 For example, there are sections describing a range of different hashing algorithms, 54 00:04:54,080 --> 00:04:59,040 for numbers and strings. There's no single, right way to create hashes - there are loads of different 55 00:04:59,040 --> 00:05:03,920 ways to do it. You'll see a description of an algorithm that uses the Fibonacci numbers, 56 00:05:03,920 --> 00:05:09,220 if you check out the various ways shown here. Now we wrote a function for calculating Fibonacci numbers, 57 00:05:09,220 --> 00:05:14,080 in the Functions section of this course, and this is one use for them. But before I leave 58 00:05:14,080 --> 00:05:19,720 you to read all this, here's a tip: When you get to stuff that makes no sense at all, move on. 59 00:05:19,720 --> 00:05:25,851 Don't waste time trying to understand things like - and I'll search for this - algebraic coding, 60 00:05:26,960 --> 00:05:33,405 and you see this example here. Now all of that might make sense to you, but the chances are, 61 00:05:33,405 --> 00:05:38,880 it just looks horrible and scary. That's fine, move on. Unless you have to write your own hashing function, 62 00:05:38,880 --> 00:05:42,130 you don't actually need to understand all of this. 63 00:05:43,440 --> 00:05:48,320 That's a good tip when reading any documentation, by the way - if it looks like complete nonsense, 64 00:05:48,320 --> 00:05:52,640 then move on. If a section of documentation is going to be useful to you, then you'll 65 00:05:52,640 --> 00:05:57,680 know everything you need to understand it. If you can't make sense of it, then it's no use to you. 66 00:05:57,680 --> 00:06:01,440 Sitting there, staring at it and panicking, won't achieve anything. 67 00:06:01,440 --> 00:06:06,480 If I was asked to write a hashing function, using algebraic coding, I'd probably have to spend a week 68 00:06:06,480 --> 00:06:11,706 or so brushing up on the maths behind it. It'd be more efficient for me to ask someone else to do it. 69 00:06:11,706 --> 00:06:18,138 I'd ask J-P, but he already told me that none of this algebra coding made any sense to him, either. 70 00:06:18,720 --> 00:06:23,840 So the point here, don't panic when you see stuff like this. You'd have to be programming for years, 71 00:06:23,840 --> 00:06:28,320 before anyone would consider asking you to write a hashing function. Even then, it would 72 00:06:28,320 --> 00:06:33,360 be a job more suited to a mathematician than a programmer. Skip the bits you don't understand, 73 00:06:33,360 --> 00:06:39,610 focus on the bits you do, and you should come away from this article with the following points: 74 00:06:40,000 --> 00:06:46,000 A hash function produces fixed-size hash values from its input. The hashes are usually integers, 75 00:06:46,000 --> 00:06:50,880 but don't have to be. There are many different ways to implement a hash function. There's no single 76 00:06:50,880 --> 00:06:56,240 way to write one, and different algorithms have their own strengths, weaknesses and applications. 77 00:06:56,240 --> 00:07:01,103 A hash function produces values that can be used to index a fixed-size data structure 78 00:07:01,103 --> 00:07:06,880 called a hash table. If the hash table can hold 500 items, then the hash function should produce 79 00:07:06,880 --> 00:07:13,200 500 distinct hashes. A hash, or hash code, doesn't have to be unique. For example, two different 80 00:07:13,200 --> 00:07:18,720 strings can have the same hash. That's known as a collision. There are several different 81 00:07:18,720 --> 00:07:22,960 strategies for handling collisions. One of the simplest, is to dump all keys with the 82 00:07:22,960 --> 00:07:28,320 same hash into the same bucket. You then compare each item in the bucket with the original key, 83 00:07:28,320 --> 00:07:33,760 to see if it exists. Because handling collisions is slower than indexing directly into the table, 84 00:07:33,760 --> 00:07:38,480 it's important that a hashing function produces as few collisions as possible. The best case is 85 00:07:38,480 --> 00:07:44,640 that every key has a unique hash. And finally, the worst case is every key has the same hash. If that 86 00:07:44,640 --> 00:07:49,840 happens, the hashing function isn't suitable for that particular application. Alright, so moving on. 87 00:07:49,840 --> 00:07:56,240 In the next couple of videos, we'll see how a hash table works in practice. See you in the next video.