Maps and sets in everyday code

Arrays find things by position. A great many problems need to find things by value instead: have I seen this number before, how many times does this word appear, where was this character last. For that, every language has a map and a set.

• A set holds values with no duplicates, and answers "is this in here?" in about one step.
• A map pairs each key with a value, like a word with its count, and finds the value for a key in about one step.

How they manage one step, however large they get, is the subject of the lesson on hash tables. This lesson is how to use them.

Sets#

unordered_set<int> seen;
seen.insert(5);
bool has = seen.count(5) > 0;     // true
seen.erase(5);
int size = seen.size();

Set<Integer> seen = new HashSet<>();
seen.add(5);
boolean has = seen.contains(5);   // true
seen.remove(5);
int size = seen.size();

seen = set()
seen.add(5)
has = 5 in seen                   # True
seen.discard(5)                   # remove, without an error if it is absent
size = len(seen)

"Does this array contain a duplicate?" becomes one pass: for each value, if it is already in the set, the answer is yes; otherwise add it.

Maps#

unordered_map<string, int> count;
count["apple"]++;                 // a missing key starts at 0
count["apple"]++;
int apples = count["apple"];      // 2

if (count.count("pear")) { ... }  // check without creating the key

for (auto& [word, n] : count) {
    // every key and its value
}

Map<String, Integer> count = new HashMap<>();
count.merge("apple", 1, Integer::sum);          // add one, starting from 0
count.merge("apple", 1, Integer::sum);
int apples = count.getOrDefault("apple", 0);    // 2

if (count.containsKey("pear")) { ... }

for (Map.Entry<String, Integer> e : count.entrySet()) {
    // e.getKey(), e.getValue()
}

count = {}
count["apple"] = count.get("apple", 0) + 1
count["apple"] = count.get("apple", 0) + 1
apples = count["apple"]                         # 2

if "pear" in count: ...

for word, n in count.items():
    ...

# Counting is common enough to have its own tool:
from collections import Counter
count = Counter(["apple", "apple", "pear"])     # {'apple': 2, 'pear': 1}

Two traps, one in each direction:

• C++: reading count[key] for a key that is not there quietly adds it with the value 0. Handy for counting, surprising when you only meant to look. Use count.count(key) or count.find(key) to check without changing anything.
• Python: reading count[key] for a key that is not there raises an error. Use count.get(key, 0), or collections.defaultdict(int), which starts missing keys at 0.

And in C#

C has no map or set in its standard library. For these problems there are two good substitutes, and you will reach for them in the other languages too because they are faster still.

When the values are small, use an array as the map. The value is the index.

// Count each lowercase letter in a string.
int count[26] = {0};
for (int i = 0; s[i] != '\0'; i++) {
    count[s[i] - 'a']++;
}
// count[0] is how many 'a', count[25] how many 'z'.

int count[26] = {0};
for (char c : s) count[c - 'a']++;

int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;

count = [0] * 26
for c in s:
    count[ord(c) - ord('a')] += 1

That is how Valid anagram is usually solved: count the letters of both words, and compare the two arrays of 26.

When the values are large, sort first. After sorting, equal values sit next to each other, so a duplicate is simply two neighbours that match. That costs n log n rather than n, which is almost always fast enough.

Order is not kept#

unordered_map, HashMap and HashSet give you their contents in no particular order, and the order can change as they grow. Never rely on it. If you need keys in sorted order, use map in C++ or TreeMap in Java, which keep keys sorted at a small extra cost. Python's dict does keep the order in which keys were first added, but a set does not.

Try it#

Contains duplicate is a set. Valid anagram is two counts compared. Two sum is a map from each value to where it was seen, and the lesson on hash maps for lookups walks through exactly why that turns a slow answer into a fast one.