1 00:00:01,330 --> 00:00:03,890 - [Instructor] Okay, now we've got a two for here. 2 00:00:03,890 --> 00:00:05,410 We're gonna make two changes 3 00:00:05,410 --> 00:00:10,410 to our hash table to implement linear probing and rehashing. 4 00:00:11,300 --> 00:00:14,350 And we've seen in previous videos, what these are 5 00:00:14,350 --> 00:00:16,970 as we did with separate training 6 00:00:16,970 --> 00:00:18,830 we're gonna take the hash table class. 7 00:00:18,830 --> 00:00:20,150 We first created 8 00:00:20,150 --> 00:00:24,203 and modify that to suit our new requirements. 9 00:00:25,300 --> 00:00:27,470 So let's open that file. 10 00:00:27,470 --> 00:00:29,580 Okay. And we have our hash table here 11 00:00:31,030 --> 00:00:33,630 and we're gonna add a couple of methods 12 00:00:33,630 --> 00:00:38,630 and then we're gonna modify, insert, find and remove. 13 00:00:39,430 --> 00:00:42,330 So let's put in placeholders 14 00:00:42,330 --> 00:00:45,030 we're gonna need int next Prime 15 00:00:48,540 --> 00:00:49,373 int N. 16 00:00:51,050 --> 00:00:55,170 And that's gonna take some integer 17 00:00:55,170 --> 00:00:56,760 and return the next prime. 18 00:00:56,760 --> 00:00:58,190 Why do we need that? 19 00:00:58,190 --> 00:01:03,120 As you recall, we want our table sizes to be prime. 20 00:01:03,120 --> 00:01:05,170 And when we rehash, what we're gonna do is 21 00:01:05,170 --> 00:01:09,110 we're gonna take the existing table size, double it 22 00:01:09,110 --> 00:01:10,860 and then find the next prime. 23 00:01:10,860 --> 00:01:13,360 Therefore, we're gonna need this method. 24 00:01:13,360 --> 00:01:17,330 That's gonna calculate the next prime on any given N. 25 00:01:17,330 --> 00:01:20,190 So we can use that as our new table size. 26 00:01:20,190 --> 00:01:24,510 And we're also gonna need another function called Rehash. 27 00:01:24,510 --> 00:01:25,973 That'll be a void function. 28 00:01:30,270 --> 00:01:31,103 Sorry. 29 00:01:32,820 --> 00:01:36,000 And what rehash is going to do is it's going to 30 00:01:36,000 --> 00:01:41,000 fetch the existing table size, double it, call next prime 31 00:01:41,300 --> 00:01:45,090 get the new table size, create a new table 32 00:01:45,090 --> 00:01:50,090 rehash all the elements of the old table into the new table 33 00:01:50,170 --> 00:01:52,030 and then delete the old table. 34 00:01:52,030 --> 00:01:53,743 That's what rehash is gonna do. 35 00:01:55,470 --> 00:01:59,020 So let's just put a note to this effect. 36 00:01:59,020 --> 00:02:00,160 Find 37 00:02:00,160 --> 00:02:00,993 next 38 00:02:02,000 --> 00:02:02,833 prime 39 00:02:04,160 --> 00:02:06,630 for use as 40 00:02:06,630 --> 00:02:08,123 new table size. 41 00:02:10,480 --> 00:02:11,313 This is 42 00:02:12,350 --> 00:02:13,290 rehash 43 00:02:14,480 --> 00:02:15,680 when 44 00:02:15,680 --> 00:02:17,270 load 45 00:02:17,270 --> 00:02:18,120 factor 46 00:02:20,250 --> 00:02:21,787 exceeds threshold. 47 00:02:26,967 --> 00:02:29,800 And this will be called by insert. 48 00:02:32,580 --> 00:02:33,413 Okay. 49 00:02:34,490 --> 00:02:36,070 So far so good 50 00:02:36,070 --> 00:02:39,390 As you recall, when we're using linear probing 51 00:02:39,390 --> 00:02:42,620 and we remove an item, we want to mark the item 52 00:02:42,620 --> 00:02:47,060 as deleted or removed, but not actually empty it out. 53 00:02:47,060 --> 00:02:50,320 And that's so we don't break our probe sequence. 54 00:02:50,320 --> 00:02:53,200 Okay. So we can find elements 55 00:02:53,200 --> 00:02:55,640 beyond that and the probe sequence. 56 00:02:55,640 --> 00:02:59,690 So what we're gonna do here is I'm gonna create 57 00:02:59,690 --> 00:03:03,330 a new probably seen something very similar in Java. 58 00:03:03,330 --> 00:03:05,843 I'm gonna create, what's called an enum. 59 00:03:07,967 --> 00:03:09,573 And we'll put that here. 60 00:03:12,754 --> 00:03:17,363 enum is short for enumeration called state. 61 00:03:18,750 --> 00:03:21,903 and it'll take on the values empty, 62 00:03:23,580 --> 00:03:25,140 filled 63 00:03:25,140 --> 00:03:26,143 or removed. 64 00:03:28,720 --> 00:03:32,390 And if you've never seen enum before 65 00:03:32,390 --> 00:03:34,040 an enum is a 66 00:03:35,240 --> 00:03:36,400 user 67 00:03:36,400 --> 00:03:37,310 defined 68 00:03:39,620 --> 00:03:40,453 data type 69 00:03:42,080 --> 00:03:43,760 that can only 70 00:03:45,080 --> 00:03:46,790 take certain 71 00:03:47,960 --> 00:03:48,860 enumerated 72 00:03:50,670 --> 00:03:51,503 values. 73 00:03:52,970 --> 00:03:55,130 Okay so this is, this is a new data type. 74 00:03:55,130 --> 00:03:56,540 We have strings, we have ins. 75 00:03:56,540 --> 00:03:58,230 Now we have something called state 76 00:03:58,230 --> 00:04:01,230 and state can be one of these three 77 00:04:01,230 --> 00:04:04,653 and only one at a time and empty, filled or removed. 78 00:04:05,510 --> 00:04:09,150 So we're gonna attach this essentially 79 00:04:09,150 --> 00:04:12,650 to elements in our hash table. 80 00:04:12,650 --> 00:04:14,550 And so we'll be able to set the state. 81 00:04:14,550 --> 00:04:16,590 Is this element empty? 82 00:04:16,590 --> 00:04:19,480 Is it filled or has it been removed? 83 00:04:19,480 --> 00:04:20,630 Okay. 84 00:04:20,630 --> 00:04:24,100 And in order to put that to use, we're going to create 85 00:04:24,100 --> 00:04:28,170 what's called a struct, which is short for structure 86 00:04:29,240 --> 00:04:31,680 and we're gonna call that our hash item 87 00:04:34,850 --> 00:04:36,933 and it's gonna include a hashable, 88 00:04:40,980 --> 00:04:42,253 we'll call that item. 89 00:04:43,120 --> 00:04:45,760 And it's also gonna include the state 90 00:04:45,760 --> 00:04:47,453 that we just created. 91 00:04:49,070 --> 00:04:49,923 And we'll call that status 92 00:04:49,923 --> 00:04:52,740 because we don't want a collision of names there. 93 00:04:52,740 --> 00:04:53,573 Okay. 94 00:04:54,900 --> 00:04:57,170 So what is the struct? 95 00:04:57,170 --> 00:05:01,240 You can think of it as a super baby minimalist class, 96 00:05:01,240 --> 00:05:03,840 but more accurately. 97 00:05:03,840 --> 00:05:06,147 It's an aggregate, an aggregate 98 00:05:09,758 --> 00:05:10,591 aggregate 99 00:05:11,840 --> 00:05:12,673 data type 100 00:05:14,420 --> 00:05:15,820 that 101 00:05:15,820 --> 00:05:17,530 groups 102 00:05:17,530 --> 00:05:18,640 individual 103 00:05:20,040 --> 00:05:21,110 variables 104 00:05:22,540 --> 00:05:23,373 together. 105 00:05:28,100 --> 00:05:33,100 So a hash item structure includes a hashable item 106 00:05:33,400 --> 00:05:34,700 and a state status 107 00:05:34,700 --> 00:05:37,840 and state can be one of these three values. 108 00:05:37,840 --> 00:05:38,673 Okay. 109 00:05:39,730 --> 00:05:44,730 So we're gonna use that in our implementation now. 110 00:05:44,950 --> 00:05:48,400 And so our table is not going to be 111 00:05:49,310 --> 00:05:51,370 of optional hashable types. 112 00:05:51,370 --> 00:05:54,993 It's gonna be of hash items. 113 00:05:58,700 --> 00:06:00,230 Okay. 114 00:06:00,230 --> 00:06:04,030 And in doing that, we're going to be able to 115 00:06:04,030 --> 00:06:07,810 access the elements in the struct 116 00:06:07,810 --> 00:06:09,280 here 117 00:06:09,280 --> 00:06:10,470 with a dot notation. 118 00:06:10,470 --> 00:06:13,560 So we'll have things like 119 00:06:13,560 --> 00:06:14,480 table 120 00:06:14,480 --> 00:06:15,660 sub I 121 00:06:17,220 --> 00:06:19,690 item to fetch the item 122 00:06:19,690 --> 00:06:21,323 and table. 123 00:06:22,700 --> 00:06:23,680 So by 124 00:06:25,530 --> 00:06:26,640 status 125 00:06:27,600 --> 00:06:30,900 to check whether it's empty, filled or removed. 126 00:06:30,900 --> 00:06:33,153 Table size remains unchanged. 127 00:06:36,090 --> 00:06:39,380 We still are gonna store this, get key function. 128 00:06:39,380 --> 00:06:42,163 We're still gonna store this hash function. 129 00:06:43,275 --> 00:06:44,400 And 130 00:06:45,670 --> 00:06:46,503 you know what? 131 00:06:46,503 --> 00:06:48,990 I put these here among the public methods 132 00:06:48,990 --> 00:06:50,200 I'm gonna move them. 133 00:06:50,200 --> 00:06:51,690 I'm gonna make them private 134 00:06:52,640 --> 00:06:55,340 because they don't need to be called from the outside. 135 00:06:56,930 --> 00:06:58,300 So I've just moved these. 136 00:06:58,300 --> 00:06:59,530 So next, next prime 137 00:06:59,530 --> 00:07:03,940 and rehash will be private methods, not public methods. 138 00:07:03,940 --> 00:07:05,423 So my bad on that one. 139 00:07:06,690 --> 00:07:07,523 All right. 140 00:07:07,523 --> 00:07:10,340 So let's implement those real quick. 141 00:07:10,340 --> 00:07:11,173 This 142 00:07:13,050 --> 00:07:14,850 we're gonna use 143 00:07:14,850 --> 00:07:17,760 kind of a brute force approach. 144 00:07:17,760 --> 00:07:20,080 And so if the 145 00:07:20,080 --> 00:07:22,680 input integer N is 146 00:07:22,680 --> 00:07:24,020 even then, 147 00:07:24,020 --> 00:07:26,270 it's clearly not prime. 148 00:07:26,270 --> 00:07:31,270 And so what we'll do is we'll do a conditional to check 149 00:07:31,330 --> 00:07:32,163 If it's even. 150 00:07:33,160 --> 00:07:35,690 If N mod two 151 00:07:35,690 --> 00:07:36,840 equals zero, 152 00:07:36,840 --> 00:07:37,690 then it's even 153 00:07:40,140 --> 00:07:41,707 We're just gonna to pin on that 154 00:07:44,390 --> 00:07:48,380 So we've received N as a parameter we've checked to see 155 00:07:48,380 --> 00:07:49,890 is it even if it's even 156 00:07:49,890 --> 00:07:52,490 we're just gonna bump it up to the next odd number. 157 00:07:52,490 --> 00:07:54,830 Okay so now we have an odd number N 158 00:07:56,200 --> 00:07:57,540 and that may or may not be prime. 159 00:07:57,540 --> 00:07:58,460 We don't know yet. 160 00:07:58,460 --> 00:08:01,770 Okay. So we'll have a bool prime 161 00:08:03,590 --> 00:08:05,633 and we'll initialize that to false. 162 00:08:07,270 --> 00:08:11,943 And then we're gonna have a while loop while not prime. 163 00:08:13,870 --> 00:08:16,670 And what are we gonna do while not prime? 164 00:08:16,670 --> 00:08:18,210 Well, what we're gonna do is we're gonna 165 00:08:18,210 --> 00:08:19,230 set prime 166 00:08:21,240 --> 00:08:22,073 equal two 167 00:08:23,470 --> 00:08:25,363 and then we're gonna do some stuff. 168 00:08:26,200 --> 00:08:29,240 And if certain conditions are met 169 00:08:29,240 --> 00:08:31,900 we're gonna switch prime back to false 170 00:08:31,900 --> 00:08:36,050 before we end a particular iteration of the while loop. 171 00:08:36,050 --> 00:08:37,100 Okay. So what are we gonna do? 172 00:08:37,100 --> 00:08:39,010 Remember we've got an odd number 173 00:08:39,010 --> 00:08:41,430 and what we're gonna do is we're gonna check to see 174 00:08:41,430 --> 00:08:42,587 if it has any divisors 175 00:08:42,587 --> 00:08:47,587 and we have to check divisors up to a square root event. 176 00:08:49,620 --> 00:08:51,810 Obviously we don't need to check beyond that. 177 00:08:51,810 --> 00:08:54,650 So we'll create a little for-loop here 178 00:08:54,650 --> 00:08:55,540 for 179 00:08:56,450 --> 00:08:57,630 int 180 00:08:57,630 --> 00:08:59,533 I equals three. 181 00:09:01,200 --> 00:09:02,320 I 182 00:09:02,320 --> 00:09:03,690 times I 183 00:09:04,640 --> 00:09:05,560 less than N 184 00:09:07,820 --> 00:09:11,320 so that is, I is less than or equal 185 00:09:11,320 --> 00:09:16,250 to the square root of N we're gonna increment by twos. 186 00:09:16,250 --> 00:09:17,720 I plus equal two. 187 00:09:17,720 --> 00:09:18,553 Why? 188 00:09:19,960 --> 00:09:22,500 We don't need to increment one at a time. 189 00:09:22,500 --> 00:09:24,760 We've made this number odd. 190 00:09:24,760 --> 00:09:27,010 We're gonna increment two at a time. 191 00:09:27,010 --> 00:09:29,720 So we're gonna continue to check odd numbers. 192 00:09:29,720 --> 00:09:32,720 We don't, if we incremented by one, we'd do a useless check 193 00:09:32,720 --> 00:09:36,860 on an even number that we already know is not a divisor. 194 00:09:36,860 --> 00:09:39,400 So we're just gonna skip over the even numbers. 195 00:09:39,400 --> 00:09:40,817 And then we have if 196 00:09:42,292 --> 00:09:43,125 N 197 00:09:44,920 --> 00:09:46,820 mod I 198 00:09:46,820 --> 00:09:48,043 equals zero. 199 00:09:49,070 --> 00:09:51,040 So we have this N we're gonna iterate 200 00:09:51,040 --> 00:09:52,713 through all these I's. 201 00:09:53,760 --> 00:09:57,610 And what happens if N mod I is zero, 202 00:09:57,610 --> 00:09:59,400 then we know it's not prime. 203 00:09:59,400 --> 00:10:01,423 So we switched prime back to false. 204 00:10:06,280 --> 00:10:07,920 All right. 205 00:10:07,920 --> 00:10:10,660 So we're gonna proceed with this for loop checking 206 00:10:10,660 --> 00:10:11,563 for divisors. 207 00:10:12,400 --> 00:10:15,730 And then when we're done with that for loop, 208 00:10:15,730 --> 00:10:18,580 we're going to increment N by two 209 00:10:19,540 --> 00:10:22,870 and see if we can find any divisors there. 210 00:10:22,870 --> 00:10:24,320 N 211 00:10:24,320 --> 00:10:26,640 plus equal two, 212 00:10:26,640 --> 00:10:28,740 if we found a divisor 213 00:10:28,740 --> 00:10:33,740 prime is false plus equals to increment by two 214 00:10:33,980 --> 00:10:36,693 for the next test in our, in our loop. 215 00:10:37,660 --> 00:10:40,070 This is the next odd number. 216 00:10:40,070 --> 00:10:41,883 If we exit this loop, 217 00:10:43,170 --> 00:10:45,560 then we know that the last number N 218 00:10:45,560 --> 00:10:48,900 that we found was prime. 219 00:10:48,900 --> 00:10:51,080 So we need to return 220 00:10:52,375 --> 00:10:53,843 N minus two, 221 00:10:56,630 --> 00:11:01,630 because we added two here, but we found that it's prime. 222 00:11:02,890 --> 00:11:04,590 So that's our next prime function. 223 00:11:07,880 --> 00:11:09,423 Now our rehash function. 224 00:11:13,450 --> 00:11:16,080 First thing we're gonna wanna do on a rehash 225 00:11:16,960 --> 00:11:18,600 is we're gonna want to save 226 00:11:19,510 --> 00:11:21,943 a copy of the hash table, 227 00:11:24,380 --> 00:11:25,470 because remember we're gonna take 228 00:11:25,470 --> 00:11:29,530 all the elements of the old hash table and insert them 229 00:11:29,530 --> 00:11:31,600 into the new hash table. 230 00:11:31,600 --> 00:11:33,100 So we'll have a standard 231 00:11:34,370 --> 00:11:35,203 vector 232 00:11:36,870 --> 00:11:38,053 of hash items. 233 00:11:40,240 --> 00:11:41,453 That's our new struct. 234 00:11:42,550 --> 00:11:44,010 We'll call that old table 235 00:11:48,128 --> 00:11:52,600 And we'll assign to that the value of the current table. 236 00:11:52,600 --> 00:11:56,670 And then we want to get the new table size. 237 00:11:56,670 --> 00:11:58,110 So table size 238 00:11:59,890 --> 00:12:01,350 equal next prime 239 00:12:04,620 --> 00:12:05,770 table size 240 00:12:06,800 --> 00:12:07,633 sorry 241 00:12:08,690 --> 00:12:10,000 times two. 242 00:12:10,000 --> 00:12:11,630 So what's happening here. 243 00:12:11,630 --> 00:12:16,360 We have this, a private member table size. 244 00:12:16,360 --> 00:12:18,384 That's an unsigned long. 245 00:12:18,384 --> 00:12:20,030 We want to update it. 246 00:12:20,030 --> 00:12:22,530 So we multiply by two. 247 00:12:22,530 --> 00:12:23,780 We find the next prime 248 00:12:23,780 --> 00:12:27,710 and we reassign that to the table size member. 249 00:12:27,710 --> 00:12:29,320 Okay. 250 00:12:29,320 --> 00:12:31,670 Now we know our new table size 251 00:12:31,670 --> 00:12:34,340 so we're just gonna empty out our table table clear 252 00:12:37,670 --> 00:12:40,230 and that's fine because we've already made a copy. 253 00:12:40,230 --> 00:12:41,260 So we're good. 254 00:12:41,260 --> 00:12:43,180 And then we're gonna resize our table 255 00:12:43,180 --> 00:12:45,113 table resize, 256 00:12:47,300 --> 00:12:48,273 table size. 257 00:12:49,500 --> 00:12:52,440 And that's just a method that that's just 258 00:12:52,440 --> 00:12:54,480 a standard vector method. 259 00:12:54,480 --> 00:12:56,110 These are both standard vector methods. 260 00:12:56,110 --> 00:12:57,120 I should say, clear 261 00:12:57,120 --> 00:12:59,513 and resize are both standard vector methods. 262 00:13:00,420 --> 00:13:04,060 And so this will resize the table to our news table size 263 00:13:04,060 --> 00:13:06,640 and then we want to re insert all of our items. 264 00:13:06,640 --> 00:13:08,510 So we'll start with num items 265 00:13:10,110 --> 00:13:12,893 equals zero to reset that value. 266 00:13:16,060 --> 00:13:17,423 We have num items? 267 00:13:20,820 --> 00:13:21,653 We'll look at that, 268 00:13:21,653 --> 00:13:22,580 we don't have num items. 269 00:13:22,580 --> 00:13:23,573 I have to fix that. 270 00:13:25,630 --> 00:13:27,030 So we'll make unsigned 271 00:13:28,640 --> 00:13:30,150 long num items 272 00:13:31,750 --> 00:13:33,180 and that's just keeping track of the number 273 00:13:33,180 --> 00:13:36,750 of items that we have in our vector, in our hash table. 274 00:13:36,750 --> 00:13:37,800 Okay so now we're good. 275 00:13:37,800 --> 00:13:38,633 Sorry. 276 00:13:39,890 --> 00:13:40,723 Okay. 277 00:13:40,723 --> 00:13:42,230 So what happens next? 278 00:13:42,230 --> 00:13:43,700 Well, we have to iterate 279 00:13:43,700 --> 00:13:47,980 through old table and when we find a value 280 00:13:47,980 --> 00:13:50,320 we're gonna want to insert it into our new table. 281 00:13:50,320 --> 00:13:51,220 Simple as that. 282 00:13:51,220 --> 00:13:52,210 So for 283 00:13:53,290 --> 00:13:54,370 unsigned 284 00:13:55,580 --> 00:13:56,413 long 285 00:13:57,550 --> 00:13:59,003 I equals zero. 286 00:14:00,320 --> 00:14:02,300 I less than 287 00:14:02,300 --> 00:14:03,133 hold 288 00:14:04,070 --> 00:14:05,600 table 289 00:14:05,600 --> 00:14:06,460 size 290 00:14:09,260 --> 00:14:10,760 plus, plus I 291 00:14:10,760 --> 00:14:14,120 so that's gonna iterate through our old table 292 00:14:14,120 --> 00:14:17,980 and then we're gonna use that status element 293 00:14:17,980 --> 00:14:19,250 in our struct 294 00:14:20,176 --> 00:14:21,910 that enum, 295 00:14:21,910 --> 00:14:23,520 if 296 00:14:23,520 --> 00:14:24,670 old table, 297 00:14:24,670 --> 00:14:25,503 sorry, 298 00:14:26,640 --> 00:14:27,690 old table 299 00:14:28,880 --> 00:14:29,713 I 300 00:14:30,880 --> 00:14:32,810 status 301 00:14:32,810 --> 00:14:33,940 equal filled 302 00:14:36,590 --> 00:14:39,370 then we know we have a value insert 303 00:14:42,070 --> 00:14:43,210 old 304 00:14:43,210 --> 00:14:44,043 table 305 00:14:46,095 --> 00:14:47,750 I 306 00:14:47,750 --> 00:14:48,583 items. 307 00:14:48,583 --> 00:14:50,177 So that's explain what's going on here. 308 00:14:50,177 --> 00:14:51,120 (clearing throat) 309 00:14:51,120 --> 00:14:51,953 Excuse me. 310 00:14:53,610 --> 00:14:56,600 We're looping through the old table 311 00:14:57,480 --> 00:15:02,400 we're gonna ignore anything that has been removed. 312 00:15:02,400 --> 00:15:06,820 So we're only gonna concern ourselves with the elements 313 00:15:06,820 --> 00:15:11,820 in our hash table that have their status set to fill. 314 00:15:12,171 --> 00:15:15,780 Then we know we want to insert those into our new table. 315 00:15:15,780 --> 00:15:18,860 And then what we do is we're fetching. 316 00:15:18,860 --> 00:15:23,250 Remember we have a struct now, so we're fetching old table 317 00:15:23,250 --> 00:15:26,690 at this index item and that's our rehash function. 318 00:15:26,690 --> 00:15:28,660 That's all there is to that. 319 00:15:28,660 --> 00:15:29,850 Now let's move on 320 00:15:29,850 --> 00:15:33,993 and do our modifications to insert, 321 00:15:34,870 --> 00:15:36,833 find and remove. 322 00:15:37,710 --> 00:15:39,430 We'll start with insert. 323 00:15:39,430 --> 00:15:40,300 Now here 324 00:15:41,730 --> 00:15:44,400 in our old insert function 325 00:15:45,960 --> 00:15:49,460 we were just calculating the hash to get an index 326 00:15:49,460 --> 00:15:53,100 and then put that item at the spot in the vector. 327 00:15:53,100 --> 00:15:53,933 Okay. 328 00:15:53,933 --> 00:15:56,140 We don't want to do that anymore. 329 00:15:56,140 --> 00:16:01,140 What we want to do instead is we want to do a linear probe. 330 00:16:05,900 --> 00:16:07,470 Okay. 331 00:16:07,470 --> 00:16:11,090 And that is, we'll use a while loop 332 00:16:11,090 --> 00:16:11,923 while 333 00:16:14,690 --> 00:16:15,523 table 334 00:16:16,830 --> 00:16:17,690 index 335 00:16:19,380 --> 00:16:20,470 status. 336 00:16:20,470 --> 00:16:24,493 Again, we're gonna access that status equal filled. 337 00:16:27,250 --> 00:16:30,140 Then we're gonna increment our index. 338 00:16:30,140 --> 00:16:31,120 Index 339 00:16:32,270 --> 00:16:33,520 equal 340 00:16:33,520 --> 00:16:34,563 index. 341 00:16:36,930 --> 00:16:39,160 Sorry plus one. 342 00:16:39,160 --> 00:16:41,233 Why did I put that in parentheses? 343 00:16:42,190 --> 00:16:43,113 What's missing? 344 00:16:44,750 --> 00:16:46,130 You ask? 345 00:16:46,130 --> 00:16:48,020 We have to module, take the module 346 00:16:48,020 --> 00:16:49,363 of the table size. 347 00:16:50,980 --> 00:16:52,250 Why do we do that? 348 00:16:52,250 --> 00:16:56,300 So that we don't run off the end of our hash table. 349 00:16:56,300 --> 00:16:58,500 So we don't want to keep incrementing this. 350 00:16:58,500 --> 00:17:02,100 We want to wrap around to index zero as needed. 351 00:17:02,100 --> 00:17:06,170 So we take the modules table size. 352 00:17:06,170 --> 00:17:07,220 Okay. 353 00:17:07,220 --> 00:17:11,830 So that's going to probe in a while loop 354 00:17:11,830 --> 00:17:16,290 until it finds a spot that's not filled. 355 00:17:16,290 --> 00:17:20,490 Now that could be an empty or something that's previously 356 00:17:20,490 --> 00:17:21,730 been removed. 357 00:17:21,730 --> 00:17:22,563 Okay. 358 00:17:23,660 --> 00:17:25,940 So then the first thing we're gonna want to do 359 00:17:25,940 --> 00:17:30,940 on the insert is we're going to save a copy of the status 360 00:17:31,200 --> 00:17:32,033 state 361 00:17:33,710 --> 00:17:34,543 temp 362 00:17:35,940 --> 00:17:36,773 equal 363 00:17:38,220 --> 00:17:39,053 table 364 00:17:40,880 --> 00:17:41,770 index 365 00:17:42,750 --> 00:17:44,020 status. 366 00:17:44,020 --> 00:17:45,623 That's the old status. 367 00:17:46,600 --> 00:17:48,190 Okay. 368 00:17:48,190 --> 00:17:50,380 And then 369 00:17:50,380 --> 00:17:51,560 We insert the item 370 00:17:55,570 --> 00:17:56,403 table 371 00:17:57,420 --> 00:17:58,310 index 372 00:17:59,810 --> 00:18:00,830 item 373 00:18:00,830 --> 00:18:01,833 equal item. 374 00:18:03,320 --> 00:18:07,680 That's the item that we passed in here gets assigned 375 00:18:07,680 --> 00:18:11,963 to table index item that we found by probing. 376 00:18:13,630 --> 00:18:16,070 And now we're gonna set that status 377 00:18:16,070 --> 00:18:16,903 to filled 378 00:18:17,790 --> 00:18:18,623 table 379 00:18:20,280 --> 00:18:21,180 index 380 00:18:22,880 --> 00:18:23,880 status 381 00:18:24,740 --> 00:18:25,903 equal filled. 382 00:18:30,560 --> 00:18:32,493 And then what do we need to do? 383 00:18:33,630 --> 00:18:38,190 This is where we check to see if we need to rehash. 384 00:18:38,190 --> 00:18:42,270 And so here's where having saved that state comes in. 385 00:18:42,270 --> 00:18:46,560 The number of objects in our table has only grown. 386 00:18:46,560 --> 00:18:50,940 If we've written to an empty element in our hash table 387 00:18:52,050 --> 00:18:56,730 if we've written to a deleted or removed item 388 00:18:56,730 --> 00:18:59,090 we don't need to rehash because we're just 389 00:18:59,090 --> 00:19:02,360 reusing a spot that had already previously been deleted. 390 00:19:02,360 --> 00:19:04,070 Okay that's why. 391 00:19:04,070 --> 00:19:05,620 So if 392 00:19:05,620 --> 00:19:06,453 temp 393 00:19:07,430 --> 00:19:09,030 equals empty 394 00:19:11,240 --> 00:19:15,333 then we're gonna increase the number of items. 395 00:19:17,430 --> 00:19:19,970 Then we need to check if we need to rehash. 396 00:19:19,970 --> 00:19:21,020 So 397 00:19:21,020 --> 00:19:22,090 if 398 00:19:22,090 --> 00:19:23,310 num items 399 00:19:25,020 --> 00:19:28,543 greater than table size, 400 00:19:30,040 --> 00:19:31,070 divided by two 401 00:19:33,040 --> 00:19:36,630 if our hash table is more than half filled 402 00:19:37,850 --> 00:19:38,730 hash 403 00:19:38,730 --> 00:19:39,940 table 404 00:19:39,940 --> 00:19:42,603 more than one half full, 405 00:19:44,010 --> 00:19:45,063 then we rehash. 406 00:19:48,980 --> 00:19:51,653 And all that's gonna do is gonna call 407 00:19:51,653 --> 00:19:53,240 a rehash method. 408 00:19:53,240 --> 00:19:55,670 It's gonna make a copy of the old table 409 00:19:55,670 --> 00:19:58,010 double the table size, find the next prime, 410 00:19:58,010 --> 00:19:59,000 empty out the table, 411 00:19:59,000 --> 00:20:00,260 resize the table, 412 00:20:00,260 --> 00:20:02,620 reset num items to zero 413 00:20:02,620 --> 00:20:04,250 loop through the old table, 414 00:20:04,250 --> 00:20:06,510 find all the filled items and insert them 415 00:20:06,510 --> 00:20:07,830 into the new table. 416 00:20:07,830 --> 00:20:09,250 That's our rehashing. 417 00:20:09,250 --> 00:20:10,350 Okay. 418 00:20:10,350 --> 00:20:11,950 And we only do that on inserts 419 00:20:15,210 --> 00:20:16,120 Next. 420 00:20:16,120 --> 00:20:17,040 What do we need to do? 421 00:20:17,040 --> 00:20:20,830 Well, you saw that we have this linear probing here. 422 00:20:20,830 --> 00:20:25,830 We're gonna need to add that to our other methods as well. 423 00:20:27,150 --> 00:20:30,400 So let me just, I'm gonna modify this 424 00:20:30,400 --> 00:20:31,710 but leave the code up there 425 00:20:31,710 --> 00:20:34,433 so you can see how it's changing. 426 00:20:36,980 --> 00:20:40,680 So we're gonna have a wild loop again while 427 00:20:42,660 --> 00:20:43,493 sorry 428 00:20:44,810 --> 00:20:45,643 table 429 00:20:48,020 --> 00:20:48,880 index 430 00:20:50,830 --> 00:20:51,830 status 431 00:20:53,840 --> 00:20:55,063 is not empty. 432 00:20:56,770 --> 00:20:57,750 Why are we doing that? 433 00:20:57,750 --> 00:21:00,990 Because we want to step over previously 434 00:21:00,990 --> 00:21:05,990 removed items that have their status set to removed. 435 00:21:06,030 --> 00:21:08,640 So we don't break the probe sequence. 436 00:21:08,640 --> 00:21:09,900 Okay. 437 00:21:09,900 --> 00:21:12,020 So then we check to see if there's an item 438 00:21:12,020 --> 00:21:14,170 and to see if that's the one that we're looking for. 439 00:21:14,170 --> 00:21:15,180 So if 440 00:21:16,990 --> 00:21:18,310 table 441 00:21:18,310 --> 00:21:19,300 index 442 00:21:21,250 --> 00:21:22,480 status 443 00:21:23,330 --> 00:21:24,490 equal filled 444 00:21:26,400 --> 00:21:27,660 and 445 00:21:27,660 --> 00:21:28,493 key 446 00:21:28,493 --> 00:21:32,920 remember we're passing in key here equal 447 00:21:32,920 --> 00:21:33,910 get key 448 00:21:37,360 --> 00:21:39,460 for that item table 449 00:21:41,890 --> 00:21:42,850 index 450 00:21:45,310 --> 00:21:46,143 item. 451 00:21:47,570 --> 00:21:50,870 Then we know we found our object 452 00:21:50,870 --> 00:21:52,510 and we just returned that item 453 00:21:52,510 --> 00:21:53,343 return 454 00:21:54,860 --> 00:21:55,693 table 455 00:21:56,660 --> 00:21:57,570 index 456 00:21:58,590 --> 00:21:59,423 item 457 00:22:03,810 --> 00:22:05,380 otherwise 458 00:22:07,110 --> 00:22:08,630 we do what we just did before. 459 00:22:08,630 --> 00:22:11,030 Remember this probe sequence here 460 00:22:12,220 --> 00:22:14,433 we're gonna do that exact same thing. 461 00:22:16,710 --> 00:22:18,400 We're gonna increment our index. 462 00:22:18,400 --> 00:22:20,060 And we're gonna take the modulates 463 00:22:20,060 --> 00:22:22,130 with the table size to make sure 464 00:22:22,130 --> 00:22:23,310 that we don't run off the end 465 00:22:23,310 --> 00:22:26,760 of our half table that we wrap around back to zero. 466 00:22:26,760 --> 00:22:28,740 And then the last thing we're gonna do is 467 00:22:28,740 --> 00:22:29,930 we're gonna return null up. 468 00:22:29,930 --> 00:22:33,550 So that bit of code that I've just produced here 469 00:22:33,550 --> 00:22:36,580 is gonna replace this bit of code here. 470 00:22:36,580 --> 00:22:38,180 So we'll just take that out now. 471 00:22:40,040 --> 00:22:41,690 Right? 472 00:22:41,690 --> 00:22:43,390 So that's our find method 473 00:22:45,260 --> 00:22:48,663 and we're gonna do something very similar for delete. 474 00:22:49,970 --> 00:22:51,970 So we're gonna probe the same way 475 00:22:53,680 --> 00:22:54,513 while 476 00:22:55,830 --> 00:22:56,950 table 477 00:22:56,950 --> 00:22:57,783 index. 478 00:22:57,783 --> 00:22:59,030 This is pretty much identical 479 00:23:03,140 --> 00:23:04,170 status 480 00:23:05,150 --> 00:23:06,680 not equal empty 481 00:23:11,020 --> 00:23:11,853 All right? 482 00:23:12,950 --> 00:23:16,494 And I'm just gonna copy this code and I don't 483 00:23:16,494 --> 00:23:17,630 see any reason to re-type it here. 484 00:23:17,630 --> 00:23:18,800 So I'm gonna get that 485 00:23:21,070 --> 00:23:24,840 if it's filled and the key matches 486 00:23:24,840 --> 00:23:27,980 then we found our item and what do we want to do here? 487 00:23:27,980 --> 00:23:30,470 Here's where we remove it. 488 00:23:30,470 --> 00:23:31,550 We set 489 00:23:31,550 --> 00:23:33,200 table 490 00:23:33,200 --> 00:23:34,150 index 491 00:23:36,630 --> 00:23:38,260 status 492 00:23:38,260 --> 00:23:40,050 equal remove 493 00:23:41,760 --> 00:23:42,670 removed 494 00:23:43,553 --> 00:23:45,600 and then we return the item 495 00:23:45,600 --> 00:23:46,590 return 496 00:23:48,060 --> 00:23:48,893 table 497 00:23:49,890 --> 00:23:51,520 index 498 00:23:51,520 --> 00:23:52,353 item. 499 00:23:53,900 --> 00:23:56,360 And then we're just gonna borrow this piece 500 00:23:56,360 --> 00:23:58,583 of code again, exactly the same thing. 501 00:24:00,650 --> 00:24:03,303 We're just gonna continue in our while loop, okay. 502 00:24:04,330 --> 00:24:09,330 And increment and take the modules to the table size. 503 00:24:10,670 --> 00:24:15,670 And that bit of code is gonna replace 504 00:24:15,720 --> 00:24:17,920 this bit of code here. 505 00:24:17,920 --> 00:24:19,130 So we'll take this out 506 00:24:22,180 --> 00:24:23,770 And that is our 507 00:24:24,880 --> 00:24:25,853 delete function. 508 00:24:27,860 --> 00:24:29,083 Now let's give it a run. 509 00:24:31,260 --> 00:24:35,353 I think the same demo here is gonna work. 510 00:24:36,310 --> 00:24:37,840 We've run this before. 511 00:24:37,840 --> 00:24:40,750 You've seen this before we have the Horner hash 512 00:24:40,750 --> 00:24:42,030 we have to get key function. 513 00:24:42,030 --> 00:24:44,830 We're using our little dictionary class. 514 00:24:44,830 --> 00:24:47,690 We're creating dictionary items 515 00:24:48,910 --> 00:24:50,040 and 516 00:24:50,040 --> 00:24:51,520 then 517 00:24:51,520 --> 00:24:55,280 printing out the table and then we're removing an item 518 00:24:55,280 --> 00:24:57,790 and I'm printing the table again. 519 00:24:57,790 --> 00:24:59,173 So let's run this now. 520 00:25:03,540 --> 00:25:07,780 Oh gosh I forgot to update the print method. 521 00:25:07,780 --> 00:25:09,493 I'm sorry, my bad. 522 00:25:10,740 --> 00:25:13,040 So this has to change 523 00:25:13,040 --> 00:25:15,500 because we no longer have simple objects. 524 00:25:15,500 --> 00:25:16,750 Now we have those struct. 525 00:25:17,890 --> 00:25:19,840 Okay so let's see here 526 00:25:21,160 --> 00:25:24,273 we print the index. 527 00:25:25,240 --> 00:25:26,073 If 528 00:25:26,073 --> 00:25:27,160 table 529 00:25:27,160 --> 00:25:27,993 I 530 00:25:27,993 --> 00:25:29,320 status 531 00:25:30,770 --> 00:25:32,273 equal filled. 532 00:25:34,230 --> 00:25:36,120 Okay. Then what do we do? 533 00:25:36,120 --> 00:25:37,240 Then we 534 00:25:38,420 --> 00:25:40,010 standard see out 535 00:25:42,010 --> 00:25:43,280 table 536 00:25:45,290 --> 00:25:46,910 I sorry. 537 00:25:46,910 --> 00:25:48,150 I 538 00:25:48,150 --> 00:25:49,730 item. 539 00:25:49,730 --> 00:25:50,563 Okay. 540 00:25:52,530 --> 00:25:53,480 Else 541 00:25:54,330 --> 00:25:55,163 if 542 00:25:57,020 --> 00:25:58,190 table 543 00:26:00,370 --> 00:26:01,850 I 544 00:26:01,850 --> 00:26:03,040 status 545 00:26:03,950 --> 00:26:05,370 equal removed 546 00:26:07,190 --> 00:26:09,990 then we'll print an X to indicate 547 00:26:14,180 --> 00:26:15,030 that it's been 548 00:26:15,030 --> 00:26:18,200 that there's been an item deleted at that position. 549 00:26:18,200 --> 00:26:20,180 And then the rest should be the same. 550 00:26:20,180 --> 00:26:22,183 So that should be okay now let's run it. 551 00:26:26,490 --> 00:26:27,550 Okay. There we go. 552 00:26:27,550 --> 00:26:29,133 So what have we got here? 553 00:26:30,250 --> 00:26:31,240 We have 554 00:26:32,910 --> 00:26:33,963 our hash table. 555 00:26:36,940 --> 00:26:37,773 Let me see. 556 00:26:37,773 --> 00:26:39,923 We have all of our values now. 557 00:26:42,600 --> 00:26:45,490 And you can see that it's been rehashed once 558 00:26:45,490 --> 00:26:48,940 since we initialized it with a size of 17 559 00:26:51,327 --> 00:26:53,960 and now it's size 37, 560 00:26:53,960 --> 00:26:56,120 twice 17 is 34. 561 00:26:56,120 --> 00:26:58,250 Next prime number is 37. 562 00:26:58,250 --> 00:27:01,740 So that's why we have a table of a size 37. 563 00:27:01,740 --> 00:27:02,573 And you see here 564 00:27:02,573 --> 00:27:07,010 this is where we had deleted a giggle that was 565 00:27:07,010 --> 00:27:09,823 at 27 years giggle 27. 566 00:27:10,970 --> 00:27:15,460 But notice also that we have a very nice example here 567 00:27:16,350 --> 00:27:19,483 of some primary clustering. 568 00:27:19,483 --> 00:27:21,090 Okay we have a bunch 569 00:27:21,090 --> 00:27:25,490 of elements that are all right there in a row. 570 00:27:25,490 --> 00:27:29,130 And that is one of the things that can happen 571 00:27:29,130 --> 00:27:30,713 with a linear probing. 572 00:27:32,200 --> 00:27:36,060 So codes on blackboard, have a look, give it a try. 573 00:27:36,060 --> 00:27:37,010 See what you think. 574 00:27:37,920 --> 00:27:38,753 More later.