1 00:00:01,970 --> 00:00:02,670 Hi, everyone. 2 00:00:02,690 --> 00:00:08,029 So now we will start implementing our own hash map using separate chinning. 3 00:00:09,420 --> 00:00:12,720 So what will do, we will create a class map. 4 00:00:13,820 --> 00:00:20,150 Now, inside this glass map, I was told I will have variables, key and value, I will have gained 5 00:00:20,150 --> 00:00:22,600 value now in built hash map. 6 00:00:22,970 --> 00:00:24,830 This is actually a template. 7 00:00:25,130 --> 00:00:32,980 So key can be anything integer, flawed, double string student, etc. and similarly in map values, 8 00:00:32,990 --> 00:00:33,910 also a template. 9 00:00:34,430 --> 00:00:39,230 So value can be anything in the character, anything student, anything basically. 10 00:00:40,130 --> 00:00:40,550 But. 11 00:00:42,060 --> 00:00:51,100 In our implementation, we will take as a string and we will take value as a template in our Hashmat 12 00:00:51,160 --> 00:00:51,960 implementation. 13 00:00:52,830 --> 00:00:55,890 So I am taking Gey as a string. 14 00:00:56,490 --> 00:01:02,520 So they the reason behind it, because, for example, Yorkeys, a student, if you will take me as 15 00:01:02,520 --> 00:01:06,480 a student, then how you will be able to find out the high school. 16 00:01:08,130 --> 00:01:10,800 So that's why I am taking key as a string. 17 00:01:12,450 --> 00:01:17,700 So if you want to write a general code, if you want to write a generic code, basically if you want 18 00:01:17,940 --> 00:01:24,120 your kid to be a template, then basically you have to define a way for finding out the code for each 19 00:01:24,120 --> 00:01:24,480 type. 20 00:01:25,350 --> 00:01:31,770 But here for our ease of implementation, I am thinking to be a string and value will be a template. 21 00:01:32,820 --> 00:01:35,130 So I'm repeating myself, what do we have? 22 00:01:36,510 --> 00:01:38,510 So this is my bucket, daddy. 23 00:01:38,910 --> 00:01:40,590 Let's see, the size is 20. 24 00:01:42,350 --> 00:01:47,030 And each bucket will represent the head of a long list. 25 00:01:50,260 --> 00:01:53,390 Simple now inside one node. 26 00:01:53,500 --> 00:02:01,140 So this is a node not of a long list now of so I'm going to take a string for key. 27 00:02:01,780 --> 00:02:03,070 My value will be template. 28 00:02:03,080 --> 00:02:07,480 So we value and obviously we will have next pointer. 29 00:02:08,620 --> 00:02:10,900 So our next point, North Star, next. 30 00:02:11,680 --> 00:02:17,190 So I am taking it as a string via string because we know how to find the hash code for a string. 31 00:02:17,840 --> 00:02:22,780 If you want to write a genetic code, basically, if you want your key to be a template, then you have 32 00:02:22,780 --> 00:02:29,740 to define the hash code for each type, for student, for integer, for double for characters. 33 00:02:30,010 --> 00:02:33,940 But here for the ease of implementation, I am taking key as a string. 34 00:02:34,660 --> 00:02:37,110 Simple now after this. 35 00:02:37,690 --> 00:02:40,480 So what is the entry of entry. 36 00:02:41,170 --> 00:02:43,240 So my entry will look like this. 37 00:02:44,780 --> 00:02:47,640 Node V start. 38 00:02:48,170 --> 00:02:52,870 So basically each entry is a is representing is containing the head of a link list. 39 00:02:53,480 --> 00:02:56,600 So that's why this is so this is at entry. 40 00:02:56,660 --> 00:03:01,400 OK, now I want to create an eddy, so I will write star and letter. 41 00:03:01,460 --> 00:03:02,960 The name of that is it's. 42 00:03:04,550 --> 00:03:11,830 So this is my area, so I'm repeating myself, so this is one entry, so how one day will look like 43 00:03:12,140 --> 00:03:13,570 so this will be a.. 44 00:03:14,240 --> 00:03:16,930 And since it is a pointer to the head of the linked list. 45 00:03:16,940 --> 00:03:20,430 So this will be NovaStar and I want to create an array. 46 00:03:20,440 --> 00:03:23,480 So that's why against that and the name of that. 47 00:03:23,600 --> 00:03:25,290 But it's simple. 48 00:03:25,820 --> 00:03:30,370 So apart from this area, apart from this backstory, what else we need? 49 00:03:30,620 --> 00:03:32,240 So we need a variable count. 50 00:03:33,560 --> 00:03:37,550 So discount will store how many entries are present in my map. 51 00:03:38,210 --> 00:03:39,700 OK, Nemirovsky value beer. 52 00:03:40,610 --> 00:03:44,110 And similarly, we will also need a variable number kids. 53 00:03:44,690 --> 00:03:45,720 So what is no good? 54 00:03:45,780 --> 00:03:47,930 So all you can say, Buckett says. 55 00:03:49,950 --> 00:03:52,500 So, for example, the bucket size is 20 here. 56 00:03:54,190 --> 00:03:56,140 So we need these three variables. 57 00:03:58,250 --> 00:04:06,200 And similarly, a normal store as I value V, a template value and a next pointer simple. 58 00:04:07,070 --> 00:04:09,530 So now let's start writing our regular. 59 00:04:15,160 --> 00:04:21,370 So first, I'm writing the code for this one, for creating a. so I have a Class A.. 60 00:04:26,540 --> 00:04:30,380 So class, let's say, nor is Map A.. 61 00:04:33,120 --> 00:04:41,130 And obviously so we need three variables, let's make them public, so the first one is actually string 62 00:04:41,440 --> 00:04:41,950 string. 63 00:04:43,740 --> 00:04:49,440 We need a value, our template value and similarly, we need a next pointer. 64 00:04:49,440 --> 00:04:51,360 So map not start next. 65 00:04:55,040 --> 00:04:58,910 Now, since this class is using template, so I have to write. 66 00:05:01,890 --> 00:05:03,690 Template type name be. 67 00:05:12,670 --> 00:05:15,100 OK, so DV is used here. 68 00:05:16,230 --> 00:05:18,090 Now, let us also create a constructor. 69 00:05:19,610 --> 00:05:26,090 So I have to episode so this constructive will take the values and put. 70 00:05:28,070 --> 00:05:29,420 Stringy and value. 71 00:05:40,420 --> 00:05:42,520 So this Rakowski and. 72 00:05:45,000 --> 00:05:45,690 Similarly. 73 00:05:48,060 --> 00:05:49,170 This added value. 74 00:05:51,520 --> 00:05:52,180 His value. 75 00:05:54,520 --> 00:05:56,590 And my next point, there will be none. 76 00:06:01,110 --> 00:06:04,110 Simple, now let us also create our districted. 77 00:06:05,140 --> 00:06:07,240 So I have this distractor. 78 00:06:10,240 --> 00:06:12,700 And this destructive will destroy. 79 00:06:13,800 --> 00:06:15,000 Next point, Denso. 80 00:06:16,590 --> 00:06:22,710 It will destroy next winter, so I will write the next. 81 00:06:23,960 --> 00:06:25,670 Now, when you are writing the next. 82 00:06:27,920 --> 00:06:30,500 So basically, this is your budgetary. 83 00:06:33,970 --> 00:06:35,950 I want to delete this whole link list. 84 00:06:38,460 --> 00:06:42,510 I want to delete this whole link list, so what I will write, I will write to delete next. 85 00:06:43,960 --> 00:06:45,800 So by writing the next, what will happen? 86 00:06:45,820 --> 00:06:48,970 So this whole list will be destroyed because this is recursive. 87 00:06:51,360 --> 00:06:55,260 OK, so this whole list will be destroyed because it is recursive. 88 00:06:59,640 --> 00:07:04,530 Now, let us also create this glass glass map. 89 00:07:05,450 --> 00:07:12,110 So this glass will have Buckett then count and similarly, no kids, so this bucket is using a value. 90 00:07:12,110 --> 00:07:13,300 So our template value. 91 00:07:13,310 --> 00:07:15,170 So I have to write template type NIMBY. 92 00:07:16,400 --> 00:07:17,630 So this map glass. 93 00:07:19,170 --> 00:07:20,760 Is actually using template. 94 00:07:22,330 --> 00:07:24,730 So let's say the name of the class is Minyip. 95 00:07:27,440 --> 00:07:31,580 So this class will use a template, so let's include. 96 00:07:32,610 --> 00:07:33,450 So template. 97 00:07:46,550 --> 00:07:50,450 No public, so what do we want to so first of all. 98 00:07:51,520 --> 00:07:54,490 We need buckets to map. 99 00:07:55,820 --> 00:07:56,690 Value is V.. 100 00:07:58,240 --> 00:07:59,680 So this is map old. 101 00:08:01,210 --> 00:08:08,250 A.B., so this is one entry, this is one in three of the three, and I want to create an array. 102 00:08:08,260 --> 00:08:12,370 So WINSTAR And then buckets, let's say the name of the Adès buckets. 103 00:08:14,760 --> 00:08:22,230 Simple, now we need a variable count to store how many entries are present and let us also take a variable 104 00:08:22,230 --> 00:08:22,630 number. 105 00:08:23,490 --> 00:08:24,840 What is the size of the area? 106 00:08:27,150 --> 00:08:27,690 Simple. 107 00:08:30,400 --> 00:08:34,270 So let's make all these properties as private, let's write private here. 108 00:08:36,840 --> 00:08:38,400 And now we will ride public. 109 00:08:41,929 --> 00:08:49,340 So let us write the contract for this class, so my map initially the county zero. 110 00:08:59,180 --> 00:09:02,900 So the count is zero and let's say the size of the. 111 00:09:04,420 --> 00:09:06,520 At initially, let's say it is five. 112 00:09:08,400 --> 00:09:14,160 And then let us create already so buckets is new. 113 00:09:15,900 --> 00:09:20,610 Map A. We start and no gets. 114 00:09:24,550 --> 00:09:25,680 So what is happening here? 115 00:09:28,470 --> 00:09:30,960 So now we have created this number, Cotati. 116 00:09:32,660 --> 00:09:34,730 So we have this Buckethead. 117 00:09:36,590 --> 00:09:37,880 But each and every. 118 00:09:39,280 --> 00:09:41,950 So each entry is containing a garbage address. 119 00:09:44,160 --> 00:09:49,980 Each entries containing a garbage address and know garbage addresses are very dangerous, so what we 120 00:09:49,980 --> 00:09:53,010 will do, we will iterate over this barcode said, and we will put. 121 00:09:54,310 --> 00:09:55,240 In each entry. 122 00:09:57,190 --> 00:10:04,300 Now, one more thing, so here I have taken all these things, so all these three variables are actually 123 00:10:04,300 --> 00:10:04,760 public. 124 00:10:05,560 --> 00:10:06,530 So what should I do? 125 00:10:06,550 --> 00:10:07,870 I should make them private. 126 00:10:10,040 --> 00:10:14,630 Why I made them public, because all these three variables are will be used in this class. 127 00:10:15,920 --> 00:10:20,180 So all these three variables are going to be used in this class, so that's why I made them public. 128 00:10:20,360 --> 00:10:24,140 But I believe what we should do, we should make this very private. 129 00:10:24,350 --> 00:10:30,410 And then with the help of friends classes, what I will do, I will make this class a friend of this 130 00:10:30,410 --> 00:10:30,740 class. 131 00:10:30,750 --> 00:10:34,550 So that's how this class will be able to access the private properties. 132 00:10:35,210 --> 00:10:38,240 But since we are not learning the concept of the classes. 133 00:10:38,600 --> 00:10:41,000 So that's why I made these things public. 134 00:10:41,540 --> 00:10:42,080 Simple. 135 00:10:43,070 --> 00:10:46,990 OK, so now let's do this thing instead of garbage address. 136 00:10:47,000 --> 00:10:47,630 Let's put. 137 00:10:51,500 --> 00:10:58,220 So, again, ideally, these three variables should be private, but these three variables are going 138 00:10:58,220 --> 00:11:02,260 to be used in my class, so that's why I made them public. 139 00:11:02,750 --> 00:11:09,130 But if you want, you can write private here and then you can make this class, my friend of Mechanoid 140 00:11:09,140 --> 00:11:09,540 Class. 141 00:11:10,010 --> 00:11:10,880 So that should work. 142 00:11:11,210 --> 00:11:14,930 But since we are not learning French classes, so that's why I made them public. 143 00:11:16,970 --> 00:11:21,920 Now, what we have to do so garbagey this is are very dangerous, so we will make them null. 144 00:11:33,210 --> 00:11:34,310 So buckets of a. 145 00:11:39,080 --> 00:11:39,680 Mesnil. 146 00:11:42,850 --> 00:11:46,000 Now, let us also create their districted. 147 00:11:50,970 --> 00:11:55,300 So this is glass distractor, my distracter, so what, it will destruct. 148 00:11:55,320 --> 00:11:55,800 So what? 149 00:11:55,800 --> 00:11:56,440 It will destroy. 150 00:11:56,490 --> 00:12:00,840 So it will destroy this BUGALDIE OK, we have to destroy the Bacardi. 151 00:12:01,770 --> 00:12:03,220 So what do we have? 152 00:12:03,240 --> 00:12:05,310 I want to destroy this Bacardi. 153 00:12:06,060 --> 00:12:13,400 So if you didley destroyed the Bacardi, it will simply write delete buckets, then what will happen? 154 00:12:14,040 --> 00:12:16,710 So you will not be able to delete this link list. 155 00:12:17,500 --> 00:12:19,690 You will not be able to delete these link list. 156 00:12:19,710 --> 00:12:25,020 So what we will do first, we will trade over liberatory and we will delete all the link list. 157 00:12:26,010 --> 00:12:27,710 We will limit this oil link list. 158 00:12:27,720 --> 00:12:33,540 And finally, after deleting all the link list, we will delete the obligatory I'm repeating myself, 159 00:12:34,230 --> 00:12:35,370 but we will do so. 160 00:12:35,370 --> 00:12:37,440 Basically, each entry is a long list. 161 00:12:39,220 --> 00:12:40,480 Each day is a long list. 162 00:12:41,440 --> 00:12:43,960 Now, what I want to do, I want to delete this whole. 163 00:12:45,430 --> 00:12:51,160 So what I have to do, I will go through each and every element and I will destroy the list first after 164 00:12:51,160 --> 00:12:53,320 destroying the list, and then I will destroy the book. 165 00:12:53,380 --> 00:12:59,110 Teddy, if you will destroy the bacteria first, then there is no way for us to delete this link list. 166 00:12:59,920 --> 00:13:01,750 So let's delete link list first. 167 00:13:03,730 --> 00:13:05,980 So that means we have to wait it over, the Bucket said. 168 00:13:16,050 --> 00:13:16,740 So delete. 169 00:13:19,260 --> 00:13:20,100 Buckets of far. 170 00:13:20,730 --> 00:13:24,960 So this is a recursive function, so our whole linked list will get deleted. 171 00:13:25,440 --> 00:13:28,860 Now after destroying the linked list, I can destroy the adding. 172 00:13:29,910 --> 00:13:32,310 So delete delete bucket. 173 00:13:35,670 --> 00:13:36,210 Simple. 174 00:13:37,550 --> 00:13:42,150 So now what we have to do, so that is right, some function. 175 00:13:42,170 --> 00:13:44,540 So, for example, size. 176 00:13:45,620 --> 00:13:51,130 So this is what it will return, it will return me how many elements are present inside my map. 177 00:13:51,680 --> 00:13:53,240 So basically I have to return. 178 00:13:54,820 --> 00:13:58,250 Count, so I will return this count, OK? 179 00:13:58,270 --> 00:14:03,640 I have to return the site, that means how many elements, how many loopier I present inside my map 180 00:14:03,940 --> 00:14:05,200 so I will return count. 181 00:14:06,300 --> 00:14:13,920 Now, what other functions we need in our map, so there should be a function, get value, so there 182 00:14:13,920 --> 00:14:19,860 should be a function, get value and it will take as input and it will return the value. 183 00:14:20,220 --> 00:14:22,520 So I need this function get value. 184 00:14:22,890 --> 00:14:24,200 It will return the value. 185 00:14:24,210 --> 00:14:27,580 We will retain value of retape. 186 00:14:28,830 --> 00:14:30,600 Now, similarly, what else we need? 187 00:14:31,050 --> 00:14:35,510 So we need insert function now this insert function, what it will take. 188 00:14:35,880 --> 00:14:40,170 So it will take key and value so stinky and we value. 189 00:14:42,420 --> 00:14:49,410 So that we can insert values into our map now, we have great value, we have installed we have sites 190 00:14:49,410 --> 00:14:52,050 function, so we need one more function, remove. 191 00:14:54,320 --> 00:14:55,760 So the return will be void. 192 00:14:57,620 --> 00:15:03,320 Well, remove and what it will take, it will take years input and it will remove that entry. 193 00:15:05,020 --> 00:15:08,130 So instead of returning type void, what do you return, pipis? 194 00:15:08,620 --> 00:15:14,800 So this remote function, we remove the entry and it will also return the value, it will return the 195 00:15:14,800 --> 00:15:18,880 value corresponding to the Gilinsky symbol. 196 00:15:21,220 --> 00:15:27,970 So let's start with the insert function, let's start implementing insert function, so how can we insert? 197 00:15:29,170 --> 00:15:30,010 So basically. 198 00:15:31,810 --> 00:15:39,580 Quite insulting, I will have a key and I have a value, so this guy will actually pass through a hash 199 00:15:39,580 --> 00:15:40,060 function. 200 00:15:41,280 --> 00:15:48,090 This key will pass through a hash function, and that hash function will give me Buckett index, the 201 00:15:48,090 --> 00:15:50,970 index at which I have to insert my entry. 202 00:15:53,370 --> 00:15:58,260 So basically, first of all, we have to write this hash function, I want to insert I want to write 203 00:15:58,260 --> 00:15:59,460 this function insert function. 204 00:15:59,490 --> 00:16:04,830 So first of all, I need to find out the value of Bookit index for finding out the value of market index. 205 00:16:04,840 --> 00:16:06,390 We should have hash function. 206 00:16:07,530 --> 00:16:09,750 So let us first rate the hash function. 207 00:16:13,280 --> 00:16:18,050 So what do I want to do, something like this, so Buchardt index. 208 00:16:20,710 --> 00:16:25,360 So what I will do, I will write a function, get a good index. 209 00:16:28,380 --> 00:16:36,660 And I will pass key, so now let us write this function, get Buchard Index, so obviously this function 210 00:16:36,660 --> 00:16:37,530 has to be private. 211 00:16:40,230 --> 00:16:45,270 So get market index, what it will return, so it will return any integer. 212 00:16:48,620 --> 00:16:51,320 And what it will take so it will take. 213 00:16:52,360 --> 00:16:53,110 Stringy. 214 00:16:56,820 --> 00:16:59,380 So how can we complete this function? 215 00:16:59,790 --> 00:17:03,440 So basically there are two parts of this function get market index. 216 00:17:03,480 --> 00:17:04,470 So there are two parts. 217 00:17:05,190 --> 00:17:09,770 So our hash function, so this and get market index, it does nothing. 218 00:17:09,790 --> 00:17:11,349 It is just the hash function. 219 00:17:11,760 --> 00:17:13,400 So this house function has two parts. 220 00:17:13,440 --> 00:17:17,849 The first one is finding out the hash code and then applying decompression function. 221 00:17:19,470 --> 00:17:21,950 So applying the compression function is very, very simple. 222 00:17:21,990 --> 00:17:25,290 We will just take percentage but size. 223 00:17:26,710 --> 00:17:30,730 In our case, our bucket size is actually represented by a variable number. 224 00:17:30,790 --> 00:17:31,090 It's. 225 00:17:33,870 --> 00:17:40,350 Now, how can we find the high school, so if you remember in our last lesson we discussed, so you 226 00:17:40,350 --> 00:17:47,250 have a string ABC and we will represent this string ABC as no no with BCB. 227 00:17:49,230 --> 00:17:57,420 No, with BSP, so this ABC, it is nothing, it is just the value of a multiply Bisquick. 228 00:17:57,750 --> 00:18:04,980 Similarly, the asset value of B multiply B and similarly the asset value of C, multiply Butel, the 229 00:18:04,980 --> 00:18:07,620 power of zero and B the prime number. 230 00:18:07,650 --> 00:18:10,440 So let's say in our case we are taking B 37. 231 00:18:10,570 --> 00:18:11,880 You can take any prime number. 232 00:18:12,920 --> 00:18:15,570 So generally, the large number is better. 233 00:18:15,740 --> 00:18:19,700 So I'm taking 37 now, how can we find this value? 234 00:18:20,030 --> 00:18:21,170 So basically, what do we do? 235 00:18:21,200 --> 00:18:23,600 We will start our trading of the string from the end. 236 00:18:24,510 --> 00:18:31,580 It will take the string in this manner from end to this start, and we will calculate our record. 237 00:18:32,660 --> 00:18:34,340 So let's calculate our high school. 238 00:18:36,790 --> 00:18:38,270 So what do we have here? 239 00:18:38,560 --> 00:18:43,420 So initially our hash code is zero, so let's take a variable hash called. 240 00:18:44,340 --> 00:18:49,230 So initially, our high school is zero and what we have to do so at the end. 241 00:18:51,480 --> 00:18:56,880 What we have to do then we have to apply the compression function, so I will return high school, then 242 00:18:56,880 --> 00:18:58,330 I'm applying the compression function. 243 00:18:58,390 --> 00:18:59,670 So this is no good. 244 00:19:01,560 --> 00:19:02,100 Simple. 245 00:19:03,330 --> 00:19:06,210 This one, no, so I'm a blinding oppression function. 246 00:19:06,610 --> 00:19:08,720 Now let's try to find out our high school. 247 00:19:09,180 --> 00:19:11,850 So what we have to do, we have to start out from the end. 248 00:19:12,690 --> 00:19:14,370 So let's do it from the end. 249 00:19:14,520 --> 00:19:16,320 So ECLSS Guitard. 250 00:19:17,990 --> 00:19:24,920 Sighs Minus one, and I didn't get close to zero, I minus minus. 251 00:19:29,050 --> 00:19:30,010 So hash called. 252 00:19:31,000 --> 00:19:37,900 Plus equals two, so what we have to do, so this guy, the character will be multiplied with. 253 00:19:39,450 --> 00:19:42,870 A base value, so initially this base value is one. 254 00:19:44,270 --> 00:19:52,580 Initially, the base value is one and our prime number B is actually, let's say 37, our prime number 255 00:19:52,580 --> 00:19:57,730 is 27 and bases when so initially for the first time, it will get multiplied with base. 256 00:19:58,160 --> 00:20:06,260 And then what we will do so base equals base multiply B BS our premium, but. 257 00:20:07,300 --> 00:20:08,450 Now, what is happening here? 258 00:20:08,500 --> 00:20:10,570 So suppose you have this string ABC. 259 00:20:11,590 --> 00:20:18,610 And what I want to calculate the value of a multiply be squared, similarly, the asset value of B multiply 260 00:20:19,480 --> 00:20:23,390 bruited about one and the value of C multiply P to zero. 261 00:20:24,010 --> 00:20:26,680 So this period about zero, it is one. 262 00:20:26,890 --> 00:20:29,140 I'm calling it as BS. 263 00:20:29,140 --> 00:20:31,380 So this is base basis one then. 264 00:20:31,990 --> 00:20:33,480 So this is part of the Power-One. 265 00:20:33,940 --> 00:20:40,810 So what will happen based will get multiplied with B, so base will become B here and here for A what 266 00:20:40,810 --> 00:20:46,810 will happen based will again get multiplied would be so p multiply P so base will become P squared simple 267 00:20:47,620 --> 00:20:50,820 and GFI is basically the current character. 268 00:20:51,670 --> 00:20:52,140 Simple. 269 00:20:53,080 --> 00:20:54,670 Now what is the problem with this whole. 270 00:20:55,710 --> 00:20:57,140 The problem is very simple. 271 00:20:58,140 --> 00:21:01,680 Our integer, our values will become out of range. 272 00:21:02,400 --> 00:21:08,820 So these variables, so base is getting multiplied with 37 and similarly, the hash code is increasing 273 00:21:08,820 --> 00:21:09,870 at a very fast rate. 274 00:21:10,230 --> 00:21:12,840 So hash code and base. 275 00:21:13,930 --> 00:21:16,010 They are increasing at a very fast rate. 276 00:21:16,030 --> 00:21:20,180 So what will happen, they will become out of range of the interior very, very fast. 277 00:21:21,220 --> 00:21:22,630 So how can we avoid this? 278 00:21:23,790 --> 00:21:24,750 So what we will do? 279 00:21:26,240 --> 00:21:29,790 So there is a property of more or less operator by operator. 280 00:21:30,290 --> 00:21:33,020 So, for example, you have three numbers, let's say N1. 281 00:21:34,310 --> 00:21:35,720 And to an entry. 282 00:21:36,900 --> 00:21:42,930 And you have to find you will multiply all the numbers and then you have to take percentage are so there 283 00:21:42,930 --> 00:21:48,330 there's a formula for this and the formula is you do like this and when Morde are. 284 00:21:49,580 --> 00:21:59,200 Then you multiply it with N2 Marda, then you multiply it with entry big Mordred and then take Morde 285 00:21:59,210 --> 00:22:00,440 R for the complete one. 286 00:22:02,000 --> 00:22:04,550 So let's take an example to suppose you want to find out. 287 00:22:04,940 --> 00:22:11,480 So this is for any number of men, for any number of men, not just three, it can be four, five, 288 00:22:11,480 --> 00:22:14,360 six to seven, nine, 10, anything. 289 00:22:14,630 --> 00:22:15,860 So let's take the number. 290 00:22:16,400 --> 00:22:21,890 Let's say I want to find out for multiply seven and more three. 291 00:22:23,330 --> 00:22:29,540 Let's say I want to find out this answer, so it will be so this will be 28 more three. 292 00:22:29,930 --> 00:22:30,810 So it is one. 293 00:22:31,610 --> 00:22:33,550 And now let us apply this formula. 294 00:22:33,980 --> 00:22:42,140 So according to this formula, it will get converted into four more three, then multiply with seven. 295 00:22:42,140 --> 00:22:42,680 More three. 296 00:22:43,720 --> 00:22:45,610 And then take more three for all. 297 00:22:48,340 --> 00:22:52,690 So it it will become when then it will get multiplied. 298 00:22:52,870 --> 00:22:53,890 So this is also one. 299 00:22:55,300 --> 00:22:58,570 But multiply one and then I have this more three. 300 00:23:00,270 --> 00:23:02,550 So what is one more three, so this is one. 301 00:23:03,840 --> 00:23:05,660 And you can see our answer, you see? 302 00:23:06,990 --> 00:23:12,650 Now, in our caution, in our problem, what we have to do, so we are returning percentage, no buckets, 303 00:23:13,650 --> 00:23:14,320 so what do we do? 304 00:23:14,340 --> 00:23:16,770 We will apply the number of bullets at every step. 305 00:23:17,220 --> 00:23:18,360 We will use this formula. 306 00:23:19,050 --> 00:23:20,130 We will use this formula. 307 00:23:20,340 --> 00:23:21,130 So it will take. 308 00:23:21,180 --> 00:23:24,150 So what I am doing, I'm calculating my high school. 309 00:23:26,260 --> 00:23:31,930 And then at the time of returning my household, I am applying decompression function, so take decompression 310 00:23:31,930 --> 00:23:37,960 friction, so take the compression function inside, so apply the compression friction at each point 311 00:23:38,200 --> 00:23:40,030 so that your number becomes smaller. 312 00:23:40,210 --> 00:23:41,710 It will not get out of range. 313 00:23:41,740 --> 00:23:42,070 OK. 314 00:23:46,530 --> 00:23:50,940 So what is happening here, base is increasing at a very frustrated has is also increasing at a very 315 00:23:50,940 --> 00:23:57,570 frustrated and we want to store them in India, we want to store them and individual variables. 316 00:23:58,810 --> 00:23:59,650 So what we will do? 317 00:24:01,970 --> 00:24:06,920 We will apply percentage no buckets at each step, so what we will do? 318 00:24:11,930 --> 00:24:13,010 So harsh is. 319 00:24:14,820 --> 00:24:17,700 Hash called percentage number, it's. 320 00:24:19,180 --> 00:24:21,880 And similarly, base is also increasing at a very fast rate. 321 00:24:24,280 --> 00:24:26,740 So basically, this base percentage. 322 00:24:28,070 --> 00:24:28,970 No, it's. 323 00:24:36,800 --> 00:24:43,250 So why we are doing this percentage so that the things are smaller, so that we can keep our things 324 00:24:43,250 --> 00:24:48,060 smaller, and while this is correct, this is correct because of the property of more or less operator. 325 00:24:48,110 --> 00:24:50,450 OK, so these are the properties of the more or less operator. 326 00:24:50,900 --> 00:24:54,410 And we are doing this because we want to make our things. 327 00:24:54,410 --> 00:24:56,060 We want to keep our things smaller. 328 00:24:57,630 --> 00:25:00,130 So I will get back to the index function is ready. 329 00:25:00,750 --> 00:25:03,030 So now let us complete our insert function. 330 00:25:03,510 --> 00:25:07,980 So gutbucket index, I will give guys input and it will return me the bucket index. 331 00:25:09,010 --> 00:25:09,550 Simple. 332 00:25:11,930 --> 00:25:14,660 So after doing this, what is the scenario? 333 00:25:15,830 --> 00:25:18,590 So I have in the inside function, what do we have? 334 00:25:22,980 --> 00:25:26,160 So basically, I have this Buckett index. 335 00:25:28,410 --> 00:25:30,570 I am able to find out the Buckeridge index. 336 00:25:31,700 --> 00:25:36,710 So we will pass through the hash function and hash function is returning the budget index. 337 00:25:37,190 --> 00:25:42,290 So now for the insert function, I know at which index I want to insert. 338 00:25:43,100 --> 00:25:44,240 Now, how do we insert? 339 00:25:44,540 --> 00:25:46,210 So at this point, what do we have? 340 00:25:46,490 --> 00:25:48,620 So I have a list at this point. 341 00:25:50,810 --> 00:25:54,480 So what they can do, we can insert our key will appear at different. 342 00:25:54,860 --> 00:25:57,140 So how can we insert I will make a node. 343 00:25:58,340 --> 00:26:05,540 So this node will point towards the original head and this bucket will point towards this one, but 344 00:26:05,540 --> 00:26:06,320 is this correct? 345 00:26:07,130 --> 00:26:08,570 So this is not correct. 346 00:26:09,770 --> 00:26:10,990 We will insert that front. 347 00:26:11,330 --> 00:26:12,760 So there is no problem with this. 348 00:26:12,780 --> 00:26:13,430 This is correct. 349 00:26:13,700 --> 00:26:16,460 But directly inserting a different this is wrong. 350 00:26:16,470 --> 00:26:17,240 Why this is wrong? 351 00:26:17,390 --> 00:26:19,130 Because we know the keys. 352 00:26:19,820 --> 00:26:21,380 The keys are unique in the hash map. 353 00:26:21,560 --> 00:26:23,780 For example, you want to insert ABC? 354 00:26:24,960 --> 00:26:28,840 The ABC and the values to and suppose ABC's already present. 355 00:26:29,520 --> 00:26:32,680 Suppose ABC is already present then, but they have to do so. 356 00:26:32,700 --> 00:26:39,690 Our first step is basically when you reach the head of the list, so you will traverse this link list. 357 00:26:40,290 --> 00:26:45,150 We will have to traverse this link list so that we can check whether the given already exists or not. 358 00:26:45,780 --> 00:26:51,900 So, for example, initially you have this value ABC and you have ABC and the Values one. 359 00:26:52,110 --> 00:26:53,850 So he inserted ABC Common. 360 00:26:55,130 --> 00:26:56,900 OK, you inserted a bicycle motion. 361 00:26:57,150 --> 00:27:02,460 Now you want to insert a comma, too, so the values get that values getting updated. 362 00:27:02,480 --> 00:27:08,240 So what you will do, you will traverse this long list and then you will find, yes, ABC is already 363 00:27:08,240 --> 00:27:08,560 there. 364 00:27:08,570 --> 00:27:09,450 You will Maggi. 365 00:27:09,860 --> 00:27:11,350 So ABC is already there. 366 00:27:11,390 --> 00:27:16,520 Then what you will do, you will update the schedule so the value will become to OK, value will become 367 00:27:16,520 --> 00:27:16,790 to. 368 00:27:17,700 --> 00:27:22,060 Now, if you get something like this, the F and then three. 369 00:27:22,410 --> 00:27:23,610 So basically what will happen? 370 00:27:23,610 --> 00:27:30,540 You will I did this long list and you will not be able to find the key beef in this linked list since 371 00:27:30,540 --> 00:27:32,090 you are not able to find this guy. 372 00:27:32,430 --> 00:27:35,230 So that means this guy is unique. 373 00:27:35,280 --> 00:27:36,730 This guy is coming for the first time. 374 00:27:36,990 --> 00:27:42,220 So in that case, we will do this approach, will create a new node and we will insert the node at different. 375 00:27:43,020 --> 00:27:44,380 So let's write the code. 376 00:27:45,930 --> 00:27:51,210 So after finding out the background index, now let us find out the head pointer. 377 00:27:51,300 --> 00:27:53,190 OK, so what is the point out? 378 00:27:53,340 --> 00:27:54,270 The is actually. 379 00:27:56,200 --> 00:27:58,510 So this is my head, but it's very. 380 00:28:00,060 --> 00:28:02,370 And I will pass this index, but good index. 381 00:28:07,880 --> 00:28:10,830 OK, so this is the head of the list now. 382 00:28:10,910 --> 00:28:14,180 We have to do first, we have to traverse the head of the linked list. 383 00:28:14,450 --> 00:28:18,860 We have to traverse the complete list so that we can check whether the given case already present or 384 00:28:18,860 --> 00:28:19,200 not. 385 00:28:19,580 --> 00:28:21,350 So let us trade over the long list. 386 00:28:23,080 --> 00:28:23,890 So what will do? 387 00:28:25,800 --> 00:28:28,170 Vieillard is not acquisitional. 388 00:28:31,610 --> 00:28:33,890 We will do Heracles next offered. 389 00:28:36,810 --> 00:28:41,470 OK, so we are traversing the list and we have to check, so we have to check. 390 00:28:42,690 --> 00:28:44,130 So is there a.. 391 00:28:45,930 --> 00:28:54,210 Is there a. whose value is basically close to the given key value and if are able to find that node, 392 00:28:54,600 --> 00:28:55,530 then you have to do. 393 00:28:55,710 --> 00:28:57,150 You do not have to insert anything. 394 00:28:57,150 --> 00:28:59,310 You just have to appreciate the value. 395 00:28:59,730 --> 00:29:00,180 So. 396 00:29:01,090 --> 00:29:04,330 That Norvelle will get updated to Disvalue. 397 00:29:06,550 --> 00:29:11,650 So this has value and then you don't have to insert you can back later than simple. 398 00:29:12,680 --> 00:29:13,850 Now, what is happening here? 399 00:29:15,950 --> 00:29:16,730 So what I'm doing. 400 00:29:17,670 --> 00:29:23,700 So this guy is actually passing through a hash function and it is returning me a bucket index. 401 00:29:25,230 --> 00:29:26,520 So this is Buckeridge Index. 402 00:29:27,720 --> 00:29:29,370 Now, what I am doing so this is my book. 403 00:29:31,370 --> 00:29:33,170 So let's say this is the budget index. 404 00:29:35,270 --> 00:29:36,980 And then we have a linked list here. 405 00:29:40,500 --> 00:29:42,130 So where does this head? 406 00:29:42,150 --> 00:29:45,110 So this head is pointing towards the head of the linked list. 407 00:29:46,510 --> 00:29:49,840 And now all we have to do so I suppose first you inserted ABC. 408 00:29:51,300 --> 00:29:59,560 Cameron, so ABC Cameron is already present now the query is you want to insert ABC Clamato so you can 409 00:29:59,560 --> 00:30:03,310 not directly insert the key because in MAP the keys are unique. 410 00:30:03,840 --> 00:30:08,220 So what you'll do, you will insert you will basically traverse this link list. 411 00:30:09,030 --> 00:30:12,360 So I am traversing the link list, Bilitis in order to move ahead. 412 00:30:13,480 --> 00:30:16,900 And basically, you will check, you will check. 413 00:30:17,110 --> 00:30:19,130 So whether this is already present. 414 00:30:19,180 --> 00:30:21,400 Yes, this guy is already present. 415 00:30:21,670 --> 00:30:24,230 So hedgie is equal to the given key. 416 00:30:25,060 --> 00:30:28,510 OK, so if they had the key is equal to the given key. 417 00:30:28,750 --> 00:30:30,760 So that means you do not have to insert anything. 418 00:30:30,760 --> 00:30:32,260 You just have to update the value. 419 00:30:32,500 --> 00:30:33,910 So initially the value was one. 420 00:30:34,120 --> 00:30:35,140 Now the value is two. 421 00:30:35,470 --> 00:30:37,940 So here ABC cameraman was present. 422 00:30:38,230 --> 00:30:39,970 Now instead of when you will write to. 423 00:30:40,210 --> 00:30:44,490 So you will update the value and then you can return nothing else. 424 00:30:45,460 --> 00:30:47,380 But if I will reach this line. 425 00:30:48,750 --> 00:30:51,660 Basically, line number seventy five, so that means. 426 00:30:53,410 --> 00:30:59,660 I teach needlepoint, so this is null pointer, so if I am reaching the null pointer, so that means 427 00:30:59,680 --> 00:31:02,380 so this is null point if I am reaching the null pointer. 428 00:31:02,680 --> 00:31:07,390 So that means this gurantee ABC's not present, for example, for the key, the ECF. 429 00:31:08,960 --> 00:31:15,440 Now for the the ITF, if you will, little bit over the kid, the effort is not present, so finally 430 00:31:15,440 --> 00:31:18,490 you will reach the null pointer and then what we have to do. 431 00:31:19,130 --> 00:31:21,020 So first of all, we will create a.. 432 00:31:22,980 --> 00:31:30,510 DCF and let's face value is three, so I will create an audio commentary, then this D.F. commentary 433 00:31:30,510 --> 00:31:35,490 will point towards the first node, will point towards the head, it will point towards the head. 434 00:31:35,490 --> 00:31:37,670 And then what I will do, I will update the herd. 435 00:31:37,980 --> 00:31:44,490 So this budget, budgetary, this budget, and they will point towards this newly created node and we 436 00:31:44,490 --> 00:31:45,620 will delete this link. 437 00:31:47,130 --> 00:31:54,480 So Steps is a very simple first step, is basically creating this new node, then inserting at the head 438 00:31:54,480 --> 00:31:56,790 and then basically this. 439 00:31:56,970 --> 00:32:00,230 We will update the head and we will unlink the original. 440 00:32:04,250 --> 00:32:05,700 So at this point, what you have to do. 441 00:32:05,930 --> 00:32:09,840 We have to insert a different and we already know how to insert a different. 442 00:32:10,550 --> 00:32:12,050 So basically we have to create. 443 00:32:13,120 --> 00:32:14,140 A new first. 444 00:32:18,110 --> 00:32:20,630 So let's say its name is Naude. 445 00:32:24,070 --> 00:32:25,510 So this is new Map Naude. 446 00:32:29,260 --> 00:32:35,160 And if you can see, I already have the constructor, so with the constructor, so this is the constructor, 447 00:32:35,290 --> 00:32:37,610 so I have to Paskey and I have to pass value. 448 00:32:37,750 --> 00:32:43,000 So we already have constructor, so I have to parseghian value key and value. 449 00:32:44,000 --> 00:32:48,560 OK, so this one, this one and this one value, so I'm thinking in value. 450 00:32:50,430 --> 00:32:51,540 And then what we have to do. 451 00:32:52,720 --> 00:32:55,150 So I will do Naude next. 452 00:32:58,610 --> 00:33:00,500 So not I don't think it is actually this one. 453 00:33:01,510 --> 00:33:04,000 Had so I have to find her again. 454 00:33:05,280 --> 00:33:11,820 So let's copy this one and let's be attrited and then what we have to do, so we have to update this 455 00:33:11,820 --> 00:33:14,160 value, we have to update our head so. 456 00:33:15,580 --> 00:33:18,820 This is actually my nolde. 457 00:33:21,450 --> 00:33:22,560 So what I'm doing here. 458 00:33:25,910 --> 00:33:27,020 So this is actually. 459 00:33:27,980 --> 00:33:33,740 The linked list, and I want to insert a different salvo in starting a different I created a new node. 460 00:33:33,750 --> 00:33:35,930 So this is node then? 461 00:33:36,320 --> 00:33:37,580 This is the first step. 462 00:33:38,300 --> 00:33:40,310 And the second step is basically a link. 463 00:33:40,310 --> 00:33:43,430 This node and this node will point to this node. 464 00:33:44,210 --> 00:33:45,470 So I'm doing just the same. 465 00:33:46,760 --> 00:33:48,140 I'm creating this new node. 466 00:33:48,530 --> 00:33:54,520 Then node next is pointing towards the first node and then I'm updating my head. 467 00:33:55,220 --> 00:33:56,060 So one more thing. 468 00:33:57,230 --> 00:34:00,380 If you remember, we have a variable count, so I have to do count plus. 469 00:34:00,380 --> 00:34:02,860 Plus I have to do countless lists. 470 00:34:02,870 --> 00:34:07,160 So this very well will store how many developers are present inside the map. 471 00:34:07,640 --> 00:34:10,820 Now, one thing I am not doing countless bets here. 472 00:34:11,510 --> 00:34:15,730 I'm not doing countless puzzle here because here we are just updating the value. 473 00:34:15,739 --> 00:34:18,920 We are not inserting a new developer here. 474 00:34:19,250 --> 00:34:21,020 I'm starting a new developer. 475 00:34:21,030 --> 00:34:23,300 So that's why I did countless press here only. 476 00:34:24,550 --> 00:34:29,440 So what we will do so in the next video, we will write the code for get value and we will write the 477 00:34:29,440 --> 00:34:30,590 code for any more function. 478 00:34:31,120 --> 00:34:32,620 I will see in the next one by.