1 00:00:00,460 --> 00:00:06,910 ‫So now we're going to do hash tables and with a hash table, we're going to have an address space. 2 00:00:07,120 --> 00:00:10,660 ‫And this address space is just an array. 3 00:00:10,960 --> 00:00:18,340 ‫And what I'm going to do in this section is use a hash table for keeping the inventory of a hardware 4 00:00:18,340 --> 00:00:18,940 ‫store. 5 00:00:19,300 --> 00:00:23,950 ‫And one of the things that we would have in a hardware store would be nails. 6 00:00:24,400 --> 00:00:33,760 ‫This is what is known as a key value pair, where nails is the key and a thousand is the value. 7 00:00:34,150 --> 00:00:39,400 ‫And what we'll do with this key value pair is we will run it through a hash function. 8 00:00:39,400 --> 00:00:45,070 ‫We will write that hash function in a couple of videos, but I'm just going to graphically represent 9 00:00:45,070 --> 00:00:45,820 ‫it here. 10 00:00:46,300 --> 00:00:50,140 ‫And the hash is performed on the key. 11 00:00:50,410 --> 00:00:54,640 ‫So we run the key through the hash, we'll get our key value pair back. 12 00:00:54,640 --> 00:01:02,620 ‫But the thing that the hash function does is based on the calculation that we do on this key, it gives 13 00:01:02,620 --> 00:01:04,690 ‫us an address. 14 00:01:05,050 --> 00:01:11,980 ‫And that address is one of the indexes in this address space, and that is where this key value pair 15 00:01:12,010 --> 00:01:13,240 ‫will be stored. 16 00:01:13,630 --> 00:01:19,600 ‫So now let's talk a little bit more about this hash function that we're going to write and the characteristics 17 00:01:19,600 --> 00:01:20,140 ‫of it. 18 00:01:20,500 --> 00:01:25,450 ‫So the first thing to know about hashes is they are one way. 19 00:01:25,840 --> 00:01:32,500 ‫So let's say if we have a key nails and we run it through the hash function and it produces the number 20 00:01:32,500 --> 00:01:39,850 ‫two, you cannot take the number two and run it through the hash and get nails. 21 00:01:39,850 --> 00:01:41,950 ‫It only goes one way. 22 00:01:42,630 --> 00:01:47,040 ‫The other thing about hashes is that they are deterministic. 23 00:01:47,040 --> 00:01:56,010 ‫And that means if Nails produces the number two, it will always produce the number two. 24 00:01:56,520 --> 00:02:01,260 ‫So this hash function contains both of these characteristics. 25 00:02:01,770 --> 00:02:04,230 ‫So let's bring our address space back here. 26 00:02:04,860 --> 00:02:12,330 ‫So we will create a couple of other functions in the hash table section that will use the hash function. 27 00:02:12,750 --> 00:02:15,540 ‫One of those will be set. 28 00:02:15,840 --> 00:02:18,840 ‫We'll pass this a key and a value. 29 00:02:19,200 --> 00:02:22,980 ‫So let's say we pass this nails and 1000. 30 00:02:23,280 --> 00:02:29,760 ‫The set function will call on the hash function and the set function will create this key value pair. 31 00:02:29,760 --> 00:02:36,240 ‫But the hash function will create an address and that is where we'll store the key value pair. 32 00:02:36,750 --> 00:02:39,900 ‫So let's add a few more of these to our hash table. 33 00:02:39,900 --> 00:02:46,850 ‫Say we have set screws and that'll create this key value pair and an address of six. 34 00:02:46,860 --> 00:02:52,980 ‫That key value pair goes down there and then we'll say, set nuts, 1200. 35 00:02:53,340 --> 00:02:55,080 ‫Now when we do this. 36 00:02:55,800 --> 00:02:59,280 ‫We get an address we've already used. 37 00:02:59,790 --> 00:03:02,280 ‫This gives us an index of two. 38 00:03:02,670 --> 00:03:07,800 ‫Now, what we don't want to do is overwrite the other key value pair. 39 00:03:07,800 --> 00:03:13,080 ‫We want to leave the other key value pair there and add this one. 40 00:03:13,500 --> 00:03:20,970 ‫What this situation is called a collision where you have more than one key value pair at a particular 41 00:03:20,970 --> 00:03:21,810 ‫address. 42 00:03:22,200 --> 00:03:26,610 ‫And we'll talk about a couple of ways that can be dealt with in the next video. 43 00:03:27,030 --> 00:03:28,830 ‫So let's just add one more. 44 00:03:28,830 --> 00:03:31,110 ‫So we have a more full hash table. 45 00:03:31,110 --> 00:03:36,690 ‫We'll say set bolts, we'll get a key value pair and an address and that goes there. 46 00:03:36,690 --> 00:03:44,160 ‫And that brings us to the next function that will build, which is called Get Get also uses the hash 47 00:03:44,160 --> 00:03:47,280 ‫function and remember that hashes are deterministic. 48 00:03:47,280 --> 00:03:53,310 ‫So when we run bolts through this, we know the index where bolts would be stored. 49 00:03:53,310 --> 00:03:55,380 ‫It's going to be at the index of four. 50 00:03:55,530 --> 00:04:02,040 ‫So we go to the index of four and we'll return the value that goes with that key value pair. 51 00:04:02,580 --> 00:04:06,030 ‫So now let's look at get on another key value pair. 52 00:04:06,030 --> 00:04:07,770 ‫We'll say nails. 53 00:04:08,010 --> 00:04:11,790 ‫And when we run this, we get the index of two. 54 00:04:11,790 --> 00:04:16,350 ‫And at the index of two we have more than one key value pair. 55 00:04:16,680 --> 00:04:22,470 ‫So part of the get function is we're going to have to have a way to iterate through all the different 56 00:04:22,470 --> 00:04:26,100 ‫key value pairs that might be at a particular address. 57 00:04:26,400 --> 00:04:33,330 ‫And when we iterate through in this situation, we will find nails and return 1000. 58 00:04:33,930 --> 00:04:38,160 ‫And that is our quick introduction to hash tables.