In this post we will learn how hashmap works in JAVA.
HashMap works on the principle of Hashing . This can be explained using three terms first i.e Hash Function , Hash Value and Bucket .
First lets forget about JAVA. Lets understand how hashmap as a datastructure works.
What is map : Map is a key,value pair
What is HashMap : An derivation from map that works on hashing.
What is Hashing: Hashing is the method that defines out of so many empty rows for key value, In which row the data is going to be placed
Now in technical terms the process of passing key to a function that gives the index (row) in which the key value pair is going to be placed is called as hashing.
Suppose we want to store [AGE -> STUDENT]. Where AGE is the key and STUDENT is the name student.
Now suppose we have a map of 5 rows.
25 : Sameer
26 : Rajesh
15 : Manish
20 :Abdul
21: Mike
22 : John
22 : Ravi
23 : Subi
27 : Shree
29 : Asha
but we have 10 records to be stored in 5 rows , How to achieve it ?
Only storing the data is not important, We should be even able to retrieve the data.
So what we do is we get the age divide it by no. of rows and store the data in the remainder number of row :
Example: 25/5 remainder is 0 so the record goes in 0th means first row
27/5 remainder is 2 so the record goes in third row
This method of deciding which row the record is going to be stored is called hashing.
Now When two records go in the same index that is called hashcollision.
"So It is not important for two hashcodes to be same to have hash collision"
In order to store multiple data in the same index we can use what ever datastructure we want (Just keep in mind that we need to store both key and value, because we do get via key).
ex: You can use Linked list, Binary search Tree, Hashmap again etc.
Java used linked list till Java7.
Now since Java8 they convert Linked list into binary search tree if they get more that 6 elements in same bucket.
