Introduction

HashMap and TreeMap both store key-value pairs, but they optimize for different properties. HashMap optimizes for fast average-case lookup and insertion with no ordering guarantee, while TreeMap maintains keys in sorted order and pays logarithmic cost to do it.

So if the question is specifically insertion complexity, the usual summary is: HashMap is average-case O(1) amortized, and TreeMap is O(log n). The useful part is understanding why that difference exists and when it matters in practice.

Why HashMap Is Usually Faster

HashMap uses a hash table. It computes a bucket index from the key’s hash code and then inserts the entry into that bucket. If the hash function spreads keys well, the map touches only a small part of its internal structure for each insertion.

1import java.util.HashMap;
2import java.util.Map;
3
4public class Main {
5    public static void main(String[] args) {
6        Map<Integer, String> map = new HashMap<>();
7        map.put(10, "ten");
8        map.put(20, "twenty");
9        map.put(30, "thirty");
10        System.out.println(map.get(20));
11    }
12}

The average insertion cost is constant time, but it is still called amortized because occasional resize operations rehash existing entries.

Why TreeMap Costs O(log n)

TreeMap uses a balanced search tree, specifically a red-black tree in Java. Each insertion must find the correct sorted position for the new key and may rebalance the tree afterward.

1import java.util.Map;
2import java.util.TreeMap;
3
4public class Main {
5    public static void main(String[] args) {
6        Map<Integer, String> map = new TreeMap<>();
7        map.put(20, "twenty");
8        map.put(10, "ten");
9        map.put(30, "thirty");
10        System.out.println(map.keySet());
11    }
12}

The output stays ordered because the tree structure maintains key ordering, and that maintenance is what costs O(log n) per insertion.

Worst-Case Nuance for HashMap

Older explanations often say HashMap insertion can degrade to O(n) in the worst case because too many keys collide into one bucket. Conceptually that is still the important warning: poor hashing can destroy constant-time expectations.

In modern Java, heavy collision buckets may be treeified, which improves the worst case for those buckets. Even so, the practical design message remains the same: HashMap is fastest when hashes distribute well, while TreeMap gives predictable sorted behavior regardless of hashing.

Choose Based on Required Behavior

Use HashMap when:

• you do not need sorted keys
• average insertion and lookup speed matter most
• the key type has a good hashCode implementation

Use TreeMap when:

• you need keys sorted
• you need range operations such as headMap or tailMap
• deterministic ordered iteration matters

The map type should be chosen by required behavior first, not only by the big-O line in a table.

Ordered Iteration Is the Real Tradeoff

The reason teams keep using TreeMap despite the extra insertion cost is that sorted iteration is built in. If you need keys in natural order, nearest-key lookups, or subrange views, TreeMap avoids an extra sorting step later. If you only need fast key lookup and do not care about order, paying O(log n) on every insertion is usually wasted work.

Common Pitfalls

• Choosing TreeMap when no ordering feature is actually needed.
• Assuming HashMap is always constant time with no collision caveats.
• Ignoring the cost of resizing when discussing HashMap performance.
• Using keys with poor hashCode implementations and then blaming the data structure.
• Focusing only on insertion cost and forgetting lookup, iteration order, and range-query needs.

Summary

• 'HashMap insertion is usually O(1) amortized on average.'
• 'TreeMap insertion is O(log n) because it maintains sorted order in a balanced tree.'
• 'HashMap can degrade under collisions, though modern Java reduces the damage in some cases.'
• 'TreeMap is slower for insertion but provides ordered keys and range operations.'
• Pick the structure based on behavior requirements, not on one complexity number in isolation.