1
00:00:01,400 --> 00:00:02,120
Hi, everyone.

2
00:00:02,150 --> 00:00:05,630
So in today's lecture, we are going to study this topic, Hashmat.

3
00:00:06,770 --> 00:00:13,040
The name of Hashmat is basically stable, so there is very little difference between these two terms

4
00:00:13,040 --> 00:00:15,890
and these two terms are basically used interchangeably.

5
00:00:16,190 --> 00:00:18,920
So we will study we will also study the difference between these two.

6
00:00:19,910 --> 00:00:22,930
So first, let us discuss hash map.

7
00:00:23,780 --> 00:00:26,990
So hash map are basically very, very useful for us.

8
00:00:27,320 --> 00:00:32,180
Whenever you will be working on a website, wherever you will be doing web development, Android app

9
00:00:32,240 --> 00:00:32,720
development.

10
00:00:32,720 --> 00:00:35,180
So a hash map will be used at every place.

11
00:00:35,690 --> 00:00:39,200
Hash map is really, really very powerful and it is very, very useful.

12
00:00:39,470 --> 00:00:43,220
You will always use hash map in your day to day life and you will start calling.

13
00:00:44,170 --> 00:00:48,010
So first of all, let us discuss why do we need the need of the.

14
00:00:49,770 --> 00:00:57,300
So for understanding the need, let us first take the help of caution, so given a string, so you are

15
00:00:57,300 --> 00:01:02,700
provided with the string and what we have to do, you have to find out the highest auguring character

16
00:01:02,790 --> 00:01:03,500
in the string.

17
00:01:04,349 --> 00:01:09,270
So by the highest auguring character, what we have to do, we have to find the correct in the string,

18
00:01:09,270 --> 00:01:13,320
which has the maximum frequency, the character which is appearing maximum number of times.

19
00:01:14,500 --> 00:01:16,150
So how can resolve this question?

20
00:01:16,870 --> 00:01:19,960
So the first way of solving this question is basically brute force.

21
00:01:20,560 --> 00:01:21,410
So what do we do?

22
00:01:21,790 --> 00:01:24,950
Every character and find the kind of this character.

23
00:01:25,090 --> 00:01:27,980
Now, the second character, find the character of this character.

24
00:01:28,000 --> 00:01:33,690
So basically picking every character and finding the account of that character so that all the time,

25
00:01:33,700 --> 00:01:39,220
complexity, so time, complexity will be square, picking every character and then finding out its

26
00:01:39,220 --> 00:01:39,560
count.

27
00:01:39,580 --> 00:01:40,930
And finally, you will take.

28
00:01:42,310 --> 00:01:47,210
We will find out the maximum count and you will return the corresponding character simple.

29
00:01:48,100 --> 00:01:50,850
Now, some people can say we can use sorting.

30
00:01:51,220 --> 00:01:53,050
Yes, we can definitely use sorting.

31
00:01:54,430 --> 00:01:56,280
So what will happen if you will use sorting?

32
00:01:56,620 --> 00:02:01,870
So after sorting all the characters, all the same characters will come together, for example, all

33
00:02:01,870 --> 00:02:03,340
there is will come together.

34
00:02:03,490 --> 00:02:07,220
All the bees will come together, all the seeds will come together and so on.

35
00:02:07,570 --> 00:02:10,840
So basically, let's say this is my string, so it will happen.

36
00:02:11,380 --> 00:02:13,170
All that is will come together.

37
00:02:13,210 --> 00:02:15,190
I will find out how many pieces are together.

38
00:02:15,550 --> 00:02:17,500
Then all the bees will come together.

39
00:02:17,500 --> 00:02:19,360
I will find out how many bees are there.

40
00:02:20,020 --> 00:02:23,890
I will find out how many pieces are there and so on and what will do.

41
00:02:23,890 --> 00:02:28,120
We will take a variable maximum and we will try to find out.

42
00:02:28,690 --> 00:02:30,820
We will find out the maximum count.

43
00:02:31,780 --> 00:02:36,810
We will compare the count and we will find out the maximum count and then we will return the character

44
00:02:36,820 --> 00:02:39,620
corresponding to the maximum count, simple.

45
00:02:40,130 --> 00:02:42,190
Now, what do the time complexities?

46
00:02:42,210 --> 00:02:44,080
So first we will start the.

47
00:02:45,130 --> 00:02:46,630
So we will start this thing.

48
00:02:46,630 --> 00:02:53,080
So the time complexity will be in Logan and then for then for finding out the character.

49
00:02:53,080 --> 00:02:55,040
We will iterate over this string.

50
00:02:55,300 --> 00:02:58,850
So this will be an order of big, often so long and.

51
00:02:59,590 --> 00:03:01,240
So finally it will be in Logan.

52
00:03:03,690 --> 00:03:07,440
Now, I want to solve this question in one time, big golf or in.

53
00:03:08,340 --> 00:03:10,980
So how can we solve this question in big oftentime?

54
00:03:10,990 --> 00:03:14,640
So what we can do, we can take we can apply our heck.

55
00:03:15,150 --> 00:03:17,370
So let's discuss what we can apply.

56
00:03:19,140 --> 00:03:26,880
So how many characters are present, so there are total 256 characters, if you will see the keyboard,

57
00:03:27,460 --> 00:03:32,760
they are a total of 256 different characters that you have now.

58
00:03:32,790 --> 00:03:34,260
You will iterate over the string.

59
00:03:34,270 --> 00:03:35,610
So this is your string.

60
00:03:36,620 --> 00:03:42,020
What I will do, since there are 256 different character, I will make a character, I will make an.

61
00:03:43,340 --> 00:03:47,750
So I will construct Tonetti and the size of the array will be 256.

62
00:03:48,740 --> 00:03:54,230
The size of the area will be 256 and I will initialize this individual's.

63
00:03:55,540 --> 00:04:01,700
OK, I will construct a narrative and I will initialize the area with zeroes simple.

64
00:04:02,290 --> 00:04:09,340
Now, if you are creating all the if you encounter a character, so what is the asset value to ascribe

65
00:04:09,340 --> 00:04:09,630
values?

66
00:04:09,640 --> 00:04:10,660
Basically 97.

67
00:04:10,930 --> 00:04:14,140
So what you will do, you will go to the 97 index.

68
00:04:15,810 --> 00:04:18,779
You will go to the dentist index and you will put one here.

69
00:04:19,920 --> 00:04:21,810
Similarly, contract can be.

70
00:04:22,810 --> 00:04:25,040
It's about values and ideals.

71
00:04:25,120 --> 00:04:32,540
What he will do, you will go to 98 character 98 index and they will put one here and so on.

72
00:04:33,070 --> 00:04:35,110
So basically you are at your frequency.

73
00:04:35,320 --> 00:04:38,650
So this is our frequency at a lower frequency array will be ready.

74
00:04:39,550 --> 00:04:40,680
Let me take an example.

75
00:04:40,680 --> 00:04:44,600
Also, consider the string eBay and let it be.

76
00:04:45,040 --> 00:04:46,060
So this is my string.

77
00:04:46,060 --> 00:04:46,730
So it will do.

78
00:04:46,750 --> 00:04:52,600
We will construct an array of size 256 because they are total 256 different characters.

79
00:04:53,470 --> 00:04:54,880
Now we will attach to the string.

80
00:04:54,880 --> 00:04:59,000
So e so what we do, we will go to 97 to index.

81
00:04:59,020 --> 00:05:03,800
I will put one B so I will go to ninety eight index.

82
00:05:04,210 --> 00:05:05,950
I will put one then again.

83
00:05:06,550 --> 00:05:09,820
So what I will do I will make it to again.

84
00:05:09,820 --> 00:05:11,520
B I will make it two.

85
00:05:11,620 --> 00:05:12,640
Then I have again.

86
00:05:12,730 --> 00:05:13,990
So I will make it three.

87
00:05:16,010 --> 00:05:17,240
So I will make it three.

88
00:05:17,260 --> 00:05:25,250
So finally at 9:00, the seventh location, you have three and the 90 year location, you have to then

89
00:05:25,250 --> 00:05:29,450
for finding out the maximum character, what you will you will iterate over this.

90
00:05:30,620 --> 00:05:37,400
256 to Cesari, you will see three is basically good then two, so I went to the index, what I will

91
00:05:37,400 --> 00:05:41,510
do, I restore the index, I will take a variable maximum.

92
00:05:41,510 --> 00:05:47,090
This maximum will contain what is the maximum number of trees, the maximum and I was told the corresponding

93
00:05:47,750 --> 00:05:48,470
the index.

94
00:05:48,470 --> 00:05:52,040
So I will told 97 and I know corresponding to 97 the correct.

95
00:05:52,760 --> 00:05:56,110
So that's how I will be able to find out the correctly.

96
00:05:56,450 --> 00:05:58,040
So what would be the time complexity.

97
00:05:58,610 --> 00:06:05,420
So first I have to iterate over this string to prepare this to have precise accessory.

98
00:06:05,840 --> 00:06:12,110
Then I will iterate over this frequency to have the successor and I will be able to find my answer.

99
00:06:12,380 --> 00:06:13,820
So first, trading on this.

100
00:06:13,820 --> 00:06:18,210
This is NP and then I am Armatrading on this, so and plus 256.

101
00:06:19,070 --> 00:06:21,130
So this is basically big often.

102
00:06:21,740 --> 00:06:24,770
So that's how I will be able to solve this question in big often.

103
00:06:25,840 --> 00:06:30,070
OK, so what, you buy gold, so my gold will look something like this.

104
00:06:31,230 --> 00:06:38,370
First of all, I will create an area of size 256, I will initialize the area with zeros, then what

105
00:06:38,370 --> 00:06:44,670
I will do so I will iterate all the string so I will use a loop to get rid of the string equals zero

106
00:06:44,670 --> 00:06:48,480
Ellerston string dot size and I placeless.

107
00:06:48,930 --> 00:06:56,880
Then what I will do so inside the loop I will write one simple statement of string of.

108
00:06:57,090 --> 00:06:58,650
So this is basically string.

109
00:06:58,900 --> 00:07:02,340
So aof sfi and I will do placeless.

110
00:07:03,420 --> 00:07:04,230
So what will happen.

111
00:07:04,260 --> 00:07:10,110
This string of it is containing characters and this will be converted into integers with the help of

112
00:07:10,110 --> 00:07:14,700
Disko value and this integer will work as basically index of the area.

113
00:07:15,510 --> 00:07:19,230
OK, so after this loop my frequency, I will be ready.

114
00:07:19,230 --> 00:07:26,490
Then what I have to do, I have to hydrate over this frequency starting from zero less than two C++.

115
00:07:26,730 --> 00:07:33,420
I will find out which index is basically having the maximum count and then I will return the character

116
00:07:33,420 --> 00:07:35,720
corresponding to that index sample.

117
00:07:36,510 --> 00:07:39,090
So our time complexity is basically outdraw and.

118
00:07:40,950 --> 00:07:45,510
This is our draft to discuss what we can say, Constantine.

119
00:07:47,150 --> 00:07:48,210
This is Question Time.

120
00:07:48,230 --> 00:07:51,200
So basically we are able to solve this question big often.

121
00:07:52,380 --> 00:07:57,810
Simple, why we are able to solve the situation, we are able to solve this question because there are

122
00:07:57,810 --> 00:08:03,390
fixed number of characters available to us, they are only two of the six different characters available

123
00:08:03,390 --> 00:08:09,150
to us so we can create a fix to society if the different number of characters, if the different number

124
00:08:09,150 --> 00:08:14,730
of characters available to us are basically infinite, then obviously I cannot create infinite sized

125
00:08:14,730 --> 00:08:18,240
Eddie, so I will not be able to use this approach.

126
00:08:19,140 --> 00:08:24,870
This approach I'm calling this approach as heck, we are able to use this approach because there are

127
00:08:24,870 --> 00:08:27,810
only two of the six different characters that tried this approach will work.

128
00:08:30,100 --> 00:08:35,200
Now, let us discuss the second question now, given a string.

129
00:08:36,850 --> 00:08:42,610
You will be provided with a string and what you have to do this time, you have to find out the highest

130
00:08:42,610 --> 00:08:43,429
orcharding word.

131
00:08:43,990 --> 00:08:45,790
I'm not talking about the character.

132
00:08:45,790 --> 00:08:47,620
I'm talking about the word.

133
00:08:48,700 --> 00:08:50,920
You have to find out the highest orcharding word.

134
00:08:53,040 --> 00:08:57,360
Now, there are basically infinite number of words available to us.

135
00:08:58,610 --> 00:09:03,980
I'm not talking about English language, but if you will combine any combination of characters will

136
00:09:04,010 --> 00:09:05,260
basically give me a word.

137
00:09:05,270 --> 00:09:06,700
For example, ABC's The World.

138
00:09:06,920 --> 00:09:10,670
So any combination of character will result in a wide formation.

139
00:09:11,270 --> 00:09:15,710
So basically, we have finite world because there are no limit on the length.

140
00:09:15,710 --> 00:09:17,790
Also, Lent can be anything.

141
00:09:17,810 --> 00:09:19,790
So basically we have infinite number of words.

142
00:09:20,030 --> 00:09:22,220
So that means above approach will not work.

143
00:09:22,310 --> 00:09:24,640
The above hack approach will not work.

144
00:09:24,650 --> 00:09:27,140
You cannot create an infinite sized any.

145
00:09:28,730 --> 00:09:31,060
So above approach is not going to work.

146
00:09:32,510 --> 00:09:40,550
So in these type of problems, I need a hash map and we will see how the hash map can help us.

147
00:09:41,800 --> 00:09:44,590
So basically in the above approach, what I'm doing.

148
00:09:45,880 --> 00:09:50,050
So I am writing something like this aof character A.

149
00:09:51,260 --> 00:09:53,130
And then something, something.

150
00:09:53,600 --> 00:10:02,210
So basically this is converted into sars-cov-2 97 and basically 97 is working as index for the 80,

151
00:10:02,940 --> 00:10:04,980
97 is working as an index for the area.

152
00:10:05,300 --> 00:10:09,650
What I want in this problem, I want I can store something like this.

153
00:10:09,660 --> 00:10:14,750
So aof ABC, ABC's The World, I can do something like this.

154
00:10:15,350 --> 00:10:18,740
I want this, but I can only do this.

155
00:10:20,580 --> 00:10:27,000
So why can do this, because it is very easy to convert a character into an integer and that integer

156
00:10:27,000 --> 00:10:33,760
can work as an index, but here ABC cannot be converted into an integer.

157
00:10:34,170 --> 00:10:36,430
So how can we solve this?

158
00:10:36,450 --> 00:10:40,620
How can we achieve this so we can achieve this with the help of Hashmat?

159
00:10:42,610 --> 00:10:47,350
So basically, what passes for Hashmat is very simple, it says.

160
00:10:48,410 --> 00:10:52,430
It is Akiva loopier, so Aoki is basically value.

161
00:10:54,020 --> 00:10:54,860
This is value.

162
00:10:56,050 --> 00:11:04,600
Now, first, let's talk about Eddie, so inadequate is a situation so you can create an array of integers

163
00:11:05,050 --> 00:11:10,600
so value can be integer, you can create an array of double so valuable variable, you can create an

164
00:11:10,600 --> 00:11:11,560
array of characters.

165
00:11:11,590 --> 00:11:13,030
So the value will be corrected.

166
00:11:13,600 --> 00:11:17,200
But in case of Eddie, that guy is always engaged.

167
00:11:17,860 --> 00:11:21,920
In case of Eddie, the Keys is always in danger and that can be done.

168
00:11:21,950 --> 00:11:23,440
We call it index.

169
00:11:24,750 --> 00:11:29,040
So this is a situation in case of error is always an integer.

170
00:11:30,160 --> 00:11:36,700
And Hashmat, what assurances have Schmitz's keys can be anything, it can be, it can be, it can be

171
00:11:36,700 --> 00:11:37,140
corrected.

172
00:11:37,150 --> 00:11:37,810
It can be strong.

173
00:11:37,840 --> 00:11:38,860
It can be anything.

174
00:11:40,160 --> 00:11:42,620
So basically, Hashmat Schmitz's.

175
00:11:45,860 --> 00:11:46,670
Hashmat Schmitz's.

176
00:11:48,080 --> 00:11:52,380
Your key can be anything and your value can be anything.

177
00:11:52,400 --> 00:11:53,990
So these two can be anything.

178
00:11:57,510 --> 00:12:00,150
It can be in the battlefield, anything.

179
00:12:01,230 --> 00:12:02,380
I am repeating myself.

180
00:12:02,400 --> 00:12:08,160
So what is the limitation with that is what is the problem with that is so the problem with that is,

181
00:12:08,160 --> 00:12:16,650
is basically this guy this guy is can only be in BIJA and well, you can be anything.

182
00:12:16,650 --> 00:12:19,230
It can be integer, flawed double.

183
00:12:19,870 --> 00:12:23,020
And so value can be anything, but gey will always be integer.

184
00:12:23,040 --> 00:12:25,370
So this is the limitation of error.

185
00:12:26,370 --> 00:12:30,750
This is the limitations of adding that GUI will only be integer.

186
00:12:32,310 --> 00:12:38,970
And what the map says, maps is your key can be anything, your key can be anything.

187
00:12:40,220 --> 00:12:45,500
So basically map, but will also map is basically it will it is a given loopier.

188
00:12:46,540 --> 00:12:53,870
So MAP is basically a given loopier, as the name suggests, it will map keys to value simple.

189
00:12:54,100 --> 00:12:58,630
So what we will do, we can write something like this with the help of map aof.

190
00:12:58,630 --> 00:13:00,310
ABC is one.

191
00:13:01,680 --> 00:13:05,370
We can write something like this with the help of Map, because this is a string.

192
00:13:06,400 --> 00:13:12,560
This is key, this is key and key is basically strength and maps is key can be anything.

193
00:13:12,770 --> 00:13:15,280
So with the help of MAP, we will be able to do this.

194
00:13:17,150 --> 00:13:23,930
Or you can also say this is not it is not necessary to use a square because you can also insert like

195
00:13:24,920 --> 00:13:28,380
you can use insert functions or insert into map.

196
00:13:28,940 --> 00:13:29,950
This is key.

197
00:13:30,380 --> 00:13:33,200
So the Keys, ABC and the values run.

198
00:13:33,890 --> 00:13:36,520
So insert the key loopier inside the map.

199
00:13:36,980 --> 00:13:38,660
So we are using insert function.

200
00:13:39,440 --> 00:13:41,400
OK, so I hope you understood the logic.

201
00:13:41,750 --> 00:13:51,080
So finally in a guy will only be integer and value can be anything, value can be anything in Hashmat

202
00:13:51,890 --> 00:13:53,040
G can be anything.

203
00:13:53,060 --> 00:13:55,520
It is not necessary to be an integer, it can be anything.

204
00:13:55,700 --> 00:13:57,360
And again, value can be anything.

205
00:13:57,740 --> 00:14:01,400
So basically hash map solve our problem.

206
00:14:02,720 --> 00:14:09,410
OK, so this was a limitation that will always be in danger for the day, but this guy can be anything,

207
00:14:09,590 --> 00:14:15,760
so you can definitely write like this aof ABC Abkhasia string is basically, let's say 25.

208
00:14:15,770 --> 00:14:17,580
You can do anything Ghinwa.

209
00:14:17,620 --> 00:14:18,350
You can be anything.

210
00:14:19,250 --> 00:14:22,170
Now let's see what other functions that we want in Hashmat.

211
00:14:23,050 --> 00:14:27,350
So functions that we want Hashmat should have.

212
00:14:28,340 --> 00:14:31,010
So first, it should have been function.

213
00:14:32,660 --> 00:14:37,760
Insert functions in the insert function, I will give the key and I will give the value.

214
00:14:38,900 --> 00:14:42,980
So this is a key value bill, so insert key and value.

215
00:14:43,820 --> 00:14:45,320
So insert function should be there.

216
00:14:46,580 --> 00:14:52,310
Now, the second function that I want, it should be get value, I will give you a key and you give

217
00:14:52,310 --> 00:14:53,660
me the corresponding value.

218
00:14:55,410 --> 00:15:01,110
So this is the second function, I will give you the key and tell me what is the value corresponding

219
00:15:01,110 --> 00:15:01,670
to that key?

220
00:15:03,060 --> 00:15:04,020
Now they're targeting.

221
00:15:05,060 --> 00:15:08,780
Why do we want we want there should be a function, the Liedtke.

222
00:15:09,860 --> 00:15:13,160
I will give you the key and you will delete that key.

223
00:15:13,970 --> 00:15:15,800
Now one thing, just like an.

224
00:15:17,060 --> 00:15:21,520
So in the indexes, basically what we call Leskie.

225
00:15:22,160 --> 00:15:24,080
So indexes are basically unique.

226
00:15:24,260 --> 00:15:27,210
All indexes, all guys are unique in Hashmat.

227
00:15:27,240 --> 00:15:29,150
Also, keys will be unique.

228
00:15:30,220 --> 00:15:31,530
So this will be unique.

229
00:15:31,580 --> 00:15:33,610
OK, so unique is.

230
00:15:34,790 --> 00:15:43,460
You cannot have like this, so if you had ABC is to and if you are doing a of ABC again entry, so what

231
00:15:43,460 --> 00:15:44,000
will happen?

232
00:15:44,480 --> 00:15:46,610
This cannot exist together.

233
00:15:47,090 --> 00:15:48,550
So this will be unique.

234
00:15:49,190 --> 00:15:50,480
This has to be unique.

235
00:15:51,360 --> 00:15:57,980
OK, so for example, if you use the insert function and you did something like this, if ABC is, let's

236
00:15:57,980 --> 00:16:05,690
say when you are inserting so you are inserting the value one corresponding to ABC and in the next line,

237
00:16:05,690 --> 00:16:12,790
if you will do something like this, aof ABC equals to insert the value to corresponding to the given.

238
00:16:13,220 --> 00:16:16,970
So what will happen to insert this line, to insert this given loopier.

239
00:16:17,720 --> 00:16:22,620
This value will be this given loopier will be removed, it will be removed.

240
00:16:23,060 --> 00:16:30,470
OK, so as soon as you write this line, as soon as you write this line, it will remove the old key

241
00:16:30,470 --> 00:16:31,070
value pair.

242
00:16:31,490 --> 00:16:36,020
OK, so key has to be unique, just like in adding the indexes are unique in.

243
00:16:36,500 --> 00:16:37,310
These are unique.

244
00:16:37,550 --> 00:16:38,090
Simple.

245
00:16:40,110 --> 00:16:42,560
Now, let's see, how can we implement map?

246
00:16:45,230 --> 00:16:51,890
So how can we implement Hashmat, so let us discuss the first way to implement Hashmat.

247
00:16:52,900 --> 00:16:56,080
So the first rule is basically we will take the help of legalist.

248
00:16:58,180 --> 00:17:00,220
So this is a very simple list.

249
00:17:01,360 --> 00:17:05,109
So these are notes of the long list and how long list can help us.

250
00:17:05,770 --> 00:17:11,109
So basically, if you'll remember in the long list, we used to store only one thing, basically the

251
00:17:11,109 --> 00:17:12,619
data and the next pointer.

252
00:17:12,940 --> 00:17:17,220
So instead of storing one thing, that is the data, what we will do, we will store two things.

253
00:17:17,230 --> 00:17:21,819
We will store key value pair, we will Stokey and we will store the corresponding value.

254
00:17:23,260 --> 00:17:25,250
We will talk in the corresponding value.

255
00:17:25,930 --> 00:17:29,920
So how can we insert discuss the insert function?

256
00:17:29,930 --> 00:17:31,300
You have to insert a key value pair.

257
00:17:31,330 --> 00:17:36,460
So what you can do, you can insert the key value at different simple.

258
00:17:37,180 --> 00:17:41,110
Now if you want to delete a given key, so delete.

259
00:17:42,210 --> 00:17:45,190
The given key, so how can it lead to a given so what do you have to do?

260
00:17:45,780 --> 00:17:47,400
You will, I dread over the long list.

261
00:17:48,680 --> 00:17:54,650
And then you will and then you will match the given key with the key present at the node, so if they

262
00:17:54,650 --> 00:17:56,710
are safe, that means you have to delete this one.

263
00:17:56,960 --> 00:17:58,250
So I will delete like this.

264
00:18:00,260 --> 00:18:03,600
OK, so we are able to delete what is our time complexity.

265
00:18:03,620 --> 00:18:08,790
So first you have to get rid of the list to find the node that we have to delete.

266
00:18:08,810 --> 00:18:12,320
And basically we will match the key, which we have to delete.

267
00:18:12,320 --> 00:18:12,650
So.

268
00:18:13,630 --> 00:18:21,310
Since we have to all the time, complexity will be big often now what you have to do, you have to search.

269
00:18:21,340 --> 00:18:27,190
Let's say you want to search, given key check whether the given key is basically present inside the

270
00:18:27,190 --> 00:18:27,820
map or not.

271
00:18:28,090 --> 00:18:34,480
So, again, you have to do you will trade over the long list and you will compare the lower key value

272
00:18:34,630 --> 00:18:37,750
with the given key value if they assume you are able to find it.

273
00:18:38,080 --> 00:18:41,680
So again, the time complexity in case of search is also big often.

274
00:18:43,160 --> 00:18:48,380
Now, what is the time, complexity of inside function, so I told you the insert function, what we

275
00:18:48,380 --> 00:18:50,320
can do, we can insert at different.

276
00:18:51,500 --> 00:18:56,030
So you might think that our time complexity is big often, but this is wrong time.

277
00:18:56,030 --> 00:18:57,740
Complexity is basically big off.

278
00:18:57,740 --> 00:19:04,190
And because first what you have to do, you will migrate over the long list and you will check whether

279
00:19:04,190 --> 00:19:08,490
the key exists or not, whether the key already exists in the linked list or not.

280
00:19:08,510 --> 00:19:11,960
Because I told you that Keith has to be unique.

281
00:19:13,090 --> 00:19:14,040
He has to be unique.

282
00:19:14,350 --> 00:19:19,330
So, for example, if the given key so I told you to insert a given key.

283
00:19:20,170 --> 00:19:25,540
So first you will check whether this given key is already present inside the linked list or not.

284
00:19:25,570 --> 00:19:29,920
So basically, you will have to iterate over the long list and then you will check.

285
00:19:29,920 --> 00:19:31,540
Yes, the given key is already present.

286
00:19:31,570 --> 00:19:36,600
So basically you will update its value, you will update its values or insert function will take two

287
00:19:36,610 --> 00:19:37,970
things key and the value.

288
00:19:38,440 --> 00:19:40,660
So basically you will insert the value.

289
00:19:42,050 --> 00:19:47,450
OK, so again, this insert function is also big, often because you have to add to the list to ensure

290
00:19:47,450 --> 00:19:48,650
that these are unique.

291
00:19:49,800 --> 00:19:55,770
If you will use list to implement hash map, then insert, delete and search, all three operations

292
00:19:55,770 --> 00:19:58,810
are big often and this is very, very bad.

293
00:19:59,370 --> 00:20:00,950
We definitely want something better.

294
00:20:00,960 --> 00:20:02,910
Big often is really, really bad.

295
00:20:04,050 --> 00:20:07,780
Now, let's see the second approach for implementing the Hashmat.

296
00:20:08,730 --> 00:20:16,230
Now, the second approach for implementing the hash map is basically balanced, a balanced binary search

297
00:20:16,230 --> 00:20:16,540
tree.

298
00:20:17,220 --> 00:20:24,210
So for balance, the height is basically always low often, and it's the total number of nodes.

299
00:20:24,600 --> 00:20:27,180
So first starters discuss inside function.

300
00:20:27,900 --> 00:20:32,000
So what is I think we know for inserting a node in about.

301
00:20:33,160 --> 00:20:40,060
The time complexity is basically proportional to the height and height is basically low often, so insert

302
00:20:40,060 --> 00:20:41,590
function will take longer time.

303
00:20:42,430 --> 00:20:46,290
OK, so the balance, there will be some ordering of keys.

304
00:20:46,900 --> 00:20:52,750
So how can we order keys, for example, you want to insert the strings so I can say about basically

305
00:20:52,750 --> 00:20:59,710
less than the we can use the ordering like lexicographical, we can compare the strings we can order

306
00:21:00,430 --> 00:21:02,530
with the help of like lexicographical ordering.

307
00:21:02,540 --> 00:21:06,410
So this character is basically less than this or a bit less than the.

308
00:21:06,730 --> 00:21:09,220
So somehow there will always be ordering exist.

309
00:21:09,220 --> 00:21:11,950
So ordering will always exist somehow.

310
00:21:12,280 --> 00:21:19,540
So we can use ordering and we will put the corresponding key value added scores at the right position.

311
00:21:20,020 --> 00:21:24,730
We can push the key value inside the body at its right position.

312
00:21:24,820 --> 00:21:28,270
So and we know inserting an ordinary BSD log of an.

313
00:21:30,200 --> 00:21:36,740
So deletion in balance again, so deletion is proportional to height and height is basically logoff.

314
00:21:36,750 --> 00:21:42,800
And similarly, if you want to search for a node so in best you can, searching is also proportional

315
00:21:42,800 --> 00:21:43,250
to height.

316
00:21:43,260 --> 00:21:47,300
So this is also lower than ideally will go left or ideally will go right.

317
00:21:48,560 --> 00:21:55,490
So if you lose the balance to bisdee for implementing the Hashmat insert, delete and search, all three

318
00:21:55,490 --> 00:21:57,370
operations are taking longer time.

319
00:21:58,070 --> 00:22:00,620
OK, so this is better than Linklaters implementation.

320
00:22:02,130 --> 00:22:09,270
So actually, this hash map, so this kind of balanced budget is already implemented in C++, so this

321
00:22:09,270 --> 00:22:09,950
is inbuilt.

322
00:22:10,650 --> 00:22:16,420
We already have this implemented in C++ and we will use we will definitely use it.

323
00:22:17,490 --> 00:22:18,890
Now, there is one more way.

324
00:22:19,660 --> 00:22:25,560
There is a third way and it is called with the help of hash tables, we can implement hash map.

325
00:22:26,600 --> 00:22:33,770
With the help of hash table, so in this case, the insert function, that function Birdwood function

326
00:22:33,770 --> 00:22:37,160
and the search function, all three operations are basically big offline.

327
00:22:37,190 --> 00:22:42,410
Yes, kynaston time we can insert in question time we can believe in constant time.

328
00:22:42,410 --> 00:22:45,590
Began searching Question Time with the help of hash tables.

329
00:22:47,260 --> 00:22:48,040
So we will see.

330
00:22:49,620 --> 00:22:56,610
We will study it thoroughly, but now first let us discuss in the next video, how can we use this inbuilt

331
00:22:56,610 --> 00:22:57,140
hash map?

332
00:22:57,870 --> 00:23:03,590
So in the next video, we will see the world map and we will definitely discuss the hash table.

333
00:23:03,600 --> 00:23:08,100
But later in the lessons, I will meet you in the next one by.