Maps and sets (Fundamentals) | Programming Tutorials

A list answers the question “what is at position 3?”. Often the question is different: “what is the price of apples?”, “have I seen this word before?”, “which users are in both groups?”. For these you want to ask by name or by content, not by position. Maps and sets are built for exactly that.

Maps: keys and values

A map stores key/value pairs. You give it a key and it gives back the value stored under that key. Other names for the same idea are dictionary (Python), object or Map (JavaScript), hash map (Java’s HashMap) and associative array. C has no built-in map; its standard library offers only arrays, so C programmers write their own or use a library.

key        value
"apples"   3
"pears"    5
"plums"    0

Each key appears at most once. Storing a new value under an existing key replaces the old one. Values can repeat freely.

Counting words

The classic first use of a map is counting. We go through a list of words and keep a tally per word: if the word is new, its count starts at 1; if it was already there, add one.

Python

words = ["the", "cat", "and", "the", "hat", "and", "the", "bat"]

counts = {}
for word in words:
    if word in counts:
        counts[word] += 1
    else:
        counts[word] = 1

for word, n in counts.items():
    print(f"{word}: {n}")

print("has 'cat':", "yes" if "cat" in counts else "no")
print("has 'dog':", "yes" if "dog" in counts else "no")
print("count of 'hat':", counts["hat"])

JavaScript

const words = ["the", "cat", "and", "the", "hat", "and", "the", "bat"];

const counts = new Map();
for (const word of words) {
  if (counts.has(word)) {
    counts.set(word, counts.get(word) + 1);
  } else {
    counts.set(word, 1);
  }
}

for (const [word, n] of counts) {
  console.log(`${word}: ${n}`);
}

console.log("has 'cat':", counts.has("cat") ? "yes" : "no");
console.log("has 'dog':", counts.has("dog") ? "yes" : "no");
console.log("count of 'hat':", counts.get("hat"));

Java

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

public class MapCount {
    public static void main(String[] args) {
        List<String> words = List.of("the", "cat", "and", "the", "hat", "and", "the", "bat");

        // LinkedHashMap remembers insertion order, which keeps the output predictable.
        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String word : words) {
            if (counts.containsKey(word)) {
                counts.put(word, counts.get(word) + 1);
            } else {
                counts.put(word, 1);
            }
        }

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

        System.out.println("has 'cat': " + (counts.containsKey("cat") ? "yes" : "no"));
        System.out.println("has 'dog': " + (counts.containsKey("dog") ? "yes" : "no"));
        System.out.println("count of 'hat': " + counts.get("hat"));
    }
}

#include <stdio.h>
#include <string.h>

#define MAX 16

/* A tiny map: two parallel arrays that are searched one entry at a time.
   Real C programs use a hash table, which they write themselves or borrow from a library. */
static const char *keys[MAX];
static int values[MAX];
static int size = 0;

static int find(const char *key) {
    for (int i = 0; i < size; i++) {
        if (strcmp(keys[i], key) == 0) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    const char *words[] = {"the", "cat", "and", "the", "hat", "and", "the", "bat"};
    int count = sizeof words / sizeof words[0];

    for (int i = 0; i < count; i++) {
        int at = find(words[i]);
        if (at >= 0) {
            values[at] += 1;
        } else {
            keys[size] = words[i];
            values[size] = 1;
            size++;
        }
    }

    for (int i = 0; i < size; i++) {
        printf("%s: %d\n", keys[i], values[i]);
    }

    printf("has 'cat': %s\n", find("cat") >= 0 ? "yes" : "no");
    printf("has 'dog': %s\n", find("dog") >= 0 ? "yes" : "no");
    printf("count of 'hat': %d\n", values[find("hat")]);
    return 0;
}

The C version scans the keys one by one, so it shows the idea but not the speed. The next section explains what a real map does instead.

All four print:

the: 3
cat: 1
and: 2
hat: 1
bat: 1
has 'cat': yes
has 'dog': no
count of 'hat': 1

Why lookup is fast: hashing, in intuition

A naive map could keep its pairs in a list and scan for the key, exactly as the C version above does, but that gets slower with every pair you add. Real maps use a hash table. The idea:

A hash function turns a key into a number. The same key always gives the same number, and different keys usually give different numbers.
That number picks one of many buckets (slots) where the pair is stored.
To look a key up, hash it again, go straight to its bucket, and check there.

key "cat"  --hash-->  7  --> bucket 7: ("cat", 1)
key "the"  --hash-->  2  --> bucket 2: ("the", 3)
key "hat"  --hash-->  7  --> bucket 7: collision, stored next to "cat"

Think of a coat check: instead of searching every coat, you hand over a ticket number and the attendant goes to one hook. Two different keys occasionally land in the same bucket (a collision), and the table has ways to cope, but on average a lookup, an insertion and a removal all take roughly the same short time whether the map holds ten pairs or ten million.

Two consequences matter in daily use:

Keys must be hashable, which in practice means they must not change while they are in the map. Strings and numbers work well as keys everywhere. Whether a list may be a key depends on the language, as the table in the “More tools” section shows.
Order is not the point. Hash tables do not promise any particular order. Modern Python and JavaScript maps happen to remember insertion order, and Java’s LinkedHashMap does too, but Java’s plain HashMap does not. If you need a sorted order, sort the keys explicitly.

Sets: unique values

A set is a collection of values with no duplicates, and no positions. It is like a map that keeps only the keys. Membership tests (“is this in there?”) are as fast as map lookups, which makes sets the right tool for “have I seen this before?” and for removing duplicates.

Sets also support the operations you know from school mathematics: union (everything in either), intersection (only what is in both), and difference (in the first but not the second).

Python

a = {1, 2, 3, 4}
b = {3, 4, 5}

print("union:", sorted(a | b))
print("intersection:", sorted(a & b))
print("difference:", sorted(a - b))
print("3 in a:", "yes" if 3 in a else "no")

unique = set([2, 7, 2, 2, 9, 7])
print("unique count:", len(unique))

JavaScript

const a = new Set([1, 2, 3, 4]);
const b = new Set([3, 4, 5]);

const sorted = (s) => `[${[...s].sort((x, y) => x - y).join(", ")}]`;

console.log("union:", sorted(new Set([...a, ...b])));
console.log("intersection:", sorted(new Set([...a].filter((x) => b.has(x)))));
console.log("difference:", sorted(new Set([...a].filter((x) => !b.has(x)))));
console.log("3 in a:", a.has(3) ? "yes" : "no");

const unique = new Set([2, 7, 2, 2, 9, 7]);
console.log("unique count:", unique.size);

Java

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SetOps {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = Set.of(3, 4, 5);

        Set<Integer> union = new TreeSet<>(a);
        union.addAll(b);
        Set<Integer> intersection = new TreeSet<>(a);
        intersection.retainAll(b);
        Set<Integer> difference = new TreeSet<>(a);
        difference.removeAll(b);

        System.out.println("union: " + union);
        System.out.println("intersection: " + intersection);
        System.out.println("difference: " + difference);
        System.out.println("3 in a: " + (a.contains(3) ? "yes" : "no"));

        Set<Integer> unique = new HashSet<>(java.util.List.of(2, 7, 2, 2, 9, 7));
        System.out.println("unique count: " + unique.size());
    }
}

#include <stdbool.h>
#include <stdio.h>

#define N 10   /* this set can hold the whole numbers 0 to 9 */

/* A set of small numbers: in[v] is true when v is a member. */
static void print_set(const char *label, const bool in[N]) {
    printf("%s: [", label);
    bool first = true;
    for (int v = 0; v < N; v++) {
        if (in[v]) {
            printf("%s%d", first ? "" : ", ", v);
            first = false;
        }
    }
    printf("]\n");
}

int main(void) {
    bool a[N] = {false};
    bool b[N] = {false};
    int a_values[] = {1, 2, 3, 4};
    int b_values[] = {3, 4, 5};
    for (int i = 0; i < 4; i++) a[a_values[i]] = true;
    for (int i = 0; i < 3; i++) b[b_values[i]] = true;

    bool uni[N], inter[N], diff[N];
    for (int v = 0; v < N; v++) {
        uni[v] = a[v] || b[v];
        inter[v] = a[v] && b[v];
        diff[v] = a[v] && !b[v];
    }

    print_set("union", uni);
    print_set("intersection", inter);
    print_set("difference", diff);
    printf("3 in a: %s\n", a[3] ? "yes" : "no");

    int repeated[] = {2, 7, 2, 2, 9, 7};
    bool seen[N] = {false};
    int unique_count = 0;
    for (int i = 0; i < 6; i++) {
        if (!seen[repeated[i]]) {
            seen[repeated[i]] = true;
            unique_count++;
        }
    }
    printf("unique count: %d\n", unique_count);
    return 0;
}

C has no set type either. When the values are small whole numbers, a row of true/false flags indexed by value is a perfectly good set, and it is also how a bit set works.

All four print the same thing:

union: [1, 2, 3, 4, 5]
intersection: [3, 4]
difference: [1, 2]
3 in a: yes
unique count: 3

The sorting is only there to make the output predictable, since sets themselves have no order.

More tools

Three idioms come up constantly. Each shows a way around the “is it there yet?” branch or a trap around missing keys.

A default for a missing key

Counting with an if and an else works but is wordy. Every language has a way to ask for a value with a fallback:

Python

words = ["the", "cat", "and", "the", "hat"]

counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1

for w, n in counts.items():
    print(f"{w}: {n}")

JavaScript

const words = ["the", "cat", "and", "the", "hat"];

const counts = new Map();
for (const w of words) {
  counts.set(w, (counts.get(w) ?? 0) + 1);
}

for (const [w, n] of counts) {
  console.log(`${w}: ${n}`);
}

Java

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

public class DefaultCount {
    public static void main(String[] args) {
        String[] words = {"the", "cat", "and", "the", "hat"};

        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String w : words) {
            counts.put(w, counts.getOrDefault(w, 0) + 1);
        }

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

C has no default-returning lookup, so the usual shape is a small helper that returns 0 for a word it has not met.

#include <stdio.h>
#include <string.h>

#define MAX 16

static const char *keys[MAX];
static int values[MAX];
static int size = 0;

static int count_of(const char *key) {
    for (int i = 0; i < size; i++) {
        if (strcmp(keys[i], key) == 0) {
            return values[i];
        }
    }
    return 0;
}

static void set_count(const char *key, int n) {
    for (int i = 0; i < size; i++) {
        if (strcmp(keys[i], key) == 0) {
            values[i] = n;
            return;
        }
    }
    keys[size] = key;
    values[size] = n;
    size++;
}

int main(void) {
    const char *words[] = {"the", "cat", "and", "the", "hat"};
    for (int i = 0; i < 5; i++) {
        set_count(words[i], count_of(words[i]) + 1);
    }
    for (int i = 0; i < size; i++) {
        printf("%s: %d\n", keys[i], values[i]);
    }
    return 0;
}

All four print:

the: 2
cat: 1
and: 1
hat: 1

Grouping under a key

A map can hold a list under each key. Here the words are grouped by their length:

Python

words = ["a", "bb", "cc", "d", "eee"]

by_length = {}
for w in words:
    by_length.setdefault(len(w), []).append(w)

for length, group in by_length.items():
    print(length, "[" + ", ".join(group) + "]")

JavaScript

const words = ["a", "bb", "cc", "d", "eee"];

const byLength = new Map();
for (const w of words) {
  if (!byLength.has(w.length)) {
    byLength.set(w.length, []);
  }
  byLength.get(w.length).push(w);
}

for (const [length, group] of byLength) {
  console.log(length, `[${group.join(", ")}]`);
}

Java

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class GroupByLength {
    public static void main(String[] args) {
        String[] words = {"a", "bb", "cc", "d", "eee"};

        Map<Integer, List<String>> byLength = new LinkedHashMap<>();
        for (String w : words) {
            byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
        }

        for (Map.Entry<Integer, List<String>> e : byLength.entrySet()) {
            System.out.println(e.getKey() + " " + e.getValue());
        }
    }
}

Here the key is a small number, so the “map” is an array indexed by length, with one row of words per length.

#include <stdio.h>
#include <string.h>

#define MAX_LEN 4
#define MAX_PER_GROUP 5

int main(void) {
    const char *words[] = {"a", "bb", "cc", "d", "eee"};
    const char *groups[MAX_LEN][MAX_PER_GROUP];
    int sizes[MAX_LEN] = {0};

    for (int i = 0; i < 5; i++) {
        int len = (int)strlen(words[i]);
        groups[len][sizes[len]] = words[i];
        sizes[len]++;
    }

    for (int len = 1; len < MAX_LEN; len++) {
        printf("%d [", len);
        for (int j = 0; j < sizes[len]; j++) {
            printf("%s%s", j > 0 ? ", " : "", groups[len][j]);
        }
        printf("]\n");
    }
    return 0;
}

All four print:

1 [a, d]
2 [bb, cc]
3 [eee]

Missing keys and unhashable keys

Asking for a key that is not there is a question every language answers differently. A map holds apples at 3, and we ask for pears:

Python

prices = {"apples": 3}

print(prices.get("pears"))
try:
    prices["pears"]
except KeyError as err:
    print("KeyError:", err)

Output

None
KeyError: 'pears'

get returns None, but square-bracket lookup raises an exception.

JavaScript

const prices = new Map([["apples", 3]]);

console.log(prices.get("pears"));
console.log(prices.has("pears"));

Output

undefined
false

A missing key gives undefined quietly, so use has when “absent” and “stored as undefined” must differ.

Java

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

public class MissingKey {
    public static void main(String[] args) {
        Map<String, Integer> prices = new HashMap<>();
        prices.put("apples", 3);

        System.out.println(prices.get("pears"));
        System.out.println(prices.containsKey("pears"));
    }
}

Output

null
false

A missing key gives null. Assigning that to an int later throws a NullPointerException.

#include <stdio.h>
#include <string.h>

static const char *names[] = {"apples"};
static int prices[] = {3};

/* Returns the index of the key, or -1 when it is absent. */
static int find(const char *key) {
    for (int i = 0; i < 1; i++) {
        if (strcmp(names[i], key) == 0) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    printf("%d\n", find("pears"));
    printf("%d\n", find("apples") >= 0 ? prices[find("apples")] : -1);
    return 0;
}

Output

-1
3

Your own map decides the convention. Here the lookup returns -1 for absent, and the caller must check it.

Keys must not change while stored, which is why languages differ on whether a list may be one:

Language	A list as a key
Python	rejected with `TypeError: unhashable type: 'list'` (the exact wording varies by version)
JavaScript `Map`	allowed, but compared by identity: a different list with the same contents is a different key
Java	allowed, and compared by contents; changing the list afterwards makes the entry impossible to find
C	not applicable: there is no built-in map

Choosing: list, map or set?

You want to	Use
Keep items in order, reach them by position, allow repeats	a list
Look something up by a name or id	a map
Count, or group things under a label	a map
Know whether something is present, or remove duplicates	a set
Combine collections (both, either, only one)	sets

If you find yourself looping through a list again and again just to find an item, a map or set is almost certainly a better fit.

Common pitfalls

Assuming an order. Do not depend on iteration order unless the language promises one. Sort the keys if the output has to be stable.
Missing keys. Reading a key that is not present raises KeyError in Python, returns undefined in a JavaScript Map, and returns null in Java. Check first, or use a default-returning form such as get(key, default).
Changeable keys. A key must not change after being stored, which is why Python rejects lists as dictionary keys.
Using a list for membership. Checking whether a list contains an item looks at every element. With thousands of items, a set is much faster.
Expecting {} to be an empty set. In Python {} is an empty dictionary; write set() for an empty set.

ExerciseWord-frequency counter

Write a program that counts how often each word occurs in "to be or not to be that is the question" and prints the words that occur more than once, together with their counts. Expected output, in order of first appearance:

to 2
be 2

Show solution

Count with a map, then print only the entries whose count is above one.

Python

text = "to be or not to be that is the question"

counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1

for word, n in counts.items():
    if n > 1:
        print(word, n)

JavaScript

const text = "to be or not to be that is the question";

const counts = new Map();
for (const word of text.split(" ")) {
  counts.set(word, (counts.get(word) ?? 0) + 1);
}

for (const [word, n] of counts) {
  if (n > 1) {
    console.log(word, n);
  }
}

Java

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

public class WordFreq {
    public static void main(String[] args) {
        String text = "to be or not to be that is the question";

        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String word : text.split(" ")) {
            counts.put(word, counts.getOrDefault(word, 0) + 1);
        }

        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            if (e.getValue() > 1) {
                System.out.println(e.getKey() + " " + e.getValue());
            }
        }
    }
}

#include <stdio.h>
#include <string.h>

#define MAX 16

static const char *keys[MAX];
static int values[MAX];
static int size = 0;

int main(void) {
    const char *words[] = {"to", "be", "or", "not", "to", "be", "that", "is", "the", "question"};
    int count = sizeof words / sizeof words[0];

    for (int i = 0; i < count; i++) {
        int at = -1;
        for (int j = 0; j < size; j++) {
            if (strcmp(keys[j], words[i]) == 0) {
                at = j;
            }
        }
        if (at >= 0) {
            values[at] += 1;
        } else {
            keys[size] = words[i];
            values[size] = 1;
            size++;
        }
    }

    for (int i = 0; i < size; i++) {
        if (values[i] > 1) {
            printf("%s %d\n", keys[i], values[i]);
        }
    }
    return 0;
}

The words are listed in an array here, because splitting text in C needs strtok, which modifies its input.

All four print:

to 2
be 2

ExerciseRemove duplicates, keep order

Given [4, 1, 4, 2, 1, 3], produce [4, 1, 2, 3]: each value once, in the order it first appeared. Why is “put the values in a set and take them back out” not a reliable answer?

Show solution

Keep a set of values already seen. The set makes each check fast, and the list preserves the order.

Python

values = [4, 1, 4, 2, 1, 3]

seen = set()
result = []
for v in values:
    if v not in seen:
        seen.add(v)
        result.append(v)
print(result)

JavaScript

const values = [4, 1, 4, 2, 1, 3];

const seen = new Set();
const result = [];
for (const v of values) {
  if (!seen.has(v)) {
    seen.add(v);
    result.push(v);
  }
}
console.log(`[${result.join(", ")}]`);

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DedupeOrdered {
    public static void main(String[] args) {
        int[] values = {4, 1, 4, 2, 1, 3};

        Set<Integer> seen = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        for (int v : values) {
            if (!seen.contains(v)) {
                seen.add(v);
                result.add(v);
            }
        }
        System.out.println(result);
    }
}

#include <stdbool.h>
#include <stdio.h>

#define N 10   /* the values are whole numbers 0 to 9 */

int main(void) {
    int values[] = {4, 1, 4, 2, 1, 3};
    bool seen[N] = {false};
    int result[6];
    int size = 0;

    for (int i = 0; i < 6; i++) {
        if (!seen[values[i]]) {
            seen[values[i]] = true;
            result[size++] = values[i];
        }
    }

    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%s%d", i > 0 ? ", " : "", result[i]);
    }
    printf("]\n");
    return 0;
}

All four print:

[4, 1, 2, 3]

Converting a set back to a list removes duplicates, but a plain set promises no particular order (Java’s HashSet, for example), so the result may come back in a different order from the input.

ExerciseList or map?

You have 50,000 customer records, each with a unique id, and your program must find a customer by id thousands of times. Would you store them in a list or a map, and why? Expected: one choice and a reason in a sentence or two.

Show solution

A map keyed by customer id. Each lookup goes straight to the record. With a list you would scan through up to 50,000 records for every lookup, which adds up fast when you do it thousands of times.

Summary

A map stores key/value pairs and finds a value from its key quickly, thanks to hashing. A set stores unique values and tests membership just as quickly.
Use maps to look up, count and group; use sets to remove duplicates and combine collections.
Do not rely on order unless the language promises it, and make sure keys cannot change.

Next: Grouping data: records and objects, for values that belong together but are not alike.