Explain internal working of a HashMap? #java #interview #interviewtips

Key Concepts:

• HashMap
• Key-Value Pair
• Buckets (Array of Buckets)
• Node (Key, Value, Reference to Next Node)
• put Method
• Hash Value
• equals Method
• Linked List of Nodes

Internal Working of HashMap in Java

A HashMap in Java is a data structure used to store key-value pairs. The internal workings involve an array of buckets.

1. Data Structure:

• Internally, a HashMap creates an array of buckets.
• Each bucket contains a node.
• A node consists of:
  • Key
  • Value
  • Reference to the next node (allowing for linked lists within buckets).

2. The put Method:

When the put method is invoked to insert a key-value pair, the following steps occur:

• Hash Value Calculation: The hash value of the key is calculated.
• Bucket Mapping: This hash value is then mapped to a specific bucket within the array.

3. Scenarios within a Bucket:

Three scenarios can occur when mapping the key to a bucket:

• Empty Bucket: If the bucket is empty, a new node is created. This node contains the given key, value, and a null reference for the next node.
• Bucket Filled, equals Returns True: If the bucket is already filled, the equals method is used to compare the given key with the existing key in the node. If equals returns true (meaning the keys are equal), the value within the existing node is updated with the new value.
• Bucket Filled, equals Returns False: If the bucket is filled and the equals method returns false (meaning the keys are not equal), a new node is created with the given key-value pair. The reference of the existing node is then updated to point to this new node, creating a linked list of nodes within the bucket.

4. Linked List of Nodes:

In the case where multiple keys hash to the same bucket (collision), a linked list of nodes is formed within that bucket. Each node in the list represents a different key-value pair that maps to the same bucket index.

Conclusion:

The HashMap in Java uses an array of buckets and linked lists to efficiently store and retrieve key-value pairs. The put method calculates the hash value of the key, maps it to a bucket, and either creates a new node, updates an existing node, or adds a new node to a linked list within the bucket, depending on whether the bucket is empty and whether the equals method returns true or false.