HashMap vs TreeMap vs LinkedHashMap in Java

Q: Is HashMap faster than TreeMap?

Yes, for single lookups and inserts: `HashMap` is O(1) on average and `TreeMap` is O(log n). Choose `TreeMap` only when you need sorted keys or range methods.

Q: Can a TreeMap have a null key?

No. With natural ordering, `put(null, value)` throws `NullPointerException`. Values can be `null`.

Q: Which map should I use in coding interviews?

`HashMap` for counting and lookups (most problems), `TreeMap` when the problem asks for the nearest, smallest or largest key, and `LinkedHashMap` for LRU cache questions.

9 min readUpdated 17 October 2026

All three store key-value pairs and share the same Map methods, so the code that uses them looks the same. What changes is the order you get the keys back in and how fast each operation is. This guide shows the difference side by side and tells you which one to pick.

The short answer

Use HashMap by default: fastest, no order.
Use LinkedHashMap when you need the keys back in the order you inserted them (or for a simple LRU cache).
Use TreeMap when you need the keys sorted, or questions like "the largest key below 50".

Comparison table

All three are not thread safe. Use ConcurrentHashMap when many threads write to one map.
	HashMap	LinkedHashMap	TreeMap
Key order	No order you can rely on	Insertion order (or access order)	Sorted by key
get / put / remove	O(1) on average	O(1) on average	O(log n)
Inside	Array of buckets (hash table)	Hash table plus a linked list of entries	Red-black tree
`null` key	One allowed	One allowed	Not allowed (throws `NullPointerException`)
Key needs	`hashCode()` and `equals()`	`hashCode()` and `equals()`	`Comparable` or a `Comparator`
Extra methods	None	`removeEldestEntry` for caches	`firstKey`, `floorKey`, `ceilingKey`, `headMap`, `tailMap` …
Memory	Lowest	A bit more (links between entries)	More (tree nodes)

The same data in all three

Here the same five cities go into each map. Only the printed order changes.

Same puts, three different orders

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

public class MapOrder {
    static void fill(Map<String, Integer> map) {
        map.put("Pune", 3);
        map.put("Delhi", 1);
        map.put("Mumbai", 2);
        map.put("Chennai", 5);
        map.put("Bengaluru", 4);
    }

    public static void main(String[] args) {
        Map<String, Integer> hash = new HashMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        Map<String, Integer> tree = new TreeMap<>();
        fill(hash);
        fill(linked);
        fill(tree);
        System.out.println("HashMap:       " + hash);
        System.out.println("LinkedHashMap: " + linked);
        System.out.println("TreeMap:       " + tree);
    }
}

Output

HashMap:       {Delhi=1, Chennai=5, Bengaluru=4, Pune=3, Mumbai=2}
LinkedHashMap: {Pune=3, Delhi=1, Mumbai=2, Chennai=5, Bengaluru=4}
TreeMap:       {Bengaluru=4, Chennai=5, Delhi=1, Mumbai=2, Pune=3}

The HashMap order comes from the hash codes. It can look sorted or random and can change when the map grows, so never write code that depends on it.

HashMap: fast lookups, no order

A HashMap uses each key's hashCode() to jump straight to a bucket, so get and put take about the same time whether the map has ten entries or ten million. It is the right choice for counting, caching and looking things up by id.

Counting words with HashMap.merge

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

public class WordCount {
    public static void main(String[] args) {
        String[] words = {"java", "map", "java", "tree", "map", "java"};
        Map<String, Integer> count = new HashMap<>();
        for (String w : words) {
            count.merge(w, 1, Integer::sum);
        }
        System.out.println(count.get("java"));
        System.out.println(count.getOrDefault("python", 0));
        System.out.println(count.size());
    }
}

Output

3
0
3

LinkedHashMap: insertion order and LRU caches

A LinkedHashMap is a HashMap that also links its entries together, so iteration follows insertion order. Created with accessOrder = true, it moves an entry to the end every time you read it; together with removeEldestEntry that gives you a least-recently-used (LRU) cache in a few lines.

An LRU cache with LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache {
    public static void main(String[] args) {
        final int capacity = 3;
        Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > capacity;
            }
        };
        cache.put("a", "Apple");
        cache.put("b", "Banana");
        cache.put("c", "Cherry");
        cache.get("a");            // "a" is now the most recently used
        cache.put("d", "Date");    // over capacity: removes the least recently used, "b"
        System.out.println(cache.keySet());
    }
}

Output

[c, a, d]

TreeMap: sorted keys and range questions

A TreeMap keeps its keys in a balanced tree, sorted by their natural order or by a Comparator you pass in. Each operation costs O(log n), but you get methods a HashMap cannot offer: the smallest and largest key, the nearest key below or above a value, and whole ranges.

Grade bands with floorEntry and ceilingKey

import java.util.TreeMap;

public class GradeBands {
    public static void main(String[] args) {
        TreeMap<Integer, String> grades = new TreeMap<>();
        grades.put(90, "A");
        grades.put(75, "B");
        grades.put(60, "C");
        grades.put(40, "D");
        grades.put(0, "F");

        System.out.println(grades.floorEntry(82).getValue());   // largest key <= 82 is 75
        System.out.println(grades.floorEntry(95).getValue());
        System.out.println(grades.ceilingKey(61));              // smallest key >= 61
        System.out.println(grades.firstKey() + " to " + grades.lastKey());
        System.out.println(grades.headMap(60));                 // keys below 60
        System.out.println(grades.descendingMap());
    }
}

Output

B
A
75
0 to 90
{0=F, 40=D}
{90=A, 75=B, 60=C, 40=D, 0=F}

When to use which

You need…	Use
Fast lookup by key, order does not matter	`HashMap`
Output in the order items were added (e.g. form fields, JSON-like output)	`LinkedHashMap`
A small LRU cache	`LinkedHashMap` with `accessOrder = true`
Keys printed in sorted order	`TreeMap`
Nearest key, ranges, top or bottom entries (leaderboards, time slots, price bands)	`TreeMap`
Many threads updating the same map	`ConcurrentHashMap`

Common mistakes

Expecting a HashMap to keep insertion order. It does not; use LinkedHashMap.
Putting a null key into a TreeMap. It throws NullPointerException because it cannot compare null.
Using your own class as a HashMap key without overriding equals() and hashCode(). Lookups with an equal object then return null.
Changing a field of an object while it is a key in the map. Its hash code changes and the entry becomes unreachable.
Picking TreeMap "to be safe". If you never need sorted keys or ranges, HashMap is simpler and faster.

Frequently asked questions

Is HashMap faster than TreeMap?

Yes, for single lookups and inserts: HashMap is O(1) on average and TreeMap is O(log n). Choose TreeMap only when you need sorted keys or range methods.

Does HashMap maintain insertion order?

No. Its order depends on hash codes and can change when it resizes. LinkedHashMap keeps insertion order.

Can a TreeMap have a null key?

No. With natural ordering, put(null, value) throws NullPointerException. Values can be null.

Which map should I use in coding interviews?

HashMap for counting and lookups (most problems), TreeMap when the problem asks for the nearest, smallest or largest key, and LinkedHashMap for LRU cache questions.

Practise this, step by step

Short lessons with quizzes, practice and interview questions, from your first program to job-ready.

Create account See the course

HashMap vs TreeMap vs LinkedHashMap in Java

9 min readUpdated 17 October 2026

The short answer

Use HashMap by default: fastest, no order.
Use LinkedHashMap when you need the keys back in the order you inserted them (or for a simple LRU cache).
Use TreeMap when you need the keys sorted, or questions like "the largest key below 50".

Comparison table

All three are not thread safe. Use ConcurrentHashMap when many threads write to one map.
	HashMap	LinkedHashMap	TreeMap
Key order	No order you can rely on	Insertion order (or access order)	Sorted by key
get / put / remove	O(1) on average	O(1) on average	O(log n)
Inside	Array of buckets (hash table)	Hash table plus a linked list of entries	Red-black tree
`null` key	One allowed	One allowed	Not allowed (throws `NullPointerException`)
Key needs	`hashCode()` and `equals()`	`hashCode()` and `equals()`	`Comparable` or a `Comparator`
Extra methods	None	`removeEldestEntry` for caches	`firstKey`, `floorKey`, `ceilingKey`, `headMap`, `tailMap` …
Memory	Lowest	A bit more (links between entries)	More (tree nodes)

The same data in all three

Here the same five cities go into each map. Only the printed order changes.

Same puts, three different orders

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

public class MapOrder {
    static void fill(Map<String, Integer> map) {
        map.put("Pune", 3);
        map.put("Delhi", 1);
        map.put("Mumbai", 2);
        map.put("Chennai", 5);
        map.put("Bengaluru", 4);
    }

    public static void main(String[] args) {
        Map<String, Integer> hash = new HashMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        Map<String, Integer> tree = new TreeMap<>();
        fill(hash);
        fill(linked);
        fill(tree);
        System.out.println("HashMap:       " + hash);
        System.out.println("LinkedHashMap: " + linked);
        System.out.println("TreeMap:       " + tree);
    }
}

Output

HashMap:       {Delhi=1, Chennai=5, Bengaluru=4, Pune=3, Mumbai=2}
LinkedHashMap: {Pune=3, Delhi=1, Mumbai=2, Chennai=5, Bengaluru=4}
TreeMap:       {Bengaluru=4, Chennai=5, Delhi=1, Mumbai=2, Pune=3}

The HashMap order comes from the hash codes. It can look sorted or random and can change when the map grows, so never write code that depends on it.

HashMap: fast lookups, no order

Counting words with HashMap.merge

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

public class WordCount {
    public static void main(String[] args) {
        String[] words = {"java", "map", "java", "tree", "map", "java"};
        Map<String, Integer> count = new HashMap<>();
        for (String w : words) {
            count.merge(w, 1, Integer::sum);
        }
        System.out.println(count.get("java"));
        System.out.println(count.getOrDefault("python", 0));
        System.out.println(count.size());
    }
}

Output

3
0
3

LinkedHashMap: insertion order and LRU caches

An LRU cache with LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache {
    public static void main(String[] args) {
        final int capacity = 3;
        Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > capacity;
            }
        };
        cache.put("a", "Apple");
        cache.put("b", "Banana");
        cache.put("c", "Cherry");
        cache.get("a");            // "a" is now the most recently used
        cache.put("d", "Date");    // over capacity: removes the least recently used, "b"
        System.out.println(cache.keySet());
    }
}

Output

[c, a, d]

TreeMap: sorted keys and range questions

Grade bands with floorEntry and ceilingKey

import java.util.TreeMap;

public class GradeBands {
    public static void main(String[] args) {
        TreeMap<Integer, String> grades = new TreeMap<>();
        grades.put(90, "A");
        grades.put(75, "B");
        grades.put(60, "C");
        grades.put(40, "D");
        grades.put(0, "F");

        System.out.println(grades.floorEntry(82).getValue());   // largest key <= 82 is 75
        System.out.println(grades.floorEntry(95).getValue());
        System.out.println(grades.ceilingKey(61));              // smallest key >= 61
        System.out.println(grades.firstKey() + " to " + grades.lastKey());
        System.out.println(grades.headMap(60));                 // keys below 60
        System.out.println(grades.descendingMap());
    }
}

Output

B
A
75
0 to 90
{0=F, 40=D}
{90=A, 75=B, 60=C, 40=D, 0=F}

When to use which

You need…	Use
Fast lookup by key, order does not matter	`HashMap`
Output in the order items were added (e.g. form fields, JSON-like output)	`LinkedHashMap`
A small LRU cache	`LinkedHashMap` with `accessOrder = true`
Keys printed in sorted order	`TreeMap`
Nearest key, ranges, top or bottom entries (leaderboards, time slots, price bands)	`TreeMap`
Many threads updating the same map	`ConcurrentHashMap`

Common mistakes

Expecting a HashMap to keep insertion order. It does not; use LinkedHashMap.
Putting a null key into a TreeMap. It throws NullPointerException because it cannot compare null.
Using your own class as a HashMap key without overriding equals() and hashCode(). Lookups with an equal object then return null.
Changing a field of an object while it is a key in the map. Its hash code changes and the entry becomes unreachable.
Picking TreeMap "to be safe". If you never need sorted keys or ranges, HashMap is simpler and faster.

Frequently asked questions

Is HashMap faster than TreeMap?

Yes, for single lookups and inserts: HashMap is O(1) on average and TreeMap is O(log n). Choose TreeMap only when you need sorted keys or range methods.

Does HashMap maintain insertion order?

No. Its order depends on hash codes and can change when it resizes. LinkedHashMap keeps insertion order.

Can a TreeMap have a null key?

No. With natural ordering, put(null, value) throws NullPointerException. Values can be null.

Which map should I use in coding interviews?

HashMap for counting and lookups (most problems), TreeMap when the problem asks for the nearest, smallest or largest key, and LinkedHashMap for LRU cache questions.

Practise this, step by step

Short lessons with quizzes, practice and interview questions, from your first program to job-ready.

Create account See the course

The short answer

Comparison table

The same data in all three

HashMap: fast lookups, no order

LinkedHashMap: insertion order and LRU caches

TreeMap: sorted keys and range questions

When to use which

Common mistakes

Frequently asked questions

Learn it step by step

Practise this, step by step

The short answer

Comparison table

The same data in all three

HashMap: fast lookups, no order

LinkedHashMap: insertion order and LRU caches

TreeMap: sorted keys and range questions

When to use which

Common mistakes

Frequently asked questions

Learn it step by step

Practise this, step by step