# Set and Map

Course: [Java](https://www.devtutorials.ai/learn/java) · Section: Collections Framework
Source: https://www.devtutorials.ai/learn/java/collections-framework/set-and-map

> Store key-value pairs with HashMap and unique items with HashSet, loop through them, use set operations, and compare them with Hashtable and TreeSet.

Think about a school.

The office keeps a register. You give it a roll number, and it tells you the student's name straight away. Each roll number belongs to exactly one student. That is like a **map**: you look up a value by its key.

The school also keeps a list of clubs each student has joined. A student cannot join the chess club twice. Joining again changes nothing. That is like a **set**: every item appears only once.

In simple words: a `HashMap` finds a value by its key, and a `HashSet` keeps a group of items with no repeats.

## What You Will Learn

In this lesson, you will learn:

1. How `HashMap` stores key-value pairs, and how to add, read, update, remove and search them.
2. How to loop through a `HashMap` in three ways.
3. How `HashMap` handles `null`, and how it differs from `Hashtable` and `HashSet`.
4. How `HashSet` keeps elements unique, and how to add, remove, search and loop through it.
5. How to do union, intersection and difference with sets.
6. How `HashSet` differs from `TreeSet` and `HashMap`.

## Start With a Working Example

Press **Run**.

```java runnable title="A map for prices, a set for unique tags"
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> prices = new HashMap<>();
        prices.put("Pen", 20);
        prices.put("Notebook", 45);
        prices.put("Pen", 25);

        System.out.println("Pen costs " + prices.get("Pen"));
        System.out.println("Products: " + prices.size());

        Set<String> tags = new HashSet<>();
        tags.add("sale");
        tags.add("new");
        tags.add("sale");

        System.out.println("Number of tags: " + tags.size());
        System.out.println("Is it on sale? " + tags.contains("sale"));
    }
}
```

Expected output:

```text
Pen costs 25
Products: 2
Number of tags: 2
Is it on sale? true
```

Putting `"Pen"` a second time **replaced** its price. Keys in a map are unique.

Adding `"sale"` a second time did **nothing**. Elements in a set are unique.

### Try This

Add `prices.put("Bag", 499);` and `tags.add("popular");`. Both sizes grow by one.

## HashMap

### Introduction to HashMap

A **`HashMap`** stores data as **key-value pairs**. You give it a key, and it gives back the matching value, very fast.

It is the most used `Map` in Java. It lives in `java.util`.

How it stays fast: when you add a pair, `HashMap` turns the key into a number called a **hash code**, using the key's `hashCode()` method. That number decides which "bucket" the pair goes into. To find the value later, it works out the same number and goes straight to that bucket. It does not have to search every pair.

Think of a cloakroom. You hand over your coat and get ticket number 47. Later you show ticket 47, and the attendant goes straight to hook 47.

Key facts:

- Keys are **unique**. Values can repeat.
- It keeps **no guaranteed order**.
- It allows **one `null` key** and any number of `null` values.
- Adding, finding and removing are very fast, no matter how many pairs it holds.

### Key-Value Pairs

A **key** is what you look things up by. A **value** is what you get back.

| Key | Value |
|---|---|
| Roll number `101` | Student name `"Asha"` |
| Word `"apple"` | Meaning `"a round fruit"` |
| Product `"Pen"` | Price `20` |
| Country `"Japan"` | Capital `"Tokyo"` |

The key type and value type are given in angle brackets: `Map<String, Integer>` has `String` keys and `Integer` values.

### Creating HashMaps

```text
Map<String, Integer> stock = new HashMap<>();                 // empty
HashMap<Integer, String> students = new HashMap<>();           // empty, class type
Map<String, String> capitals = new HashMap<>(Map.of(           // with starting pairs
        "India", "New Delhi",
        "Japan", "Tokyo"));
```

`Map.of(...)` creates a map that cannot be changed. Wrapping it in `new HashMap<>(...)` gives a changeable copy.

### Adding Elements

| Method | What it does |
|---|---|
| `put(key, value)` | Adds the pair. If the key exists, replaces its value and returns the old one |
| `putIfAbsent(key, value)` | Adds the pair only if the key is not there yet |
| `putAll(otherMap)` | Copies every pair from another map |

### Accessing Elements

| Method | What it does |
|---|---|
| `get(key)` | Returns the value, or `null` if the key is missing |
| `getOrDefault(key, fallback)` | Returns the value, or `fallback` if the key is missing |

```java runnable title="Add pairs and read values by key"
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> students = new HashMap<>();

        students.put(101, "Asha");
        students.put(102, "Ravi");
        students.put(103, "Meena");
        students.putIfAbsent(101, "Someone else");

        System.out.println("Roll 102: " + students.get(102));
        System.out.println("Roll 101: " + students.get(101));
        System.out.println("Roll 999: " + students.get(999));
        System.out.println("Roll 999 (safe): " + students.getOrDefault(999, "Not found"));
        System.out.println("Total students: " + students.size());
    }
}
```

Expected output:

```text
Roll 102: Ravi
Roll 101: Asha
Roll 999: null
Roll 999 (safe): Not found
Total students: 3
```

`putIfAbsent(101, ...)` did nothing, because roll 101 already had a name.

`get(999)` returned `null` because there is no roll 999. `getOrDefault` gave a friendlier answer.

### Removing Elements

| Method | What it does |
|---|---|
| `remove(key)` | Removes the pair and returns its value, or `null` |
| `remove(key, value)` | Removes it only if the key has exactly that value |
| `clear()` | Removes every pair |

### Updating Elements

| Method | What it does |
|---|---|
| `put(key, newValue)` | Replaces the value for an existing key |
| `replace(key, newValue)` | Replaces only if the key already exists |
| `merge(key, value, rule)` | Adds the pair, or combines it with the old value using the rule |

`merge` is perfect for counting. `counts.merge(word, 1, Integer::sum)` adds 1 to the word's count, or starts it at 1. Read the code, then look at the output below it.

```java readonly title="Update stock, remove an item and count words"
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("Pens", 40);
        stock.put("Bags", 6);
        stock.put("Caps", 12);

        stock.put("Pens", stock.get("Pens") - 5);
        stock.replace("Bags", 10);
        stock.replace("Shoes", 3);
        stock.remove("Caps");

        System.out.println("Pens: " + stock.get("Pens"));
        System.out.println("Bags: " + stock.get("Bags"));
        System.out.println("Has Caps? " + stock.containsKey("Caps"));
        System.out.println("Has Shoes? " + stock.containsKey("Shoes"));

        Map<String, Integer> counts = new HashMap<>();
        String[] words = {"tea", "coffee", "tea", "juice", "tea"};
        for (String w : words) {
            counts.merge(w, 1, Integer::sum);
        }
        System.out.println("tea was ordered " + counts.get("tea") + " times");
    }
}
```

Output:

```text
Pens: 35
Bags: 10
Has Caps? false
Has Shoes? false
tea was ordered 3 times
```

`replace("Shoes", 3)` did nothing, because `Shoes` was never in the map. `replace` only changes keys that already exist. `put` would have added it.

### Searching Elements

| Method | Returns |
|---|---|
| `containsKey(key)` | `true` if the key is present (very fast) |
| `containsValue(value)` | `true` if any key has that value (slower, it checks every pair) |
| `isEmpty()` | `true` if there are no pairs |

### Iterating through HashMap

A map has three views you can loop over:

| View | Gives you | Use when |
|---|---|---|
| `keySet()` | Every key | You only need the keys |
| `values()` | Every value | You only need the values |
| `entrySet()` | Every key-value pair, as a `Map.Entry` | You need both (most common) |

You can also call `map.forEach((key, value) -> ...)`. Read the code, then look at the output below it.

```java readonly title="Loop over keys, values, or both together"
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> marks = new HashMap<>();
        marks.put(1, 72);
        marks.put(2, 88);
        marks.put(3, 65);

        System.out.print("Roll numbers: ");
        for (int roll : marks.keySet()) {
            System.out.print(roll + " ");
        }
        System.out.println();

        int total = 0;
        for (int m : marks.values()) {
            total += m;
        }
        System.out.println("Total marks: " + total);

        for (Map.Entry<Integer, Integer> e : marks.entrySet()) {
            System.out.println("Roll " + e.getKey() + " scored " + e.getValue());
        }

        System.out.println("Has a mark of 88? " + marks.containsValue(88));
    }
}
```

Output:

```text
Roll numbers: 1 2 3
Total marks: 225
Roll 1 scored 72
Roll 2 scored 88
Roll 3 scored 65
Has a mark of 88? true
```

`entrySet()` is the best choice when you need both parts. Each `Map.Entry` gives you `getKey()` and `getValue()`.

A `HashMap` does not promise any order. Small whole-number keys often come out in order, as above, but that is luck, not a rule. If you need insertion order, use `LinkedHashMap`. If you need keys sorted, use `TreeMap`.

### HashMap Methods

| Method | What it does |
|---|---|
| `put(k, v)` | Adds or replaces a pair |
| `get(k)` | Returns the value, or `null` |
| `getOrDefault(k, d)` | Returns the value, or `d` |
| `putIfAbsent(k, v)` | Adds only if the key is missing |
| `remove(k)` | Removes a pair |
| `replace(k, v)` | Replaces only if the key exists |
| `merge(k, v, rule)` | Adds, or combines with the old value |
| `containsKey(k)` | Checks for a key |
| `containsValue(v)` | Checks for a value |
| `keySet()` | All keys, as a `Set` |
| `values()` | All values, as a `Collection` |
| `entrySet()` | All pairs, as a `Set` of `Map.Entry` |
| `size()` / `isEmpty()` / `clear()` | Count, check, empty |

### Null Keys and Null Values

`HashMap` allows:

- **one** `null` key, because keys are unique;
- **any number** of `null` values.

This causes a puzzle. If `get(key)` returns `null`, did the key have a `null` value, or was it missing? Use `containsKey` to tell the difference.

```java runnable title="A null value is not the same as a missing key"
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> nicknames = new HashMap<>();
        nicknames.put("Asha", "Ash");
        nicknames.put("Ravi", null);
        nicknames.put(null, "Unknown guest");

        System.out.println("Ravi: " + nicknames.get("Ravi"));
        System.out.println("Meena: " + nicknames.get("Meena"));
        System.out.println("Ravi is a key? " + nicknames.containsKey("Ravi"));
        System.out.println("Meena is a key? " + nicknames.containsKey("Meena"));
        System.out.println("null key: " + nicknames.get(null));
    }
}
```

Expected output:

```text
Ravi: null
Meena: null
Ravi is a key? true
Meena is a key? false
null key: Unknown guest
```

Both `get` calls returned `null`. Only `containsKey` showed that Ravi exists with a `null` nickname, while Meena does not exist at all.

### HashMap vs Hashtable

`Hashtable` is an older class from Java 1.0. It does the same job as `HashMap`, with some differences.

| | `HashMap` | `Hashtable` |
|---|---|---|
| Added in | Java 1.2 | Java 1.0 |
| `null` keys and values | Allowed (one `null` key) | Not allowed |
| Thread-safe | No | Yes, every method is locked |
| Speed | Faster | Slower, because of the locking |
| Use in new code? | Yes | No |

For a thread-safe map in new code, use `ConcurrentHashMap` instead of `Hashtable`.

### HashMap vs HashSet

| | `HashMap` | `HashSet` |
|---|---|---|
| Interface | `Map` | `Set` |
| Stores | Key-value pairs | Single elements |
| Duplicates | Keys unique, values can repeat | Elements unique |
| Add with | `put(key, value)` | `add(element)` |
| Typical question | "What is the value for this key?" | "Is this item here?" |

Fun fact: a `HashSet` is built on top of a `HashMap`. Each element is stored as a key, with a dummy value.

## HashSet

### Introduction to HashSet

A **`HashSet`** is a collection of **unique** elements. It implements the `Set` interface and lives in `java.util`.

It uses the same hash-code trick as `HashMap`, so adding, removing and checking are very fast.

Key facts:

- No duplicates. Adding an element that is already there does nothing.
- **No guaranteed order.**
- No index. There is no `get(0)`.
- Allows one `null` element.

A `HashSet` has **no index** and **no `get` method**. You cannot ask for "the first element". You can only add, remove, check with `contains`, or loop through all the elements.

### Unique Elements

How does a `HashSet` know two elements are "the same"? It uses two methods every object has:

- `hashCode()` decides which bucket the element goes in;
- `equals()` checks whether it matches an element already in that bucket.

Built-in types like `String` and `Integer` already have these methods. For your own classes, you must write both, or use a **record**, which writes them for you.

### Creating HashSet

```text
Set<String> emails = new HashSet<>();                              // empty
Set<Integer> rolls = new HashSet<>(List.of(101, 102, 103));        // from a collection
```

Creating a `HashSet` from a list is a quick way to **remove duplicates** from that list.

### Adding Elements

`add(element)` returns `true` if the element was added, or `false` if it was already there. `addAll(collection)` adds many at once.

### Removing Elements

`remove(element)` removes it, and returns `true` if it was there. `removeIf(rule)` and `clear()` work too.

### Searching Elements

`contains(element)` returns `true` if the element is present. This is the main reason to use a set: it answers this question almost instantly, even for millions of elements.

```java runnable title="add tells you whether the element was new"
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> registered = new HashSet<>();

        System.out.println("Asha added? " + registered.add("asha@mail.com"));
        System.out.println("Ravi added? " + registered.add("ravi@mail.com"));
        System.out.println("Asha again? " + registered.add("asha@mail.com"));

        System.out.println("Accounts: " + registered.size());
        System.out.println("Is Ravi registered? " + registered.contains("ravi@mail.com"));

        registered.remove("ravi@mail.com");
        System.out.println("After Ravi leaves: " + registered.size());
        System.out.println("Is Ravi registered? " + registered.contains("ravi@mail.com"));
    }
}
```

Expected output:

```text
Asha added? true
Ravi added? true
Asha again? false
Accounts: 2
Is Ravi registered? true
After Ravi leaves: 1
Is Ravi registered? false
```

`add` returned `false` for the repeated email. A sign-up page can use that to say "this email is already registered".

### Iterating through HashSet

Loop with for-each, an `Iterator`, or `forEach`. The order is not guaranteed.

If you need a predictable order for display, copy the set into a `TreeSet`, which keeps elements sorted.

```java runnable title="Remove duplicates from a list, then show them sorted"
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        List<String> visits = List.of("Pune", "Goa", "Pune", "Ooty", "Goa", "Pune");

        Set<String> places = new HashSet<>(visits);
        System.out.println("Visits: " + visits.size() + ", different places: " + places.size());

        int letters = 0;
        for (String p : places) {
            letters += p.length();
        }
        System.out.println("Total letters in place names: " + letters);

        Set<String> sorted = new TreeSet<>(places);
        System.out.println("Sorted: " + sorted);
    }
}
```

Expected output:

```text
Visits: 6, different places: 3
Total letters in place names: 11
Sorted: [Goa, Ooty, Pune]
```

The for-each loop visited each place once. Adding up the letters gives the same answer in any order. Copying into a `TreeSet` gave a sorted display.

### HashSet Methods

| Method | What it does |
|---|---|
| `add(e)` | Adds `e`; returns `false` if it was already there |
| `addAll(c)` | Adds every element of `c` (union) |
| `remove(e)` | Removes `e` |
| `removeAll(c)` | Removes every element that is in `c` (difference) |
| `retainAll(c)` | Keeps only elements that are also in `c` (intersection) |
| `contains(e)` | Checks for `e` |
| `size()` / `isEmpty()` / `clear()` | Count, check, empty |

### Null Values in HashSet

A `HashSet` allows **one** `null` element. Adding `null` a second time does nothing, just like any other duplicate.

`TreeSet` does **not** allow `null`, because it cannot compare `null` with other elements to sort it.

### Set Operations

Sets support the same operations you learned in maths. Each one changes the set it is called on, so make a **copy** first if you want to keep the original.

#### Union

The **union** of two sets is every element that is in **either** set. Use `addAll`.

#### Intersection

The **intersection** is every element that is in **both** sets. Use `retainAll`.

#### Difference

The **difference** A − B is every element in A that is **not** in B. Use `removeAll`.

```text
 A = {Maths, Science, English}      B = {Science, Art, English}

 Union         A ∪ B = {Art, English, Maths, Science}
 Intersection  A ∩ B = {English, Science}
 Difference    A − B = {Maths}
```

```java runnable title="Union, intersection and difference of two clubs"
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> chess = new TreeSet<>(Set.of("Asha", "Ravi", "Meena"));
        Set<String> music = new TreeSet<>(Set.of("Ravi", "Arjun", "Meena", "Divya"));

        Set<String> anyClub = new TreeSet<>(chess);
        anyClub.addAll(music);
        System.out.println("In any club: " + anyClub);

        Set<String> bothClubs = new TreeSet<>(chess);
        bothClubs.retainAll(music);
        System.out.println("In both clubs: " + bothClubs);

        Set<String> chessOnly = new TreeSet<>(chess);
        chessOnly.removeAll(music);
        System.out.println("Chess only: " + chessOnly);

        System.out.println("Chess is unchanged: " + chess);
    }
}
```

Expected output:

```text
In any club: [Arjun, Asha, Divya, Meena, Ravi]
In both clubs: [Meena, Ravi]
Chess only: [Asha]
Chess is unchanged: [Asha, Meena, Ravi]
```

Each operation started from a **copy** of `chess`. So the original `chess` set never changed.

`TreeSet` is used here so the output is sorted and easy to read. The same methods work on a `HashSet`.

| Operation | Maths symbol | Method | Keeps |
|---|---|---|---|
| Union | A ∪ B | `a.addAll(b)` | Everything in either |
| Intersection | A ∩ B | `a.retainAll(b)` | Only what is in both |
| Difference | A − B | `a.removeAll(b)` | What is in A but not B |

### HashSet vs TreeSet

| | `HashSet` | `TreeSet` |
|---|---|---|
| Order | None guaranteed | Sorted (natural order, or a comparator) |
| Speed | Fastest | A little slower |
| `null` allowed? | One `null` | No |
| Elements need | `equals` and `hashCode` | To be comparable (`Comparable` or a `Comparator`) |
| Extra methods | — | `first()`, `last()`, `headSet()`, `tailSet()` |
| Use when | You only need uniqueness and speed | You also need sorted order |

There is also **`LinkedHashSet`**, which keeps elements in the order you added them.

### HashSet vs HashMap

| | `HashSet` | `HashMap` |
|---|---|---|
| Holds | Single elements | Key-value pairs |
| Add | `add(e)` | `put(k, v)` |
| Check | `contains(e)` | `containsKey(k)` |
| Read a value | — | `get(k)` |
| Use when | You only need "is it there?" | You also need data linked to each key |

**Easy Way to Remember:** a **set** answers **"is it there?"**. A **map** answers **"what goes with it?"**.

## Common mistakes

The following mistakes are common when working with sets and maps. Each row shows what you see, why it happens and how to fix it.

| Symptom | Cause | Fix |
|---|---|---|
| `NullPointerException` after `get` | The key was missing | Use `getOrDefault`, or check `containsKey` |
| A value disappears | `put` with the same key replaced it | Use a list as the value, or a different key |
| `cannot find symbol: method get(int)` on a set | Sets have no index | Loop with for-each |
| Duplicate objects in a set | The class has no `equals` and `hashCode` | Write both, or use a record |
| `ConcurrentModificationException` | The set or map changed during a for-each loop | Use `removeIf` or an `Iterator` |
| Items print in a surprising order | `HashMap` and `HashSet` keep no order | Use `LinkedHash...` or `Tree...` classes |

## What to Remember

- A `HashMap` stores unique keys, each with one value. `put` adds or replaces, `get` reads, `remove` deletes.
- Use `getOrDefault` for keys that might be missing, and `containsKey` to tell a missing key from a `null` value.
- Loop over a map with `keySet()`, `values()` or `entrySet()`. `HashMap` keeps no order.
- A `HashSet` stores unique elements, with very fast `add`, `remove` and `contains`. It has no index and no order.
- Set operations: union with `addAll`, intersection with `retainAll`, difference with `removeAll`. Work on copies.
- Use `TreeSet` or `TreeMap` for sorted order. Avoid the old `Hashtable` in new code.

Next: Linear Data Structures