Java Interview Questions

HashMap is a part of the Java Collections Framework and is found in the java.util package. It provides the basic implementation of the Map interface and stores data in key-value pairs. A HashMap allows you to store and retrieve elements based on a key, which provides fast access time. It is widely used due to its efficient handling of large datasets.

Key Characteristics of HashMap

1. Key-Value Pairs: Each entry in a HashMap consists of a key and a corresponding value.
2. Unique Keys: Keys must be unique within the map. If a key is inserted that already exists, the new value will replace the old value.
3. Null Values: HashMap allows one null key and multiple null values.
4. Unordered: The elements in a HashMap are not ordered. There is no guarantee that the order will remain constant over time.

How HashMap Works

HashMap uses an array of nodes (often called buckets) and a linked list or tree structure to handle hash collisions. Here's a detailed breakdown of its workings:

1. Hashing: When a key-value pair is added to the HashMap, the key is passed through a hash function to generate a hash code. This hash code is then used to determine the index of the array (bucket) where the entry should be stored.

2. Buckets: The HashMap maintains an array of buckets. Each bucket is essentially a linked list or a balanced tree, depending on the implementation (since Java 8, it uses balanced trees if the number of elements in a bucket exceeds a certain threshold).

3. Handling Collisions: If two keys hash to the same index (a collision), they are stored in the same bucket. Initially, a linked list structure is used to store multiple entries in the same bucket. If the number of entries in a bucket exceeds a certain threshold, the linked list is converted to a balanced tree to improve performance.

4. Operations:

   • Insertion: To insert a key-value pair, the key is hashed, and the hash code determines the bucket. If the bucket is empty, the entry is added. If the bucket contains entries, the HashMap checks for duplicate keys and either updates the existing entry or adds the new entry at the end of the list/tree.
   • Retrieval: To retrieve a value, the key is hashed, and the hash code determines the bucket. The HashMap then searches through the entries in the bucket to find the key and return the associated value.
   • Deletion: To delete an entry, the key is hashed to find the bucket, and the HashMap searches for the key in the bucket and removes the entry if found.

Example Usage

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // Create a HashMap
        Map<String, Integer> map = new HashMap<>();

        // Add key-value pairs
        map.put("Apple", 10);
        map.put("Banana", 15);
        map.put("Orange", 20);

        // Retrieve value by key
        int appleCount = map.get("Apple");
        System.out.println("Apple Count: " + appleCount); // Output: Apple Count: 10

        // Remove key-value pair
        map.remove("Banana");

        // Iterate over the HashMap
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // Output: 
        // Apple: 10
        // Orange: 20
    }
}

Performance Considerations

• Time Complexity:

  • Best Case: O(1) for insertion, deletion, and retrieval.
  • Worst Case: O(n) for insertion, deletion, and retrieval, in case of many collisions and if a linked list is used. However, with balanced trees, this can be reduced to O(log n).

• Load Factor: The load factor is a measure of how full the HashMap is allowed to get before its capacity is automatically increased. The default load factor is 0.75, meaning the HashMap will be resized when it is 75% full. Resizing involves rehashing all entries, which can be an expensive operation.

When to Use HashMap

• When you need fast access to key-value pairs and the order of elements does not matter.
• When you have a large dataset and performance is critical.
• When you need to frequently insert, delete, and retrieve elements based on keys.

Conclusion

HashMap is a powerful and efficient data structure for storing and managing key-value pairs in Java. It provides constant-time performance for basic operations under typical conditions, making it a preferred choice for many applications where fast access and modification of data are required. Understanding its internal workings, such as hashing, bucket storage, and collision handling, is essential for making the most out of this versatile collection.