Java HashMap Interview Questions

Key Takeaways

• HashMap in Java is implemented as an array indexed by hashed keys, providing O(1) access time in optimal conditions.
• Initial capacity and load factor are critical to HashMap performance; resizing overhead can be costly.
• HashMap is not thread safe; for thread safety, consider using ConcurrentHashMap.

1) How does put() work?

When you call put() with a key/value pair in a HashMap, the key's hashCode() is used to compute the index in an internal array. If the index is empty, the key/value pair is inserted directly. If there's an existing entry (a collision), the entries are managed as a linked list or a binary tree at that position.

2) What is a HashMap's initial capacity?

The initial capacity is the size of the array initially used by the HashMap to store elements. By default, this capacity is 16. A low initial capacity might increase resizing frequency, while a higher initial capacity is suitable for larger datasets to minimize resizing costs.

3) How is HashMap implemented in Java?

A HashMap is primarily implemented as an array, where the array indices are calculated from the hash values of the keys. This design ensures very fast lookups and assignments, generally resulting in constant time complexity, O(1), under normal circumstances.

4) What does put() return with a new key?

When put() is invoked with a new key, it returns null since there was no prior association for that key.

5) What is the time complexity of get()?

The time complexity of retrieving a value using get() is generally O(1), owing to direct index-based access in the array. However, in worst-case scenarios (many collisions), this can degrade to O(log n) if many elements map to the same index and form a tree structure.

6) What is the performance cost of the initial capacity being too low?

A HashMap with a low initial capacity may frequently exceed its load factor, triggering costly resizing operations. Resizing involves creating a new array and rehashing all entries, which is computationally expensive.

7) What is the performance cost of the initial capacity being too high?

If the initial capacity is set too high, and the number of elements is low relative to the capacity, it can lead to inefficient memory usage and unnecessary iteration over empty slots in the array, degrading performance due to cache misses.

8) What is the load factor?

The load factor determines when the resizing of the HashMap occurs. The default load factor is 0.75, meaning the map will resize and expand its capacity when 75% of the current capacity is full, balancing time and space efficiency.

9) What is capacity?

Capacity refers to the number of buckets, or slots, used to hold entries in the Map. It's a critical factor that influences performance, particularly when dealing with large datasets.

10) What is collision?

A collision happens when two distinct keys have the same calculated index in the underlying array. In such cases, these entries are stored in a linked list format at the shared index, and potentially as a binary tree if the list grows beyond a predefined threshold.

11) How is collision handled in the HashMap implementation?

In response to collisions, Java stores multiple entries with the same index as a linked list in earlier versions or a balanced tree (after Java 8) when a threshold is reached, optimizing both memory and access times on average.

12) Is HashMap thread safe?

No, HashMap is not thread safe by design. For synchronized access in concurrent situations, consider using ConcurrentHashMap or explicitly synchronizing access to the HashMap.

FAQ

Why is the default load factor set to 0.75?

The default load factor of 0.75 offers a good trade-off between space and time complexity, minimizing the frequency of resizing while maintaining efficient lookup times.

What is the difference between HashMap and Hashtable?

A HashMap is not synchronized and is generally faster, while Hashtable is synchronized, making it thread safe but typically slower. For modern multithreaded environments, ConcurrentHashMap is preferred.

When should you manually adjust the initial capacity and load factor?

Manual adjustment is useful in performance-critical applications dealing with large data sets, where minimizing resizing operations or optimizing memory usage is necessary.

Can a mutable object be a valid key in a HashMap?

While technically possible, using mutable objects as keys can lead to unpredictable behavior if their hash codes change during their time in the map, complicating retrieval and potentially causing data loss.