Hello friends, this is Deepak. In the last part, I had made you guys to do an implemented class of map that was tree map. What is tree map, what are its properties and I had made its practical part. In today's part, we are going to do hash table. So what is hash table, what are its properties and what is the working of hash table. These three things I am going to explain to you deeply today. So, let's start with the introduction part of hash table. Hash table is a directly implemented class of the hash table map. Which you can see here in hierarchy. So, hash table is inheriting the map interface directly. So we can write first point simple that is hash table is the direct implemented class of map interface. Okay. And second point is its syntax is very simple syntax. That is class hash table implements map. Hash table implements map. Okay. and here its constructors and methods will come. Okay, here one more point to keep in mind that hash table inherits dictionary class. Take care of this thing. Okay, and along with the map, it also inherits the clonable and serializable interface. Okay, so take care of both these points. And in which package is this present? that is package java.util this java.util package is present in it ok then next point third point one more most important point that hash table is legacy class legacy class keep in mind this was introduced in 1.0 version so I can say here that is it is a legacy class and was introduced in jdk 1.0 version this was introduced in jdk 1.0 version ok and its internal or underlined data structure hash table's underlined data structure is hash table ok so keep this point in mind that is hash table underlined data structure is hash table ok How does hash table actually work? I am going to explain this to you now. So these are the four points for hash table that you have to keep in mind. We can keep these things in mind in the simple introduction part. Then after this, we have properties of hash table today. What are the properties? Keep in mind that the properties are the same as they were of math. You can see it in the diagram here. First property of hash table is that it stores data in the form of key value pair. And every key value pair is called data entry. That same map property will come. Then second point, the keys should always be unique. They can't be duplicate. Whereas the values can be duplicate. Point clear, again this is the first property. Then hash table can store heterogeneous element at key position. On key position hash table can store different type of data. Then hash table can't store null value. Then next point. Hash table doesn't follow insertion and sorting order. And last point. Hash table is a synchronized map So from this point these are the properties that you have to of okay okay now I will explain you the next part which is the important part that is working of hash table yes what is the working of hash table we will see this thing once okay okay then take care here First of all, I will create a hash table. So, it is simple. What I have done here? Hash table. Ht equals to new hash table. I have simply created a hash table. Okay. Now, keep in mind the point here. How much is the initial capacity of the hash table? That is 11. So, as soon as I create the hash table object, So here we will have a hash table created. And its initial capacity will be 11. So here we will have 0. The value will start from 0 index position. And the last part will be 10. So, here we have a hash table created. So, here I create these buckets. We call them buckets. So, 0, 1, 2, 3, 4, 5, then 6, 7, 8, 9 and 10. So, here we have a hash table created. simple we have a hash table created ok now what do I do now I store elements in it so simple I put element here for example I put like 106 comma here I have stored for example Deepak ok so first element which I have stored now see how it will be stored So, this is the key and this is the value. So, first of all, we have to understand that the key has a hash code value. For example, we assume that the hash code value of 106 is 106. Normally, the hash code value of integer is integer. So, we assume that its hashcode value is 106. Now, you should know what is hashcode value. Hashcode value is a unique integer value of each object that JVM generates. So, for example, it will have a unique hashcode value. For example, we assume 106. So, I write here that we have its hashcode. We have hash code value 106. Now, the hash code value is modulus. Modulus will be 11. If I take out the modulus, what will we get? That is remainder. What will be the remainder? that is 11,999 then 106 minus 99 so what will happen to us? that is 7 so this value which we have in this position in the bucket this value will be stored in this position means this entry will be stored here so keep in mind this is a value which we have which is this value? that is index position and here we have 106 equals to or colon we have deepak will be stored here point clear to everyone so we have d small so we have deepak will be stored ok so keep Deepak So keep in mind what is happening here First the entry has a key It will get the hashcode value of the key. The hashcode value will come. We have to do modulus 11. Why? Because the default capacity of the hash table is 11. Clear? So, I have done modulus 11. So whatever value we get, the value will be stored at that index position. So this was the first point when I inserted the first value. Then similarly, I am inserting the second value here. That is, I have done here, for example, 102, for example, Kamal, I have stored. So again, the same step will remain with us. its hashcode value is 102, modulus 11, remainder is 3, so on third index position, this value key value pair will be stored, that is 102, colon, comma will be stored here. So, these types of values are stored here. I will store one more value here. That is, ht.put I have provided any value here. Ok, key value pair. Again, what will be? 108 modulus 11 equals to We will get the value that is 9. So, what will be on the 9 index position? This value that is key value pair will be stored. that is 108 108 comma or colon Ravi will be stored here. Okay, so keep in mind that this type of values are stored. Okay, but here we will take one more point. For example, here I have stored that is ht dot bot 117 comma Rahul. For example, here I have stored that is 117 comma Rahul. Now see one point here, 117 is hash code value, modulus 11, so what will be the remainder? 11 10s are 110, 117 minus 110 will be 7. So we have 7 index positions, now we already have elements at 7 index positions. Now, how will it store? Remember, this situation is called hash collision. Here, the hash, the index position, collided. Now, how will the second element be stored? Remember, here, we will have a linked list. It will start working. A linked list will come. and we have a node here a node will be created here and in that we will have the value which will be stored that is 117 and Rahul so here we will have the value that is 117 and Rahul point clear so you have to be careful if your index position is the same through hashing technique I am using the term hashing technique here So, this is the hashing technique term through which it is getting the index position or indices. So, this is the hashing technique. If through hashing technique we get the same index position, then we call that situation hash collation. So how will we store the element in that case This element will be stored in the same index position But here on the backend we will start doing something That is linked list So we will have a node created After this this node will point So both the elements will be stored in the 7th index position So this type of hash table works for us Now, you can store as many elements as you want. It will keep storing in this type. Keep in mind that 10 will be the maximum index position. 11 can't be the index position. Why? Because I am doing modulus 11 here. If I do modulus 11, then 0 can be the index position. 11 can't be the index position. Clearages. So all the elements will be stored in this type. And on the backend, we will also have a linked list. if we have a hash collision clear edges ok so this was the working of hash table now let's talk about when elements are retrieved when simple elements are retrieved how will they be retrieved you have to keep this in mind retrieved from top to bottom and from right to left yes keep this point in mind when we have the retrieved elements how will they be retrieved from top to bottom and from right to left clear it is right to right to left so if we talk about this then what will be its output if we talk about its output then what will be its output first we will get that is 108 colon Ravi then comma second output we will get 7 index position per element so right to left so 117 colon Rahul Then we have 106 colon Deepak. And then again, the bottom side will come. That is 102 comma colon Kamal. Clearages. So, from this type, top to bottom and right to left, that will start retrieving the elements. Point clearages to everyone. Okay. So, this was our simple working hash table, which you have to keep in mind. If you do this thing programmatically, If you do it properly, then this output will come. Ok, so keep in mind that we have the introduction part of hash table. Then I told you the properties and what is the working of the hash table. You have to keep this point in mind. There are a lot of things here that you have to keep in mind. First of all, we call them buckets. So what will be the initial capacity of the hash table? That is 11. So we will have 11 buckets created. Then whenever I insert an element in the hash table, it generates the value of the key. It generates it from the beginning. What will JVM do? Through hashing technique, it will get the index position of that key and store that value on that index position. So every element will be stored in this way. If we have index value of any one here, then we call this situation hash collision. So if we have hash collision here, then in that case the next element will be a node of the linked list and will store the element there. So, this is how simple elements are stored. Then, what will be in the retrieve case? Top to bottom and right to left. So, top to bottom and right to left will be retrieved and output will be provided. So, I hope you understood this simple working. You can try this program practically once. In case if you have any doubt, then you can ask in the comments. Okay, thank you. you