Note | Coconote

Hi, in this video we will see how HashMap works in Java. Also we will see what are the enhancements done to HashMaps in Java 8. Plus I'll show you a couple of animations regarding put and get operations so that the implementation is more evident for you. So now let's quickly see what exactly is a HashMap. The java.util package provides a lot of built-in data structures so that we don't have to implement it from our own you know, we don't have to hand create them. So the popular data structures are like lists, sets and maps. So maps are basically associative arrays that lets you store key value associations. That means you can store key against value and then later if you want to look up the value, you can just use the key and look it up. So that makes it one of the popular data structures in terms of enterprise applications where you can use this to represent big. caches where you will have a key and some big object as the value. Later on somewhere in the application you can use the same key and reach the value and retrieve the value whenever you need it. Also you can imagine a hash map or a map as a dictionary. So now what exactly is a hash map? Hash map is one of the implementations of the map interface and hash map is known as a hash map because it It is based on a technique called hashing. So hashing is basically a technique where you will transform a large string into a large string or basically as an object into a short fixed length representation. So for example you know let's consider the string a large string you can convert that into a small fixed length integer. So that helps us faster indexing and lookups. At the same time there are some catches that we should be aware of. So let's see them. So basically in Java as you know each and every object has a hash code method available. So that hash code method is supposed to return the hash of the object. For example if you call the hash code API on a string you will get an integer back. And there is a equals and hash code contract that exists in Java that basically goes like this. If two objects are equal they should have the same hash code as well. So that means it's very important to have robust hash code implementation in your classes. And if you have difficulty in implementing your own hash code, for example, you are implementing a account class, for example, and you're not able to provide a very good hash code implementation, you can always let the IDE generate for you. And they do a good job sometimes in generating hash code implementations. So that's a good example. Okay, now coming back to the equals and hash code contract. Why is it important? It is important because the hash code is used in storing values into the hash map. So when we look up you know values corresponding to a given key if the hash code is not consistent you won't be able to look up the corresponding value ever. So we will see why exactly is that in the following animation regarding hash map. But before that let's quickly touch upon the implementation details. So as you can see here on high level, HashMap is basically implementation of the map interface. At the same time if you look at the low level details, HashMap has a table, an array of nodes and nodes are basically int hash, the key that you send to the HashMap, the value that you will add to the table. a pointer to the next node. So basically the node itself is a linked list inside the table. So each index in this array that you can imagine as a as a node which actually can be linked list of nodes. Okay, so basically each index in the table is known as a bucket for example and each bucket is a node which in turn can be a linked list of nodes. So let's see how this implementation works in terms of the put operation. So in this example, we are trying to put a person name and the score he scored in some game or something. And we are trying to store that into a hash map. So as we said, the hash map comprises of a table initially. And the table is sized based on 2 raised to n. So by default, the hash map comes with... a table of size 16 that's one six sixteen and So the index of the table ranges from 0 to 15 So we need to fit these entries into this table. So let's see how it works when the put operation happens. So first we are trying to put the key king and value 100 into the hash map. So the put API is called and the put API basically computes hash of the key which is hash of king which is 2306996 and then we cannot have array of this size in Java 2306996 theoretically you can have that kind of an array but if each and every hash hash map is going to have such a huge array within it soon you will run out of memory and you will have a lot of other issues so that's why the hash map is sized the hash map table is sized to 2 raised to n and now we have to run a little index computation to find out where exactly we can fit this hash code in our table of range 0 to 15. So the index is computed using a modular operation. So basically you divide the hash code using the you know maximum value of the range and you get the reminder and the reminder will be a value that you can fit within the range. So to make it faster HashMap implementation uses the bitwise operation as shown here. So the index computes to 4 and that means the entry will go into this index 4 as a node. So you can see a new node is created with the key value and the hash value and the value itself which is 100 which is a score and null meaning it's not pointing to any other node. Now let's see how the next entry will be entered into the hash. So we call scores.putClark with score 90. So computation of the key hash of the key happens which is a big number. So we try to find out on what index we can fit this hash code into. So which is the index 2. So that goes into the index 2 of the table as an entry with the key, with the hash code, with the value 90 and null indicating that it's not pointing to any more nodes right now. So now let's try to insert the entry Blake with score 10 into the hash map. So the hash of Blake is computed which is 632 81940 and we are trying to find out the index where it can be fitted that happens before. So here we have in theory some sort of a collision because we already have an entry at index 4. So what we would do is that this entry will be added as the next node of the already existing node at index 4. So that means The pointer in this node which is basically created for king will point to the new node that is created for Blake and It will have these Properties in it now Let's go and put forward with score 110 the hash of the key is computed The index is computed as 10 and it's fitted into 10 now comes the next entry which is Smith with value 10 so hash is computed index is computed as 6 it goes to index 6. Now we are trying to put ward with score 99 hash is computed index is computed as 4 so we already have two entries here at index 4 so ward will be this entry will be added as a new node after the node blake so let's see how that happens there you go. Now comes scores.put Jones with value 99. So the hash of Jones is computed which is this value and the index is computed as 0 and the entry goes at index 0. So this is how the hash map will look like at the end of all these put operations. So as we saw whenever there is a collision theoretically like if all these hash codes were same or if they were computing the same index those entries will be stored as a linked list of nodes and also we should know we should know that hash map lets you store null as a key so null will always have a hash of zero so the index of null key will be always index zero so there is no confusion regarding so that's how the hash map put operations work now let's see how the get operations work in java So scores.getClark. So we want to get the score. that clerk had. So first we call the get operation get object key. So the get operation also does the same set of operations. It finds the hash of the key which is this number. Now it computes the index where that key could have fitted. So the index computed as 2. So now we will look up index 2 on the table. We have an entry. So with that entry we compare the hash code. of the key against the hash code available there on that entry. That matches. Now we will compare the key itself that was used against the key that is available on that entry using the equals method. That also matches. That means we have found a match. So the value at that node is returned to the caller and the caller gets the score which is 90. So now let's see how scores.getKing will work. It works in the same way hash is computed for king and the possible index is computed which is 4. So we will see what is there on 4. So we see one entry. Now we will compare the hash code of the given key with the hash code at the entry. Matched. Now we will compare the given key with using equals method against the key that is stored on the node. that also matches so that means we can return this value to the caller so the score of king we got 100 perfect now let's see how exactly scores.get word will work so again it will go through the same steps hash for word is computed which is this number now the possible index is computed which is basically four so that so we see that there is an entry and then we compare the hash code for given key against the hash code at the entry. So now the hash codes don't match. So we kind of skip that entry and go to the next entry and try to match the hash code against that entry's hash code. Again that hash codes did not match. So then we go to the next entry in that link list and try to match the hash code there. And there's a match. So since we found a match on hash code, We will compare the key Using the equals method against the key that was given that also passes that means we return the value 99 to the color So that's how the map lookup works in a hash map. So what has changed in Java 8? So in Java 8 what has happened is that when we have too many unequal keys which are producing the same hash code or the index as we saw when the number of such items actually exceeds a threshold for example number eight that is a basic threshold when it exceeds that threshold hash map implementation internally converts that linked list into a balance tree so a balance tree is theoretically faster than a linked list as balance tree provides you worst case performance of log n which is compared to which is compared to order of n performance of a linked list which is definitely better. So that is the change in java 8 which gives you which gives you performance improvements when there is too many unequal keys providing you the same hash code or resolving to the same index. So balanced search tree is basically ordered based on the hash code as the smaller hash code will be on the left hand side left hand node and the higher hash code will be on the right side and in case when the hash codes are same the the the keys are compared and the bigger key goes to the right and smaller key goes to the left so again the efficiency of the the tree based implementation enhancement depends a lot on how your hash codes and comparable implementations that you have provided so that is the enhancement in Java 8 so in our next session what we will see is that what are the various different kinds of maps that are out there in Java and what is the exact purpose of these hash maps or map implementations and when we can use them so for today's session we have seen how the hash map works So what we have to keep in mind is basically what exactly is a map. what is the importance of equals to and hashcode contract and what exactly is hashcode collisions basically when two unequal objects creating same hashcode that's called the hashcode collision and how the hashcode collision is managed within the hash map for example using the link list or the balance tree in java 8. so that pretty much concludes this topic and please stay tuned for the upcoming updates on further videos Thank you.

The java.util package provides a lot of built-in data structures so that we don't have to implement it from our own you know, we don't have to hand create them. So the popular data structures are like lists, sets and maps. So maps are basically associative arrays that lets you store key value associations.

That means you can store key against value and then later if you want to look up the value, you can just use the key and look it up. So that makes it one of the popular data structures in terms of enterprise applications where you can use this to represent big. caches where you will have a key and some big object as the value. Later on somewhere in the application you can use the same key and reach the value and retrieve the value whenever you need it.

Also you can imagine a hash map or a map as a dictionary. So now what exactly is a hash map? Hash map is one of the implementations of the map interface and hash map is known as a hash map because it It is based on a technique called hashing. So hashing is basically a technique where you will transform a large string into a large string or basically as an object into a short fixed length representation. So for example you know let's consider the string a large string you can convert that into a small fixed length integer.

So that helps us faster indexing and lookups. At the same time there are some catches that we should be aware of. So let's see them. So basically in Java as you know each and every object has a hash code method available. So that hash code method is supposed to return the hash of the object.

For example if you call the hash code API on a string you will get an integer back. And there is a equals and hash code contract that exists in Java that basically goes like this. If two objects are equal they should have the same hash code as well. So that means it's very important to have robust hash code implementation in your classes.

And if you have difficulty in implementing your own hash code, for example, you are implementing a account class, for example, and you're not able to provide a very good hash code implementation, you can always let the IDE generate for you. And they do a good job sometimes in generating hash code implementations. So that's a good example.

Okay, now coming back to the equals and hash code contract. Why is it important? It is important because the hash code is used in storing values into the hash map. So when we look up you know values corresponding to a given key if the hash code is not consistent you won't be able to look up the corresponding value ever. So we will see why exactly is that in the following animation regarding hash map.

But before that let's quickly touch upon the implementation details. So as you can see here on high level, HashMap is basically implementation of the map interface. At the same time if you look at the low level details, HashMap has a table, an array of nodes and nodes are basically int hash, the key that you send to the HashMap, the value that you will add to the table.

a pointer to the next node. So basically the node itself is a linked list inside the table. So each index in this array that you can imagine as a as a node which actually can be linked list of nodes.

Okay, so basically each index in the table is known as a bucket for example and each bucket is a node which in turn can be a linked list of nodes. So let's see how this implementation works in terms of the put operation. So in this example, we are trying to put a person name and the score he scored in some game or something.

And we are trying to store that into a hash map. So as we said, the hash map comprises of a table initially. And the table is sized based on 2 raised to n.

So by default, the hash map comes with... a table of size 16 that's one six sixteen and So the index of the table ranges from 0 to 15 So we need to fit these entries into this table. So let's see how it works when the put operation happens. So first we are trying to put the key king and value 100 into the hash map.

So the put API is called and the put API basically computes hash of the key which is hash of king which is 2306996 and then we cannot have array of this size in Java 2306996 theoretically you can have that kind of an array but if each and every hash hash map is going to have such a huge array within it soon you will run out of memory and you will have a lot of other issues so that's why the hash map is sized the hash map table is sized to 2 raised to n and now we have to run a little index computation to find out where exactly we can fit this hash code in our table of range 0 to 15. So the index is computed using a modular operation. So basically you divide the hash code using the you know maximum value of the range and you get the reminder and the reminder will be a value that you can fit within the range. So to make it faster HashMap implementation uses the bitwise operation as shown here. So the index computes to 4 and that means the entry will go into this index 4 as a node.

So you can see a new node is created with the key value and the hash value and the value itself which is 100 which is a score and null meaning it's not pointing to any other node. Now let's see how the next entry will be entered into the hash. So we call scores.putClark with score 90. So computation of the key hash of the key happens which is a big number. So we try to find out on what index we can fit this hash code into.

So which is the index 2. So that goes into the index 2 of the table as an entry with the key, with the hash code, with the value 90 and null indicating that it's not pointing to any more nodes right now. So now let's try to insert the entry Blake with score 10 into the hash map. So the hash of Blake is computed which is 632 81940 and we are trying to find out the index where it can be fitted that happens before. So here we have in theory some sort of a collision because we already have an entry at index 4. So what we would do is that this entry will be added as the next node of the already existing node at index 4. So that means The pointer in this node which is basically created for king will point to the new node that is created for Blake and It will have these Properties in it now Let's go and put forward with score 110 the hash of the key is computed The index is computed as 10 and it's fitted into 10 now comes the next entry which is Smith with value 10 so hash is computed index is computed as 6 it goes to index 6. Now we are trying to put ward with score 99 hash is computed index is computed as 4 so we already have two entries here at index 4 so ward will be this entry will be added as a new node after the node blake so let's see how that happens there you go.

Now comes scores.put Jones with value 99. So the hash of Jones is computed which is this value and the index is computed as 0 and the entry goes at index 0. So this is how the hash map will look like at the end of all these put operations. So as we saw whenever there is a collision theoretically like if all these hash codes were same or if they were computing the same index those entries will be stored as a linked list of nodes and also we should know we should know that hash map lets you store null as a key so null will always have a hash of zero so the index of null key will be always index zero so there is no confusion regarding so that's how the hash map put operations work now let's see how the get operations work in java So scores.getClark. So we want to get the score. that clerk had.

So first we call the get operation get object key. So the get operation also does the same set of operations. It finds the hash of the key which is this number. Now it computes the index where that key could have fitted.

So the index computed as 2. So now we will look up index 2 on the table. We have an entry. So with that entry we compare the hash code.

of the key against the hash code available there on that entry. That matches. Now we will compare the key itself that was used against the key that is available on that entry using the equals method. That also matches.

That means we have found a match. So the value at that node is returned to the caller and the caller gets the score which is 90. So now let's see how scores.getKing will work. It works in the same way hash is computed for king and the possible index is computed which is 4. So we will see what is there on 4. So we see one entry. Now we will compare the hash code of the given key with the hash code at the entry. Matched.

Now we will compare the given key with using equals method against the key that is stored on the node. that also matches so that means we can return this value to the caller so the score of king we got 100 perfect now let's see how exactly scores.get word will work so again it will go through the same steps hash for word is computed which is this number now the possible index is computed which is basically four so that so we see that there is an entry and then we compare the hash code for given key against the hash code at the entry. So now the hash codes don't match.

So we kind of skip that entry and go to the next entry and try to match the hash code against that entry's hash code. Again that hash codes did not match. So then we go to the next entry in that link list and try to match the hash code there. And there's a match. So since we found a match on hash code, We will compare the key Using the equals method against the key that was given that also passes that means we return the value 99 to the color So that's how the map lookup works in a hash map.

So what has changed in Java 8? So in Java 8 what has happened is that when we have too many unequal keys which are producing the same hash code or the index as we saw when the number of such items actually exceeds a threshold for example number eight that is a basic threshold when it exceeds that threshold hash map implementation internally converts that linked list into a balance tree so a balance tree is theoretically faster than a linked list as balance tree provides you worst case performance of log n which is compared to which is compared to order of n performance of a linked list which is definitely better. So that is the change in java 8 which gives you which gives you performance improvements when there is too many unequal keys providing you the same hash code or resolving to the same index. So balanced search tree is basically ordered based on the hash code as the smaller hash code will be on the left hand side left hand node and the higher hash code will be on the right side and in case when the hash codes are same the the the keys are compared and the bigger key goes to the right and smaller key goes to the left so again the efficiency of the the tree based implementation enhancement depends a lot on how your hash codes and comparable implementations that you have provided so that is the enhancement in Java 8 so in our next session what we will see is that what are the various different kinds of maps that are out there in Java and what is the exact purpose of these hash maps or map implementations and when we can use them so for today's session we have seen how the hash map works So what we have to keep in mind is basically what exactly is a map.

what is the importance of equals to and hashcode contract and what exactly is hashcode collisions basically when two unequal objects creating same hashcode that's called the hashcode collision and how the hashcode collision is managed within the hash map for example using the link list or the balance tree in java 8. so that pretty much concludes this topic and please stay tuned for the upcoming updates on further videos Thank you.

Transcript for: