1

00:00:01,490 --> 00:00:02,150

Hi everyone.



2

00:00:02,150 --> 00:00:09,020

So in today's lecture we are going to study this topic hash map the name of hash map is basically hash



3

00:00:09,020 --> 00:00:09,880

table.



4

00:00:10,250 --> 00:00:16,170

So there is very little difference between these two terms and these two terms are basically used interchangeably.



5

00:00:16,220 --> 00:00:17,140

So we will study.



6

00:00:17,150 --> 00:00:19,900

We will also study the difference between these two them.



7

00:00:19,970 --> 00:00:28,340

So first let us discuss hash map so hash map are basically very very useful for us whenever you will



8

00:00:28,340 --> 00:00:32,740

be working on our website whenever you will be doing web development Android app development.



9

00:00:32,750 --> 00:00:38,720

So a hash map will be used at every place hash map is really really very powerful and it is very very



10

00:00:38,720 --> 00:00:39,530

useful.



11

00:00:39,530 --> 00:00:44,010

You will always use hash map in your day to day life and you will start coding.



12

00:00:44,230 --> 00:00:47,040

So first of all let us discuss why do we need a hash map.



13

00:00:47,050 --> 00:00:51,240

What is the need of the map so for understanding the need.



14

00:00:51,240 --> 00:00:54,590

Let us first take the help of equation.



15

00:00:54,600 --> 00:01:01,350

So given a string so you are provided with the string and what you have to do you have to find out the



16

00:01:01,380 --> 00:01:03,600

highest auctioning connected industries.



17

00:01:04,410 --> 00:01:09,240

So by these high used all getting connected what we have to do we have to find the connecting the string



18

00:01:09,270 --> 00:01:15,280

which has the maximum frequency the connector which is appearing maximum number of times so how can



19

00:01:15,280 --> 00:01:16,900

we solve this question.



20

00:01:16,930 --> 00:01:20,590

So the first way of solving this question is basically brute force.



21

00:01:20,590 --> 00:01:25,180

So what do a little bit every character and find the current of this character.



22

00:01:25,180 --> 00:01:27,990

Now pick the second character find the current of this character.



23

00:01:28,000 --> 00:01:32,830

So basically picking every character and finding the count of that character.



24

00:01:32,830 --> 00:01:34,700

So what do the time complexity.



25

00:01:34,750 --> 00:01:39,630

So time complexity will be inscribed picking every character and then finding out its count.



26

00:01:39,640 --> 00:01:46,690

And finally you will take it will find out the maximum count and you will return the corresponding character.



27

00:01:46,780 --> 00:01:48,150

Simple.



28

00:01:48,160 --> 00:01:54,330

Now some people can say we can use starting yes we can definitely use sorting.



29

00:01:54,460 --> 00:01:56,680

So what will happen if you will use sorting.



30

00:01:56,680 --> 00:02:02,020

So after sorting all the characters all the same characters will come together for example all that



31

00:02:02,050 --> 00:02:07,610

is will come together all the B's will come together all the seats will come together and so on.



32

00:02:07,630 --> 00:02:10,090

So basically let's say this is my string.



33

00:02:10,090 --> 00:02:13,270

So what will happen all the A's will come together.



34

00:02:13,270 --> 00:02:17,500

I will find out how many e's are together then all the B's will come together.



35

00:02:17,500 --> 00:02:19,490

I will find out how many B's are there.



36

00:02:20,110 --> 00:02:26,830

I will find out how many C's out there and so on and what will do we will take a variable maximum and



37

00:02:26,920 --> 00:02:31,780

we will try to find out we will find out the maximum count.



38

00:02:31,870 --> 00:02:36,790

We will compare the count and we will find out the maximum count and then we will return the corrected



39

00:02:36,850 --> 00:02:39,160

corresponding to the maximum count.



40

00:02:39,160 --> 00:02:40,150

Simple.



41

00:02:40,150 --> 00:02:42,290

Now what do the time complexity.



42

00:02:42,290 --> 00:02:43,940

So first we will start.



43

00:02:43,940 --> 00:02:48,430

DNA So we will start the string so that time complexity will be in Logan.



44

00:02:48,760 --> 00:02:55,360

And then for men then for finding out the character we will irate or this string.



45

00:02:55,360 --> 00:02:57,360

So this will be an order often.



46

00:02:57,460 --> 00:02:59,680

Often so and log and lesson.



47

00:02:59,680 --> 00:03:03,690

So finally it will be n Logan.



48

00:03:03,760 --> 00:03:08,130

No I want to solve this question in or in time b golf or in time.



49

00:03:08,400 --> 00:03:10,980

So how can we solve this question and B girlfriend time.



50

00:03:10,980 --> 00:03:11,950

So what we can do.



51

00:03:11,970 --> 00:03:15,110

We can take we can apply our Hec.



52

00:03:15,210 --> 00:03:19,140

So let us discuss what tank we can apply.



53

00:03:19,200 --> 00:03:22,980

So how many characters are present.



54

00:03:23,040 --> 00:03:27,270

So there are total 256 characters if you will see the keyboard.



55

00:03:27,600 --> 00:03:34,290

There are total of 256 different organic best yet you have now you will irate over the string.



56

00:03:34,290 --> 00:03:37,610

So this is you a string whatever looses.



57

00:03:37,640 --> 00:03:39,590

There are two of the six different character.



58

00:03:39,590 --> 00:03:41,210

I will make a character.



59

00:03:41,360 --> 00:03:49,460

I will make an Eddie so I will construct entity and the size of the array will be 256 the size of the



60

00:03:49,460 --> 00:03:57,970

area will be 256 and I will initialize this it with zeros Okay I will construct an area of 256 and I



61

00:03:57,970 --> 00:04:01,050

will initialize the array with zeros.



62

00:04:01,210 --> 00:04:01,720

Simple.



63

00:04:02,350 --> 00:04:05,470

Now if you are trading all the string.



64

00:04:05,500 --> 00:04:07,240

If you encounter a correctly.



65

00:04:07,390 --> 00:04:08,680

So what is that ask value.



66

00:04:08,750 --> 00:04:10,970

S ask I may lose basically 97.



67

00:04:10,990 --> 00:04:18,510

So what you will do you will go to the 97 to index you will go to the 97 index and you will put one



68

00:04:18,510 --> 00:04:23,240

here similarly fair and counter but be.



69

00:04:23,510 --> 00:04:24,970

I ask I will lose nine here.



70

00:04:24,970 --> 00:04:32,350

So what you will do you will go to ninety eight corrected 98 index and you will put one head and so



71

00:04:32,350 --> 00:04:33,070

on.



72

00:04:33,100 --> 00:04:35,310

So basically you are Eddy your frequency array.



73

00:04:35,320 --> 00:04:39,580

So this is our frequency array sound frequency array will be ready.



74

00:04:39,580 --> 00:04:40,780

Let me take an example.



75

00:04:40,780 --> 00:04:45,090

So consider the string A B and let it be.



76

00:04:45,100 --> 00:04:46,750

So this is my string so it will do.



77

00:04:46,770 --> 00:04:53,530

We will construct an array of size 256 because there are total 256 different connectors.



78

00:04:53,530 --> 00:04:56,020

Now we will add data with the string so e.



79

00:04:56,320 --> 00:04:57,060

So what do we look.



80

00:04:57,070 --> 00:04:59,080

We will go to 97 to index.



81

00:04:59,080 --> 00:05:00,890

I will put one B.



82

00:05:01,000 --> 00:05:04,220

So I will go to ninety eight to index.



83

00:05:04,300 --> 00:05:06,550

I will put one then again.



84

00:05:06,580 --> 00:05:12,730

So what I will do I will make it two again B I will make it two then I have again.



85

00:05:12,760 --> 00:05:17,240

So I will make it three so I will make it three.



86

00:05:17,270 --> 00:05:25,250

So finally at ninety seventh location you have three and the ninety eighth location you have to then



87

00:05:25,250 --> 00:05:27,780

for finding out the maximum character what do we look.



88

00:05:27,800 --> 00:05:32,150

You will read all of this 256 to size.



89

00:05:32,330 --> 00:05:34,730

You will see three is basically good then two.



90

00:05:34,790 --> 00:05:36,710

So I restored the index.



91

00:05:36,980 --> 00:05:43,640

What I will do I was told the index I will take a variable maximum this maximum will contain what is



92

00:05:43,640 --> 00:05:49,070

the maximum number so to use the maximum but an average stored the corresponding the index so that I



93

00:05:49,070 --> 00:05:52,670

will store 97 and I know corresponding to 97 the correct posy.



94

00:05:52,820 --> 00:05:56,420

So that's how I will be able to find out correctly.



95

00:05:56,510 --> 00:05:58,640

So what will be the time complexity.



96

00:05:58,670 --> 00:06:05,830

So first I have two I tripped over this string to prepare this to have precise two basic size ready.



97

00:06:05,870 --> 00:06:06,640

Then I will.



98

00:06:06,690 --> 00:06:12,350

I or this frequency two of the six I's that end I will be able to find my answer.



99

00:06:12,440 --> 00:06:13,820

So first I are trading on this.



100

00:06:13,820 --> 00:06:15,020

This is an.



101

00:06:15,190 --> 00:06:16,600

And then I am trading on this.



102

00:06:16,610 --> 00:06:19,050

So and plus 256.



103

00:06:19,160 --> 00:06:21,140

So this is basically big often.



104

00:06:21,800 --> 00:06:25,740

So that's how I will be able to solve this quotient in big often.



105

00:06:25,960 --> 00:06:27,860

Okay so overtly by accord.



106

00:06:28,120 --> 00:06:31,120

So my code will look something like this.



107

00:06:31,260 --> 00:06:34,680

First of all I will create an area of size 256.



108

00:06:34,830 --> 00:06:38,010

I will initialize the edit with zeroes.



109

00:06:38,010 --> 00:06:39,960

Then what I will do so I will.



110

00:06:40,050 --> 00:06:41,150

Trade or the string.



111

00:06:41,160 --> 00:06:47,880

So I will use a loop to white rate or this thing I equals zero i.e. less than string dot size and I



112

00:06:47,880 --> 00:06:50,120

plus plus then what I will do.



113

00:06:50,310 --> 00:06:57,090

So inside the loop I will write one simple statement of string off.



114

00:06:57,120 --> 00:07:02,370

So this is basically String s so eof SFI and I will loop plus plus.



115

00:07:03,510 --> 00:07:04,260

So what will happen.



116

00:07:04,260 --> 00:07:09,990

This a string of I it is containing characters and this will be converted into in pages with the help



117

00:07:09,990 --> 00:07:11,020

of dice game value.



118

00:07:11,130 --> 00:07:15,500

And this integer will work as basically index of the 80.



119

00:07:15,600 --> 00:07:19,230

Okay so after this loop my frequency I will be ready.



120

00:07:19,260 --> 00:07:24,930

Then what I have to do I have to iterate over this frequency array starting from zero.



121

00:07:24,930 --> 00:07:31,650

Let them do six eight plus plus I will find out which index is basically having the maximum count and



122

00:07:31,650 --> 00:07:35,190

then I will return the connector corresponding to that index.



123

00:07:35,190 --> 00:07:35,730

Simple.



124

00:07:36,570 --> 00:07:43,790

So our time complexity is basically our of and this is our draft 256.



125

00:07:43,860 --> 00:07:48,230

Or we can see constant pain this is question time.



126

00:07:48,230 --> 00:07:55,120

So basically we are able to solve this caution and bingo often simple via variable to solve this question



127

00:07:55,780 --> 00:08:00,620

variable to solve this question because there are fixed number of correct best available to us.



128

00:08:00,730 --> 00:08:07,090

There are only 256 different characters available to us so we can create a fix to size any if the different



129

00:08:07,090 --> 00:08:11,820

number of correctness of the different number of correct that's available to us are basically infinite.



130

00:08:11,980 --> 00:08:19,440

Then obviously I cannot create in finite sized Eddie so I will not be able to use this approach this



131

00:08:19,440 --> 00:08:20,150

approach.



132

00:08:20,240 --> 00:08:25,350

I am calling this approach as heck we are able to use this approach because because there are only two



133

00:08:25,350 --> 00:08:26,490

of the six different characters.



134

00:08:26,490 --> 00:08:30,010

That's why this approach will work.



135

00:08:30,160 --> 00:08:34,030

No let us discuss the second question.



136

00:08:34,180 --> 00:08:41,020

No given a string you will be provided with a string and what do you have to do this time you have to



137

00:08:41,020 --> 00:08:44,100

find out the highest all word.



138

00:08:44,090 --> 00:08:48,550

I am not talking about the character I am talking about the word.



139

00:08:48,790 --> 00:08:53,840

You have to find out the highest all getting word now.



140

00:08:53,980 --> 00:08:58,540

There are basically in finite number of words available to us.



141

00:08:58,590 --> 00:09:04,520

I am not talking about English language but if you will combine any combination of characters will basically



142

00:09:04,580 --> 00:09:05,250

give me a word.



143

00:09:05,270 --> 00:09:11,270

For example ABC is a word so any combination of character will result in to avoid information.



144

00:09:11,300 --> 00:09:15,750

So basically we have in finite words because there are no limit on the length.



145

00:09:15,750 --> 00:09:17,780

Also land can be anything.



146

00:09:17,810 --> 00:09:19,980

So basically we have infinite number of words.



147

00:09:20,090 --> 00:09:22,850

So that means above approach will not work in the above.



148

00:09:22,850 --> 00:09:24,610

Heck approach will not work.



149

00:09:24,650 --> 00:09:33,930

You cannot create an infinite sized Eddy so above approach is not going to work so in these type of



150

00:09:33,930 --> 00:09:34,650

problems.



151

00:09:34,650 --> 00:09:41,840

I need a hash map and we will see how the hash map can help us.



152

00:09:41,860 --> 00:09:49,910

So basically in the above heck approach what I am doing so I am writing something like this off correctly



153

00:09:49,930 --> 00:09:53,660

a and then something something.



154

00:09:53,660 --> 00:10:02,930

So basically this is converted into a task I value 97 and basically 97 is working as index for the eddy.



155

00:10:02,990 --> 00:10:05,330

97 is working as an index for the array.



156

00:10:05,360 --> 00:10:09,660

What I want in this problem I want I can store something like this.



157

00:10:09,680 --> 00:10:10,650

So EOF.



158

00:10:10,700 --> 00:10:11,610

ABC.



159

00:10:11,660 --> 00:10:15,410

ABC is a word I can do something like this.



160

00:10:15,470 --> 00:10:18,840

I want this but edit can only do this.



161

00:10:20,640 --> 00:10:26,970

So why Eric can do this because it is very easy to convert a character into an integer and that integer



162

00:10:27,000 --> 00:10:29,700

can book as an index.



163

00:10:29,700 --> 00:10:34,160

But here ABC cannot be converted into I budget.



164

00:10:34,230 --> 00:10:36,420

So how can we solve this.



165

00:10:36,420 --> 00:10:42,660

How can we achieve this so we can achieve this with the help of a hash map.



166

00:10:42,670 --> 00:10:46,720

So basically what hash map sees the hash map is very simple.



167

00:10:46,720 --> 00:10:49,780

It says it is a key value here.



168

00:10:49,790 --> 00:10:53,940

So Aoki is basically value.



169

00:10:54,080 --> 00:10:59,380

This is value now First let us talk about Eddie.



170

00:10:59,410 --> 00:11:01,310

So in that is what is the situation.



171

00:11:01,480 --> 00:11:06,200

So you can create Eddie often do just so value can be in digit.



172

00:11:06,220 --> 00:11:08,110

You can create an Eddie of a double.



173

00:11:08,110 --> 00:11:09,550

So value will be double.



174

00:11:09,640 --> 00:11:11,590

You can create an Eddie of this.



175

00:11:11,620 --> 00:11:13,420

So the value will be connected.



176

00:11:13,660 --> 00:11:17,590

But in case of Eddie the keys are always in danger.



177

00:11:17,950 --> 00:11:19,680

In case of Eddie.



178

00:11:19,720 --> 00:11:21,060

The key is always in danger.



179

00:11:21,070 --> 00:11:21,940

And that can be done.



180

00:11:21,950 --> 00:11:24,710

We call it index.



181

00:11:24,810 --> 00:11:31,730

So this is a situation key in case of and it is always an integer and a hash map.



182

00:11:31,750 --> 00:11:33,610

What punishments is hash Pepsis.



183

00:11:33,610 --> 00:11:34,630

These can be anything.



184

00:11:34,690 --> 00:11:35,560

It can be beaten.



185

00:11:35,560 --> 00:11:36,310

It can be double.



186

00:11:36,310 --> 00:11:37,150

It can be corrected.



187

00:11:37,150 --> 00:11:37,840

It can be string.



188

00:11:37,840 --> 00:11:40,050

It can be anything.



189

00:11:40,190 --> 00:11:42,620

So basically hash maps is



190

00:11:45,920 --> 00:11:52,370

hash maps is your key can be anything and your value can be anything.



191

00:11:52,400 --> 00:11:57,500

So these two can be anything.



192

00:11:57,600 --> 00:11:59,510

It can be in beta double floored.



193

00:11:59,580 --> 00:12:01,170

Anything.



194

00:12:01,390 --> 00:12:06,890

I mean everything myself and so what is the limitation with that is what is the problem with that is.



195

00:12:06,930 --> 00:12:16,690

So the problem with that is is basically this key this key is can only be integer and value can be anything.



196

00:12:16,710 --> 00:12:23,010

It can be integer flawed double exact travel so value can be anything but key will always be in danger.



197

00:12:23,040 --> 00:12:25,750

So this is the limitation of error.



198

00:12:26,430 --> 00:12:34,400

This is the limitations of any that Key will only be integer and what the map says.



199

00:12:34,410 --> 00:12:40,270

Maps is your key can be anything your key can be anything.



200

00:12:40,280 --> 00:12:44,000

So basically in MAP what we lose so map is basically it will.



201

00:12:44,000 --> 00:12:52,120

It is a key value pair so map is basically a key value pair as the name suggests it will map keys to



202

00:12:52,120 --> 00:12:53,440

value.



203

00:12:53,440 --> 00:12:54,140

Simple.



204

00:12:54,160 --> 00:13:02,310

So what we will do we can write something like this with the help of Mark if ABC is one we can write



205

00:13:02,310 --> 00:13:07,630

something like this with the help of map because this is a string this is key.



206

00:13:07,630 --> 00:13:12,580

This is key and key is basically a string and maps is key can be anything.



207

00:13:12,850 --> 00:13:20,810

So with the help of map we will be able to do this or you can also say this is not it is not necessary



208

00:13:20,810 --> 00:13:28,970

to use a square because you can also insert like you can use insert functions so insert into map.



209

00:13:28,970 --> 00:13:29,990

This is key.



210

00:13:30,410 --> 00:13:36,890

So the keys ABC and the values 1 so insert the key value pair inside the map.



211

00:13:37,040 --> 00:13:39,500

So we are using insert function.



212

00:13:39,500 --> 00:13:39,750

Okay.



213

00:13:39,770 --> 00:13:41,810

So I hope you understood the logic.



214

00:13:41,810 --> 00:13:50,750

So finally in every game will only be integer and value can be anything value can be anything in a hash



215

00:13:50,750 --> 00:13:53,080

map key can be anything.



216

00:13:53,150 --> 00:13:54,690

It is not necessary to be an integer.



217

00:13:54,710 --> 00:13:55,670

It can be anything.



218

00:13:55,820 --> 00:13:57,800

And again value can be anything.



219

00:13:57,800 --> 00:14:03,070

So basically hash map solves our problem okay.



220

00:14:03,110 --> 00:14:08,990

So this was the limitation that key will always be in danger for the area but hash Pepsi's key can be



221

00:14:08,990 --> 00:14:09,530

anything.



222

00:14:09,650 --> 00:14:15,790

So you can definitely write like this a of ABC ABC the string is basically let's say 25.



223

00:14:15,830 --> 00:14:16,940

You can do anything.



224

00:14:17,120 --> 00:14:19,330

Can we look and see anything.



225

00:14:19,340 --> 00:14:20,040

Now let's see.



226

00:14:20,060 --> 00:14:28,200

But at the functions that we want in hash map so functions that we want hash map should have.



227

00:14:28,370 --> 00:14:29,400

So first.



228

00:14:29,420 --> 00:14:33,530

It should have insert function insert function.



229

00:14:33,530 --> 00:14:37,790

So in the insert function I will give the key and I will give the value.



230

00:14:38,960 --> 00:14:40,640

So this is the key value here.



231

00:14:40,670 --> 00:14:43,850

So Insert key and value.



232

00:14:43,880 --> 00:14:46,650

So insert function should be the.



233

00:14:46,670 --> 00:14:50,250

Now the second function that I want it should be get value.



234

00:14:50,270 --> 00:14:55,330

I will give you key and you give me the corresponding value.



235

00:14:55,440 --> 00:14:57,240

So this is the second function.



236

00:14:57,240 --> 00:15:05,280

I will give you the key and tell me what is the value corresponding to that key now that targeting my



237

00:15:05,280 --> 00:15:07,160

do we want we want.



238

00:15:07,190 --> 00:15:14,040

This should be a function delete key I will give you the key and you will delete that key.



239

00:15:14,060 --> 00:15:16,740

Now one thing just like an eddy.



240

00:15:17,090 --> 00:15:25,400

So in Eddy the index is basically what we call ASCII so indexes are basically unique all indexes all



241

00:15:25,400 --> 00:15:31,670

keys are unique in hash map also keys will be unique so keys will be unique.



242

00:15:31,670 --> 00:15:41,690

OK so a unique keys you cannot have like this so if your ABC is 2 and if you are doing a of ABC again



243

00:15:42,250 --> 00:15:43,110

a..



244

00:15:43,160 --> 00:15:44,350

So what will happen.



245

00:15:44,510 --> 00:15:46,930

This cannot exist together.



246

00:15:47,150 --> 00:15:51,360

So keys will be unique Keys has to be unique.



247

00:15:51,480 --> 00:15:58,100

Okay so for example if you use the insert function and you did something like this if ABC is let's say



248

00:15:58,100 --> 00:16:05,360

when you are inserting so you are inserting the value when corresponding to key ABC and in the next



249

00:16:05,360 --> 00:16:12,770

line if you will do something like this if ABC equals to insert the value to corresponding to the given



250

00:16:12,770 --> 00:16:13,220

key.



251

00:16:13,280 --> 00:16:17,530

So what will happen to insert this line to insert this key way loop here.



252

00:16:17,750 --> 00:16:23,050

This value will be this give a loop it will be removed it will be removed.



253

00:16:23,150 --> 00:16:23,450

Okay.



254

00:16:23,480 --> 00:16:30,560

So as soon as you write this line as soon as you write this line it will remove the all the key value



255

00:16:30,580 --> 00:16:31,070

beer.



256

00:16:31,550 --> 00:16:36,490

OK so key has to be unique just like in Eddy the index is not unique in a hash map.



257

00:16:36,510 --> 00:16:37,610

Keys are unique.



258

00:16:37,610 --> 00:16:39,800

Simple.



259

00:16:40,170 --> 00:16:45,090

Now let's say how can we implement hash map.



260

00:16:45,260 --> 00:16:53,760

So how can we implement hash map so let's discuss the first way to implement hash map so the first way



261

00:16:53,760 --> 00:16:56,080

is basically we will take the help off linked list.



262

00:16:58,240 --> 00:17:04,870

So this is a very simple linked list so these are nodes of dealing list and how linked list can help



263

00:17:04,870 --> 00:17:05,820

us.



264

00:17:05,830 --> 00:17:10,430

So basically if you remember in the linked list we used to store only one thing.



265

00:17:10,480 --> 00:17:12,610

Basically the data and the next pointer.



266

00:17:13,000 --> 00:17:17,240

So instead of storing one thing that is the data what do we look we will store two things.



267

00:17:17,260 --> 00:17:19,050

We will store key value here.



268

00:17:19,060 --> 00:17:24,940

We will stop key and we will store the corresponding value really restore key and the corresponding



269

00:17:24,940 --> 00:17:25,930

value.



270

00:17:25,990 --> 00:17:31,290

So how can we insert that does this the insert function you have to insert the key way loop here.



271

00:17:31,330 --> 00:17:37,230

So what you can do you can insert the key way loop here at different simple.



272

00:17:37,250 --> 00:17:44,670

Now if you want to delete a given key so delete the given key so how can it lead the given keys so what



273

00:17:44,670 --> 00:17:45,770

do you have to do.



274

00:17:45,840 --> 00:17:49,820

You will hydrate over the link list and then you will.



275

00:17:49,820 --> 00:17:54,030

And then you will match the given key with the key present at the node.



276

00:17:54,050 --> 00:17:55,040

So if they are the same.



277

00:17:55,040 --> 00:17:56,960

That means you have to delete this one.



278

00:17:57,020 --> 00:18:00,180

So I will delete like this.



279

00:18:00,410 --> 00:18:03,620

Okay so we are able to delete what is our time complexity.



280

00:18:03,620 --> 00:18:08,780

So first we have to iterate over the linked list to find the node that we have to delete.



281

00:18:08,870 --> 00:18:14,920

And basically we will match the key which gives you have to delete so since we have to either know the



282

00:18:14,920 --> 00:18:15,790

linked list.



283

00:18:16,060 --> 00:18:18,490

So time complexity will be big often.



284

00:18:18,680 --> 00:18:21,350

Now what you have to do is you have to search.



285

00:18:21,370 --> 00:18:27,430

Let's say you want to search given key check whether the given key is basically present inside the map



286

00:18:27,430 --> 00:18:27,790

or not.



287

00:18:28,120 --> 00:18:34,480

So again they have to do you will trade over the linked list and you will compare the node key value



288

00:18:34,690 --> 00:18:36,100

with the given key value.



289

00:18:36,100 --> 00:18:37,770

If they assume you are able to find it.



290

00:18:38,140 --> 00:18:44,480

So again that time complexity in case of search is also big off in now what is that time complexity



291

00:18:44,480 --> 00:18:45,910

of insert function.



292

00:18:45,950 --> 00:18:52,940

So I told you the insert function murder can do we can insert at different so you might think that our



293

00:18:52,940 --> 00:18:59,360

time complexity is big often but this is wrong time complexity is basically big off and because first



294

00:18:59,420 --> 00:19:05,510

what we have to do you will address it or the linked list and you will check whether the key exists



295

00:19:05,510 --> 00:19:11,330

or not whether the key already exists in the linked list or not because I told you that Keys has to



296

00:19:11,330 --> 00:19:14,340

be unique key has to be unique.



297

00:19:14,380 --> 00:19:21,640

So for example if the given key so I told you to insert a given key so first you will check whether



298

00:19:21,640 --> 00:19:25,540

this given key is already present inside the linked list or not.



299

00:19:25,570 --> 00:19:30,810

So basically you will have to iterate over the linked list and then you will check yes the given key



300

00:19:30,810 --> 00:19:31,540

is already present.



301

00:19:31,570 --> 00:19:33,860

So basically you will update its value.



302

00:19:34,180 --> 00:19:38,370

You will update its values or insert function will take two things key and devalue.



303

00:19:38,500 --> 00:19:42,580

So basically you will insert the value okay.



304

00:19:42,650 --> 00:19:47,450

So again this insert function is also be golfing because you have to identify the linked list to ensure



305

00:19:47,450 --> 00:19:54,690

that keys are unique if you will use linked list to implement hash map then insert delete and such.



306

00:19:54,840 --> 00:19:59,430

All three operations are big often and this is very very bad.



307

00:19:59,430 --> 00:20:04,040

We definitely want something better big orphan is really really bad.



308

00:20:04,140 --> 00:20:08,740

Now let's see the second approach for implementing the hash map.



309

00:20:08,800 --> 00:20:15,720

Now the second approach for implementing the hash it hash map is basically balanced BSG balanced binary



310

00:20:15,750 --> 00:20:23,880

search tree so for balanced BSG the height is basically always low often and is the total number of



311

00:20:23,880 --> 00:20:24,550

nodes.



312

00:20:24,660 --> 00:20:27,160

So Foster does discuss insert function.



313

00:20:27,930 --> 00:20:35,500

So it is our thing we know for inserting a node in a BSD the time complexity is basically proportional



314

00:20:35,500 --> 00:20:41,630

to the height and height is basically low often so insert function will take logging time.



315

00:20:42,550 --> 00:20:48,190

Okay so the unbalanced BSD there will be some ordering of keys so how can we order keys.



316

00:20:48,190 --> 00:20:55,300

For example you want to insert the strings so I can say ABC basically less than the we can use the ordering



317

00:20:55,380 --> 00:21:02,200

like like so graphically we can compare the strings we can order with the help of like looks or graphical



318

00:21:02,200 --> 00:21:06,740

ordering so this character is basically less than D or a B is less than the.



319

00:21:06,790 --> 00:21:13,660

So somehow there will always be ordering exist so ordering will always exist somehow so we can use ordering



320

00:21:13,660 --> 00:21:18,170

and we will put the corresponding give a loop here added squatters.



321

00:21:18,250 --> 00:21:25,930

Edit the right position we can push the key value pair inside the BSG adults right equation so and we



322

00:21:25,930 --> 00:21:34,460

know inserting an ordinary BSD log often so deletion in balance BSG again so deletion is proportional



323

00:21:34,460 --> 00:21:37,490

to height and height is basically log often.



324

00:21:37,610 --> 00:21:41,230

Similarly if you want to search for a node so in BSD you can.



325

00:21:41,330 --> 00:21:43,270

Searching is also proportional to height.



326

00:21:43,310 --> 00:21:49,820

So this is also low often either you will go left or ideally it will go right so if you will use the



327

00:21:49,820 --> 00:21:56,540

balanced BSD for implementing the hash map insert delete and search all three operations are taking



328

00:21:56,540 --> 00:21:57,650

log often.



329

00:21:58,130 --> 00:22:04,470

Okay so this is better than linked list implementation so actually this hash map.



330

00:22:04,560 --> 00:22:08,910

So this kind of balanced BSD already implemented in C++.



331

00:22:08,910 --> 00:22:10,600

So this is in bold.



332

00:22:10,680 --> 00:22:15,240

We already have this implemented in C++ and we will use.



333

00:22:15,240 --> 00:22:17,120

We will definitely use it.



334

00:22:17,550 --> 00:22:19,570

Now there is one more TV.



335

00:22:19,760 --> 00:22:27,110

There is Tavi and it is called with the help of hash tables we can implement hash map with the help



336

00:22:27,110 --> 00:22:28,060

of hash table.



337

00:22:28,080 --> 00:22:34,730

So in this case the insert function that the lit function better delete function and the search function.



338

00:22:34,730 --> 00:22:37,220

All three operations are basically big golf one.



339

00:22:37,280 --> 00:22:41,040

Yes constant time we get in the starting question time.



340

00:22:41,060 --> 00:22:45,590

We can deleting constant Constantine because searching clustering came with the help of hash tables



341

00:22:47,290 --> 00:22:51,480

so we will see we will study it thoroughly.



342

00:22:51,480 --> 00:22:57,790

But now first let us discuss in the next video how can we use this inbuilt hash map.



343

00:22:57,890 --> 00:23:03,560

So in the next we do we will see the inbuilt hash map and we will definitely discuss the hash table



344

00:23:03,600 --> 00:23:07,670

but later in the lessons I will meet you in the next one.



345

00:23:07,750 --> 00:23:08,020

My.