1 00:00:01,560 --> 00:00:03,917 - [Instructor] Okay, so let's make a HashTable. 2 00:00:05,570 --> 00:00:08,380 Let's start with a header file 3 00:00:11,930 --> 00:00:13,430 and we'll call that HashTable. 4 00:00:19,940 --> 00:00:24,070 And let's see, what are we gonna need? 5 00:00:24,070 --> 00:00:27,890 Let's use that snippet from the previous video, 6 00:00:27,890 --> 00:00:29,690 one of the previous videos, anyway. 7 00:00:29,690 --> 00:00:33,723 This is the optionals here. 8 00:00:36,940 --> 00:00:39,360 I'll explain again what that is in case you missed that 9 00:00:39,360 --> 00:00:41,640 in the one of the previous videos. 10 00:00:41,640 --> 00:00:45,643 What we're doing here is we want to use C++ optionals, 11 00:00:46,755 --> 00:00:50,110 and they're in different locations depending 12 00:00:50,110 --> 00:00:53,570 on the standard of C++ that you're using. 13 00:00:53,570 --> 00:00:57,470 If your standard is less than 17, 14 00:00:57,470 --> 00:01:00,130 they're to be found in experimental. 15 00:01:00,130 --> 00:01:04,470 And if your standard is 17 or greater, 16 00:01:04,470 --> 00:01:09,130 they're kind of built in and you can just include optional 17 00:01:09,130 --> 00:01:12,700 directly rather than experimental optional. 18 00:01:12,700 --> 00:01:15,790 So, we have these preprocessor directive 19 00:01:15,790 --> 00:01:18,310 with a little if else to handle that. 20 00:01:19,880 --> 00:01:22,070 And what else are we gonna need? 21 00:01:22,070 --> 00:01:23,500 We're gonna need functional. 22 00:01:23,500 --> 00:01:26,463 That was also introduced in an earlier video. 23 00:01:30,970 --> 00:01:33,370 So, let me stop here and say this. 24 00:01:33,370 --> 00:01:36,250 If you haven't watched the videos 25 00:01:36,250 --> 00:01:39,540 for optionals and passing functions, 26 00:01:39,540 --> 00:01:42,260 then please go back and watch those videos 27 00:01:42,260 --> 00:01:43,960 before you continue with this one. 28 00:01:45,200 --> 00:01:48,493 That said, I'm gonna need iostream. 29 00:01:55,340 --> 00:01:56,733 We're gonna need string. 30 00:02:01,360 --> 00:02:02,760 And we're gonna need vector. 31 00:02:08,670 --> 00:02:11,000 What I'm going to do is I'm gonna go through HashTable, 32 00:02:11,000 --> 00:02:13,700 make a very simple HashTable, 33 00:02:13,700 --> 00:02:15,890 and then we'll add features to it as we go. 34 00:02:15,890 --> 00:02:18,960 So, we'll start out with just handling strings 35 00:02:18,960 --> 00:02:20,700 and then we'll set it up so 36 00:02:20,700 --> 00:02:23,540 that it can handle objects of your custom type. 37 00:02:23,540 --> 00:02:25,640 And then later on we'll expand it 38 00:02:25,640 --> 00:02:29,510 to handle collisions and things like that. 39 00:02:29,510 --> 00:02:31,460 But right now, it's just going to be bare bones. 40 00:02:31,460 --> 00:02:33,590 But nevertheless, I'm gonna set this up 41 00:02:33,590 --> 00:02:35,950 as templated planning for the future. 42 00:02:35,950 --> 00:02:37,393 So template, 43 00:02:39,620 --> 00:02:40,763 type name, 44 00:02:42,100 --> 00:02:44,913 HashTable, or Hashable, sorry Hashable, 45 00:02:46,970 --> 00:02:51,117 Hashable type and class HashTable. 46 00:02:57,550 --> 00:03:00,023 And we're gonna have some private members. 47 00:03:03,280 --> 00:03:05,993 And we're gonna have a standard vector. 48 00:03:10,210 --> 00:03:14,583 That's optional HashTable. 49 00:03:15,780 --> 00:03:17,840 I'll explain in a second. 50 00:03:17,840 --> 00:03:19,140 And we'll call that table, 51 00:03:20,800 --> 00:03:23,113 and we're going to have an unsigned long, 52 00:03:26,040 --> 00:03:28,953 just so we can handle very large numbers, table size. 53 00:03:32,280 --> 00:03:35,550 Now, what have I done here? 54 00:03:35,550 --> 00:03:38,053 Standard vector optional Hashable table. 55 00:03:39,030 --> 00:03:43,860 We have a vector of optional Hashables. 56 00:03:43,860 --> 00:03:46,730 And that means that the vector can hold 57 00:03:46,730 --> 00:03:50,413 either a null pointer or a Hashable object. 58 00:03:51,720 --> 00:03:55,070 And again, if you haven't seen the video 59 00:03:55,070 --> 00:03:58,820 for C++ optionals, please, please do so now. 60 00:03:58,820 --> 00:04:01,290 But this allows us to return an indicator 61 00:04:01,290 --> 00:04:05,480 that an element in our vector is empty 62 00:04:06,510 --> 00:04:11,510 and return the object stored in that element, 63 00:04:12,010 --> 00:04:14,250 if there is in fact an object stored there. 64 00:04:14,250 --> 00:04:16,650 So, that's what optionals are doing for us here. 65 00:04:18,142 --> 00:04:23,100 And then again, hearkening, back to a previous video, 66 00:04:23,100 --> 00:04:26,790 we showed how to pass functions around in C++. 67 00:04:26,790 --> 00:04:29,870 Here, we're gonna wanna store our hash function. 68 00:04:29,870 --> 00:04:34,870 And so, we're going to have standard, and this is function. 69 00:04:35,360 --> 00:04:38,330 So, this is a function type. 70 00:04:38,330 --> 00:04:43,330 And it's a function that returns an unsigned long 71 00:04:47,080 --> 00:04:51,970 and takes as parameters, a standard string 72 00:04:53,290 --> 00:04:57,000 which is gonna be our key value, and an unsigned long 73 00:04:59,900 --> 00:05:03,240 which is our table size. 74 00:05:03,240 --> 00:05:04,690 And we'll call that hashFunc. 75 00:05:06,540 --> 00:05:09,470 Here, we're declaring a private member. 76 00:05:09,470 --> 00:05:12,810 That's a function that returns an unsigned long 77 00:05:12,810 --> 00:05:16,363 and takes a string and an unsigned long as parameters. 78 00:05:17,460 --> 00:05:19,833 That's where we'll store our hash function. 79 00:05:20,940 --> 00:05:23,613 And now, our public members, so public. 80 00:05:26,200 --> 00:05:27,870 And we're going to need a constructor 81 00:05:27,870 --> 00:05:29,613 as you might expect, HashTable, 82 00:05:32,550 --> 00:05:33,810 unsigned long 83 00:05:37,500 --> 00:05:38,443 table size. 84 00:05:44,080 --> 00:05:46,440 And we're also gonna pass in that function. 85 00:05:46,440 --> 00:05:48,490 Let's just grab all this good stuff here. 86 00:05:59,570 --> 00:06:03,060 So, that's the signature of our constructor. 87 00:06:03,060 --> 00:06:05,820 And then when we get those parameters, 88 00:06:05,820 --> 00:06:07,370 what are we gonna do with them? 89 00:06:08,440 --> 00:06:10,400 We're going to set this 90 00:06:12,350 --> 00:06:13,673 table size, 91 00:06:15,140 --> 00:06:16,593 equal table size, 92 00:06:19,380 --> 00:06:23,950 and this hash function 93 00:06:27,160 --> 00:06:31,550 equal hashFunc. 94 00:06:31,550 --> 00:06:35,493 So, we're storing a function in this private member here. 95 00:06:37,670 --> 00:06:39,920 And then we're going to call a function here, 96 00:06:41,370 --> 00:06:44,723 table resize, 97 00:06:46,124 --> 00:06:46,957 tableSize. 98 00:06:51,420 --> 00:06:54,457 So, we have this table here 99 00:06:58,320 --> 00:07:03,320 and when we pass in this unsigned long table size, 100 00:07:04,780 --> 00:07:07,430 then we're going to call resize 101 00:07:07,430 --> 00:07:09,230 on table passing in that parameter 102 00:07:09,230 --> 00:07:11,243 so it adjusts the size of our table. 103 00:07:14,410 --> 00:07:15,820 Now, what else are we gonna need? 104 00:07:15,820 --> 00:07:19,857 We're gonna need void insert Hashable key. 105 00:07:24,330 --> 00:07:27,927 So, we're gonna insert some key into our HashTable. 106 00:07:30,080 --> 00:07:32,623 We're going to want a find, 107 00:07:33,750 --> 00:07:38,743 so that's going to be optional Hashable. 108 00:07:41,640 --> 00:07:44,740 So, when we find, we're either gonna return the object 109 00:07:44,740 --> 00:07:47,430 or we're gonna return this null thing, 110 00:07:47,430 --> 00:07:48,960 and that's find 111 00:07:51,765 --> 00:07:54,230 Hashable, sorry, Hashable key. 112 00:08:00,870 --> 00:08:03,813 And we're gonna want a delete method. 113 00:08:08,990 --> 00:08:09,823 Optional 114 00:08:11,950 --> 00:08:12,783 Hashable 115 00:08:15,860 --> 00:08:17,903 remove, we'll call it, 116 00:08:19,535 --> 00:08:20,618 Hashable key. 117 00:08:26,077 --> 00:08:27,940 And so, when we remove an object, 118 00:08:27,940 --> 00:08:30,970 it'll either remove the object and return it, 119 00:08:30,970 --> 00:08:33,973 or it will return that null opt. 120 00:08:34,940 --> 00:08:38,800 And then this will come in handy. 121 00:08:38,800 --> 00:08:41,303 This is a getter for table size. 122 00:08:50,160 --> 00:08:53,720 So, that we can check to see what our table size is. 123 00:08:53,720 --> 00:08:56,120 And you'll see why that's handy 124 00:08:56,120 --> 00:08:57,970 a couple of lectures from now. 125 00:08:57,970 --> 00:09:01,600 So, trust me on this one, we're gonna want that getter. 126 00:09:01,600 --> 00:09:06,600 And then finally, a void function to print the table. 127 00:09:12,730 --> 00:09:15,030 Okay, and that's gonna be a constant function. 128 00:09:17,540 --> 00:09:18,373 So is this. 129 00:09:23,370 --> 00:09:27,120 So, let's knock off the perfunctory ones first. 130 00:09:27,120 --> 00:09:32,120 This one's super easy, return table size. 131 00:09:35,220 --> 00:09:37,870 And then let's do that print table 132 00:09:37,870 --> 00:09:40,770 and have a little loop 133 00:09:40,770 --> 00:09:45,770 through our table for int i equal zero, 134 00:09:50,030 --> 00:09:52,813 i less than table size, 135 00:09:55,690 --> 00:09:58,013 plus plus i, there's our loop. 136 00:09:59,690 --> 00:10:04,140 And while we do that standard c-out 137 00:10:06,770 --> 00:10:10,800 i will give the index there, 138 00:10:10,800 --> 00:10:14,743 and then we'll put a little divider here. 139 00:10:18,600 --> 00:10:19,980 And then recall that we may 140 00:10:19,980 --> 00:10:22,630 or may not have a value at that index. 141 00:10:22,630 --> 00:10:27,630 We may have a pointer to the value, or we may have null opt. 142 00:10:27,810 --> 00:10:29,010 So, we have to deal with that. 143 00:10:29,010 --> 00:10:33,713 So, we'll do a test here, if table sub i. 144 00:10:35,570 --> 00:10:36,820 If there's anything there 145 00:10:38,170 --> 00:10:41,673 then we're going to print that stuff. 146 00:10:45,000 --> 00:10:50,000 And recall that optionals will give us null opt 147 00:10:50,950 --> 00:10:53,940 or a pointer, so we have to dereference that pointer 148 00:10:57,480 --> 00:10:58,603 to get our object. 149 00:11:00,690 --> 00:11:03,903 And then here, 150 00:11:05,540 --> 00:11:06,640 we'll put an end line. 151 00:11:16,140 --> 00:11:18,590 So, that's our print table function. 152 00:11:18,590 --> 00:11:22,860 So now, let's get to the meat of this thing here, insert. 153 00:11:22,860 --> 00:11:25,003 Well, what happens when we insert? 154 00:11:26,050 --> 00:11:27,780 We've got a key. 155 00:11:27,780 --> 00:11:28,980 And so, what do we need to do? 156 00:11:28,980 --> 00:11:31,210 We need to do the calculation that turns 157 00:11:31,210 --> 00:11:34,690 that key into an index. 158 00:11:34,690 --> 00:11:36,640 And that's what our hash function does. 159 00:11:40,950 --> 00:11:41,910 Unsigned long 160 00:11:45,550 --> 00:11:48,573 index equals hash function, 161 00:11:51,750 --> 00:11:54,253 key, table size. 162 00:11:58,030 --> 00:12:01,300 So, when we constructed the object, 163 00:12:01,300 --> 00:12:03,980 we passed in a function that got stored 164 00:12:03,980 --> 00:12:06,280 in this private member here. 165 00:12:06,280 --> 00:12:09,270 And then when we do an insert, 166 00:12:09,270 --> 00:12:12,420 we're gonna call that stored function, 167 00:12:12,420 --> 00:12:14,580 passing in the key and the table size 168 00:12:14,580 --> 00:12:19,240 to get our index where we want to store our object. 169 00:12:19,240 --> 00:12:24,240 And then it's a simple matter, table index equals our key. 170 00:12:26,530 --> 00:12:28,830 Again, I'm keeping this pretty simple. 171 00:12:28,830 --> 00:12:30,480 We're gonna expand on this later. 172 00:12:32,070 --> 00:12:35,980 Now, finding, we're gonna do exactly the same thing. 173 00:12:35,980 --> 00:12:37,050 We're passing in a key. 174 00:12:37,050 --> 00:12:42,050 We wanna know, is there an object that matches or not? 175 00:12:42,160 --> 00:12:45,193 And so, we're gonna get that index again. 176 00:12:47,560 --> 00:12:50,683 And then just as we did here, 177 00:12:51,830 --> 00:12:54,663 where we were testing to see if there was something 178 00:12:54,663 --> 00:12:57,490 in fact stored at that index, 179 00:12:57,490 --> 00:12:59,270 we're gonna do the same thing here. 180 00:12:59,270 --> 00:13:04,270 So, if table index, 181 00:13:04,300 --> 00:13:06,083 if there's something there, 182 00:13:08,640 --> 00:13:11,120 and then we're gonna perform a comparison. 183 00:13:11,120 --> 00:13:15,803 If key equals table index, 184 00:13:19,130 --> 00:13:21,530 that is, we've checked to see 185 00:13:21,530 --> 00:13:23,530 if there's something stored at that index. 186 00:13:23,530 --> 00:13:26,430 And now, we're checking to see if the value stored 187 00:13:26,430 --> 00:13:29,543 at that index does in fact match our key. 188 00:13:30,420 --> 00:13:34,040 And if that's the case. then we're gonna return that thing. 189 00:13:34,040 --> 00:13:38,523 Return, and remember we have to dereference it. 190 00:13:42,020 --> 00:13:45,453 Now, what do we do if we don't find anything? 191 00:13:46,790 --> 00:13:51,050 Well, we return null opt 192 00:13:55,160 --> 00:13:57,450 to indicate that we weren't able 193 00:13:57,450 --> 00:14:00,313 to find that value in our table. 194 00:14:01,430 --> 00:14:05,710 And then finally, we have a method to remove an item, 195 00:14:05,710 --> 00:14:08,130 and this is gonna look very much the same. 196 00:14:08,130 --> 00:14:10,493 So, let me just copy this good stuff here. 197 00:14:14,570 --> 00:14:16,240 That's gonna be very much the same. 198 00:14:16,240 --> 00:14:20,810 We're going to calculate the hash to get the index. 199 00:14:20,810 --> 00:14:23,450 We're gonna look at that index, 200 00:14:23,450 --> 00:14:26,030 see if there's anything in fact stored there. 201 00:14:26,030 --> 00:14:28,450 We're gonna check to see if it matches our key. 202 00:14:28,450 --> 00:14:31,923 And if it does, then what we're going to do is, 203 00:14:31,923 --> 00:14:34,593 what we'll do is we'll call this return item. 204 00:14:39,030 --> 00:14:43,723 That's going to be a Hashable. 205 00:14:44,870 --> 00:14:49,200 And then we're going to set the value 206 00:14:50,180 --> 00:14:53,063 at that index to null opt, to indicate deletion. 207 00:14:57,990 --> 00:14:59,193 Sorry, null opt. 208 00:15:01,300 --> 00:15:03,550 And then we're gonna return this return item. 209 00:15:10,828 --> 00:15:12,995 And that is our HashTable. 210 00:15:14,880 --> 00:15:18,393 Now, let's write some code to run it through its paces. 211 00:15:19,360 --> 00:15:23,810 So, we'll write a little program here to test this. 212 00:15:23,810 --> 00:15:26,923 We'll call this HT, short for HashTable demo. 213 00:15:29,460 --> 00:15:31,673 All right, we're going to need iostream, 214 00:15:36,952 --> 00:15:39,869 and we're gonna need our HashTable. 215 00:15:50,010 --> 00:15:54,010 Now, we're going to need a hash function. 216 00:15:54,010 --> 00:15:56,940 Because remember when we instantiate objects 217 00:15:56,940 --> 00:16:00,550 of the HashTable type, we need to provide it 218 00:16:00,550 --> 00:16:03,660 with a function, a hash function. 219 00:16:03,660 --> 00:16:07,170 That gets passed in and stored and then used as needed 220 00:16:07,170 --> 00:16:09,200 as we've seen in the header file. 221 00:16:09,200 --> 00:16:11,213 So, unsigned long, 222 00:16:13,781 --> 00:16:15,270 and we'll call this hornerHash, 223 00:16:15,270 --> 00:16:17,250 'cause we're going to use that hornerHash function 224 00:16:17,250 --> 00:16:18,983 that we saw on an earlier video. 225 00:16:20,610 --> 00:16:25,610 And that's gonna take us, and our string, call it key, 226 00:16:25,910 --> 00:16:27,963 and a tableSize, unsigned, 227 00:16:29,770 --> 00:16:31,327 long tableSize. 228 00:16:36,725 --> 00:16:37,577 And then we're gonna have main. 229 00:16:43,860 --> 00:16:45,600 And it's gonna return zero, 230 00:16:45,600 --> 00:16:47,600 and we'll fill that out in a little bit. 231 00:16:49,200 --> 00:16:51,490 So, if you'll recall 232 00:16:52,930 --> 00:16:55,820 from the earlier lecture, 233 00:16:55,820 --> 00:16:58,700 what we do with the hornerHash is we start 234 00:16:58,700 --> 00:17:00,083 with an unsigned long. 235 00:17:04,100 --> 00:17:05,200 I'll call it hashValue 236 00:17:08,987 --> 00:17:09,820 equals zero. 237 00:17:11,980 --> 00:17:13,610 And then we're passing in a string. 238 00:17:13,610 --> 00:17:15,210 We're gonna iterate through that string. 239 00:17:15,210 --> 00:17:19,447 So, for constant character, 240 00:17:22,030 --> 00:17:23,123 call it letter. 241 00:17:24,880 --> 00:17:26,090 Nah, I like c better. 242 00:17:26,090 --> 00:17:29,393 C in key, 243 00:17:30,370 --> 00:17:31,350 that's just gonna iterate 244 00:17:31,350 --> 00:17:34,850 through all of the characters in our string. 245 00:17:34,850 --> 00:17:38,000 And yes, we are pretending that Unicode 246 00:17:38,000 --> 00:17:41,370 and multibyte and codings and all that stuff don't exist. 247 00:17:41,370 --> 00:17:43,460 But this will serve for our purposes. 248 00:17:43,460 --> 00:17:45,450 Again, we're just gonna iterate 249 00:17:45,450 --> 00:17:50,260 through the characters in our key. 250 00:17:50,260 --> 00:17:53,170 And then we're gonna calculate hashVal, 251 00:17:53,170 --> 00:17:54,763 using Horner's Method, 252 00:17:56,590 --> 00:17:58,153 equals hashVal. 253 00:18:01,350 --> 00:18:02,960 And it's got to be a prime number here, 254 00:18:02,960 --> 00:18:06,673 or it should be a prime number, 37 plus c. 255 00:18:07,970 --> 00:18:10,020 And then when we're done, 256 00:18:10,020 --> 00:18:12,073 return hashVal modulo, 257 00:18:16,510 --> 00:18:17,573 the table size. 258 00:18:19,520 --> 00:18:23,770 And that is our hornerHash function that we're going to pass 259 00:18:23,770 --> 00:18:28,730 to the constructor when we create our HashTable. 260 00:18:28,730 --> 00:18:29,833 So, let's do that. 261 00:18:31,621 --> 00:18:32,454 HashTable, 262 00:18:35,000 --> 00:18:36,910 and we have to give a type, 263 00:18:36,910 --> 00:18:41,910 standard string HashTable, we'll call it. 264 00:18:43,760 --> 00:18:48,583 And we'll make it of size 53, 53 is prime, hornerHash. 265 00:18:50,870 --> 00:18:54,210 So, we're passing in the size 266 00:18:54,210 --> 00:18:56,940 and we're passing in this function 267 00:18:58,350 --> 00:19:00,753 that will become part of our HashTable object. 268 00:19:02,340 --> 00:19:04,549 Now, let's do some insertions. 269 00:19:04,549 --> 00:19:07,863 HashTable insert, 270 00:19:10,210 --> 00:19:11,433 Hello, World! 271 00:19:16,520 --> 00:19:18,433 And let's just do a few more. 272 00:19:19,700 --> 00:19:22,200 Just gonna copy this and replace the strings here. 273 00:19:23,310 --> 00:19:24,957 Oh, CS, UVM CS 124, 274 00:19:33,150 --> 00:19:38,053 who is Egbert Porcupine? 275 00:19:39,680 --> 00:19:41,580 Doesn't really matter what our strings are here. 276 00:19:41,580 --> 00:19:42,490 We're just testing. 277 00:19:42,490 --> 00:19:46,383 And then UVM stands for in Latin, 278 00:19:48,063 --> 00:19:48,980 Universitas 279 00:19:52,498 --> 00:19:53,331 Viridis 280 00:19:56,100 --> 00:19:57,083 Montis. 281 00:19:58,430 --> 00:20:01,130 That's Latin for University of the Green Mountains. 282 00:20:01,130 --> 00:20:03,023 That's what UVM is all about. 283 00:20:04,610 --> 00:20:06,893 And then we're gonna print our HashTable. 284 00:20:06,893 --> 00:20:09,763 HashTable, print, 285 00:20:11,830 --> 00:20:13,683 sorry, print table. 286 00:20:16,210 --> 00:20:18,110 And let's just run this real quick 287 00:20:18,110 --> 00:20:19,993 to see what that looks like. 288 00:20:24,290 --> 00:20:27,303 Make sure that we're, oops, what have I done wrong? 289 00:20:28,950 --> 00:20:30,363 Oh, functional, sorry. 290 00:20:37,180 --> 00:20:40,323 This should be functional, not function. 291 00:20:43,560 --> 00:20:45,163 Now, let's build it again. 292 00:20:49,450 --> 00:20:50,803 Another typo. 293 00:20:52,510 --> 00:20:54,663 Where's my typo? Here, endl. 294 00:20:55,650 --> 00:20:57,553 Left out an L, sorry. 295 00:21:00,800 --> 00:21:01,700 Okay, there we go. 296 00:21:03,180 --> 00:21:05,080 So, let's just take a quick look here. 297 00:21:05,960 --> 00:21:09,380 We have a HashTable of 53 elements. 298 00:21:09,380 --> 00:21:13,603 So, the indices run from zero to 52, as we expected. 299 00:21:17,764 --> 00:21:19,333 Where's our demo code? There we are. 300 00:21:20,680 --> 00:21:25,360 We inserted these strings, UVM CS 124 wound up 301 00:21:25,360 --> 00:21:27,910 at index five using that hornerHash function. 302 00:21:27,910 --> 00:21:31,080 Hello, World! wound up index 13. 303 00:21:31,080 --> 00:21:34,430 Who is Egbert Porcupine wound up at index 22. 304 00:21:34,430 --> 00:21:38,340 And Universitas Viridis Montis wound up at index 40. 305 00:21:38,340 --> 00:21:41,770 So, that looks like our print table function 306 00:21:41,770 --> 00:21:45,780 and our insertion function are working okay. 307 00:21:45,780 --> 00:21:47,370 So, let's expand our code a little bit 308 00:21:47,370 --> 00:21:50,333 to exercise some of the other parts of our code. 309 00:21:53,260 --> 00:21:54,153 Let's do a find. 310 00:21:56,101 --> 00:21:59,107 And we're gonna get a optional back 311 00:22:01,720 --> 00:22:06,600 because we may or may not have a value, standard string, 312 00:22:09,620 --> 00:22:12,980 S equal HashTable find 313 00:22:15,650 --> 00:22:18,703 and we'll search on Hello, World! 314 00:22:20,420 --> 00:22:24,210 And if we find that, then let's print it. 315 00:22:24,210 --> 00:22:29,210 So, if S, if what's returned is not 316 00:22:30,010 --> 00:22:35,010 that null opt, then standard c-out. 317 00:22:37,573 --> 00:22:38,750 Dereference S 318 00:22:41,660 --> 00:22:44,343 is in the table, 319 00:22:47,140 --> 00:22:51,140 S-T-D, E-N-D-L, 320 00:22:51,140 --> 00:22:53,023 remember the L this time, Clayton. 321 00:22:54,423 --> 00:22:56,780 And then let's do a remove. 322 00:22:56,780 --> 00:23:00,570 S, and it's gonna be the same thing here 323 00:23:03,580 --> 00:23:05,493 except we're gonna make this remove. 324 00:23:09,120 --> 00:23:10,893 And then the same thing here, 325 00:23:15,920 --> 00:23:19,143 if S then we're gonna say, 326 00:23:20,380 --> 00:23:22,813 has been removed. 327 00:23:24,090 --> 00:23:26,233 And we could put in an else clause here. 328 00:23:28,870 --> 00:23:31,133 Let's just do that else, 329 00:23:39,940 --> 00:23:44,940 Hello, World! was not found. 330 00:23:47,470 --> 00:23:50,583 And if everything goes right, that won't print. 331 00:23:55,300 --> 00:23:57,300 And again, we'll do the same thing here. 332 00:23:58,430 --> 00:24:01,963 Add an else clause, Hello, World! was not removed. 333 00:24:05,330 --> 00:24:08,203 And so, when we do this, when we run this code, 334 00:24:09,210 --> 00:24:11,100 it's gonna find Hello, World! 335 00:24:11,100 --> 00:24:14,100 It's gonna call find with the Hello, World! parameter there. 336 00:24:15,050 --> 00:24:18,520 And if we get back a non null value 337 00:24:18,520 --> 00:24:22,780 then it's gonna print the dereferenced value 338 00:24:23,650 --> 00:24:25,490 and say, yes, we found it in the table. 339 00:24:25,490 --> 00:24:28,030 Otherwise, it's going to say it was not found. 340 00:24:28,030 --> 00:24:29,210 And then we're gonna remove it. 341 00:24:29,210 --> 00:24:31,720 And then let's just print that table one more time 342 00:24:32,800 --> 00:24:35,233 to verify that it was in fact removed. 343 00:24:38,010 --> 00:24:39,560 Now, let's run this code again. 344 00:24:45,170 --> 00:24:46,070 Let's take a look. 345 00:24:48,090 --> 00:24:50,010 So, this is the table that we printed 346 00:24:50,010 --> 00:24:53,690 at the beginning running from zero to 52. 347 00:24:53,690 --> 00:24:56,030 And it has all four of the strings that we inserted. 348 00:24:56,030 --> 00:24:57,420 That's good. 349 00:24:57,420 --> 00:25:00,090 We have this output showing that Hello, World! was 350 00:25:00,090 --> 00:25:03,150 in the table, that Hello, World! was in fact removed. 351 00:25:03,150 --> 00:25:04,640 And now, when we print the table 352 00:25:04,640 --> 00:25:07,420 we should see that Hello, World! is not in the table. 353 00:25:07,420 --> 00:25:09,393 What was the index it was at, 13? 354 00:25:10,360 --> 00:25:11,740 13 is empty. 355 00:25:11,740 --> 00:25:13,183 So, it was in fact removed. 356 00:25:14,150 --> 00:25:18,450 So, that completes our bare bones implementation 357 00:25:18,450 --> 00:25:20,210 of a HashTable. 358 00:25:20,210 --> 00:25:23,350 And in the next video, what we'll do is we'll expand 359 00:25:23,350 --> 00:25:26,780 on this so that it can handle objects of your custom type. 360 00:25:26,780 --> 00:25:29,810 And you'll see that we'll have to add another function 361 00:25:29,810 --> 00:25:31,710 and pass in another function 362 00:25:31,710 --> 00:25:36,170 to the HashTable when we construct it. 363 00:25:36,170 --> 00:25:39,053 And we'll go from there. 364 00:25:40,270 --> 00:25:41,220 That's all for now.