Difference between HashMap and TreeMap.

HashMap and TreeMap are both implementations of the Map interface used to store key-value pairs. The main difference is that HashMap stores entries without maintaining any order, while TreeMap automatically keeps entries sorted based on their keys. HashMap generally offers faster performance, whereas TreeMap is preferred when sorted data is required.

Key Points: • HashMap does not guarantee any ordering of keys. • TreeMap stores keys in sorted order by default. • HashMap uses hashing, while TreeMap uses a Red-Black Tree. • HashMap provides faster average performance for most operations. • TreeMap supports sorted and range-based operations.

Internal Implementation

HashMap:

• Uses an array of buckets. • Relies on hashCode() and equals(). • Handles collisions using Linked Lists or Red-Black Trees (Java 8+).

TreeMap:

• Uses a Red-Black Tree. • Maintains keys in sorted order. • Uses Comparable or Comparator for sorting.

Ordering

HashMap:

No ordering guarantee.

Example:

{103=Mike, 101=John, 102=David}

Output order may vary.

TreeMap:

Automatically sorts keys.

Example:

{101=John, 102=David, 103=Mike}

Time Complexity

HashMap:

• put() → O(1) average • get() → O(1) average • remove() → O(1) average

TreeMap:

• put() → O(log n) • get() → O(log n) • remove() → O(log n)

Null Handling

HashMap:

• Allows one null key. • Allows multiple null values.

TreeMap:

• Does not allow null keys. • Allows multiple null values.

Example:

HashMap<String, String> map =
        new HashMap<>();

map.put(null, "Java");

Valid.

TreeMap<String, String> map =
        new TreeMap<>();

map.put(null, "Java");

Throws NullPointerException.

Sorting Support

HashMap:

• No sorting support.

TreeMap:

• Supports natural ordering. • Supports custom sorting using Comparator.

Example: Suppose we are storing employee records.

If ordering is not important:

Use HashMap.

If records must be displayed in ascending employee ID order:

Use TreeMap.

Code Example:

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

public class Demo {

    public static void main(String[] args) {

        Map<Integer, String> hashMap =
                new HashMap<>();

        hashMap.put(103, "Mike");
        hashMap.put(101, "John");
        hashMap.put(102, "David");

        Map<Integer, String> treeMap =
                new TreeMap<>();

        treeMap.put(103, "Mike");
        treeMap.put(101, "John");
        treeMap.put(102, "David");

        System.out.println(hashMap);

        System.out.println(treeMap);
    }
}

Output:

HashMap: Order not guaranteed

TreeMap: {101=John, 102=David, 103=Mike}

When to Use HashMap?

• Fast lookups are required. • Ordering is not important. • Maximum performance is preferred.

Examples:

• Caching • Session storage • Configuration data

When to Use TreeMap?

• Sorted data is required. • Range-based searches are needed. • First, last, higher, or lower key operations are required.

Examples:

• Leaderboards • Ranking systems • Sorted reports • Employee records sorted by ID

Comparison Table

Feature HashMap TreeMap

Ordering No Sorted by Key

Internal Structure Hash Table Red-Black Tree

Insertion O(1) O(log n)

Retrieval O(1) O(log n)

Deletion O(1) O(log n)

Null Key One Allowed Not Allowed

Null Values Allowed Allowed

Sorting Support No Yes

Interview Tip: A concise interview answer is:

"HashMap stores key-value pairs without maintaining any order and provides O(1) average-time performance using hashing. TreeMap stores entries in sorted key order using a Red-Black Tree and provides O(log n) performance for insertion, retrieval, and deletion. Use HashMap when speed is important and TreeMap when sorted data is required."