Hi everyone.
In this video we are going to discuss the hash table data structure.
Now these are the four parts of this video.
We will discuss what hash tables are.
We will discuss about a hashing function and how it works, and how it's used in the case of a hash
table or a hash map.
And then we will discuss about collision handling.
And finally we will discuss the space and time complexity of common operations on a hash table.
So let's get started.
So hash tables are built in almost every programming language.
So that's the good thing about hash tables.
All right.
And they are very useful in JavaScript we have objects.
And in Python we have dictionaries etc..
All right.
So you can find them in almost every programming language.
And hash tables are just key value pairs.
All right.
So for example if this is your hash table and then you have key one which is pointing to value one.
And then you have key two which is pointing to value two.
And then we can just call this anything.
Let's say this is h t which is hash table.
So this over here is an example of a hash table.
Now if you notice that the arrow is in this direction.
Again the syntax in JavaScript is not like this.
It would be a colon.
All right.
Now this arrow over here is just to symbolize that we can only get the value from the key right.
We can get the value from the key.
But from the value we cannot get the key.
So we cannot go in the reverse direction.
That's an interesting thing to remember about hash tables.
Now let's proceed.
And let's try to see how they work.
And what's the benefit of hash tables.
Let's say we have this data.
We have three people John, Abby and Sarah.
And we have these numbers which is related to these three people.
And we need to store these numbers.
Now one way of storing it is like we could just use an array.
So that would be storing it in this manner.
Right.
So we have these three numbers at zero one and two indices.
Now if we want to retrieve this number we could just say array at one.
Again we are calling this array over here as r.
So in that case we could just say r at one.
So this is index one right.
So this is zero one and two.
So this is index one.
So we would get back this number.
But then it's difficult right.
How do we know that we have to call R at one.
So it's difficult to remember.
And it's it's not um friendly.
So it's much better to use an object or a hash table.
And in that case we could store it like this.
So we have John, Abby and Sarah.
Now you can see that the difference over here is in the case of array, the indices over here have to
be the integer zero, one and two.
But then in the case of an object we can have anything as key.
It can be a string.
It can be a number.
It can be anything.
Right.
So we can just say let's say this, this, uh, hash table over here is called h t.
Now if we want to access the number of Abby, which is this number, we can just say h t at Abby.
And it would give back this key value.
All right.
So over here this is the key.
So TX at the key gives back the value.
So you can see it's very useful.
All right.
Another interesting thing to observe over here is that an array is ordered.
You have zero one and two.
Right now when you're inserting another element or pushing an element to the array you would insert
it over here.
Right.
If you're pushing it at the end.
So that would be again at index three.
But when it comes to a hash table it's not ordered.
So you just have John and Abby.
Both of these are there in the hash table.
It's not that John is ahead of Abby.
So a hash table is not ordered.
All right.
So we've understood what a hash table is.
Now let's proceed and take a look at hashing functions and how they are used.
In the case of a hash table.
Now a hash table is built on top of an array.
Now let's again take this example where we have John, Abby, Sarah and these three numbers which are
related to them.
All right.
And we are storing them in a hash table, let's say where these are keys.
And these over here are values.
Now over here again let's try to see how this works.
All right.
So hash tables are built on top of arrays.
So let's say we have this array over here.
And remember the size of this array will actually actually depend on the size of the information that
we have to store.
So let's just keep that aside for a moment and let's see how the hashing function works over here.
So let's say this hash table where these keys and values are stored is built on top of this array over
here.
Now what is going to happen is we are we will take a key at a time and we will pass it to a hashing
function.
And this hashing function will convert this key to an integer in the range between 0 and 5.
Because we are using this array over here to build the hash table.
So again let me repeat for example, it will take this John over here which is the first key it will
pass in, pass it in to the hashing function.
And then this hashing function will spit out an integer between 0 and 5.
So let's say we are getting two.
All right.
So that means that this value which is 994836 will be stored at index two.
So next time we want to access the value at key John.
All we do is again we will pass the key which is John.
And the hashing function will give us two.
And then we directly come over to index two in this array.
And we can access this.
And we know that if we have the index we can access from an array in constant time.
All right.
So this is how a hash table works.
Now let's proceed.
Let's say we take the next key which is a b.
And that gives us the index zero.
So that means 762511 will be stored at index zero.
And let's say when we pass to the hashing function we get the integer five.
Now in that case 357921 will be stored at index five.
So this is how a hash table works.
It takes in the key, passes it to a hashing function, and gets an integer between the indices of the
array where the hashing function is stored, and then that particular value is stored at that particular
index, which is given by the hashing function.
Now let's take a look at what are the necessities for a good hashing function.
There are three necessities.
The first is that when we pass the same key, the next time, we should get back the same integer,
right?
So that is very important.
Otherwise we won't be able to read the information back.
So the same input should always give the same output.
Now the second thing is that the hashing should happen in constant time.
Now there are powerful hashing functions which already computer scientists have come up with and they
work in constant time.
So that's another important thing because we want efficient operation over here.
And then finally we want to minimize collisions.
Now let's try to understand what collisions are.
Let's say when we pass a B over here first we assume that the hashing function gave us zero.
And that's how we stored it over here.
But what would have happened if when we passed a b to the hashing function and we got back the integer
two.
In that case you can see John and Abby are both getting the integer two.
So we would have to store both these values at this index.
So this is what we call a collision.
And a good hashing function should minimize collisions.
So yes we have these computer scientists have come up with powerful hashing functions which do minimize
collisions.
But let's now go ahead and see how collisions are handled in hash tables.
So again let's take this example.
So we have the array from 0 to 5.
And we have this data over here.
All right.
Now to handle collisions in hash tables.
There are different techniques.
Now over here let's just discuss one technique.
Let's say when we pass in John and when we pass in Abby we get two.
Right.
So that's the integer two which is this over here.
So the way we would store this is this value 994836 would be over here.
Right.
We'll have a pointer which points to this value.
And then this value which is 76251.
One also will be stored at the same index.
Now this value will point to its key which is John.
And similarly this value will point to its key which is Abby.
Now for this we will use another data structure which is called linked List.
And this is something that we will learn soon in the next coming up in the coming up days.
All right.
Now we will learn this soon.
But again a linked list is just data which is connected to each other.
So you have some data over here that's pointing somewhere and that is pointing to somewhere.
And it goes on like this.
So this type of a data structure is a linked list.
So you can see over here at index two we have 994836.
And that is pointing to the next value which is 762511.
And then each of these is pointing back to its key.
Now how would we access this.
We want to get back the number of a b.
So how does retrieving work.
So let's take a look at that.
Now while retrieving we will again pass a b to the hashing function.
And it will give us two.
Right.
So we have this index two over here.
Now what we will do is we will take a look at the linked list at index two, which is this over here.
And then we will traverse this linked list and check is the key over here.
This is pointing to a value right.
So is this a b.
No it's not.
So we continue and we check.
Is this a b.
Yes this is a b.
Therefore it will identify this as the number and return it.
So it will check by traversing this linked list for matching with a B over here.
And that's how we will retrieve the value.
Again we don't need to worry about this because all of this is happening under the hood.
Now this is just to understand how a hash table works.
Now let's proceed to the final part of this video, which is taking a look at the space and time complexity
of common operations using a hash table.
Now you will understand why a hash table is very powerful when we take a look at these, uh, operations
and their space and time complexity.
Now let's start with accessing a value from a hash table.
Now with accessing, we mean, you know, the key, you are given the key and then you just want to
find the value.
Right.
We have seen that a hash table is nothing but key value pairs.
So you have key one over here which is pointing to value one.
Then key two which is pointing to value two, etc..
So let's say you know key two and you want to access value two.
So this is what we mean with accessing.
And inserting means you want to insert a new key value pair into the hash table.
And deleting means let's say you want to remove this key value pair.
Now the good thing about hash tables is that for all these operations, the time and space complexity
is O of one or constant time and constant space.
Now over here we say this on average, right?
In the case of the worst case this is going to take O of n time complexity.
Now why is that.
So let's take an example to understand this.
So let me just clear this up.
Now again let's take a look at the same data which we have over here.
We have John A, B and Sarah.
Now if the hashing function is not good and let's say John gives three when hashed.
And when we pass a b to the hashing function that also gives three and we pass when we pass Sarah to
the hashing function that also gives three.
So you can see that all the data is coming over here.
Now in this case, if we want to access the number of Sarah, we would have to traverse through the
entire linked list over here.
Right.
So we have to go.
We have to check this.
Then we have to check this.
So that's why in the worst case it's going to be O of n time complexity.
But then with respect to coding interviews we don't need to consider this because there are very good
hashing functions which which are used in, uh, programming languages.
And these give O of one average time complexity when it comes to accessing or inserting or deleting
from a hash table.
Now, what are the other things?
If you want to search for a key in a given hash table, that's a O of one time complexity operation.
But if you want to search for a value in a hash table, that's a O of n time complexity operation.
So what is this?
What's the difference between these two?
Let's say this is our hash table and you have key one.
You have value one.
Then you have key two.
You have value two.
And let's say you have key three and you have value three.
Now if you want to check if key three is there in this hash table, we can do that in constant time.
So that's the beauty of hashing hash tables.
All right.
But if you want to know if value three is there then we have to come to key one.
Then we have to go to its value one and check whether value one is equal to value three.
It's not.
So we proceed to key two.
We access its value and check whether value two is equal to value three.
It's not.
So we proceed to key three and check its value.
And we find that value three over here is equal to value three.
So for this we would have to traverse through the hash table.
So that's why searching for a value in a hash table is going to be an O of n time complexity operation.
So again just to revise hash tables are very powerful because we can access from a hash table in constant
time.
We can insert values a key value pair into a hash table in constant time, and we can delete from a
key value pair in a hash table.
In constant time.
Again, these operations don't take up space, right?
Uh, so that's why it's constant space as well.
All right.
Now let's proceed.
This is a summary of what we have discussed.
Accessing, inserting, deleting, searching for a key, searching for a value.
And then if you want to create a new hash table with n key value pairs, this is going to take up space
of the order of n.
Now you'll see that in many coding interview questions, to reduce the time complexity, we may store
some values key value pairs in a hash table.
And if you're going to store n key value pairs, then this is going to take up space of the order of
n.