How HashMap works in Java? With Animation!! whats new in java8 tutorial

hi in this video we will see how hashmap works in Java also we will see what are the enhancements done to hash maps in Java 8 plus I will show you a couple of animations through your input and get operations so that the implementation is more evident for you so now let's quickly see what exactly is a hash map the Java dot 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 caches 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 hashcode 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 and there is a equals and hashcode contract that exists in Java that basically goes like this if two objects are equal they should have the same hash code as gap 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 are 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 okay now coming back to the equals and hashcode 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 maps but before that let's quickly touch upon the implementation details so as you can see here on high level hash map is basically implementation of the map interface at the same time if you look at the low level details hash map has a table an array of nodes and nodes are basically int hash key the key that you sent to the hash map the value that you will add to the table and a pointer to the next node so basically the node itself is a linked list inside the tail 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 in a scored in some game or something and we are trying to store that into a hashmap so as we said the hashmap comprises of a table initially and the table is sized based on you know to raise to M so by default the hashmap comes with a table of size 16 that's 1 6 16 and so the index of the table ranges from 0 to 50 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 hundred into the hash map so the put myth API is called and the put API basically computes hash of the key which is hash of King which is 2 3 0 6 9 9 6 and then we cannot have an array of this size in Java 2 3 0 6 9 9 6 theoretically you can have that kind of an array but if each and every hash a hash map is going to have such a huge array within it soon you learn 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 in a 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 hash map 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 is not pointing to any other now let's see how the next entry will be entered into the hash so we call a score start put Clark 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 six three to eight point nine four zero 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 Ford 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 word with score 99 hash is computed index is computed as four so we already have two entries here at index 4 so what will be this entry will be added as a new node after the node play so let's see how that happens they're a now comes a score start put Jones with value 99 so the hash of Jones is computed which is this value and the index is computed at zero and the entry goes at index zero 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 ports 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 not we should know that hash map lets you store null as a key sonal 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 they get operations work in Java so scores don't get Clarke so we want to get this core that Clarke 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 to so now if you 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 19 so now let's see how score start get King 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 told 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 dot get word will work so again if you go through the same steps hash forward is computed which is this number now the possible index is computed which is basically 4 so 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 entries hash code again that hash codes did not match so then we go to the next entry in that linked 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 column so that's how the map look up 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 8 that is a basic threshold when it exists 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 a 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 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 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 are 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 when we can use them so for today's session we have seen how the hash map works so we what we have to keep in mind is basically what exactly is a map but on what is the importance of equals to an hashcode contract and what what exactly is hashcode collisions basically when two unequal objects creating same hashcode that is called the hashcode collision and how the hashcode collision is managed within the hashmap 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

Channel: Ranjith ramachandran

Views: 891,953

Rating: 4.8729668 out of 5

Keywords: Hash Table, Java (Programming Language), Animation, hashmap, collection, tutorial, beginner, hashmap internals, how hashmap works

Id: c3RVW3KGIIE

Length: 15min 28sec (928 seconds)

Published: Tue Jul 14 2015