DEV Community

Cover image for HashMap vs LinkedHashMap vs TreeMap: Internal Differences, Performance and Real-World Use Cases
Ramanjaneyulu Boya
Ramanjaneyulu Boya

Posted on

HashMap vs LinkedHashMap vs TreeMap: Internal Differences, Performance and Real-World Use Cases

Java provides several Map implementations, but three of the most commonly used are HashMap, LinkedHashMap, and TreeMap.

At first glance, all three store data as key-value pairs. However, their internal implementations, ordering guarantees, performance characteristics, and real-world applications are significantly different.

As a Java developer working on enterprise applications, understanding these differences is important—not just for writing code, but also for making the right architectural decisions.

Consider a banking application:

  • Customer account details need fast lookups.
  • Recent transactions should maintain insertion order.
  • Transaction records may need to be sorted by transaction date.

Would you use the same Map implementation for all three scenarios?

Probably not.

Let's understand how these Map implementations work internally and when to use each one.


1. Understanding the Map Interface

The Map interface stores data in key-value pairs.

Each key must be unique, while multiple keys can have the same value.

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

customers.put(101, "John");
customers.put(102, "David");
customers.put(103, "Michael");

System.out.println(customers.get(102));
Enter fullscreen mode Exit fullscreen mode

Output:

David
Enter fullscreen mode Exit fullscreen mode

Java provides multiple implementations of the Map interface, including:

  • HashMap
  • LinkedHashMap
  • TreeMap
  • Hashtable
  • ConcurrentHashMap

In this article, we will focus on HashMap, LinkedHashMap, and TreeMap.


2. HashMap: Fast Key-Value Lookups

HashMap is one of the most widely used Map implementations in Java.

It provides average constant-time complexity for basic operations such as:

  • put()
  • get()
  • remove()
  • containsKey()

Internal Architecture

HashMap internally uses an array of buckets.

Each bucket can contain:

  • A linked list of nodes.
  • A balanced Red-Black Tree when collision handling reaches the treeification threshold and other conditions are satisfied.

Each node stores:

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
Enter fullscreen mode Exit fullscreen mode

How does HashMap store an entry?

  1. The key's hashCode() is calculated.
  2. HashMap spreads the hash bits.
  3. The bucket index is calculated.
  4. The entry is stored in the corresponding bucket.
  5. If another key maps to the same bucket, collision handling takes place.

The simplified bucket-index calculation is:

index = (capacity - 1) & hash;
Enter fullscreen mode Exit fullscreen mode

Java uses a power-of-two table capacity to make this calculation efficient.

HashMap Internal Architecture

Hash Collision Handling

A collision occurs when multiple keys map to the same bucket.

Example:

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

map.put(1, "Customer A");
map.put(17, "Customer B");
map.put(33, "Customer C");
Enter fullscreen mode Exit fullscreen mode

Assuming a table capacity of 16, these integer keys map to the same bucket under the simplified index calculation.

HashMap handles collisions using linked nodes.

When collisions become sufficiently high, the bucket may be converted into a Red-Black Tree.

Important Java 21 implementation details:

  • Default initial capacity: 16.
  • Default load factor: 0.75.
  • Treeification threshold: 8.
  • Minimum capacity for treeification: 64.
  • Untreeification threshold: 6.

These are implementation details, not guarantees of the Map interface.

HashMap Performance

Operation Average Worst case
get() O(1) O(n)
put() O(1) O(n)
remove() O(1) O(n)

With effective hashing and treeified collision buckets, collision-heavy lookups can achieve O(log n) behavior within those buckets.

Real-World Use Cases

HashMap is suitable for:

  • Customer ID to customer details mapping.
  • Product ID to product information.
  • API response caching.
  • Configuration properties.
  • Frequently accessed reference data.

Example:

Map<String, Customer> customerCache = new HashMap<>();

customerCache.put("CUST101", customer);
Customer result = customerCache.get("CUST101");
Enter fullscreen mode Exit fullscreen mode

When should you use HashMap?

When fast key-based lookup is your primary requirement and you do not need ordering.


3. LinkedHashMap: Maintaining Insertion Order

LinkedHashMap extends HashMap and maintains a doubly linked list across its entries.

Unlike HashMap, it provides predictable iteration order.

By default, that order is insertion order.

Internal Architecture

LinkedHashMap maintains:

  1. Hash table for fast key lookup.
  2. Doubly linked list for maintaining entry order.

Each entry maintains additional references:

before
after
Enter fullscreen mode Exit fullscreen mode

These references connect entries in insertion order.

LinkedHashMap Internal Architecture

Example

Map<Integer, String> map = new LinkedHashMap<>();

map.put(103, "Michael");
map.put(101, "John");
map.put(102, "David");

map.forEach((key, value) ->
    System.out.println(key + " : " + value)
);
Enter fullscreen mode Exit fullscreen mode

Output:

103 : Michael
101 : John
102 : David
Enter fullscreen mode Exit fullscreen mode

Notice that entries are returned in insertion order.

Access-Order LinkedHashMap

One interesting feature of LinkedHashMap is that it supports access-order iteration.

LinkedHashMap<Integer, String> map =
    new LinkedHashMap<>(16, 0.75f, true);

map.put(101, "John");
map.put(102, "David");
map.put(103, "Michael");

map.get(101);

map.forEach((key, value) ->
    System.out.println(key + " : " + value)
);
Enter fullscreen mode Exit fullscreen mode

Output:

102 : David
103 : Michael
101 : John
Enter fullscreen mode Exit fullscreen mode

The accessed entry moves to the end of the iteration order.

This feature is particularly useful when implementing an LRU (Least Recently Used) cache.

Implementing an LRU Cache

class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LRUCache(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(
            Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
Enter fullscreen mode Exit fullscreen mode

Usage:

LRUCache<Integer, String> cache = new LRUCache<>(3);

cache.put(1, "Customer A");
cache.put(2, "Customer B");
cache.put(3, "Customer C");

cache.get(1);

cache.put(4, "Customer D");

System.out.println(cache);
Enter fullscreen mode Exit fullscreen mode

Entry 2 is removed because it is the least recently accessed entry.

Note: This example is not thread-safe. Production cache implementations need appropriate concurrency controls or a dedicated caching solution.

LinkedHashMap Performance

Operation Average
get() O(1)
put() O(1)
remove() O(1)
Iteration O(n)

It has additional memory overhead because every entry maintains linked-list references.

Real-World Use Cases

  • LRU cache implementation.
  • Maintaining API response insertion order.
  • Ordered transaction processing.
  • Maintaining predictable configuration output.
  • Recently accessed customer or product records.

When should you use LinkedHashMap?

When you need HashMap-like lookup performance along with predictable iteration order.


4. TreeMap: Maintaining Sorted Order

TreeMap is different from HashMap and LinkedHashMap.

It internally uses a Red-Black Tree, which is a self-balancing binary search tree.

Unlike the previous implementations, TreeMap maintains its keys in sorted order.

By default, keys are sorted using their natural ordering. You can also provide a custom Comparator.

Internal Architecture

A Red-Black Tree maintains balance through:

  • Node coloring.
  • Left and right rotations.
  • Recoloring during insertion and deletion.

These mechanisms prevent the tree from becoming excessively unbalanced.

TreeMap Red-Black Tree Architecture

Example

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

map.put(103, "Michael");
map.put(101, "John");
map.put(102, "David");

map.forEach((key, value) ->
    System.out.println(key + " : " + value)
);
Enter fullscreen mode Exit fullscreen mode

Output:

101 : John
102 : David
103 : Michael
Enter fullscreen mode Exit fullscreen mode

Even though entries were inserted in a different order, TreeMap maintains sorted key order.

Custom Sorting with Comparator

Suppose a banking application needs to sort transactions based on transaction amount.

Map<Double, String> transactions =
    new TreeMap<>(Comparator.reverseOrder());

transactions.put(5000.0, "Payment A");
transactions.put(1500.0, "Payment B");
transactions.put(9000.0, "Payment C");

System.out.println(transactions);
Enter fullscreen mode Exit fullscreen mode

Output:

{9000.0=Payment C, 5000.0=Payment A, 1500.0=Payment B}
Enter fullscreen mode Exit fullscreen mode

Important: TreeMap uses key comparison to determine key uniqueness. Two keys for which the comparator returns zero are treated as the same key.

For real financial applications, avoid using floating-point values as monetary keys. Prefer BigDecimal with a carefully defined comparator, or use a unique transaction ID as the key and sort transaction objects separately.

NavigableMap Features

TreeMap implements NavigableMap, providing useful methods:

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

map.put(100, "A");
map.put(200, "B");
map.put(300, "C");
map.put(400, "D");

System.out.println(map.firstKey());
System.out.println(map.lastKey());

System.out.println(map.lowerKey(300));
System.out.println(map.higherKey(300));

System.out.println(map.floorKey(250));
System.out.println(map.ceilingKey(250));
Enter fullscreen mode Exit fullscreen mode

Output:

100
400
200
400
200
300
Enter fullscreen mode Exit fullscreen mode

These methods are especially useful for range-based queries.

TreeMap Performance

Operation Complexity
get() O(log n)
put() O(log n)
remove() O(log n)
firstKey() O(log n)
lastKey() O(log n)

Real-World Use Cases

  • Maintaining transactions by timestamp.
  • Sorting customer records by account number.
  • Price-based product ordering.
  • Range-based searches.
  • Scheduling events by execution time.
  • Finding the nearest available time slot.

When should you use TreeMap?

When sorted keys, range queries, or navigation operations are important.


5. HashMap vs LinkedHashMap vs TreeMap

Let's compare all three implementations.

Feature HashMap LinkedHashMap TreeMap
Internal structure Hash table Hash table + doubly linked list Red-Black Tree
Ordering No guarantee Insertion/access order Sorted key order
get() O(1) average O(1) average O(log n)
put() O(1) average O(1) average O(log n)
remove() O(1) average O(1) average O(log n)
Null key One allowed One allowed Generally not allowed with natural ordering
Null values Allowed Allowed Allowed
Memory overhead Lower Higher Higher
Thread-safe No No No

Remember: HashMap and LinkedHashMap do not guarantee constant-time operations in every situation. Their performance depends on hash distribution and resizing behavior.


6. Real-World Banking Application: Choosing the Right Map

Let's consider a fintech platform with three requirements.

Scenario 1: Customer Lookup

Requirement:

Retrieve customer information quickly using customer ID.

Recommended implementation: HashMap.

Map<String, Customer> customerMap = new HashMap<>();

customerMap.put("C101", customer);

Customer customer = customerMap.get("C101");
Enter fullscreen mode Exit fullscreen mode

Reason: Fast key-based lookups without ordering requirements.

Scenario 2: Recently Accessed Accounts

Requirement:

Maintain recently accessed customer accounts in access order and remove older entries when the cache reaches its capacity.

Recommended implementation: LinkedHashMap.

Reason: Access-order iteration and eldest-entry removal support LRU cache implementation.

Scenario 3: Transactions Sorted by Timestamp

Requirement:

Maintain transaction records in timestamp order and retrieve transactions within a date range.

Recommended implementation: TreeMap.

NavigableMap<LocalDateTime, Transaction> transactions =
    new TreeMap<>();

transactions.put(
    LocalDateTime.now(),
    transaction
);
Enter fullscreen mode Exit fullscreen mode

Range query:

NavigableMap<LocalDateTime, Transaction> dailyTransactions =
    transactions.subMap(
        startTime, true,
        endTime, true
    );
Enter fullscreen mode Exit fullscreen mode

Reason: Sorted keys and efficient range navigation.

Production consideration: If multiple transactions can share the same timestamp, a TreeMap keyed only by timestamp will overwrite earlier entries. Use a composite key or another collection strategy to preserve every transaction.


7. Important Internal Concepts Every Java Developer Should Know

Understanding these concepts helps explain the performance differences during technical interviews.

A. Hashing and hashCode()

HashMap uses hashCode() to identify the bucket where an entry should be stored.

The equals() method determines whether two keys are logically equal.

The contract is important:

  • If two objects are equal according to equals(), they must have the same hashCode().
  • Different objects may have the same hashCode().
  • hashCode() does not guarantee uniqueness.

B. Resizing and Load Factor

HashMap and LinkedHashMap resize when the number of entries exceeds their threshold.

Default configuration:

capacity = 16;
loadFactor = 0.75;

threshold = capacity * loadFactor;
Enter fullscreen mode Exit fullscreen mode

Therefore:

16 * 0.75 = 12
Enter fullscreen mode Exit fullscreen mode

When the threshold is exceeded, the table is resized, generally doubling its capacity.

Resizing involves redistributing entries into the new table.

HashMap Resizing

C. Why TreeMap Does Not Need Hashing

TreeMap does not use hashCode().

It relies on key comparison using:

  • Comparable
  • Comparator

This is why TreeMap can maintain sorted key order without calculating hash buckets.

D. Thread Safety

None of these three Map implementations is inherently thread-safe.

For concurrent applications, consider:

Map<String, Customer> customerMap =
    new ConcurrentHashMap<>();
Enter fullscreen mode Exit fullscreen mode

ConcurrentHashMap supports concurrent access and updates.

For a synchronized wrapper:

Map<String, Customer> synchronizedMap =
    Collections.synchronizedMap(new HashMap<>());
Enter fullscreen mode Exit fullscreen mode

Remember that compound operations and iteration still require appropriate synchronization.


8. Common Interview Questions

Q1. Why is HashMap faster than TreeMap?

HashMap provides average O(1) lookup using hashing, whereas TreeMap uses a Red-Black Tree and provides O(log n) lookup.

Q2. Does LinkedHashMap maintain insertion order?

Yes. By default, it maintains insertion order. It can also maintain access order using its constructor parameter.

Q3. How does HashMap handle collisions?

It uses linked nodes within buckets and can convert heavily populated buckets into Red-Black Trees when the required conditions are met.

Q4. Can TreeMap contain null keys?

With natural ordering, null keys are not supported. A custom comparator may support null if it explicitly handles them.

Q5. Why is TreeMap useful for range queries?

It implements NavigableMap, which provides methods such as subMap(), headMap(), tailMap(), floorKey(), and ceilingKey().

Q6. Is LinkedHashMap suitable for implementing an LRU cache?

Yes. Its access-order mode and removeEldestEntry() method make it a convenient starting point for a simple LRU cache.

Q7. What happens when two HashMap keys have the same hashCode()?

They are placed in the same bucket. HashMap uses equals() to distinguish them.


9. Final Thoughts

Choosing a Map implementation is not just about knowing Java Collections. It is about understanding application requirements and making the right engineering trade-offs.

My recommendation:

  • Use HashMap when fast key-based lookups are the priority.
  • Use LinkedHashMap when predictable iteration order or simple LRU behavior is required.
  • Use TreeMap when sorted keys and range-based operations are important.
  • Use ConcurrentHashMap when concurrent access is required.

In enterprise applications, selecting the correct collection can improve performance, simplify implementation, and make the code easier to maintain.

A good Java developer knows how to use collections. A strong engineer knows why a particular collection is the right choice for a particular problem.


Conclusion

Java Collections are fundamental to building scalable backend applications.

Understanding their internal data structures, complexity, memory overhead, and operational trade-offs helps developers write better production code.

Keep exploring. Keep building. Keep architecting.

Ram The Architect (RTA)

Follow me for more practical insights on Java 21 | Spring Boot | Microservices | Apache Kafka | AWS | System Design | GenAI

Github: https://github.com/Ramu-fsd/
Linkedin: https://www.linkedin.com/in/ramuboya/


References

Java #Java21 #CoreJava #JavaCollections #HashMap #LinkedHashMap #TreeMap #BackendDevelopment #SoftwareArchitecture #SystemDesign #Programming

Top comments (0)