15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A HashMap stores key-value pairs and answers what belongs to a key. A HashSet stores unique keys and answers whether a key was seen. Both sit on a hash table, so lookup, insert and delete take expected O(1) time. Use a map when you need counts and a set when you need only membership.
| HashMap | key to value; get(x) returns the stored count or value |
|---|---|
| HashSet | unique keys only; contains(x) answers membership |
| Repeated insert | a set ignores it; a map put replaces the value |
| Time | expected O(1) per operation under controlled load |
| Frequency map | count[x] = count[x] + 1; the first occurrence stores 1 |
| Space | O(d), where d is the number of distinct values |
A hash table stores information by key. You have already seen hash functions, collisions, chaining, open addressing, load factor, and rehashing.
The lesson uses two hash-table-based structures:
x?”x?”For frequency counting, the value stored in the map is the number of occurrences:
When a value has not appeared before, counting logic treats its prior count as zero. The update rule is:
A set cannot replace a frequency map when counts are required. A set can tell us that 4 appeared, but cannot report whether it appeared once or three times.
The key operations used here are:
map.containsKey(x): whether x has a stored valuemap.get(x): retrieve the value for present key xmap.put(x, value): create or replace the value for xset.insert(x): record membership for xset.contains(x): test whether x is already a memberRepeated insertion into a set does not create a second copy of the key.
Use this input throughout the lesson:
1index: 0 1 2 3 4 5
2values: [4, 7, 4, 2, 7, 4]Build both structures while scanning from index 0 to index 5.
Before processing any value:
1frequency map: {}
2seen set: {}At the end, the map should be:
1{4:3, 7:2, 2:1}The set should be:
1{4, 7, 2}The map contains three keys because there are three distinct values. Its stored counts add to the input length:
Start with an empty map and an empty set. Process one input value at a time.
One pass over [4, 7, 4, 2, 7, 4]: a new value is stored with count 1, a repeat adds 1 to its count, and the set only grows on new values. The map ends {4:3, 7:2, 2:1}.
The displayed set-entry order follows first appearance in the input. A set represents membership, not duplicate positions.
| State | Value read | Frequency-map change | Frequency map after the step | Seen-set change | Seen set after the step |
|---|---|---|---|---|---|
| 0 | — | none | {} | none | {} |
| 1 | 4 | 4 is absent, so store 4:1 | {4:1} | insert 4 | {4} |
| 2 | 7 | 7 is absent, so store 7:1 | {4:1, 7:1} | insert 7 | {4, 7} |
| 3 | 4 | 4 has count 1, so replace it with 2 | {4:2, 7:1} | insert 4 again; membership is unchanged | {4, 7} |
| 4 | 2 | 2 is absent, so store 2:1 | {4:2, 7:1, 2:1} | insert 2 | {4, 7, 2} |
| 5 | 7 | 7 has count 1, so replace it with 2 | {4:2, 7:2, 2:1} | insert 7 again; membership is unchanged | {4, 7, 2} |
| 6 | 4 | 4 has count 2, so replace it with 3 | {4:3, 7:2, 2:1} | insert 4 again; membership is unchanged | {4, 7, 2} |
Consider State 3.
Before reading the second 4, the map has:
14:1The previous count is 1. Reading another 4 processes one new occurrence, so the new count is 2.
1count[4] = count[4] + 1
2count[4] = 1 + 1
3count[4] = 2The set already represents membership for 4, so inserting 4 again changes nothing.
After processing:
1[4, 7, 4]the map says:
1{4:2, 7:1}Those are the exact occurrence counts in that processed prefix. The set says:
1{4, 7}Those are exactly the distinct values in that prefix.
The following invariant holds after every step:
Invariant: After processing the first
iinput values, the frequency map stores the exact occurrence count of every value seen in that prefix, and the set contains exactly the distinct values in that prefix.
For the six-value example:
Processed prefix length i | Processed prefix | Map counts are exact for that prefix | Set contains exactly the distinct prefix values |
|---|---|---|---|
| 0 | [] | {} | {} |
| 1 | [4] | {4:1} | {4} |
| 2 | [4, 7] | {4:1, 7:1} | {4, 7} |
| 3 | [4, 7, 4] | {4:2, 7:1} | {4, 7} |
| 4 | [4, 7, 4, 2] | {4:2, 7:1, 2:1} | {4, 7, 2} |
| 5 | [4, 7, 4, 2, 7] | {4:2, 7:2, 2:1} | {4, 7, 2} |
| 6 | [4, 7, 4, 2, 7, 4] | {4:3, 7:2, 2:1} | {4, 7, 2} |
Each input item contributes exactly one increment to one map entry. After all values are processed:
For this example:
For each current value x:
x.x.count[x] as 1.1.x into the set.
x is new, the set gains it.x is already present, the set remains unchanged.Use a map when the result must answer questions such as:
1How many times did 4 occur?Use a set when the result only needs to answer:
1Did 4 occur?If only frequencies are needed, the set is unnecessary. It appears in this algorithm to make the difference between counting and membership explicit.
The procedure below scans the input once and returns both structures.
Input: values, a sequence of values indexed from 0 through values.length - 1
Return value: a pair (counts, seen) where counts maps each observed value to its occurrence count, and seen contains each observed distinct value
Mutation behavior: values is not modified. The procedure creates and mutates new local map and set objects.
Boundary behavior: if values is empty, return ({}, {}).
new Map() returns an empty map.new Set() returns an empty set.counts.containsKey(x) returns true exactly when x has an entry in counts.counts.get(x) requires counts.containsKey(x) to be true and returns the stored count.counts.put(x, c) stores count c for key x, replacing an existing count if present.seen.insert(x) ensures that x belongs to seen; inserting an existing key leaves the set unchanged.1procedure scanValues(values):
2 1. counts ← new Map()
3 2. seen ← new Set()
4
5 3. for index ← 0 to values.length - 1:
6 4. x ← values[index]
7
8 5. if counts.containsKey(x):
9 6. oldCount ← counts.get(x)
10 7. counts.put(x, oldCount + 1)
11 8. else:
12 9. counts.put(x, 1)
13
14 10. seen.insert(x)
15
16 11. return (counts, seen)For a frequency-only task, keep lines 1 and 3 through 9, then return counts. The seen set is unnecessary when the required output is only the map.
Dry-run scanValues([4, 7, 4, 2, 7, 4]).
| Executed line(s) | index | x | counts | seen |
|---|---|---|---|---|
| 1 | — | — | {} | not created yet |
| 2 | — | — | {} | {} |
| 3–4 | 0 | 4 | {} | {} |
| 5 | 0 | 4 | containsKey(4) is false | {} |
| 8–9 | 0 | 4 | {4:1} | {} |
| 10 | 0 | 4 | {4:1} | {4} |
| 3–4 | 1 | 7 | {4:1} | {4} |
| 5 | 1 | 7 | containsKey(7) is false | {4} |
| 8–9 | 1 | 7 | {4:1, 7:1} | {4} |
| 10 | 1 | 7 | {4:1, 7:1} | {4, 7} |
| 3–4 | 2 | 4 | {4:1, 7:1} | {4, 7} |
| 5 | 2 | 4 | containsKey(4) is true | {4, 7} |
| 6 | 2 | 4 | oldCount = 1 | {4, 7} |
| 7 | 2 | 4 | {4:2, 7:1} | {4, 7} |
| 10 | 2 | 4 | {4:2, 7:1} | {4, 7} |
| 3–4 | 3 | 2 | {4:2, 7:1} | {4, 7} |
| 5 | 3 | 2 | containsKey(2) is false | {4, 7} |
| 8–9 | 3 | 2 | {4:2, 7:1, 2:1} | {4, 7} |
| 10 | 3 | 2 | {4:2, 7:1, 2:1} | {4, 7, 2} |
| 3–4 | 4 | 7 | {4:2, 7:1, 2:1} | {4, 7, 2} |
| 5 | 4 | 7 | containsKey(7) is true | {4, 7, 2} |
| 6 | 4 | 7 | oldCount = 1 | {4, 7, 2} |
| 7 | 4 | 7 | {4:2, 7:2, 2:1} | {4, 7, 2} |
| 10 | 4 | 7 | {4:2, 7:2, 2:1} | {4, 7, 2} |
| 3–4 | 5 | 4 | {4:2, 7:2, 2:1} | {4, 7, 2} |
| 5 | 5 | 4 | containsKey(4) is true | {4, 7, 2} |
| 6 | 5 | 4 | oldCount = 2 | {4, 7, 2} |
| 7 | 5 | 4 | {4:3, 7:2, 2:1} | {4, 7, 2} |
| 10 | 5 | 4 | {4:3, 7:2, 2:1} | {4, 7, 2} |
| 11 | — | — | return {4:3, 7:2, 2:1} | return {4, 7, 2} |
The loop ends after index 5, because that is the final valid index of a six-value input.
We prove that scanValues returns correct frequency counts and correct distinct-value membership.
Before the loop begins, lines 1 and 2 create:
1counts = {}
2seen = {}Zero values have been processed.
The empty map gives exact counts for the empty prefix because no value has occurred. The empty set contains exactly the distinct values of the empty prefix because there are none.
So the invariant holds before the first iteration.
Assume that before an iteration at index, the invariant is true for the first index values.
Let:
1x = values[index]There are two map cases.
Case 1: x is not in counts.
By the invariant, x has not appeared in the already processed prefix. Line 9 stores:
1counts[x] = 1The current input value is the first occurrence of x, so its exact count in the expanded prefix is 1. Counts for every other key are unchanged, so they remain exact.
Case 2: x is already in counts.
By the invariant, counts[x] equals the number of occurrences of x in the processed prefix. Lines 6 and 7 read that exact count and add exactly one:
1counts[x] = oldCount + 1The current input contributes one new occurrence of x. The updated count is exact. No count for another value is changed.
In both cases, line 10 inserts x into seen.
x is new, the set gains the new distinct value.x was already present, duplicate insertion leaves membership unchanged.After the iteration, seen contains exactly the distinct values in the processed prefix including x.
So the invariant is preserved.
The loop processes every index from 0 through values.length - 1. When it ends, all input values have been processed.
By the invariant:
counts stores the exact occurrence count of every value in the full input.seen contains exactly the distinct values in the full input.Because every processed value caused exactly one increment or first-count write, the sum of all map counts equals values.length.
Thus the returned structures satisfy their required results.
Let:
n be values.lengthd be the number of distinct values in valuesThe loop runs once for each input value:
1index = 0, 1, 2, ..., n - 1So it performs n iterations.
During each iteration, the pseudocode performs:
containsKey(x).Under controlled hash-table load, these map and set operations have expected cost per iteration.
Therefore, scanning all n values takes expected:
time.
The map has one entry per distinct input value. The set also has one entry per distinct input value. Each has at most d entries, so the auxiliary structures use:
auxiliary space.
If the task returns the map, that map is output storage. The same O(d) bound describes the returned map’s size. If auxiliary space excludes returned output, the frequency-only version can still be described separately according to the convention being used; it creates one output map with d entries.
Individual hash-table operations can have collision-dependent worst cases, as established by collision handling and load-factor behavior. The expected bound here depends on the expected lookup, update, and insertion costs under controlled load.
Incorrect line:
1counts.put(x, 1)when executed for every input value.
Smallest exposing input:
1[4, 4, 4]Wrong state after the scan:
1{4:1}Each later 4 overwrites the earlier count instead of extending it.
Correction:
For an existing key, read the prior count and increment it:
1oldCount ← counts.get(x)
2counts.put(x, oldCount + 1)The correct result is:
1{4:3}Incorrect assumption:
1A set alone can produce occurrence counts.Smallest exposing input:
1[4, 7, 4]Wrong result:
1{4, 7}The set shows that 4 and 7 appeared, but it has no stored value that can report that 4 occurred twice.
Correction:
Use a map from value to count:
1{4:2, 7:1}Incorrect line:
1counts.put(x, counts.get(x) + 1)without first establishing that x is present.
Smallest exposing input:
1[2]Wrong state or behavior:
1counts.get(2)has no defined stored count because 2 is absent. Depending on the map API, this can be an invalid lookup or produce an undefined value.
Correction:
Check presence first. If the key is absent, store 1. Equivalently, counting logic may use an API that explicitly defines an absent frequency as zero.
1if counts.containsKey(x):
2 counts.put(x, counts.get(x) + 1)
3else:
4 counts.put(x, 1)Incorrect assumption:
1seen.size() equals values.lengthSmallest exposing input:
1[4, 4, 7]Wrong result:
1size = 3But a set keeps one membership representation per distinct key:
1{4, 7}Its size is 2, not 3.
Correction:
Use set size only for the number of distinct values. Use the sum of map counts for the total number of processed values.
| Input or query | Correct map | Correct set or query result |
|---|---|---|
[] | {} | {} |
[4] | {4:1} | {4} |
[4, 4, 4] | {4:3} | {4} |
[1, 2, 3] | {1:1, 2:1, 3:1} | size 3 |
query count of absent 9 | return 0 only if the API defines absent frequency as zero; otherwise report absence explicitly | — |
[-1, -1, 2] | {-1:2, 2:1} | {-1, 2} |
Negative values do not change the counting rule: keys are compared by equality. The selected hash implementation must support its documented key domain.
Implement:
1frequencyMap(values)It returns a map from each integer in values to its occurrence count.
The executable tests will check:
values.length.For this practice objective, return only the frequency map. The set is not part of the required return value because the task asks for counts, not only membership.
1def scan_values(values):
2 counts = {}
3 seen = set()
4 for x in values:
5 if x in counts:
6 counts[x] = counts[x] + 1 # existing key: read the old count, add one
7 else:
8 counts[x] = 1 # first occurrence
9 seen.add(x) # a repeat leaves the set unchanged
10 return counts, seen
11
12values = [4, 7, 4, 2, 7, 4]
13counts, seen = scan_values(values)
14print("counts: {" + ", ".join(f"{k}:{v}" for k, v in counts.items()) + "}")
15print("seen: {" + ", ".join(str(k) for k in counts) + "}") # dict keeps first-appearance order
16print("sum of counts:", sum(counts.values()), "= input length", len(values))
17print("distinct values:", len(seen))1import java.util.LinkedHashMap;
2import java.util.LinkedHashSet;
3import java.util.Map;
4import java.util.Set;
5
6public class Main {
7 public static void main(String[] args) {
8 int[] values = {4, 7, 4, 2, 7, 4};
9 Map<Integer, Integer> counts = new LinkedHashMap<>(); // keeps first-appearance order
10 Set<Integer> seen = new LinkedHashSet<>();
11 for (int x : values) {
12 if (counts.containsKey(x)) {
13 counts.put(x, counts.get(x) + 1); // existing key: read the old count, add one
14 } else {
15 counts.put(x, 1); // first occurrence
16 }
17 seen.add(x); // a repeat leaves the set unchanged
18 }
19
20 StringBuilder sb = new StringBuilder("counts: {");
21 int sum = 0;
22 boolean first = true;
23 for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
24 sb.append(first ? "" : ", ").append(e.getKey()).append(":").append(e.getValue());
25 sum += e.getValue();
26 first = false;
27 }
28 System.out.println(sb.append("}"));
29 System.out.println("seen: " + seen.toString().replace('[', '{').replace(']', '}'));
30 System.out.println("sum of counts: " + sum + " = input length " + values.length);
31 System.out.println("distinct values: " + seen.size());
32 }
33}1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <vector>
5using namespace std;
6
7int main() {
8 vector<int> values = {4, 7, 4, 2, 7, 4};
9 unordered_map<int, int> counts;
10 unordered_set<int> seen;
11 vector<int> order; // unordered_map has no order, so record first appearances
12 for (int x : values) {
13 if (counts.count(x)) {
14 counts[x] = counts[x] + 1; // existing key: read the old count, add one
15 } else {
16 counts[x] = 1; // first occurrence
17 order.push_back(x);
18 }
19 seen.insert(x); // a repeat leaves the set unchanged
20 }
21
22 int sum = 0;
23 cout << "counts: {";
24 for (size_t i = 0; i < order.size(); i++) {
25 cout << (i ? ", " : "") << order[i] << ":" << counts[order[i]];
26 sum += counts[order[i]];
27 }
28 cout << "}" << endl;
29 cout << "seen: {";
30 for (size_t i = 0; i < order.size(); i++) cout << (i ? ", " : "") << order[i];
31 cout << "}" << endl;
32 cout << "sum of counts: " << sum << " = input length " << values.size() << endl;
33 cout << "distinct values: " << seen.size() << endl;
34}1const values = [4, 7, 4, 2, 7, 4];
2const counts = new Map(); // keeps first-appearance order
3const seen = new Set();
4for (const x of values) {
5 if (counts.has(x)) {
6 counts.set(x, counts.get(x) + 1); // existing key: read the old count, add one
7 } else {
8 counts.set(x, 1); // first occurrence
9 }
10 seen.add(x); // a repeat leaves the set unchanged
11}
12
13let sum = 0;
14for (const c of counts.values()) sum += c;
15console.log(`counts: {${[...counts].map(([k, v]) => `${k}:${v}`).join(', ')}}`);
16console.log(`seen: {${[...seen].join(', ')}}`);
17console.log(`sum of counts: ${sum} = input length ${values.length}`);
18console.log(`distinct values: ${seen.size}`);No. A set shows that 4 appeared but not whether it appeared once or three times. For [4, 7, 4] the set is {4, 7}. The map {4:2, 7:1} keeps the counts.
Scan once. If x is in the map, store its old count plus 1. Otherwise store 1. The input [4, 7, 4, 2, 7, 4] gives {4:3, 7:2, 2:1}, and the counts sum to 6, the input length.
In Java, yes. HashSet stores each element as a key in an internal HashMap with a placeholder value. Conceptually, a set is a map that ignores values.
No. A set keeps one entry per distinct value. For [4, 4, 7] its size is 2 and the length is 3. The sum of the map counts gives the number of values processed.
It depends on the API. Java's HashMap.get returns null, Python's dict[x] raises KeyError, and C++ operator[] inserts a zero. Check for the key first, or use a default.