How a HashMap internally works

A quick view of a HashMap

Interface: <Map>

Speed: O(1)

Order: By default, no order for keys or values

Null values: Allow one null key and any values

Synchronized: No

Duplicates: No

The structure of a HashMap

  • The initial capacity of a HashMap is 16.
  • When you create a HashMap it will create a map with 16 buckets (0 to 15).
  • Each bucket is a LinkedList.
  • As we know a LinkedList contains nodes and each node contains a key, value, hash value, and a pointer to the next node.

What is the Load factor of a HashMap?

  • The default initial capacity of a hashmap is 16 as mentioned above and the load factor is 0.75f.
  • The load factor is the level at which its capacity should be doubled.
  • If the HashMap has filled 75%, then the capacity of the HashMap will be doubled.

Store data in a HashMap

  • When we add data into the HashMap, in the put() method, internally it will generate an index using the key.
  • That index should be 1 to 15.
  • For example, if it gets an index = 5, it will store that data in the 5th bucket.
  • Please check the below example.

Use objects as keys

  • In the above example, I used the employee object as a key in the hash map.
  • In the first case, I am going to add emp1 as the key in the hash map.
  • Internally inside the put() method, it will generate an index, and according to the index the value will be stored in a bucket out of 16 buckets as I mentioned above.
  • When storing emp2, the same process will be executed only if the index is different from the other.
  • What will happen if the index of emp2 is the same as emp1?

What is Hash collision?

  • If it generates the same index, a hash collision can happen.

How to avoid the hash collision?

  • In this case, it is required to override equals() and hashCode() methods inside the Employee object.
  • It will check the equality of the objects using the equal() method and then if it is not equal it will be saved in the same bucket as the next node to the existing node.

What will happen if the key is null?

  • If you put null values as the key, it will be saved in the 0th bucket.

HashMap vs TreeMap vs LinkedHashMap

Differences between HashMap Vs HashTable

  • The major difference is, HashTable is synchronized but HashMap is not.
  • If you are looking for a synchronized version of HashMap, you can use ConcurrentHashMap.
  • Another difference is, that HashMap allows one null key and many null values, but HashTable doesn’t allow null keys or values.

Read more about Maps in Java
How a HashMap internally works How a HashMap internally works Reviewed by Ravi Yasas on 6:54 PM Rating: 5

No comments:

Powered by Blogger.