"Background"

HashMap is a popular implementation of the Map interface in Java. It stores data in key-value pairs and uses a hash table for efficient lookups. Here’s a breakdown of how it works:

1. Internal Structure

  • Buckets: The underlying data structure is an array of linked lists (or a binary tree for optimization in Java 8+).
  • Hash Function: A key’s hash code determines its bucket index.
  • Collision Handling: Multiple keys that map to the same bucket are handled using:
  • Separate Chaining: A linked list stores entries in the same bucket.
  • Treeification (Java 8+): If a bucket’s size exceeds a threshold (default 8), it is converted to a red-black tree for faster lookups.

2. Key Operations

a. Adding an Entry put()

  • Calculate the hash code: The key’s hashCode() method is called to generate a hash.
  • Find the bucket: The hash is converted into a bucket index using index = hash % capacity.
  • Store the entry:
    • If the bucket is empty, the key-value pair is added.
    • If a collision occurs, the key-value pair is added to the linked list or tree in the bucket.
    • If the key already exists, its value is updated.

b. Retrieving a Value get()

  • Calculate the hash code of the key.
  • Find the bucket using the hash.
  • Search the bucket for the key:
    • For a linked list, it traverses the list.
    • For a tree, it uses tree traversal (logarithmic time).

c. Removing an Entry remove()

  • Calculate the hash code and locate the bucket.
  • Remove the key-value pair:
    • For a linked list, remove the corresponding node.
    • For a tree, rebalance it after removal.

3. Important Features

  • Efficiency: Provides O(1) average time complexity for put(), get(), and remove().
  • Capacity and Load Factor:
    • Initial capacity (default: 16) determines the size of the internal array.
    • Load factor (default: 0.75) decides when to resize the map (e.g., at 75% capacity).
  • Resizing: When the number of entries exceeds capacity × load factor, the hash table is resized (usually doubled), and all entries are rehashed.

4. Collision Handling in Depth

  • Separate Chaining (Linked List): Multiple entries in the same bucket are stored in a linked list.
  • Treeification (Java 8+): If a bucket’s linked list grows too long (more than 8 entries), it is converted to a red-black tree for faster lookups (O(log n)).

5. Null Keys and Values

  • HashMap allows:
    • One null key.
    • Multiple null values.
  • The null key always maps to the first bucket (index 0).

6. Fail-Fast Behavior

Iterators of HashMap are fail-fast, meaning they throw a ConcurrentModificationException if the map is modified structurally during iteration (except through the iterator itself).

Common Use Cases

  • Caching data for quick lookups.
  • Counting occurrences of elements (e.g., frequency of words).
  • Implementing associations like ID-to-name mappings.

Interview Questions

  • How does HashMap handle collisions?
  • What is the time complexity of put() and get() operations in HashMap?
  • How does treeification work in Java 8+ HashMap?
  • Why is the load factor important, and how does resizing work in HashMap?
  • Can a HashMap have null keys and values? How does it handle them?

Check out the video for a detailed explanation: