Internal Working of HashMap in Java
A HashMap in Java is part of the Java Collections Framework and implements the Map interface. It stores key-value pairs and allows for efficient retrieval based on keys.
Key Components of HashMap
- Hash Table: The underlying data structure is an array of buckets (or linked lists) where each bucket can store multiple entries.
- Hash Function: This function computes an index (bucket) for a given key using its hash code.
- Load Factor: This determines how full the HashMap can get before it needs to resize. The default load factor is 0.75.
- Threshold: The threshold is calculated as the product of the current capacity and load factor. When the number of entries exceeds this threshold, the HashMap is resized.
How HashMap Works
- Storing a Key-Value Pair:
- The key's hash code is computed using the
hashCode()
method. - The hash code is transformed into an index using a bitwise operation to fit within the bounds of the array size.
- The key-value pair is stored in the corresponding bucket. If multiple keys hash to the same index (collision), they are stored in a linked list or tree (Java 8 and later).
- The key's hash code is computed using the
- Retrieving a Value:
- The key's hash code is computed again to find the corresponding bucket.
- The linked list or tree at that bucket is searched for the key. If found, the associated value is returned.
- Resizing:
- If the number of entries exceeds the threshold, a new larger array is created (typically double the size).
- All existing entries are rehashed and redistributed into the new array based on their hash codes.
Example Code
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
HashMap map = new HashMap<>();
// Adding key-value pairs
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
// Retrieving a value
System.out.println("Value for 'Two': " + map.get("Two")); // Output: 2
// Checking size
System.out.println("Size of map: " + map.size()); // Output: 3
}
}
Conclusion
The internal workings of a HashMap involve hashing keys to determine their storage location, managing collisions, and resizing when necessary. This design allows for average-case constant time complexity for insertion and retrieval operations, making HashMaps a powerful tool for efficient data storage and access in Java applications.
Top comments (0)