Understanding Hashmaps | Geeks Classes Live | GeeksforGeeks

Key Takeaways

hi everyone i hope you all are doing great today so it's almost weekend so okay let's just wait few more minutes till then let's do have a quick chit chat in the chat box so let me know in the comment section how all you are spending your weekend it's weekend and some of you are doing binge watching netflix or some are upgrading your skills so just let me know in the comment section how you're spending your weekend you're planning to spend your weekend um are you binge watching netflix or bench eating or upgrading your skills through any course so just let me in the comment section what all you are planning to do and also tell your friends to join this amazing and interactive webinar with river pahuja to upgrade and upscale your knowledge okay let us just wait few more minutes okay i hope you all are doing great and i am mashika khandelwal from geeksforgeeks and your host for today and today with us we have pahuja who will be your mentor in this course yeah okay so roy said practicing in lead code great okay attacking boot okay great so now it's time to welcome river pahuja hey hi riba hi michiko hi everyone so hi rabbi how are you i'm good how about you i'm also good so rebecca so just uh start with a quick introduction of yourself like before we move ahead and i'll pass over this whole webinar to you so just give us a quick introduction of yourself so that our audience will you know know more about you and about the course and you know what are the topics and what other things we are going to cover in this particular webinar sure so as you all know my name is riba and i've been working as a back-end developer at sprinkler for almost two years now so i got just got promoted at sprinkler to a senior product engineer right so it's been almost two years since i have this experience in this industry and so uh my key uh areas include bsa and algorithms and like i'm more interested towards the back end stuff so in this webinar today we'll be covering hash maps right and uh we'll be going through the internal workings of the hashmap and we'll be covering end to end everything around the hashmaps yeah okay great a great robot and guys i have a surprise for you at the end of the webinar so be with us at the end of the webinar don't go anywhere don't skip this webinar because this is going to be so informational and informative so that you'll you know you'll add a knowledge and upgrade your skills through this webinar and also at the end of this webinar i'm gonna telling you what surprise i have for you guys so over to you sure so uh i'll just share my screen and uh let's start with the webinar right yeah over to you okay just a second i think it's taking time and sharing masking so i hope my screen is visible can you guys uh let me know in the comments if it is visible or not just bring a yes in the comments in case my screen is visible sure thank you so guys today we'll be going through hashing right so uh i'll be explaining what is hashing what are hashmaps how do we implement hashmaps and what are the key tricks and tips to know if a question belongs to a hashmap and how do we identify uh if if a question belongs to hashmaps right so starting with the basics first of all let me explain what basically a hashmap is and on what uh principles does it exactly work right so first of all uh let's uh understand hashing so what is passing right so basically to explain it uh hashing is nothing but it is a technique wherein uh we can use to basically get an index of an array corresponding to a string or any class for that matter right so let's say we have uh indexes in an array right so uh in order to tell uh that where does uh uh let's say we have this array so let me explain it with an example so let's say this is 1 this is 2 this is 3 this is 4 this is 5 and the indexes as we always start with 0 1 2 3 and 4 right so uh to explain it right so in case i need to access the zeroth element of the array and the array name is arr so what i do is i do arr0 right so uh so this only works with uh in integer indexes right so let's say i need to store something of the form that i need a array array at let's say abc so i need to somehow map this abc to a particular integer so that i am able to access you know uh the index of abc right so this is where in hash maps uh come into play right so uh so to uh explain it so let me first explain what is hashing so hash is basically a function it is let's say a magical function which takes in a value right and get and it gives me an integer value corresponding to that so that it is easier for me to uh access the integer array so so so uh as far as the syntax of the languages go right so this always needs to be an integer right so i'll be needing something such that the hash of that particular uh key gives me an integer so that is what exactly hashing function is right so one thing i always have to keep in mind right that if i say let's say ash of abc then it should always give me the same particular value let's say if it gives me 154 right so it's 154 right so it should always give me 154 no matter uh what uh how i calculated or when i calculate it right so uh so one key feature that comes off hash here is that a hash function always gives me the same value for a particular key right second particular feature of a hash function that comes into play is i cannot uh uh i cannot uh decipher the key from its particular hash value right so let's say a hash of abc was 154 i cannot say that if hash of a particular value was 154 then its key was abc it can be anything else right so this is where uh we can say something uh exists which is hash collision right so this is a particularly rare case wherein uh let's say two keys uh let's suppose abc abc and def for example they both give us the same hash value so let's say they both give us 154 then we obviously cannot say if the key was 150 uh abc or it was a def right so uh we cannot tell from the uh hash value about the key of the uh hash function right so this is something that is all about the hashing so this is hatching techniques right so these are hashing techniques now uh how how does it come into play during hash maps so as i said that uh for hash maps what we have is for integer arrays we have uh index uh as integers so i need to calculate an integer based on abc right i need to calculate the hash of abc so hash of abc let's say gives me zero right so i'll i'll place uh the value corresponding to abc at index of zero right so uh this is something uh that we have right so let's let's first get through uh the the uh syntax of hash maps in java then i'll explain uh further about hashmaps right so let me just share my ide screen [Music] yeah i hope my screen is visible right just give me a second yeah so uh so this is basically the implementation of a hash map right and uh what we do is uh so basically a hash map has uh three major functions right so the first one being the get so so a hash map basically let me just explain it to you so a hash map basically has three functions which are get these are the major functions get what size right so uh also a hash map is basically something uh in which we store the values as t comma value right so it is something that is similar to an array right but since an array i cannot have let's say string uh string indexes so we store it in the form of a key comma value right so let's uh we can have something of the sort let's say a corresponds to zero b corresponds to one something of that sort right so uh it is basically a key value store right so yeah and let's say b corresponds to zero so uh in order to add these to a hashmap what i will have to do is i'll have to uh like first declare a hashmap right of here we are using a hackmap of string for my integer so this will be my map and what i do is i do a new hash map so uh as you might be seeing these are something that are known as generics in uh hash maps uh in java basically so i can declare any class here for that matter it can be an integer it can be a string it can be any class uh that basically uh extends object in java right and then what i do is uh in order to save these values a comma one right i'll have to do map dot put comma 1 and similarly for b as well uh what i'll do is map dot put b comma 1 right yes so map.put b comma 1 now one thing that you will notice right is basically a hash map can have same values right but uh one key area of hash map is that it can only have one value corresponding one key corresponding to it so if i do again map.put a comma two then it will replace the value present in a corresponding to two and uh this will be overwritten right so if if this is done and i print the map it will give me b comma one and a comma two one more thing that we need to keep in mind is if i do map so if if this is the case then uh hash maps do not maintain the order of the keys in which they were added right so they do not uh keep the order so it it might be the case when i print this map it might give me a comma two and then it might give me b comma one but the value of a will always be two since it was overwritten during this function right so any questions that you have for me so far how to calculate hacks yeah we'll be going through this we'll be going through this uh any other questions uh i'll i'll be explaining how to calculate hash and the internal working of the hashmap as well okay so i'll take that as a no uh and we'll just proceed with uh the working of the hashmap right so this is basic this was basically the syntax of the hashmap and let's say i need to get the value from the hackmap all i need to do is map dot get a right so this will give me two right and uh let's say in case that that key did not exist so let's say i did map dot get c right so in this case what we'll be doing is that it will be giving me a null right so this will give me null essentially so this is some these are some places which we have to uh like take into consideration while writing the code that so map dot get c gives me null so it leads to null pointer errors in let's say so i do map dot get c and i do some other operation dot let's say uh like let's say i added to two so that might give me a null pointer exception right so that is something to be kept in mind right so yeah so that is it now uh how how how do we implement hashmap so we basically have two techniques uh one is open addressing and the other is separate chaining so let me just share my screen from the notepad and let me just explain it to you give me a second yeah so uh the techniques that we use to calculate uh calculate the where so essentially let's say we have this error list right and i need to place something corresponding to a something corresponding to b and something corresponding to 0 so in that case let's say i need to place something a and this will be the key and the value is let's say 1 right so essentially i need to place this in this array list right arrow list or an array that doesn't matter but i need to place it here right so how do i calculate where this key a will go so what i'll be doing is i'll be calculating the hash right hash of a now this hash might come uh come out to be a value greater than the size of the uh of the array list so let's say this comes out as seven right and the size of the array list is five so what i'll do is i'll essentially mod it with the size of the arrows right so that gives me a two right so i'll place it on the uh just a second i'll place it on the second index right yeah i'll place it so i'll place it 0 1 2 3 4 so i'll place the hash node with the value 1 right now so let's say i also want to place a b right and the hash value of b comes out to be 12 right so this i'll again mode mod 5 right because 5 is the size of the array right and this again comes out to be true so now this leads to a collision as to i'll have to place a has a here as well and b here as well so we have two techniques uh to cover this situation the first one being open addressing right open address thing and the second one being separate chain right so in open addressing what we do is uh we basically uh check if the next node uh so so in open addressing as well there are three techniques right let me just write them down so open addressing has three techniques so the first one is linear probing this is quadratic problem [Music] and this is double hashing right so what we do is uh in linear probing what we do is we basically check if the next value corresponding uh so uh i got b as two right so the second index is already filled so what i'll check is if the third and third index is empty right in case it is empty what we do is we place that corresponding that key comma value here right so this is linear problem right so i'll place b comma let's do here right so let's say i again uh get hash of c as 2 right so in this case i'll have to again check if 3 is filled or not and then if 4 is filled or not and if 4 was also filled i will go back again to 0 right so this is linear problem and in quadratic probing what we have is so to explain linear problem what we do is we check if hash of x plus 1 mod the size is empty or not in case it is filled then we check for hash of x comma x plus 2 and so on and so forth so in quadratic probing what we'll do is we'll check for path of x plus 1 into 1 in case that is filled we check x plus 2 into 2 and then hash of x plus 3 into 3 so as you can see this is a quadratic equation a square right x square so we do y square for that matrix since we are using x here so we do uh y square plus hash of x so uh in that case so we check uh and yes obviously this is mod size right so we in case this was this was it so we'll check 2 plus 1 then we'll check 2 plus 2 into 2 that is 2 plus 4 so that becomes 6 mod 5 so 1 we'll check this this index and after that in case this was also filled then we'll check 2 plus 9 11 mod five that is uh again one so we'll check this then 16 plus two eighteen mod five then three so so on and so forth right in double hashing what we do is uh we take a function we take two hash functions right so hash one x plus one into hash two x so this is something that will we'll calculate in case this is as this is filled as well then we uh calculate hash one x plus two into hash to x and so on and so forth so that is why it is known as double hashing because we are having two hash functions and we are calculating the next index based on that particular hash function right so any questions for me so far any questions for me vignesh is asking does a hatch map maintain order no no with nature does not maintain order for that we have linked hash maps in java but maybe we can explore it the during our sessions which probing is used in java hashmap so essentially java hashmap this implementation and that i'm talking about uh was before java 7 right and currently java hash maps use binary trees uh to you know implement the hash maps internally so that is something that we kept for the course that we will be exploring it further how do how does java 8 implement hashtags uh they were asking fascists have one one two one relationships not exactly they've so uh let's say hash of uh let me just explain it so let's say hash of one can be 150 and hash of 2 can be 150 as well right so one too many is uh so hash of 1 can be 150 hash of 2 can be 150 so as you can see so this can be many to one right many too many in fact no sorry yeah many to one so hash of one will always give me the same value right but uh two uh keys can have the same values right so that becomes a many to one relationship right any other questions that you have for me okay i'll take that as long got it so so these are the uh these are the collision handling techniques that we have for hashes right apart from that uh someone asked which i said that i'll be taking it further yeah so someone asked how to print full map elements with loop or anything else got it so let me just explain it with the code itself so to uh so so there's a function in hash maps which gives me all the keys that are present in the hashmap right so integer i so we had a string fashion applied str colon map dot as you can see this is b so str would be [Music] so this is the syntax for printing the all the hash map values and keys one more thing one more function that we have is map dot entry right so this will essentially become entry of string format integer and c dot dfp t dot get value right is hashmap similar to a dictionary in python yes oh sorry holding screen not sure yeah so uh this is something right so essentially this is the map.keyset function which essentially gives me all the keys which are present in the hashmap right so this will essentially give me a comma b right and then i iterate over all the keys and i print the key and i print the map dot get t as well so that gives me a uh and then it gives me the corresponding value that is two and then it gives me b and the corresponding value that is one right the other function that we have is map dot entry set right it gives me a basically an uh an entry object which contains both the e as well as the value so uh so this will be str dot e and get p and square value yeah so this is a function that we have to in order to print the elements i did share the id screen it is visible now right is it visible to you yeah we can have strings as the key and strings as the values yakult if we can give you the code okay any other questions difference between entry and dashboard so uh essentially as i told right that entry is basically so this is a function of the hashmap right so i have this map object the hashmap object and the entry set will give me uh will give me values of entry of string for my integer right so this is something that we have uh someone was asking can we have string as the value we definitely can have string rc value we can have any class as the values any class as a key difference between map and set very good question so what is a map is basically it has a key and a corresponding value whereas a hash set what is has uh what it has is let's say we have this i've said right so it only contains the keys it does not contain the values right so we can have a headset of a string sphere set equal to new have set so as you can see it just takes in one parameter right and we can only store uh strings corresponding to that so let's say we add str.set abc so it can only contain a key and not a corresponding value could you explain about thread safety yeah so uh ashish uh hash maps are not thread safe right so essentially when we let's say some thread is accessing and putting something into the hash map and after that some thread is let's say pulling from that hash map then it it does not guarantee that it will it give the same value or not right any other questions could you change your video set to the right mishika can we do that please someone is asking to change the video side to the right so that the id is visible yeah thank you uh deepak what do you uh want to know about the performance so yeah in case you are asking about uh the insertion deletion and uh you know searching of hash maps so essentially it basically depends on uh what exactly are we on our hash function right so let's say we want to insert something so i'll just go to go through the internal working of the hashmap i think we'll explain that any other questions from till now what we've covered till now can the keys be immutable so essentially what i explained was if i do map dot put a comma one and i do map dot put a comma two right then the next statement map dot put a comma two overwrites it right in case you are asking that if i can do this or not so in case let's say i do string spr equal to uh map dot key set right so i'm x am i am exactly not sure what you are trying to ask okay so let's go through the internal working of the hashmap so before that i'll have to explain a certain new concepts right so let me just share my screen of notepad and let me explain more concepts yeah so uh one thing that we need to know is the load factor of the hashmap right so yeah so we have something for called the load factor of the hashmap and we also have something called rehash right so now what is load factor so load factor is not a term that is related essentially to hash maps it basically is a generic term which basically denotes that how many keys do we have so no not exactly keys how many uh how do i explain yeah so how many just previous yeah so how many uh indexes which we have which are already you know covered which are which already have uh keys in them right and so load factor is basically the number of indexes that have keys and then divided by the total size of each right so essentially we need to keep this ratio always less than 0.75 so this is a threshold that java internally used to follow before java 7 right so we keep this ratio less than 0.75 and we'll be we'll also be keeping it less than 0.7 in our mode now what is rehashing right so uh there might come a certain point where in the number of indexes that have the keys might become greater than 0.75 into size right so in that case what we do is we basically increase the size of our array list in which we are storing the hashmap to twice the size so essentially then that will the load factor becomes less than 0.75 and in that case since we used to calculate the hash mod size of the of mod size of the array list then what we'll have to do is we'll have to calculate the hashes again and place the corresponding uh you know keys at the right position so let me just explain it with an example right so let's say we had this arraylist right so 0 1 right i got the hash of abc as let's say 5 then mod 3 becomes 2 sorry mod 4 becomes 1 so this is 1 then i'll place 5 exactly here right so the current load factor is 1 by 4 then let's say i calculate the hash of def it comes out to be let's say 6 mod 4 becomes 2 and i place d e f along with yeah so d e f here and the hash was 6 0 this is essentially not required we placed abc here we place the af here now the load factor becomes two by four that is the number of occupied indexes divided by the total size of the rls right and let's say we had dash of jk l and that came out to be seven we did mod four so this gives us three so we place jkl here at the third position right and now the load factors load factor becomes p by 4 right so essentially now is the time that we need to rehash our hash map right so essentially what we'll do is we'll increase the size of the array 2 twice so 8 elements in the array 4. 5 6 7 8 right so 0 1 2 3 so we increase the uh size and now so hashmap of a b hash of abc was 5 so 5 mod 7 is essentially again 5 only so we replace abc at the fifth index then def was 6 right so so this six mod eight becomes six again right so we place the ef player itself so d e f then seven mod eight so eight is the size of the array right so jkl will be placed here so as you can see the positions of the uh key is changed right so earlier it was at position one two three now it came out to be five six seven right so this is what we call rehashing right and the load factor is basically the number of occupied which is divided by the total right so any questions so far from this yeah i'll just code it right away any other questions that you guys have for me before we dive into coding okay cool i'll take that aside so let me just share my idp scheme so essentially as we saw right that map is supposed to be a generic uh generic class right so essentially by we'll first make a map node right which contains a k comma v so k denotes the key the type of key so essentially we could have it like this as well so we could have it of the form let's say integer so essentially we took it string so let's call it string only string key and integer value right but to for the map node to support uh for the map node to support different classes what we have is we have defined a generic object generate class so a key can be of any type of k and b can be of any type of b right so essentially any uh class that inherits the object class in java can be present in the map node itself right so uh now let's go through the uh map and the functions that we have right so as i said right that this uh we have an arrow list of map nodes right so and we also have the size so this is basically the array that we are trying to store as i was let me just share my entire scheme uh yeah i hope my screen is visible right so essentially what we are trying to store in buckets is basically this very so uh one thing that i want you guys to know is will be will be implementing the separate chaining separate chaining algorithm for hash maps right so in separate chaining what we do is let's say the hash of two values comes out to be two right then what we do is we meant instead of like checking the next and the next to the next like instead of doing linear probing and quadratic probing and all what we do is we maintain a linked list here right so uh let's say uh that it came out to be the hash function of two values of abc came out to be two and the hash function of def also came out to be two right then what we'll be doing is we'll be simply putting in abc here and def also came out to be two then we'll also be putting def in the in this particular linked list only and this currently points to null so essentially if another key comes in which has the hash value as 2 then we'll be putting it here in the last and we'll be making it the last node of the linked list right any questions on separate chaining then we go on to implement it okay cool so let's just go over separate chaining once so this essentially buckets is the same as our arrow list that we were trying to store here so this is what we call the buckets are list right so uh initially what we do is we can either take it take in the internal uh the exact capacity of the buckets or maybe we can initialize initialize it to a size of three right so whenever we let's say declare a map object we do buckets equal to new error list so that it is easier for us to initialize the buckets object with the size of three right so what i do is i do buckets not add null right so essentially uh this is basically nothing but these all are pointing to null objects this is null this is null this is not right so this is the the size of this is three so this doesn't matter right and all these are null objects here right so these are basically three linked lists with null as their head right now let's say we want to put something into the hashmap right so what we so what essentially goes into our mind is we'll have to first create a map node right so something wherein i can store my linked list node right so uh let's say i get abc and corresponding to that i need to put in two right so this is what that's something that i'll be doing i'll be creating a new map node object with the key abc and the value 2 and i'll be placing it at that particular position wherein my hash of abc comes out right so to code it here what i'll be doing is i'll be basically like let's say i get the bucket index so how do i get the bucket index by calculating the hash of the e right so i had the string abc and to calculate the hash we have something called the hash code as the function which is internally implemented in java right so what we do is we calculate the hash of string abc and then what we do is we mod it with the size of buckets right so this basically gives me the index at which we'll be placing the string abc right now once we get that index what i need to check is uh that do i have some elements here or not in case i do i'll have to place my abc at the end of the linked list right in case i do not have any elements i can just create a new linked list and i can place it there right so essentially head equal to buckets not yet so this this is basically what we are doing we are checking if there is something some link list present here or not right so what we do is uh we iterate over this linked list right in case there was nothing present then head becomes null temp becomes also null and we simply return null so this is get function right so in the put function head equal to buckets dot get bucket index we make a new node we initialize the key e as we say here abc and the value as 2 right so if our head was null we simply do buckets dot set bucket index from a new node right so essentially what we did here was since this was null initially what we'll do is we'll place abc comma two here right and the next of this points to none right so after this let's say def comes in its hash also came out to be two right so what i'll be doing is i'll be iterating over this linked list right i'll be checking uh if bef exists in this linked list or not right in case it does not exist i'll go to the end and i'll append def comma 3 at the end of the linked list right so this is what we are doing we are iterating over the linked list so while temp is not equal to null and we check if there exists a key deaf or in in in that particular list in case it does we simply override the value in case it does not what we do is uh we simply add it to the end right so again buckets not set so essentially buckets here we are calculating the load factor we check if it is greater than 0.75 then we do rehash as i told you guys so essentially in rehash what we are doing is we are not we are doing nothing but we are increasing the size of the buckets and we are iterating over all the linked lists and placing them on the right position right so we are essentially doing put current dot t comma current dot value and current equal to current dot next right so essentially what we have is in in separate chaining to insert an element what the time complexity what the time complexity becomes is it so let's say my uh maximum linked list size was n right so it becomes big o of n in case of uh separate chain right so in case it wasn't so on on an average since we do not have as much collisions right so on an average it becomes we go of one so what we assume is the linked list side sizes at most let's say two or three right so for each hash we have two or three uh right two or three uh linked list size right so essentially to calculate the insertion all we have to do is we have to calculate the hash function and place it at that corresponding link here right so essentially that becomes of one obviously searching also becomes of one because we need to search only in that particular linked list corresponding to the hash of the p and also deletion also becomes essentially o of one because what we are doing is we are going to iterate over the linked list and doing nothing but simply you know deleting that element so deletion in linked list is going to that particular element and deleting and since we have the size of at most two to three elements in that linked list so this is basically any questions that you guys have for me how to create this array of links okay so essentially uh yeah so satwik what we are doing is basically let's say i have this our list of map nodes right so essentially if i just have a head of the linked list and my head points to the next element and that next element points to the next of the next element so essentially all i need to do is i need to just maintain a map node arraylist right so this map node obviously contains the next element and then that can be storing the rest of the linked list right if you get that if you're familiar with linkedin in case you are not we'll be going through that in the course as well any other questions that you guys have for me [Music] okay i'll take that as a load i think that brings us to the end of the webinar we have gone through pretty much about how exactly we'll be going through the internal workings of this stuff and obviously we'll be going through a lot of you know a lot of the implementation and the workings not only that we'll also be going through the use cases we'll be going through a lot of questions that come up when and how do you implement override exactly the get dashboard function right so the get hash code function is basically something that is implemented inside the objects class only right so in order for us to have something yeah so this is something that i missed good question so essentially if we add if we need to add something to the hashmap of the java class right we need to have the equals as well as the hash function overridden inside our class right so string integer these already have that but in case we are writing our own class we need to have them uh implemented in the in in our class yeah i think okay thank you so much so it was a quite interesting webinar even i get to learn a lot of things and i have understood a bit concept of hash mapping just don't ask me questions what is hash mapping but yeah i do understand what uh a bit about of hash mapping and the concept of hash mapping so yeah it was a quite yeah interactive and informative webinar so thank you so much for this amazing webinar so i hope everyone i hope you guys enjoyed this webinar and learned a lot of things so if you want to know more about uh about the hashmapping and the dsn you want to go deep into the go deep dive into this course so just go register to this course which especially for the working professionals to enhance your skills you if you are working with the company or you know enhance or up upgrade your skills so this course is just for you and if you wanna you know if you wanna start uh with the basics and you are in the intermediate level and go into the uh upgraded version so river will be clearing all your doubt in the live course go register to this course and and avail the exciting offer the surprise which i was talking about in the initial of this webinar so if you uh if you register for this course just now you will get 15 1500 off on this on this course and also you'll get the complimentary access to the google test series as well so what are you waiting for go register yourself for this for this course where river will be your mentor and teaching you and clearing all the doubts of yours of dsa and you know if you if you are working in any company and you are you know looking to go in a top-notch uh farm or any other company you are seeking so this course is just for you so yeah thank you so much for this interactive session thank you so much i hope you and everyone has enjoyed this session yeah definitely yes yeah thank you so much thank you bye bye so yeah and also guys we also have a form as well if you have any queries regarding this course you can you can just put your query in that particular form and you know will resolve every query of yours and go just check out this course the link is in the description box go check out register for yourself and you know first come first serve go check out the course and see the every details of this course and register yourself so that you can avail the 15 percent offer 15 1500 off on this particular course and we have few more courses as well whose link which we have had which i we have added in the description go see the link and explore more thank you so much everyone it was great interacting with you all and be with geeksforgeeks for more interesting and informative webinars thank you so much everyone also to use this offer avail this offer you need to use that code upscale 15 which we have added in the description as well use coupon code upscale 15 to get 1500 discount on this particular course you