1
00:00:01,470 --> 00:00:02,220
Hi, everyone.

2
00:00:02,250 --> 00:00:07,170
So now let's start discussing how we can implement hash map using hash table.

3
00:00:08,270 --> 00:00:15,210
So basically, we want to start two things, I will stalky and I want to store value and in hash map

4
00:00:15,230 --> 00:00:18,840
you can store in Question Time and you can access in Question Time.

5
00:00:19,190 --> 00:00:22,760
So basically in hash, this is the property storing and accessing.

6
00:00:23,180 --> 00:00:24,800
They built out Question Time.

7
00:00:26,250 --> 00:00:32,130
And till now, we started only one data structure with support, storing and accessing in constant time,

8
00:00:32,369 --> 00:00:35,040
and that data structure is actually Eddie.

9
00:00:36,680 --> 00:00:43,700
So that means we have to use it for the implementation of Hashmat because it is the only structure which

10
00:00:43,700 --> 00:00:48,890
can store and accessing Konstantine, the it is very simple Syntex index elfy.

11
00:00:50,150 --> 00:00:55,250
So we will take the help of Eddie and this ad is actually called budgetary.

12
00:00:57,740 --> 00:00:59,890
The name of that is actually called Bucket Eddie.

13
00:01:01,380 --> 00:01:07,560
But I want to do so first approach is very simple, I will convert the key into integer somehow.

14
00:01:09,120 --> 00:01:13,950
So this guy can be anything, so in Hashmat, keys and values can be anything, so he can be integer.

15
00:01:15,160 --> 00:01:24,490
This can be a string, this can be student, so can be anything, so somehow I will convert the key

16
00:01:24,490 --> 00:01:25,440
into an integer.

17
00:01:26,410 --> 00:01:28,900
So what we will do, we will paskey is input.

18
00:01:30,710 --> 00:01:32,420
We have some hash function.

19
00:01:34,440 --> 00:01:41,820
And this hash function will return CNN, Pejar, and what will happen to the Intisar that it will return?

20
00:01:42,090 --> 00:01:43,650
I will go to that BIJA.

21
00:01:45,910 --> 00:01:52,480
And I will store the key here, and when I'm storing the key, I will also store the value, so I will

22
00:01:52,480 --> 00:01:53,600
store the key value here.

23
00:01:54,880 --> 00:01:59,500
For example, let's say the individual came out to be three.

24
00:02:00,820 --> 00:02:06,590
So what I will do, I will go to the next three, so zero one, two, three, so I will go to the next

25
00:02:06,590 --> 00:02:09,120
three and I will store this key here.

26
00:02:09,610 --> 00:02:11,840
And simultaneously, we will also store the value.

27
00:02:11,860 --> 00:02:13,120
So we will store two things.

28
00:02:13,930 --> 00:02:15,070
So this is basically.

29
00:02:16,130 --> 00:02:22,010
We are doing it in Question Time, so this has its function, it will take question time and we will

30
00:02:22,010 --> 00:02:22,790
be able to find out.

31
00:02:22,790 --> 00:02:28,430
Then we will go to that integer and we will start two things inside this budget that again will you

32
00:02:29,240 --> 00:02:33,230
know, how can we access we have to excess in question time.

33
00:02:33,620 --> 00:02:37,220
So for accessing the key, what we will do, we will pass the key.

34
00:02:39,550 --> 00:02:46,150
Through the same hash function, so obviously the hash function will not change, and since that input

35
00:02:46,150 --> 00:02:47,860
the same, the function is same.

36
00:02:47,980 --> 00:02:49,580
So the output will also be the same.

37
00:02:49,930 --> 00:02:53,080
So for the same key, the output will be three.

38
00:02:54,470 --> 00:03:00,230
So what we will do this is at the time of excess, so you will give the key which you want to access,

39
00:03:00,230 --> 00:03:03,410
it will go through the hash function, the output will again be same.

40
00:03:04,100 --> 00:03:07,220
Then you will go to index three and you can see.

41
00:03:07,490 --> 00:03:10,760
So this is the key that this present and this is the value that is present.

42
00:03:11,030 --> 00:03:13,490
So again, this is also constraint time.

43
00:03:14,700 --> 00:03:15,830
Everything is very clear.

44
00:03:15,860 --> 00:03:21,560
Now let us discuss what is a hash function, how it will convert a key to an integer.

45
00:03:22,370 --> 00:03:26,980
So this is the basic logic of so this is the mean idea.

46
00:03:26,990 --> 00:03:30,470
This is the main idea of working of hash map.

47
00:03:31,800 --> 00:03:37,980
You will give the key to a hash function, hash function will give you the integer and this integer

48
00:03:37,980 --> 00:03:39,460
will act as index.

49
00:03:39,960 --> 00:03:44,750
You will go to that index and you want to develop it and for the time of accessing.

50
00:03:44,760 --> 00:03:46,740
So this is at the time of storing.

51
00:03:47,970 --> 00:03:53,100
At the time of accessing, you will again give the same key, it will pass through the same hash function

52
00:03:53,490 --> 00:03:55,450
again, you will get the index.

53
00:03:55,890 --> 00:04:00,510
So this is index, you will go to that index and you can access the key value pair.

54
00:04:01,810 --> 00:04:05,410
So this is the main idea, this is the basic idea of working off hash stable.

55
00:04:06,710 --> 00:04:10,940
So now let us study the hash function, what is a hash function?

56
00:04:11,420 --> 00:04:14,150
So basically hash function comprises of two things.

57
00:04:17,079 --> 00:04:21,350
So our hash function, it comprises of two functions.

58
00:04:21,640 --> 00:04:23,380
So first one is hash called.

59
00:04:25,370 --> 00:04:28,220
And second one is basically compression function.

60
00:04:29,500 --> 00:04:37,270
Has golden compassion function, so basically, let us assume your key is a string.

61
00:04:38,890 --> 00:04:43,810
OK, so this string, it will go through the hash function.

62
00:04:44,140 --> 00:04:52,120
So, in short, I'm writing F hash function and let's say the integer is basically, let's say 20000

63
00:04:52,120 --> 00:04:53,300
593.

64
00:04:54,160 --> 00:04:58,450
So the question is, will you be able to store this string at this index?

65
00:04:59,740 --> 00:05:02,500
So the answer is it depends upon the size of the area.

66
00:05:02,740 --> 00:05:06,490
So if the size of the arrays today, you cannot store this string.

67
00:05:07,620 --> 00:05:15,900
OK, so what Haskell will do, Hedgecoe will return me any integer so it can return any integer, for

68
00:05:15,900 --> 00:05:22,080
example, thousand 593 and then what is the work of compression function?

69
00:05:22,290 --> 00:05:27,690
So compression function will convert this number two thousand five hundred ninety three from zero to

70
00:05:27,690 --> 00:05:32,400
twenty nine because the size of the size of the bucket is 30.

71
00:05:32,580 --> 00:05:34,830
So these are only the valid indexes.

72
00:05:37,010 --> 00:05:43,370
So I hope you understood the working of hash code and compression function, so high school will give

73
00:05:43,370 --> 00:05:44,330
me an integer.

74
00:05:45,270 --> 00:05:51,300
It can give an integer, but we have to make sure that that integer is basically a valid index.

75
00:05:51,330 --> 00:05:58,430
So this has to work as an index and we will convert this number 20000, 523 into a valid index.

76
00:05:58,800 --> 00:06:01,380
And this is the work of decompression function.

77
00:06:03,450 --> 00:06:10,770
So what can be a perfect comparison function, so perfect comparison function is basically percentage

78
00:06:11,280 --> 00:06:14,600
buckets, buckets means area size.

79
00:06:15,240 --> 00:06:22,170
So if the size of the ad is 30, so if you will do percentages 30, then obviously the output will be

80
00:06:22,170 --> 00:06:23,640
between zero to twenty nine.

81
00:06:27,380 --> 00:06:33,040
So the compression function, a perfect compression function, is basically percentage bucket size,

82
00:06:33,290 --> 00:06:38,280
so if you will do percentage today, you will get all the value indexes from zero to 29.

83
00:06:38,840 --> 00:06:40,370
So compression function is done.

84
00:06:41,210 --> 00:06:43,430
We know how compression function works.

85
00:06:43,850 --> 00:06:47,250
Now, the only thing left is basically Hirshfield.

86
00:06:47,810 --> 00:06:50,200
So how we can find out the Haskell.

87
00:06:51,370 --> 00:06:53,420
So now let's discuss the high school.

88
00:06:53,860 --> 00:06:55,450
So basically hash called.

89
00:06:56,740 --> 00:07:01,510
So actually, we can have many high schools, so there will be different different high school for different

90
00:07:01,510 --> 00:07:06,160
different type of kids, so suppose GI is an integer.

91
00:07:07,400 --> 00:07:12,080
Sapolsky is an integer, so what is the backing of high school, so high school?

92
00:07:13,100 --> 00:07:18,180
Erzsi has got it will take as input and it can give an integer as output.

93
00:07:18,900 --> 00:07:20,300
Now this one.

94
00:07:21,660 --> 00:07:29,850
When the keys are indigent, so let's say the value is 50 50, so what can we take so Hedgecoe can be

95
00:07:29,850 --> 00:07:30,870
identity function?

96
00:07:30,870 --> 00:07:38,010
So we will return 50 only, OK, we can take hash as identity function so it can return 50.

97
00:07:39,150 --> 00:07:44,970
Now, let's see if the keys a string if the keys are string.

98
00:07:45,270 --> 00:07:46,590
So let's take an example.

99
00:07:46,980 --> 00:07:48,210
So let's say ABC.

100
00:07:49,330 --> 00:07:55,240
Now I have to convert ABC, so this ABC will pass through the high school, I have to convert ABC into

101
00:07:55,240 --> 00:07:55,900
an integer.

102
00:07:56,950 --> 00:08:01,600
OK, so what can I do so I can hard code so I can return?

103
00:08:02,050 --> 00:08:09,940
When you give me anything, I will always return when you give me the if my high school student an integer,

104
00:08:09,940 --> 00:08:12,190
I am returning when you give me an input.

105
00:08:12,640 --> 00:08:14,350
So obviously this is very, very bad.

106
00:08:14,770 --> 00:08:19,990
What you're trying to say, given energy, I will push the key value pair, I will insert the key will

107
00:08:19,990 --> 00:08:21,160
appear at the next one.

108
00:08:21,640 --> 00:08:23,790
And obviously this is like very, very bad.

109
00:08:25,390 --> 00:08:31,360
So what Haskell, can we use so we can use Hoshko like some of ASCII values?

110
00:08:33,220 --> 00:08:36,190
So if you will use high school like this, some of our school values.

111
00:08:37,190 --> 00:08:43,940
And if you will pass string ABC, so what will be our integer so your data will be the asset value of

112
00:08:43,950 --> 00:08:45,330
a 97.

113
00:08:45,890 --> 00:08:50,780
Similarly, that's a value of B and similarly the value of C, so you can add all this.

114
00:08:52,950 --> 00:08:59,340
And this will be your engager, then this individual will pass through a compression function, which

115
00:08:59,340 --> 00:09:04,380
we already know, which is percentage of size of the area, and this will work as index.

116
00:09:06,890 --> 00:09:08,450
OK, so this thing is very short.

117
00:09:08,480 --> 00:09:12,810
We do not have to worry about this, we only have to worry about the high school of our tax code.

118
00:09:12,830 --> 00:09:18,440
We should use so if you will use this high school to some of our school values, then the problem is

119
00:09:18,440 --> 00:09:20,120
basically EBC.

120
00:09:21,170 --> 00:09:30,760
Ciba, BSI, the high score for all the permutations of ABC, they will have the same hash code because

121
00:09:30,760 --> 00:09:34,830
if you will add these three numbers, you add these numbers in any manner.

122
00:09:35,020 --> 00:09:40,510
So every permutation of ABC will have the same high called will have the same integer.

123
00:09:42,240 --> 00:09:43,780
OK, they will have the same high school.

124
00:09:43,800 --> 00:09:46,260
So this is the problem with this high school.

125
00:09:47,710 --> 00:09:55,030
OK, so what we can do now, so the third type of Hedgecoe that we can use is basically we can use like

126
00:09:55,180 --> 00:10:02,560
you give me a listing, for example, ABCDE beef and my hash court will be I will some I will take the

127
00:10:02,560 --> 00:10:04,870
sum of only the first three characters.

128
00:10:06,150 --> 00:10:12,750
I will take the sum of only the first three characters, so basically it will be ASCII value of the

129
00:10:12,750 --> 00:10:16,740
ASCII value of it and ask a value of F, so this will return in BIJA.

130
00:10:17,970 --> 00:10:25,740
Now, in this case, it will take the permutations, so let's say DCB, AEF, so we will take the permutation.

131
00:10:25,740 --> 00:10:28,070
The characters are different first, the characters are different.

132
00:10:28,500 --> 00:10:31,280
So that's why we will get a different household.

133
00:10:32,310 --> 00:10:40,200
But this high school is also not very good, white is not very good because because the range is not

134
00:10:40,200 --> 00:10:40,590
huge.

135
00:10:42,590 --> 00:10:47,750
The range is not huge if you are taking only the first three characters into consideration, how many

136
00:10:47,750 --> 00:10:49,240
different characters can be?

137
00:10:49,250 --> 00:10:54,920
So we have only 26 letters during the six alphabets, so we will not get a very huge range.

138
00:10:55,530 --> 00:10:57,740
And what is the property of a good high school?

139
00:10:58,760 --> 00:11:03,470
So the property of a good high school is basically it should give me a good distribution.

140
00:11:04,870 --> 00:11:11,290
So basically, you should give me a huge range of integers, so good high school will give us a huge

141
00:11:11,290 --> 00:11:15,290
range of integers and this is not giving us a huge range of integer.

142
00:11:15,550 --> 00:11:16,300
So this is.

143
00:11:17,600 --> 00:11:20,680
This will work, but this is not good, we can do much better.

144
00:11:21,920 --> 00:11:26,990
So now let's discuss the code, which we use in practice, which is very, very common and very, very

145
00:11:26,990 --> 00:11:27,460
popular.

146
00:11:28,610 --> 00:11:33,170
So that hash called seas, for example, you have a string ABCDE.

147
00:11:34,220 --> 00:11:40,850
So what we'll do, we will treat this ABCDE as it is a no, we will treat ABCDE as a no.

148
00:11:41,820 --> 00:11:42,960
With base.

149
00:11:44,520 --> 00:11:52,620
B, for example, you have an integer 123, so this has a very tough one, this has a rate of 10 and

150
00:11:52,620 --> 00:11:54,000
this has a rate of hundred.

151
00:11:54,420 --> 00:11:57,080
So basically, I can write like this.

152
00:11:57,090 --> 00:12:04,470
So one in 10 to the power to then to intrude into the Power-One and similarly three into 10 to the power.

153
00:12:04,540 --> 00:12:10,020
You similarly, what I will do, I will consider ABCDE as a number with BCB.

154
00:12:10,200 --> 00:12:12,060
So here we have a base of 10.

155
00:12:13,350 --> 00:12:19,020
Now, if you'll trade this number with the BSP, so what with the hash, so I can write basically like.

156
00:12:20,720 --> 00:12:22,280
Value of a multiply.

157
00:12:23,540 --> 00:12:32,840
Due to the power three plus the assembly of B multiply to the power to ask C, multiply, B to the power

158
00:12:32,860 --> 00:12:33,080
one.

159
00:12:33,350 --> 00:12:37,520
Similarly as of the multiply B to the power zero, which is B only.

160
00:12:38,330 --> 00:12:39,990
So this will be my integer.

161
00:12:41,030 --> 00:12:42,860
So if I will use this hash called.

162
00:12:45,580 --> 00:12:52,330
Then I will get huge range of integers, I will get huge range of integers, because even if you will

163
00:12:52,330 --> 00:12:53,560
change one digit.

164
00:12:53,610 --> 00:12:57,500
So, for example, if you will do a BTC, then what will happen?

165
00:12:57,850 --> 00:13:00,790
So they will come here and C will come here.

166
00:13:01,060 --> 00:13:03,300
So you will get a very different integer.

167
00:13:03,910 --> 00:13:10,260
So using this hash called, we will get huge range of integers and that is preferable.

168
00:13:10,690 --> 00:13:17,140
So that's why this is very, very popular and this is used in practice, so very popular and this is

169
00:13:17,140 --> 00:13:18,540
very much used in practice.

170
00:13:19,330 --> 00:13:28,930
So actually this bee will take B so this one VSP So bees generally taken as a prime number, for example,

171
00:13:28,930 --> 00:13:31,150
29, 31, 37.

172
00:13:31,870 --> 00:13:38,230
So it is proved that on the basis of research it has been proved that if you will take the prime number,

173
00:13:38,230 --> 00:13:40,240
then you will get a good distribution.

174
00:13:42,410 --> 00:13:47,040
If the prime number, then you will get good distribution on the basis of research.

175
00:13:47,630 --> 00:13:50,960
Now, we have discussed if the case in Peter.

176
00:13:52,490 --> 00:13:54,050
You can use identity function.

177
00:13:56,630 --> 00:14:01,730
If the case is a string, then we can use this one number with BSP.

178
00:14:03,380 --> 00:14:10,790
To get huge range of intelligence and B, will be a prime number now, what if your key is a student?

179
00:14:11,930 --> 00:14:15,260
So what if your guy is actually a student?

180
00:14:16,440 --> 00:14:24,670
So you want to use a student as your key so there's no predefined method you can use.

181
00:14:24,900 --> 00:14:27,470
Basically, you have to construct your own high school.

182
00:14:27,750 --> 00:14:34,980
So what you have to do if you want to use a student as your key, then you have to make it on your own

183
00:14:35,610 --> 00:14:39,690
because no one knows what will be the goal of any student.

184
00:14:40,470 --> 00:14:40,860
OK?

185
00:14:40,890 --> 00:14:43,680
No one knows what really has called for a student.

186
00:14:43,690 --> 00:14:46,710
So you have to make your own high school, for example.

187
00:14:46,730 --> 00:14:47,390
What can do?

188
00:14:48,510 --> 00:14:53,490
You pass a student to the high school and you can take the high score, for example, Elbrus.

189
00:14:55,600 --> 00:15:03,610
Now, we know address is actually hexadecimal and you can convert hexadecimal into an integer, OK,

190
00:15:03,620 --> 00:15:09,250
and then that integer will be passed through the completion function and that will give me the index

191
00:15:09,250 --> 00:15:09,960
of the booklet.

192
00:15:10,840 --> 00:15:12,730
OK, so this is one such example.

193
00:15:13,120 --> 00:15:18,370
You can use address as a hash code and then you will convert.

194
00:15:18,370 --> 00:15:25,600
The hexadecimal to address are actually in hexadecimal hexadecimal format and you can convert the hexadecimal

195
00:15:25,600 --> 00:15:30,130
into an integer and then the completion function, then you will get the index.

196
00:15:31,660 --> 00:15:33,400
So what is the mean idea?

197
00:15:34,930 --> 00:15:39,730
So finally, the main idea is you will be provided with the key.

198
00:15:40,100 --> 00:15:41,670
Do you want to start developing?

199
00:15:42,130 --> 00:15:44,500
This will pass through a hash function.

200
00:15:45,610 --> 00:15:49,690
That hash function will comprise of two things hash code and completion function.

201
00:15:50,620 --> 00:15:55,720
So finally, you will get a valid index in the range of the array within the range of the array.

202
00:15:56,500 --> 00:15:58,640
So this index is actually integer.

203
00:15:59,470 --> 00:16:01,120
Then you have a budgetary.

204
00:16:03,440 --> 00:16:05,060
So you have this budgetary.

205
00:16:08,410 --> 00:16:15,130
So after finding out the index, you will go to that index and you will store your key value pair.

206
00:16:17,420 --> 00:16:24,710
So this is the main logic, suppose the size of the budget area is let's say there are 20 cells, basically

207
00:16:24,710 --> 00:16:27,800
the size of the earth is 20, so 20 different cells will be there.

208
00:16:28,850 --> 00:16:35,840
Now, the problem is basically we can have infinite possibilities, strings, so we can have infinite

209
00:16:35,840 --> 00:16:36,290
strings.

210
00:16:37,250 --> 00:16:44,930
Now, the problem with infinite strings is basically so suppose you have a string ABC and the hash function

211
00:16:44,930 --> 00:16:45,890
of ABC is five.

212
00:16:46,220 --> 00:16:51,420
Similarly, you can have one more string def and the hash function of the can also be five.

213
00:16:52,220 --> 00:16:55,460
So basically there are two strings and they're hash function.

214
00:16:55,460 --> 00:16:57,300
Their index is coming out to be five.

215
00:16:58,130 --> 00:17:01,160
So how can you store two strings at one index?

216
00:17:02,850 --> 00:17:09,270
Let us take an example, so suppose the hash school of ABC, I'm talking about high school, so suppose

217
00:17:09,270 --> 00:17:15,030
you have written a very good high school and the hash code came out with one zero five for ABC and for

218
00:17:15,030 --> 00:17:19,550
the F, the hash is came out there that came out to be two zero five.

219
00:17:19,859 --> 00:17:21,750
So you have written a good hash code.

220
00:17:21,750 --> 00:17:28,170
We have a good hash called and it is giving us very different, very huge range of integers.

221
00:17:28,380 --> 00:17:34,440
But when you will apply the compression function to apply compression function Mordente apply a compression

222
00:17:34,440 --> 00:17:34,830
function.

223
00:17:34,830 --> 00:17:40,120
Mordente So the index is coming out wi fi if the index is coming out to be five.

224
00:17:40,740 --> 00:17:46,050
So the problem here is basically we have two guys who want to go to the same index.

225
00:17:46,680 --> 00:17:53,520
I'm repeating myself, I have to quiz ABC and B and they both want to go to the same index.

226
00:17:53,910 --> 00:17:55,170
So this is the same index.

227
00:17:55,410 --> 00:17:58,640
So how can you start to give a loopier at the same index?

228
00:17:58,650 --> 00:18:00,630
So we call this thing as collision.

229
00:18:02,220 --> 00:18:07,950
So this is called collision and what we have to do, we have to do collision handling.

230
00:18:09,440 --> 00:18:11,330
Which of a study in our next video?

231
00:18:14,080 --> 00:18:16,270
I will see you in the next one by.