A HashMap is a data structure in Java that is used to store and retrieve key-value pairs. It provides constant-time performance for basic operations such as insertion, deletion, and retrieval.
The underlying data structure of a HashMap is an array of linked lists. In this article, we will explore the data structure of a HashMap in detail.
How does a HashMap work?
A HashMap uses a technique called hashing to store and retrieve elements efficiently. When you insert a key-value pair into a HashMap, the key is hashed using the hashCode() method of the key object. The resulting hash code is used to determine the index in the underlying array where the element should be stored.
If two different keys have the same hash code, which is known as a collision, then those elements are stored in the same index of the array but as part of a linked list. Each element in the linked list contains both key and value information. This allows multiple elements with different keys but the same hash code to coexist in the HashMap.
Advantages of using a HashMap
- Fast Retrieval: Retrieving an element from a HashMap has constant-time complexity on average, which makes it ideal for applications that require quick lookups.
- Flexible Key-Value Pairs: A HashMap allows you to store any type of object as both keys and values, providing flexibility in how you organize and access your data.
- Automatic Resizing: As elements are added or removed from a HashMap, it automatically adjusts its size to maintain efficient performance.
Data Structure Visualization
To better understand how a HashMap works internally, let’s visualize its data structure:
HashMap:
- Array of Linked Lists
- Index 0: -> (Key1, Value1) -> (Key2, Value2)
- Index 1: -> (Key3, Value3)
- Index 2:
- Index 3: -> (Key4, Value4)
- ..
In the example above, the HashMap contains an array of linked lists. Each index of the array represents a bucket where elements with the same hash code are stored as a linked list. The buckets can be empty if there are no elements with the corresponding hash code.
Insertion:
When inserting a key-value pair into a HashMap, the key is hashed to determine its index in the array. If the bucket at that index is empty, a new node containing the key-value pair is added to the bucket. If there is already a linked list at that index due to a collision, then the new node is appended to that list.
Retrieval:
To retrieve a value from a HashMap using its key, the key is again hashed to find its index in the array. Then, each element in the linked list at that index is compared with the given key until a match is found. Once found, the corresponding value can be returned.
Deletion:
To delete an element from a HashMap using its key, first, you locate its index in the array through hashing. Then you traverse through the linked list at that index and remove any node whose key matches the given key.
In conclusion
A HashMap is a powerful data structure that provides fast retrieval and flexibility in storing key-value pairs. By using an array of linked lists, it efficiently handles collisions and ensures constant-time performance for basic operations. Understanding the internal data structure of a HashMap can help you utilize it effectively in your Java applications.