HashMap vs LinkedHashMap vs TreeMap in Java

By the end of this page, you will understand how HashMap, LinkedHashMap, TreeMap, and Hashtable differ in Java. You will learn how they store entries, whether they preserve order, how they handle null, and when each one is the right choice.

A Map in Java stores data as key-value pairs. The key is used to look up the value.

All of these classes implement the Map interface, so they share common methods such as:

• put(key, value)
• get(key)
• keySet()
• values()
• entrySet()

That is why they can look similar at first.

The real difference is how they store data internally and what guarantees they provide.

HashMap

HashMap stores entries based on the hash of the key.

Key characteristics:

• Does not guarantee iteration order
• Usually provides very fast put() and get() operations
• Allows one null key and multiple null values
• Best when you want fast lookup and do not care about order

LinkedHashMap

LinkedHashMap is like HashMap, but it also keeps a linked list of entries.

Key characteristics:

• Preserves insertion order by default
• Slightly more memory overhead than HashMap
• Allows one null key and multiple null values
• Useful when you want predictable iteration order

TreeMap

TreeMap stores keys in sorted order.

Key characteristics:

• Keys are kept sorted by their natural order or by a provided Comparator
• Slower than HashMap for basic operations because it maintains sorted structure
• Does not allow null keys in normal use
• Useful when you need ordered keys, ranges, or sorted output

Hashtable

Hashtable is an older map class from early Java.

Key characteristics:

• Synchronized, so its methods are thread-safe at the method level
• Does not allow null keys or null values
• Considered legacy in most modern Java code
• Usually replaced by:
  • HashMap for non-threaded use
  • ConcurrentHashMap for thread-safe high-performance use

Why your output can look similar

All three maps contain mostly the same data in your example. Also, one of the keys is repeated:

m1.put("schildt", "java2");
m1.put("schildt", "java2s");

A Map cannot have duplicate keys, so the second put() replaces the first value.

That means the final data is effectively:

• map -> ...
• schildt -> java2s
• mathew -> Hyden

If you print a small set of entries, the outputs may appear similar, but the important part is:

• HashMap: order is unspecified
• LinkedHashMap: order follows insertion order
• TreeMap: order is sorted by key

These differences matter a lot in real programs, especially when iteration order affects output, UI, reports, testing, or API responses.

Think of the three map types like three ways of storing index cards.

• HashMap: you throw cards into labeled buckets for fast access. It is efficient, but the cards are not arranged in a human-friendly order.
• LinkedHashMap: same fast buckets, but you also keep a string connecting cards in the order you added them.
• TreeMap: you place cards on a shelf in alphabetical order, so they are always sorted.
• Hashtable: an older locked cabinet version of HashMap. Safe in simple threaded situations, but older and less commonly used now.

So the main question is not "Do they all have keySet()?" The main question is:

How should the entries be organized, and what behavior do you need?

The common syntax is similar because all of them implement Map.

Basic syntax

Map<String, String> hashMap = new HashMap<>();
Map<String, String> linkedHashMap = new LinkedHashMap<>();
Map<String, String> treeMap = new TreeMap<>();

Example showing ordering differences

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

public class MapExample {
    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
        Map<String, Integer> treeMap = new TreeMap<>();

        String[] keys = {"banana", "apple", "cherry"};

        for (String key : keys) {
            hashMap.put(key, key.length());
            linkedHashMap.put(key, key.length());
            treeMap.put(key, key.length());
        }

        System.out.println("HashMap: " + hashMap);
        System.out.println("LinkedHashMap: " + linkedHashMap);
        System.out.println("TreeMap: " + treeMap);
    }
}

Possible output:

HashMap: {banana=6, apple=5, cherry=6}
LinkedHashMap: {banana=6, apple=5, cherry=6}
TreeMap: {apple=5, banana=6, cherry=6}

Notes:

• LinkedHashMap preserves the insertion order: banana, apple, cherry
• TreeMap sorts keys alphabetically
• HashMap may appear in a similar order sometimes, but that order is not guaranteed

Duplicate keys replace old values

Map<String, String> map = new HashMap<>();
map.put("name", "Alice");
map.put("name", "Bob");

System.out.println(map);

Output:

{name=Bob}

A map stores unique keys, so the second value overwrites the first.

Consider this example:

Map<String, String> map = new LinkedHashMap<>();
map.put("b", "Ball");
map.put("a", "Apple");
map.put("c", "Cat");
map.put("a", "Ant");

System.out.println(map.keySet());
System.out.println(map.values());

Step by step:

1. Create an empty LinkedHashMap

   • It starts with no entries.

2. map.put("b", "Ball")

   • Adds key b with value Ball
   • Map becomes: {b=Ball}

3. map.put("a", "Apple")

   • Adds key a with value Apple
   • Map becomes: {b=Ball, a=Apple}

4. map.put("c", "Cat")

   • Adds key c with value Cat
   • Map becomes: {b=Ball, a=Apple, c=Cat}

5. map.put("a", "Ant")

   • Key a already exists
   • Its value changes from Apple to Ant
   • The key is not duplicated
   • Map becomes: {b=Ball, a=Ant, c=Cat}

6. map.keySet()

   • Returns the keys in insertion order
   • Output: [b, a, c]

7. map.values()

   • Returns values in the same entry order
   • Output: [Ball, Ant, Cat]

If this were a TreeMap, the final order would be sorted by key:

• keys: [a, b, c]
• values: [Ant, Ball, Cat]

If this were a HashMap, the order would be unspecified.

When to use HashMap

Use HashMap when you want fast access and do not care about order.

Examples:

• Caching user settings by user ID
• Counting word frequency in a text file
• Mapping product codes to product details
• Looking up configuration values by key

When to use LinkedHashMap

Use LinkedHashMap when you want fast access and predictable iteration order.

Examples:

• Showing form fields in the same order they were configured
• Preserving JSON-like field order for readable output
• Building LRU-style caches using access-order mode
• Keeping log or report data in the order it was inserted

When to use TreeMap

Use TreeMap when sorted keys are important.

Examples:

• Ranking scores by key order
• Storing dates in sorted order
• Producing alphabetical reports
• Range queries such as "all keys from A to M"

When Hashtable appears

You may still see Hashtable in:

• Older Java codebases
• Legacy libraries
• Interview questions about Java collections history

In new code, it is uncommon unless you are maintaining existing software.

In real codebases, developers usually choose a map implementation based on the behavior they need rather than the interface methods.

Common patterns

1. Fast lookup with HashMap

Map<String, Integer> inventory = new HashMap<>();
inventory.put("PEN", 120);
inventory.put("BOOK", 45);

Used for:

• Lookup tables
• Counters
• ID-to-object mappings

2. Predictable output with LinkedHashMap

Map<String, String> headers = new LinkedHashMap<>();
headers.put("Content-Type", "application/json");
headers.put("Accept", "application/json");

Useful when output order should stay stable for:

• Logs
• Reports
• API payload generation
• Test assertions

3. Sorted processing with TreeMap

Map<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 88);
scores.put("Alice", 95);
scores.put("Bob", 91);

Useful for:

• Sorted displays
• Leaderboards by key
• Prefix/range processing

4. Validation before inserting into a TreeMap

Because TreeMap does not normally allow null keys, code often checks first:

if (key != null) {
    treeMap.put(key, value);
}

5. Legacy thread-safe maps

Older code may use:

Map<String, String> table = new Hashtable<>();

Modern code more often uses:

Map<String, String> table = new java.util.concurrent.ConcurrentHashMap<>();

That is usually better for concurrent programs.

Important practice

Most code declares the variable as the interface type:

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

This makes it easier to switch implementations later.

1. Assuming HashMap keeps insertion order

Broken assumption:

Map<String, Integer> map = new HashMap<>();
map.put("first", 1);
map.put("second", 2);
map.put("third", 3);

System.out.println(map);

Problem:

• The order may look correct on one run or one JDK version
• But Java does not guarantee that order for HashMap

Fix:

• Use LinkedHashMap if order matters

2. Expecting duplicate keys to create multiple entries

Broken code:

Map<String, String> map = new HashMap<>();
map.put("x", "one");
map.put("x", "two");

System.out.println(map);

Result:

{x=two}

Fix:

• Remember that keys are unique
• If you need multiple values per key, use something like Map<String, List<String>>

3. Using TreeMap without understanding sorting

Map<String, Integer> map = new TreeMap<>();
map.put("10", 10);
map.put("2", 2);
map.put("1", 1);
System.out.println(map);

Output:

{1=1, 10=10, 2=2}

Problem:

• Strings are sorted lexicographically, not numerically

Fix:

• Use Integer keys if you want numeric ordering

4. Inserting null keys into TreeMap

Broken code:

Map<String, String> map = new TreeMap<>();
map.put(null, "value");

Problem:

• This causes a NullPointerException

Fix:

• Avoid null keys in TreeMap
• Validate input before insertion

5. Using Hashtable in new code without a reason

Problem:

• It is old and less flexible than modern alternatives

Fix:

• Use HashMap for normal use
• Use ConcurrentHashMap for modern concurrent use

6. Comparing values() as if they were independently ordered

The order of values() follows the order of the map's entries.

• In LinkedHashMap, values follow insertion order
• In TreeMap, values follow sorted key order
• In HashMap, values follow unspecified entry order

HashMap vs LinkedHashMap

• Choose HashMap when order does not matter
• Choose LinkedHashMap when you want insertion order preserved

LinkedHashMap vs TreeMap

• LinkedHashMap keeps insertion order
• TreeMap keeps sorted order

HashMap vs TreeMap

• HashMap is usually faster for simple lookups
• TreeMap is better when sorted traversal is required

Hashtable vs HashMap

• Hashtable is older and synchronized
• HashMap is newer, more commonly used, and allows null
• For concurrent access today, ConcurrentHashMap is often preferred over Hashtable

Map<K, V> map = new HashMap<>();        // fast, no order guarantee
Map<K, V> map = new LinkedHashMap<>();  // insertion order
Map<K, V> map = new TreeMap<>();        // sorted by key
Map<K, V> map = new Hashtable<>();      // legacy synchronized map

Rules to remember

• A Map stores unique keys
• Adding the same key again replaces the old value
• keySet() returns keys
• values() returns values in entry iteration order
• entrySet() returns key-value pairs

Ordering

• HashMap: unspecified
• LinkedHashMap: insertion order
• TreeMap: sorted key order
• Hashtable: unspecified

Null handling

• HashMap: 1 null key, many null values
• LinkedHashMap: 1 null key, many null values
• TreeMap: no null key
• Hashtable: no null key, no null values

Quick choice guide

• Need fastest general-purpose map: HashMap
• Need stable insertion order: LinkedHashMap
• Need sorted keys: TreeMap
• Maintaining old legacy code: Hashtable

Common gotcha

map.put("a", 1);
map.put("a", 2);

Result:

{a=2}

Why do HashMap, LinkedHashMap, and TreeMap all have similar methods?

Because they all implement the Map interface. They expose similar operations but differ in ordering, performance, and null handling.

Why does my HashMap sometimes print in insertion order?

That can happen by chance for a small example, but Java does not guarantee it. You should not rely on that behavior.

Does TreeMap sort by keys or values?

TreeMap sorts by keys, not by values.

Can a map contain duplicate keys?

No. A map keeps unique keys. Adding the same key again replaces its value.

What is the difference between Hashtable and HashMap?

Hashtable is an older synchronized map that does not allow null. HashMap is more common in modern Java and allows null.

Is Hashtable obsolete?

It is still part of Java, but it is considered legacy for most new code.

Which map should I use most of the time?

Usually HashMap, unless you specifically need insertion order (LinkedHashMap) or sorted keys (TreeMap).

When should I use ConcurrentHashMap instead?

Use it when multiple threads need to read and write a map safely and efficiently.

• Map interface — The common contract implemented by HashMap, LinkedHashMap, TreeMap, and Hashtable.
• Set — keySet() returns a set of keys, so understanding sets helps explain uniqueness.
• Comparator — TreeMap can use a comparator to define custom key ordering.
• equals and hashCode — HashMap relies on these methods for correct key behavior.
• Collections Framework — These classes are all part of Java's core collections system.
• ConcurrentHashMap — A modern thread-safe alternative often used instead of Hashtable.
• ArrayList vs LinkedList — Another useful comparison showing how data structure choice affects behavior.
• SortedMap — The interface that represents maps whose keys are maintained in sorted order.