HashMap vs LinkedHashMap vs TreeMap in Java (A Beginner’s Guide)

HashMap vs LinkedHashMap vs TreeMap in java explained simply. Compare order, speed, and null handling, and learn exactly when to use each Java Map class.

1. Introduction

You have a bunch of data, and each piece has a name. A student has a roll number, a product has an ID, and a country has a capital. To store and look up such pairs, Java gives you the Map interface and three main classes: HashMap vs LinkedHashMap vs TreeMap.

So what does a Map actually do? It stores things as key-value pairs. You give it a key, and it hands back the matching value.

A plain array won’t help much here. Arrays use number positions, not names. So you can’t just ask for the value under the key “India” and get “New Delhi” back.

In this article, we’ll start with the Map interface itself. After that, we’ll compare its three main classes: HashMap, LinkedHashMap, and TreeMap. Each one stores pairs, but each behaves a little differently.

Here’s what we’ll cover:

• What a Map actually is, and how it differs from a List
• Keys, values, and the rule that keys must be unique
• How HashMap works, and why it’s so fast
• The way LinkedHashMap keeps your insertion order
• Why TreeMap keeps everything sorted
• A side-by-side comparison, plus common mistakes and interview questions

No prior Map knowledge is needed. If you know what a Java List is, you’re ready to go.

2. What Is a Map?

A Map is a collection of key-value pairs. Think of a real dictionary. You look up a word, the key, and you read its meaning, the value.

There’s no flipping through page by page. You jump straight to the word and read what’s next to it. A Java Map works in that same spirit.

2.1 Keys and Values

Every entry in a Map has two parts: a key and a value. The key is how you find things. The value is what you get back.

Say you store phone contacts. The name is the key, and the number is the value. Ask for “Mom”, and you get her number. Simple and direct.

2.2 Keys Must Be Unique

A Map does not allow duplicate keys. Each key can point to only one value at a time. This is a core rule, so keep it in mind.

What if you put the same key twice? The new value simply replaces the old one. Nothing breaks, but the earlier value is gone.

Values, on the other hand, can repeat freely. Two different keys can hold the same value with no problem at all.

2.3 Map Is Not Part of Collection

Here’s a fact that surprises beginners. The Map interface does not extend Collection. A List and a Set both come from Collection, but a Map stands on its own.

Why the split? A Collection holds single items. A Map holds pairs. Two things per entry just don’t fit the single-item model, so Map gets its own family tree.

2.4 Map vs List: A Quick Comparison

It helps to see them side by side. Both store data, yet they answer very different questions.

So you pick a List when you care about order and position. You pick a Map when you care about looking things up by a name.

2.5 The Everyday Map Methods

Before we go deeper, here’s a quick tour of the methods you’ll use daily. You don’t need to memorize them yet. Just know they exist.

• put(key, value) — add or update a pair.
• get(key) — read the value for a key.
• containsKey(key) — check if a key is present.
• remove(key) — delete a pair by key.
• keySet() — get all the keys.
• values() — get all the values.
• entrySet() — get all the key-value pairs together.
• size() — how many pairs are in the map.

That handful covers most real work. We’ll see several of them in action below.

Map<String, String> capitals = new HashMap<>();
capitals.put("India", "New Delhi");
capitals.put("Japan", "Tokyo");
capitals.put("India", "Mumbai");   // replaces New Delhi
 
System.out.println(capitals.get("India"));  // Output: Mumbai
System.out.println(capitals.size());         // Output: 2

Notice the left side says Map, not HashMap. This is a good habit. You code to the interface, so swapping the class later stays easy.

3. HashMap: The Fast Default

HashMap is the Map you’ll reach for most of the time. It’s quick, it’s simple, and it handles the common cases well.

3.1 How HashMap Finds Things So Fast

The secret is hashing. When you add a key, HashMap runs it through a hash function. That gives back a number, which points to a slot, often called a bucket.

So the key isn’t searched for one by one. Instead, HashMap computes where it should live and jumps straight there. That’s why lookups feel instant.

Because of this, get() and put() run in O(1) time on average. It doesn’t matter if the map holds ten keys or ten million. The lookup stays roughly the same speed.

3.2 No Guaranteed Order

Here’s the catch with HashMap. It does not keep any order. The pairs come out in whatever arrangement the hashing decides.

Add keys in the order A, B, C, and you might read them back as B, A, C. Or C, B, A. There’s no promise either way.

Map<String, Integer> ages = new HashMap<>();
ages.put("Amy", 30);
ages.put("Ben", 25);
ages.put("Cara", 28);
 
System.out.println(ages);
// Possible output: {Ben=25, Amy=30, Cara=28}
// The order is not guaranteed

So if order doesn’t matter to you, HashMap is perfect. If it does, keep reading. The next two classes solve that.

3.3 Nulls Are Allowed

A HashMap lets you store one null key. It also lets you store null values, as many as you like. This can be handy, though you should use it with care.

TreeMap does not share this freedom, as we’ll see soon. So this is one small point in HashMap’s favor.

4. LinkedHashMap: Order That Remembers

LinkedHashMap is a HashMap with a memory for order. It does everything HashMap does, and it also keeps track of how you added things.

4.1 It Keeps Insertion Order

When you loop over a LinkedHashMap, the pairs come out in the order you put them in. First in, first out during a read. That’s the main draw.

How? It links each entry to the next one behind the scenes, like a chain. That chain remembers the sequence, even though the fast hashing still works underneath.

Map<String, Integer> ages = new LinkedHashMap<>();
ages.put("Amy", 30);
ages.put("Ben", 25);
ages.put("Cara", 28);
 
System.out.println(ages);
// Output: {Amy=30, Ben=25, Cara=28}
// Same order you added them

Run that a hundred times, and the output stays the same. That predictability is the whole point of this class.

4.2 Almost as Fast as HashMap

You might worry that keeping order slows things down. It barely does. The extra chain adds a tiny bit of memory and a small overhead, nothing more.

So get() and put() are still O(1) on average. You gain predictable order at a very small cost. For many apps, that’s a great deal.

4.3 When You’d Pick It

Reach for LinkedHashMap when order matters but you don’t need sorting. A few good examples come up often:

• Showing items in the exact order a user entered them.
• Building a simple cache where the oldest entry leaves first.
• Printing a map in a clean, repeatable way for logs or tests.

In each case, you want the order to stay stable. HashMap can’t promise that, but LinkedHashMap can.

5. TreeMap: Always Sorted

TreeMap takes a different path. It keeps your keys in sorted order at all times. Add them in any sequence, and they come out sorted.

5.1 Sorted by Key

By default, TreeMap sorts keys in their natural order. Strings go alphabetically. Numbers go smallest to largest. You get sorting for free.

Map<String, Integer> ages = new TreeMap<>();
ages.put("Cara", 28);
ages.put("Amy", 30);
ages.put("Ben", 25);
 
System.out.println(ages);
// Output: {Amy=30, Ben=25, Cara=28}
// Sorted by key, no matter the add order

See how Cara went in first but comes out last? TreeMap re-sorts on every insert, so the read is always in order.

5.2 Backed by a Red-Black Tree

Under the hood, TreeMap uses a balanced tree called a red-black tree. You don’t need the deep theory here. Just know it keeps the tree neat and even.

Because of that tree, operations like get() and put() run in O(log n) time. That’s slower than HashMap’s O(1), but still very fast for most sizes.

So you pay a little speed to gain sorted order. Whether that trade is worth it depends on your needs.

5.3 No Null Keys

TreeMap has one strict rule. You cannot use a null key. If you try, it throws a NullPointerException right away.

Why? To sort keys, TreeMap must compare them. You can’t compare null to anything, so it simply refuses. Values may still be null, though.

5.4 Handy Sorted Methods

Sorting unlocks some extra tricks. Since keys sit in order, TreeMap can answer range questions that HashMap can’t:

• firstKey() and lastKey() — the smallest and largest keys.
• floorKey(k) — the largest key less than or equal to k.
• ceilingKey(k) — the smallest key greater than or equal to k.
• headMap(k) and tailMap(k) — a slice of keys below or above k.

These come from the NavigableMap interface. They’re a big reason people choose TreeMap over the faster HashMap.

6. HashMap vs LinkedHashMap vs TreeMap

Now let’s put all three next to each other. This is the part most people come here for, so let’s keep it clear.

6.1 The Full Comparison Table

Here’s the whole picture at a glance:

6.2 A Simple Way to Choose

Don’t overthink it. Ask yourself one question about order, and the answer usually falls out:

• Don’t care about order? Use HashMap. It’s the fastest and the default.
• Want the order you added things? Use LinkedHashMap.
• Want keys always sorted? Use TreeMap.

That’s really the heart of it. Speed favours HashMap, but the other two earn their place when order is part of the job.

6.3 A Quick Real-World Feel

Picture three small tasks to make it stick:

• Counting word frequency in a file — HashMap, since order means nothing here.
• Remembering the order pages were visited — LinkedHashMap, to keep the trail intact.
• Showing a leaderboard sorted by score — TreeMap, so ranks line up on their own.

Same data shape, three different needs. The right Map makes each one easier.

7. A Practical Walkthrough

Let’s tie it together with a small task. Say you’re counting how many times each word shows up in a sentence.

7.1 Counting with getOrDefault

A clean trick uses getOrDefault(). It reads the current count, or gives 0 if the key is new. Then you add one and put it back.

String text = "cat dog cat bird dog cat";
Map<String, Integer> count = new HashMap<>();
 
for (String word : text.split(" ")) {
    count.put(word, count.getOrDefault(word, 0) + 1);
}
 
System.out.println(count);
// Output (order may vary): {bird=1, cat=3, dog=2}

Short and readable. HashMap fits here because we don’t care what order the words print in.

7.2 Want Sorted Output? Swap the Class

Suppose your boss wants the words listed alphabetically. You don’t rewrite the loop. You just change one word: HashMap becomes TreeMap.

Map<String, Integer> count = new TreeMap<>();  // only change
 
for (String word : text.split(" ")) {
    count.put(word, count.getOrDefault(word, 0) + 1);
}
 
System.out.println(count);
// Output: {bird=1, cat=3, dog=2}  (always sorted)

This is the payoff of coding to the Map interface. The logic stays the same, and only the behaviour you need changes.

7.3 Looping Over Entries

Often you want both the key and the value together. The cleanest way is entrySet(). It hands you each pair in one shot.

for (Map.Entry<String, Integer> entry : count.entrySet()) {
    String word = entry.getKey();
    int times = entry.getValue();
    System.out.println(word + " appears " + times + " times");
}

This reads well and avoids extra lookups. Calling get() inside a keySet() loop would work too, but it does more work than needed.

8. Common Mistakes and Pitfalls

A few traps catch beginners again and again. Let’s name them so you can dodge them.

8.1 Bad hashCode and equals on Keys

If your key is a custom class, you must override hashCode() and equals(). Skip them, and the map may store duplicates or fail to find keys.

Two objects that you think are equal will land in different buckets. So the map treats them as separate keys, which is rarely what you want.

8.2 Expecting Order from a HashMap

Never rely on HashMap for order. Your test might pass today and fail tomorrow. If order matters, pick LinkedHashMap or TreeMap instead.

8.3 Using a Null Key with TreeMap

A null key crashes a TreeMap with a NullPointerException. If nulls are possible, either clean them out first or use a HashMap for that part.

8.4 Changing a Key After Insertion

Don’t change an object after using it as a key. Its hash may shift, and then the map loses track of it. Keys should stay unchanged, or immutable, once stored.

9. Interview Questions

10. Conclusion

Let’s wrap up what we covered. A Map stores key-value pairs, keeps keys unique, and lets you look up values fast by their key.

HashMap gives you raw speed with no order. LinkedHashMap adds insertion order for a tiny cost. TreeMap keeps keys sorted, trading a bit of speed for that.

So choose based on order. No order needed? Go HashMap. Insertion order? Go LinkedHashMap. Sorted keys? Go TreeMap.

Next up, we’ll open the HashMap internals and see exactly how buckets, hashing, and collisions play out under the hood.

Further Reading

• HashMap Internals in Java: Buckets, Hashing, and Collisions
• Set Interface in Java: HashSet, LinkedHashSet, and TreeSet
• Oracle Javadoc: java.util.Map, java.util.HashMap, and java.util.TreeMap