Java HashMap Interview Questions
HashMap uses an array to store entries and resizes dynamically as it accumulates more data.
Keys are mapped to array indices, which can lead to collisions when two keys hash to the same index. In such cases, entries are stored in a LinkedList at that index.
If the LinkedList grows too long, it's converted into a binary search tree. Conversely, if the tree becomes sparse, it's reverted to a LinkedList.
HashMap employs hashing techniques to evenly distribute hashCodes, minimizing collisions and improving performance.
Key Takeaways
- HashMap stores entries in arrays and handles collisions with LinkedLists and trees.
- Efficient indexing requires good hash distribution using bit manipulation.
- Resizing and restructuring (tree to list and vice versa) are costly operations.
Hashing in Action
When calling:
myMap.get("key1")It's actually referring to:
tab[index]HashMap converts the key to an index using this hash function:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Null keys return a zero hash, and the XOR bitwise operation distributes bits more evenly across the table.
Index Calculation
The index is calculated as:
i = (n - 1) & hash;Here, n is the array's length. The bitwise AND operation effectively performs a modulus but is more efficient due to its reliance on powers of two.
Rationale for Bit Manipulation
The distributed bit shifting (h >>> 16) ensures a more even spread across the indices, especially crucial in smaller tables.
Handling Collisions
Collisions force elements to be stored in a LinkedList or a Tree at the same index. The performance benefit comes from reduced collision rates achieved through proper hash distribution.
Resizing Mechanics
HashMap starts with a default capacity (e.g., 16). When the number of entries exceeds a load factor (e.g., 0.75), the array resizes automatically by doubling its current size.
The load factor dictates when resizing should occur. Each put() evaluates the need for resizing, which is computationally intensive as data must be rehashed and redistributed.
LinkedList vs Tree Implementations
Collisions are initially handled by storing conflicting keys in a LinkedList. If this list exceeds a certain threshold, it's converted to a binary tree.
This conversion is expensive but advantageous because binary trees provide faster lookups than LinkedLists, as they search logarithmically rather than linearly.
Step-by-Step Usage
Consider:
HashMap myMap = new HashMap();
myMap.put("Name","Sam"); 1) Calculate hash for "Name".
2) Determine index from hash: i = (n - 1) & hash.
3) Check if the location i is empty.
4) If empty, store key/value at i.
5) If not, use equals() to check equality.
6) Replace if keys are equal.
7) Traverse and search till end of LinkedList or tree.
8) Insert new entry if no match is found.
Efficiency and Performance
Resizing and converting data structures (LinkedList/Tree) comes at a computational cost. A well-distributed hashCode lessens collisions, allowing for O(1) lookups primarily. However, excessive collisions can degrade performance to O(n).
Optimizing the initial capacity relative to expected usage patterns minimizes these expensive operations. For heavy entry scenarios, a higher initial capacity is advisable, while lower capacity suits smaller data sets.
FAQ
How do I prevent HashMap resizing?
To reduce resizing, initialize your HashMap with a high initial capacity relative to the expected number of entries.
What is the default load factor in HashMap?
The default load factor of a HashMap is 0.75, balancing time and space costs.
Why is hash function efficiency critical?
An efficient hash function distributes entries evenly, minimizing collisions and maximizing performance.
