LuisLlamas Logo
java-mapas-hashmap-treemap-linkedhashmap

Maps in Java: HashMap, LinkedHashMap and TreeMap

  • 4 min
  • Beginner

A Map is a structure that associates unique keys with values.

So far, our collections (List, Set) stored individual elements. But in real life, data rarely comes alone. It is usually associated.

  • An ID is associated with a Person.
  • A product name is associated with a Price.
  • A cloakroom ticket is associated with a Coat.

If you use a List<Person>, to find someone by their ID you might need to traverse the entire list, with a cost of O(n).

If the ID is the key, a map enables more efficient searches.

What is a Map?

A Map is an object that associates Keys with Values.

  • Keys (K): They must be Unique (like a Set). There cannot be two identical IDs.
  • Values (V): They can be repeated. Many people can be named “Pepe”.

In a HashMap, searching by key has an average cost of O(1), although collisions and hash distribution influence the real case.

Map does NOT inherit from Collection. It is an independent interface. That’s why it doesn’t have an add() method, but put() instead.

The three implementations (the same pattern)

Just like with Sets, we have three flavors depending on whether we care about order or speed.

This is the default implementation. Use it always unless you have a reason not to.

  • Order: Chaotic. The keys follow no particular order.
  • Speed: Extremely fast.
  • Keys: Uses hashCode() to organize the data.
  • Order: Maintains the insertion order. If you insert key “Z”, then “A”, when iterating they will appear in that order.
  • Use: LRU (Least Recently Used) caches or interfaces where visual order matters.
  • Order: Sorts keys by their natural order (alphabetical or numerical).
  • Speed: Slower (O(logn)) because it has to rebalance the tree every time you insert something.

Basic Operations

Let’s create a phone book. Key: Name (String), Value: Number (Integer).

// K = String, V = Integer
Map<String, Integer> phoneBook = new HashMap<>();

// 1. Insert (PUT)
phoneBook.put("Ana", 666111222);
phoneBook.put("Bernardo", 666333444);
phoneBook.put("Ana", 123456789); // WATCH OUT! If the key exists, it OVERWRITES the value.

// 2. Retrieve (GET)
Integer number = phoneBook.get("Bernardo"); // Returns 666333444
Integer unknown = phoneBook.get("Ghost"); // Returns null

// 3. Check existence
if (phoneBook.containsKey("Ana")) {
    System.out.println("Ana is in the phone book");
}

// 4. Modern trick (Java 8+): Get Or Default
// Avoids null pointer if it doesn't exist
Integer n = phoneBook.getOrDefault("Ghost", 0); // Returns 0 if not found
Copied!

How to iterate over a map

This is the #1 doubt for beginners. Since a Map is not a List, you can’t do for (Map m : map). You have 3 ways to iterate over it:

Option a: iterate only over keys (keySet)

If you are only interested in the names.

for (String name : phoneBook.keySet()) {
    System.out.println("Key: " + name);
}
Copied!

Option b: iterate only over values (values)

If you are only interested in the numbers (note: there can be duplicates).

for (Integer phone : phoneBook.values()) {
    System.out.println("Number: " + phone);
}
Copied!

Option c: iterate over everything (entrySet) - the best one!

It’s the most efficient if you need both the key and the value.

// Map.Entry represents the pair (Key + Value)
for (Map.Entry<String, Integer> entry : phoneBook.entrySet()) {
    String k = entry.getKey();
    Integer v = entry.getValue();
    System.out.println(k + " -> " + v);
}
Copied!

The mutable key trap

There is a sacred rule in maps: Keys must be immutable.

If you use your own object as a Key (e.g., Map<User, Invoice>), and you modify an attribute of the User that affects its hashCode, the Map will lose the reference.

User u = new User("Pepe");
map.put(u, invoice);

u.setName("Jose"); // DANGER! The hash has changed.

map.get(u); // Probably returns null. The map is looking for Pepe, not Jose.
Copied!

That’s why String and Integer are the best keys: because they are immutable.

On this page