1
00:00:01,500 --> 00:00:02,250
Hi, everyone.

2
00:00:02,280 --> 00:00:04,200
So as discussed in the last video.

3
00:00:05,120 --> 00:00:11,930
You have a key, so it will pass today has function and the output will basically be an integer, so

4
00:00:11,930 --> 00:00:14,330
this integer will be within the range of the error.

5
00:00:14,390 --> 00:00:16,550
So this is my victory.

6
00:00:19,270 --> 00:00:21,550
So they can be given by the hash function.

7
00:00:23,090 --> 00:00:25,700
Will be present, will be within the range of the area.

8
00:00:25,730 --> 00:00:29,150
So from zero to sides, minus one bucket size minus one.

9
00:00:30,180 --> 00:00:34,410
And we will go to that index and we restored the key value pair.

10
00:00:36,770 --> 00:00:42,860
Now we're discussing the last video that there will be a collision problem, so more than one case wants

11
00:00:42,860 --> 00:00:44,190
to go to this same index.

12
00:00:44,660 --> 00:00:49,340
So, for example, you have two guys, geeky 11 and geeky two.

13
00:00:49,640 --> 00:00:51,080
So this is a hash function.

14
00:00:51,380 --> 00:00:56,740
And basically the hash code is the hash function is giving the same index.

15
00:00:57,170 --> 00:00:59,240
So both Keys wants to go here.

16
00:01:00,330 --> 00:01:04,410
Watkis wants to go here, so how can we solve this problem?

17
00:01:04,950 --> 00:01:07,800
So basically they are actually handling techniques.

18
00:01:08,580 --> 00:01:13,160
So in the collision handling techniques, there are two types of collision handling techniques.

19
00:01:13,170 --> 00:01:14,280
So the first one.

20
00:01:15,510 --> 00:01:18,990
The name of first one is actually close to.

21
00:01:21,780 --> 00:01:26,910
And the second one is actually called open addressing.

22
00:01:28,780 --> 00:01:30,850
So these are coalition handling techniques.

23
00:01:37,330 --> 00:01:43,900
Now, what is the meaning of closed hedging so closed means both the keys will be present at this index

24
00:01:43,900 --> 00:01:44,230
only.

25
00:01:45,040 --> 00:01:47,840
So how can we store two things at one index?

26
00:01:48,430 --> 00:01:52,480
So basically what we will do, we will make a list at this point.

27
00:01:52,600 --> 00:01:54,660
We will construct a list at this point.

28
00:01:55,630 --> 00:02:04,420
So I will store, given its value even then give to key and value we do.

29
00:02:06,150 --> 00:02:06,960
And so on.

30
00:02:09,949 --> 00:02:17,650
Contributory value, gion value, so basically each each bucket will be ahead of a long list.

31
00:02:19,920 --> 00:02:28,060
So each bucket will be a hell of a long list, so both guys giving you two wants to be present at this

32
00:02:28,060 --> 00:02:32,190
index so close to Hastings's, then both present this index only.

33
00:02:32,370 --> 00:02:39,600
So I will construct a link list at this point and I will store given Key Ghilarducci with their corresponding

34
00:02:39,600 --> 00:02:40,050
values.

35
00:02:41,100 --> 00:02:44,880
OK, so this method is actually called separate chinning.

36
00:02:47,300 --> 00:02:49,310
This method is called separate training.

37
00:02:52,190 --> 00:02:58,580
So we have separate genes for each bucket, so we will have separate genes for each bucket.

38
00:02:58,850 --> 00:03:01,760
Similarly, it will also be a long list.

39
00:03:02,730 --> 00:03:05,310
So each bucket will be head of the linked list.

40
00:03:05,340 --> 00:03:06,270
Similarly, this one.

41
00:03:10,170 --> 00:03:14,610
OK, so understood, separate training, they will be separate for each brigade.

42
00:03:15,300 --> 00:03:21,810
Now let's discuss what is open addressing so open it is open.

43
00:03:21,880 --> 00:03:23,510
The thing is, you have a key.

44
00:03:23,820 --> 00:03:27,270
It will pass through a hash function, hash function.

45
00:03:27,300 --> 00:03:28,890
It will give you the index.

46
00:03:30,920 --> 00:03:34,160
Then you go to that index, so suppose this is the index.

47
00:03:34,700 --> 00:03:36,180
Now there are two possibilities.

48
00:03:36,440 --> 00:03:38,930
So first one, this index is basically empty.

49
00:03:39,260 --> 00:03:41,110
There is no key value being stored.

50
00:03:41,300 --> 00:03:44,950
So if it is empty, then you can store your key here.

51
00:03:45,950 --> 00:03:51,300
No issues, but if it is not empty, if already a key exist.

52
00:03:51,470 --> 00:03:54,640
So what you have to do, you have to find the alternate index.

53
00:03:55,520 --> 00:03:59,540
You have to find the alternate index for storing the key value beer.

54
00:04:00,470 --> 00:04:02,540
Now, how to find out that index.

55
00:04:03,290 --> 00:04:07,070
So basically there are many ways for finding out the alternate index.

56
00:04:07,760 --> 00:04:10,970
And now let us discuss those alternate indexes technique.

57
00:04:11,720 --> 00:04:13,420
So what we can do.

58
00:04:14,240 --> 00:04:17,019
So basically, I have a key key.

59
00:04:17,570 --> 00:04:23,030
So it will pass through the hash function and the hash function will give me the index.

60
00:04:30,090 --> 00:04:39,210
So now the eighth attempt for finding the index for Qiqi is actually so hash function, I will give

61
00:04:39,210 --> 00:04:40,190
the keiki as input.

62
00:04:40,200 --> 00:04:46,010
So the original hash function give Geer's input plus F off I.

63
00:04:46,860 --> 00:04:50,130
So what is I i is basically the eighth attempt.

64
00:04:52,550 --> 00:04:58,330
I is actually the academic for finding the index for geekier, so gay is key here.

65
00:05:00,910 --> 00:05:03,830
Now, what is the basic requirement for the function FFI?

66
00:05:04,330 --> 00:05:10,870
So if the value of AI is zero, so that means zero to attempt, so Addazio to attempt the key should

67
00:05:10,870 --> 00:05:12,760
be stored at this index only.

68
00:05:14,210 --> 00:05:20,690
So that means if the value of is it also the basic requirement for the function, FFI is so FFI should

69
00:05:20,690 --> 00:05:22,490
be zero when.

70
00:05:24,010 --> 00:05:25,120
I equals zero.

71
00:05:25,510 --> 00:05:28,760
OK, so this is the basic requirement for the function FFI.

72
00:05:29,170 --> 00:05:35,030
So there are many different techniques, many different opennet techniques based on different FFI.

73
00:05:35,470 --> 00:05:41,680
So you change the value of FFI, you change FFI and you will get a different OpenNet.

74
00:05:41,680 --> 00:05:42,380
The same technique.

75
00:05:42,400 --> 00:05:46,300
So different FFI is different think technique.

76
00:05:50,960 --> 00:05:58,970
Now, one most popular technique is basically called linear probing, so what is linear probing, so

77
00:05:58,970 --> 00:06:01,700
linear probing seems so linear.

78
00:06:01,700 --> 00:06:05,990
Probing, says FFI, is actually a.

79
00:06:07,020 --> 00:06:08,010
So what is the meaning?

80
00:06:08,700 --> 00:06:12,450
What you will do when the value of is zero, you will come here.

81
00:06:14,600 --> 00:06:21,620
Then linnear probings Ortega Jump-Off, one check if it is filled or empty, if it is empty, then store

82
00:06:21,620 --> 00:06:23,810
the key value pair had otherwise move ahead.

83
00:06:24,050 --> 00:06:27,030
Similarly, check it if it is empty or not, if empty.

84
00:06:27,050 --> 00:06:30,230
So the key will appear, otherwise move ahead and so on.

85
00:06:31,070 --> 00:06:33,470
So this is actually linear probing.

86
00:06:33,470 --> 00:06:38,870
FFI is EIU, so if the value of AI is zero, then what will happen to this will become zero.

87
00:06:39,170 --> 00:06:41,000
I will store read the original index.

88
00:06:41,960 --> 00:06:47,300
If the value of AI is one, then FFI will be one if I will be one.

89
00:06:47,540 --> 00:06:49,280
So basically this value will become one.

90
00:06:49,280 --> 00:06:50,420
So I will do plus one.

91
00:06:50,630 --> 00:06:51,710
So I will do plus one.

92
00:06:53,370 --> 00:07:00,210
If the value of AI is to so FFI will become to, then I will do Plaistow, so I will do Plasto basically

93
00:07:00,210 --> 00:07:01,110
I will move ahead.

94
00:07:01,770 --> 00:07:05,310
OK, so what we are doing, we are probing linearly.

95
00:07:05,790 --> 00:07:07,080
We are probing linearly.

96
00:07:07,890 --> 00:07:10,960
So I will check if this index is empty.

97
00:07:10,990 --> 00:07:12,750
Storyteller Adres Motörhead.

98
00:07:12,960 --> 00:07:14,730
Check if this index is empty.

99
00:07:15,150 --> 00:07:17,940
Still, if it isn't pretty -- straight otherwise move ahead.

100
00:07:18,090 --> 00:07:18,650
Simple.

101
00:07:19,230 --> 00:07:20,340
So this is linear probing.

102
00:07:20,340 --> 00:07:21,030
Linear probing.

103
00:07:21,030 --> 00:07:23,550
You can see the harsh cold.

104
00:07:23,550 --> 00:07:26,610
What will be the harsh cold water with the hash function.

105
00:07:27,210 --> 00:07:29,340
So this will be the original index.

106
00:07:31,000 --> 00:07:33,430
So this will give us the original index, this one.

107
00:07:34,540 --> 00:07:36,160
And then you can write a.

108
00:07:37,510 --> 00:07:44,650
OK, so this will be actually a more and and is basically the size of the venue will reach here, then

109
00:07:44,650 --> 00:07:46,510
you have to reach at this starting position.

110
00:07:47,810 --> 00:07:48,560
So this is.

111
00:07:52,220 --> 00:07:57,070
This is linear probing, take a jump off when, when, when, when, when they go, jump off one ahead.

112
00:07:57,110 --> 00:08:00,680
OK, another second is basically quadratic blobbing.

113
00:08:01,740 --> 00:08:03,930
Now, in the quality, probing what we will do.

114
00:08:05,870 --> 00:08:11,900
So this time, FFI is actually eisgruber, FFI is actually isco.

115
00:08:11,910 --> 00:08:17,550
So if I'm talking about this veiled attempt, so it will be zero if I'm talking about the first attempt.

116
00:08:17,570 --> 00:08:22,170
So it will be fun if I'm talking about the second attempt for finding the next.

117
00:08:22,170 --> 00:08:23,450
So it will become four.

118
00:08:24,170 --> 00:08:27,180
If the value of five three third attempt, it will become nine.

119
00:08:27,470 --> 00:08:28,370
So what we will do.

120
00:08:29,990 --> 00:08:30,830
So suppose.

121
00:08:33,740 --> 00:08:40,539
This is the original index, so suppose the original index, so if this is empty, so the value of is

122
00:08:40,580 --> 00:08:42,409
zero, I restored it here.

123
00:08:42,919 --> 00:08:47,570
Now, if it is not empty, what do I take a dump of one or take a jumper off one?

124
00:08:47,870 --> 00:08:50,330
If it is empty, then storyteller advice.

125
00:08:50,330 --> 00:08:51,820
Take a jump off for me.

126
00:08:52,280 --> 00:08:53,750
So I will take a jumper for.

127
00:08:56,310 --> 00:09:01,770
No, if it is empty straight here, otherwise take a jump of nine, so I will take a jump of nine.

128
00:09:04,800 --> 00:09:10,500
And check if it is empty, then store it here, otherwise take a dump off so it will afford to take

129
00:09:10,500 --> 00:09:11,500
a dump of 16.

130
00:09:11,940 --> 00:09:14,070
So what will be our answer?

131
00:09:14,090 --> 00:09:15,450
So it will be able to function.

132
00:09:15,840 --> 00:09:18,390
Our function will be the original hash function.

133
00:09:19,650 --> 00:09:22,290
Plus, I squared Mordaunt.

134
00:09:23,880 --> 00:09:30,270
So if you will reach ahead out of so if you will reach the out of index, you will.

135
00:09:32,160 --> 00:09:33,570
Richard Defroster, next.

136
00:09:33,600 --> 00:09:38,940
OK, so that's why I square more than so at the eight attempts over the value of a zero, this will

137
00:09:38,940 --> 00:09:40,500
become zero if the value of.

138
00:09:40,980 --> 00:09:44,630
So this will become even if the value of Ista, this will become four.

139
00:09:44,670 --> 00:09:45,330
And so on.

140
00:09:45,990 --> 00:09:48,870
So I'm repeating myself linear and quadratic probing.

141
00:09:49,320 --> 00:09:52,900
So linear, linear probing, says Paga Jump-Off one.

142
00:09:53,580 --> 00:09:55,970
So basically the new index.

143
00:09:56,340 --> 00:09:59,160
So new index will be the original index.

144
00:10:01,390 --> 00:10:03,220
I will give kids input and.

145
00:10:04,510 --> 00:10:13,450
I Ma'aden and the value of a meal starts from zero, simple, it will go zero, then one, then two

146
00:10:13,450 --> 00:10:14,020
and so on.

147
00:10:14,350 --> 00:10:16,720
So basically the probing is very, very simple.

148
00:10:17,680 --> 00:10:20,830
Initially, the value of zero, so you will go to the original.

149
00:10:20,860 --> 00:10:23,590
So this will become zero, the standard becomes zero.

150
00:10:23,590 --> 00:10:26,750
So go to the original index, you will go to the original index.

151
00:10:27,370 --> 00:10:29,250
Now, if it is empty, you can store.

152
00:10:29,260 --> 00:10:30,550
Otherwise you will move ahead.

153
00:10:31,300 --> 00:10:31,910
No check.

154
00:10:32,560 --> 00:10:34,180
I have to take a jump of one one.

155
00:10:34,190 --> 00:10:36,450
OK, plus it will wait.

156
00:10:36,490 --> 00:10:39,280
It will be plus one, then it'll be plus two then plus three.

157
00:10:39,500 --> 00:10:43,170
So then plus two then plus three.

158
00:10:43,180 --> 00:10:49,630
So I am taking a jump of one at a time and this more than is due to because then you will reach at the

159
00:10:49,630 --> 00:10:56,560
last index and then you will take a jump so that you can reach the first index and the quietest provinces

160
00:10:57,520 --> 00:11:01,640
do not take a jump of one one take a jump in Times of Square.

161
00:11:01,930 --> 00:11:09,070
So this will be the new index will be the original index and this will be a square more than.

162
00:11:09,730 --> 00:11:15,820
So again, the value of I will start from zero and it will keep going on until you are able to find

163
00:11:16,210 --> 00:11:17,380
an index.

164
00:11:17,380 --> 00:11:19,120
Very constructive loopier.

165
00:11:19,600 --> 00:11:20,160
Simple.

166
00:11:20,620 --> 00:11:22,360
So again, what will happen?

167
00:11:25,570 --> 00:11:32,370
So suppose this is your original index, so the value of five will be zero if it is empty storyteller

168
00:11:32,370 --> 00:11:33,940
here, otherwise take a jump of one.

169
00:11:34,600 --> 00:11:36,340
If it is empty, store it here.

170
00:11:36,340 --> 00:11:38,800
Otherwise take a jump of what you have to do.

171
00:11:39,100 --> 00:11:41,650
So this is this is plus zero.

172
00:11:41,650 --> 00:11:44,980
Then it will be pleasant, then it will be plus four, then it will be plus nine.

173
00:11:45,220 --> 00:11:51,420
So plus four then plus nine then plus 16 and so on.

174
00:11:52,090 --> 00:11:53,110
Now which one is better.

175
00:11:53,120 --> 00:11:53,840
Quality probing.

176
00:11:53,850 --> 00:11:54,680
Probably linear probing.

177
00:11:55,180 --> 00:11:56,880
So quality probing is better.

178
00:11:56,890 --> 00:11:57,130
Why.

179
00:11:57,130 --> 00:12:01,570
It is better because if we will see the problem with the linear probing.

180
00:12:01,570 --> 00:12:03,250
Is that so suppose you have a.

181
00:12:04,350 --> 00:12:09,570
So suppose you have a very popular index, so this is let's call it local popular index.

182
00:12:10,690 --> 00:12:14,870
So somehow your household has a problem, your household is a problem.

183
00:12:14,890 --> 00:12:21,610
You had a school has a problem and every kid wants to reach every kid wants to be present at this index.

184
00:12:22,030 --> 00:12:24,330
Every kid wants to be present at this index.

185
00:12:24,370 --> 00:12:26,050
So this is local popular index.

186
00:12:26,650 --> 00:12:31,270
Then with the help of linear probing, you are taking a jump of one again.

187
00:12:31,270 --> 00:12:32,440
You will take a jump of one.

188
00:12:32,770 --> 00:12:34,400
So you are taking a jump often.

189
00:12:34,450 --> 00:12:39,460
So they will be like many kids will be present here and rest.

190
00:12:39,460 --> 00:12:45,220
All the areas will be empty, rest all at will become empty, and many kids will be present only at

191
00:12:45,700 --> 00:12:46,950
a very small area.

192
00:12:47,620 --> 00:12:51,130
But if you lose quality blobbing, it will solve this problem.

193
00:12:51,670 --> 00:12:54,130
So this is basically clustering what is happening here.

194
00:12:54,610 --> 00:12:55,850
Clustering is happening here.

195
00:12:56,230 --> 00:13:00,460
So this is a local popular index, if you will, apply linear probing.

196
00:13:00,610 --> 00:13:05,550
So many kids will be present in the nearby area of local popular index.

197
00:13:05,560 --> 00:13:06,910
So they will be clustering.

198
00:13:06,910 --> 00:13:09,760
But if you lose quality probing what it will do.

199
00:13:10,000 --> 00:13:12,680
So this this will solve the problem of clustering.

200
00:13:13,240 --> 00:13:16,860
So this is local popular index quiting dropping will say Tigger's improvement.

201
00:13:17,410 --> 00:13:22,740
So if this is filled, then take a jump-off for if this is filled, then take a Jump-Off nine.

202
00:13:23,110 --> 00:13:24,280
So with the help of.

203
00:13:25,390 --> 00:13:31,930
So with the help of quite probing question will not be there, so if this is a local pope, it is a

204
00:13:31,930 --> 00:13:36,080
local popular index, every wants to be here.

205
00:13:36,310 --> 00:13:42,040
So with the help of quite probing, we will obtain a good distribution.

206
00:13:44,850 --> 00:13:51,270
We will obtain a good distribution ghys these will be spread out all over the area, not just around

207
00:13:51,930 --> 00:13:53,280
some particular area.

208
00:13:53,730 --> 00:13:55,560
OK, so quietly probing is better.

209
00:13:56,870 --> 00:13:59,750
Now, the third way is to basically use used to function.

210
00:14:01,330 --> 00:14:04,380
So the third approach is actually called double harshing.

211
00:14:05,230 --> 00:14:06,050
Now, what is the.

212
00:14:07,760 --> 00:14:09,230
So it is very simple.

213
00:14:10,200 --> 00:14:13,110
You find out the index using the hash function when.

214
00:14:14,740 --> 00:14:16,300
Now, if so.

215
00:14:19,050 --> 00:14:23,940
Now, this is the original index where the key wants to, but if.

216
00:14:24,790 --> 00:14:26,260
This index is already occupied.

217
00:14:26,290 --> 00:14:30,100
What do you do, you will apply that hash function, hash function to.

218
00:14:31,770 --> 00:14:38,660
You will abandon his function as function to so probably if you will add the result of these to heart

219
00:14:38,670 --> 00:14:41,720
function, so it will result in less conflict.

220
00:14:44,600 --> 00:14:51,800
It will result in less conflict, so so the idea of the world is actually using off to hedge functions.

221
00:14:52,580 --> 00:14:56,000
So what we will do so this is our original function.

222
00:14:56,540 --> 00:14:58,640
You passed K through the original hash function.

223
00:14:59,180 --> 00:15:04,940
Now, if there's a conflict, if this index is already occupied, what you will do, you you will apply

224
00:15:04,940 --> 00:15:05,870
and hash function.

225
00:15:06,140 --> 00:15:12,830
You will add the result and probably you will get an index, you will get an index which is probably

226
00:15:12,830 --> 00:15:13,820
not occupied.

227
00:15:15,820 --> 00:15:20,890
Basically empty and you can store it there and you can store your loopier there.

228
00:15:21,520 --> 00:15:22,960
So in practice.

229
00:15:26,350 --> 00:15:27,370
Separate chinning.

230
00:15:30,560 --> 00:15:35,480
Performs as well as perform as good as open dressing.

231
00:15:36,870 --> 00:15:41,540
So the performance of the burgeoning and open at the same technique they are releasing, OK, separate

232
00:15:41,580 --> 00:15:44,850
training works as good as open addressing techniques.

233
00:15:45,690 --> 00:15:47,550
So, again, what a separate training.

234
00:15:47,820 --> 00:15:49,460
So separate training is very simple.

235
00:15:50,100 --> 00:15:57,540
So each bucket of the list will actually be each bucket of the array will actually be a long list.

236
00:15:58,900 --> 00:16:02,680
OK, each bucket of the will actually be elementalist.

237
00:16:07,280 --> 00:16:13,190
So these are ahead of the list, these are head of the list, so from the next video onwards, we will

238
00:16:13,190 --> 00:16:17,480
implement separate training because separate training is very easy to implement.

239
00:16:18,320 --> 00:16:20,940
So bourgeoning is easy to implement from the next video.

240
00:16:21,080 --> 00:16:25,180
We will implement separate training also in the next one by.