Before you begin
Why this matters
Removing duplicates and asking “have I seen this before?” are among the most common jobs in a program. A Set does both, but it decides on its own which values are the same. Knowing its rule lets you predict when a duplicate stays in, and when a test is slow.
What this helps you reason about
- Predict the size of a Set after you add a value twice.
- Spot two equal-looking arrays or objects that a Set keeps as two members, and build a key that it compares by value.
- Explain why has on a Set stays fast while a search through an array slows down as the array grows, and remove duplicates without losing the order.
A school chess club keeps a list of its members. Ana signs up twice, and the club still has one Ana. This lesson shows how a TypeScript Set keeps each value once, which values it treats as the same, and why asking a Set is faster than searching an array.
Already know this? The short version
- new Set<T>() holds each value once: add of a value already there changes nothing, has tests membership, and size counts.
- A Set compares with SameValueZero: numbers and strings by value, NaN equal to NaN, and objects and arrays by identity. Two [2, 3] arrays are two members; use a string key such as "2,3".
- has on a Set looks in about one place at any size; includes on an array compares with each element in turn.
- A Set keeps insertion order, so [...new Set(list)] removes duplicates and keeps the first of each.
Words in this lesson (6)
- Set and Map
- Built-in collections: a Set holds each value at most once, and a Map stores a value under a key. Both compare object keys by identity, and numbers and strings by value.
- membership test
- Asking whether a value is in a collection. For a list, that means walking through it; a set is built to answer it quickly.
- identity
- Whether two references lead to the same object. Two objects can hold equal contents and still be two objects.
- SameValueZero
- The comparison a Set and a Map use. It works like ===, except that NaN equals NaN.
- hash
- A number computed from a key. A hash map uses it to choose the bucket where the key is stored, so equal keys must give equal hashes.
- insertion order
- The order in which keys were first added to a map. Storing a new value under a key that is already there does not change it.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / Once each
What does a set keep?
A set is a collection that holds each value at most once. Adding a value that is already in it changes nothing. A set has no positions: you do not ask for its third value, you ask whether a value is in it. That question is a membership test.
In TypeScript, new Set<string>() makes an empty Set of strings. add puts a value in, has tests membership, and size counts the values. Below, "Ana" is added twice, and the Set still holds two names.
A Set compares strings exactly. "Ana" and "ana" are two different strings, so they are two members. When capital letters should not count, add name.toLowerCase(), the name in small letters, instead of the name.
const club = new Set<string>();
club.add("Ana");
club.add("Ben");
club.add("Ana"); // already there: no change
console.log(club.size); // 2
console.log(club.has("Ben")); // true
console.log(club.has("Cleo")); // falseA set holds each value once; adding a value that is already there changes nothing.
Coming from Python: Python’s x in s is s.has(x) here, and len(s) is s.size, a property without parentheses.
Experiment
Add a name twice
Adding a value compares it with the members. The second "Ana" is equal to a member, so nothing changes. "ana" is a different string, so it is a new member.
Why it matters A set removes exact duplicates only. Decide what counts as the same, such as a name with or without capital letters, and add that form of the value.
Predict the three printed values. Then change the second club.add("Ana") to club.add("ana") and predict again.
const club = new Set<string>();
club.add("Ana");
club.add("Ben");
club.add("Ana");
console.log(club.size, club.has("Ben"), club.has("Cleo"));
What to look for
Step past each add. club shows Set(1) {"Ana"}, then Set(2) {"Ana", "Ben"}, and after the second add of "Ana" it still shows Set(2) {"Ana", "Ben"}. The run prints 2 true false. After the edit, club shows Set(3) {"Ana", "Ben", "ana"} and the run prints 3 true false. The stepper sometimes stops on the same line twice; that is normal for this debugger.
Expected output
2 true false02 / The same
What makes two entries the same?
A Set decides that two values are the same with a comparison that the specification calls SameValueZero. It works like === from Equality and comparison: numbers and strings compare by value, and objects and arrays compare by identity. It differs from === in one case: NaN equals NaN, so a Set holds at most one NaN.
So two arrays with the same contents are two members. A Set of the squares that a chess piece has visited, stored as [row, column] arrays, never finds a square with a new array: has([2, 3]) creates a new array, and no member is that array.
To compare by contents, store a key that holds the contents as a string or a number. The function key below gives "2,3" for row 2 and column 3. Two squares get the same key exactly when they are the same square.
function key(row: number, column: number): string {
return row + "," + column;
}
const visited = new Set<string>();
visited.add(key(2, 3));
visited.add(key(2, 3));
console.log(visited.size); // 1
console.log(visited.has(key(2, 3))); // trueA Set compares objects and arrays by identity; to compare contents, store a string or number key built from them.
Coming from Java: A Set never calls an equals method, and there is none to override. Two objects are one member only when they are the same object.
Coming from Python: Python refuses a list in a set because a list cannot be hashed. TypeScript accepts arrays and compares them by identity, so no error warns you.
Precisely: SameValueZero and -0
SameValueZero also treats 0 and -0 as one value, as === does; Object.is tells them apart. A WeakSet holds objects only, and it also compares them by identity.
Experiment
Add the same square twice as two arrays
Each [2, 3] creates a new array. A Set compares arrays by identity, so a new array is never a member, even with equal contents. start leads to the array that was added, so has(start) is true.
Why it matters Do not use arrays or objects as Set members when you mean their contents. Use a string key, such as "2,3".
Predict the three printed values. Then change visited.add([2, 3]); to visited.add(start); and predict again.
const visited = new Set<number[]>();
const start = [2, 3];
visited.add(start);
visited.add([2, 3]);
console.log(visited.size, visited.has([2, 3]), visited.has(start));
What to look for
After the second add, visited shows Set(2) {[2, 3], [2, 3]}: two members that look the same. The panel cannot show which array is which; has is the evidence. The run prints 2 false true. After the edit, visited shows Set(1) {[2, 3]}, and the run prints 1 false true.
Expected output
2 false true03 / Cost
How much work is a membership check?
A membership test on an array walks it. list.includes(x) compares the value with the first element, then the second, until one matches or the array ends. For a value that is missing, it compares with every element: 8 comparisons for 8 names, 10,000 for 10,000.
A Set does not walk. As in Maps, dictionaries, and hashing, it computes a hash from the value, and the hash picks the one bucket where an equal value would be stored. So has compares with about one stored value, whether the set holds 8 names or 10,000.
The difference matters when the test runs inside a loop. Checking each of 10,000 sign-ups against a array of 10,000 members can take up to 100 million comparisons; against a Set, about 10,000.
const members = ["Ana", "Ben", "Cleo", "Dev"];
// compares "Zoe" with each of the 4 names
const inList = members.includes("Zoe");
const club = new Set(members);
// looks in one bucket
const inClub = club.has("Zoe");A membership test on an array walks it; a Set looks in one place.
Precisely: what the specification promises
The ECMAScript specification requires a Set to give access times that are, on average, less than proportional to the number of values. It does not name the data structure; V8, the engine in Node.js, uses a hash table. Building a Set walks the array once, so it pays off when you test membership more than a few times.
Experiment
Count the comparisons of a list search
A list search compares with each element in turn. A missing value is compared with every element, so its cost grows with the list.
Why it matters When a program tests membership often, or in a long list, put the values in a set: it looks in one place, whatever the size.
Predict the three counts. Then add "Ida", "Jo", "Kit", "Lu" to the end of members and predict again.
const members = ["Ana", "Ben", "Cleo", "Dev",
"Eli", "Fay", "Gus", "Hal"];
// Walks the list and counts the comparisons until it finds wanted.
function steps(list: string[], wanted: string): number {
let count = 0;
for (const name of list) {
count = count + 1;
if (name === wanted) {
return count;
}
}
return count;
}
const first = steps(members, "Ana");
const last = steps(members, "Hal");
const missing = steps(members, "Zoe");
console.log(first, last, missing);
What to look for
In each call to steps, count grows by 1 on every pass of the loop. For "Ana" the call returns at 1, for "Hal" at 8, and for "Zoe" the loop ends with 8. The run prints 1 8 8. After the edit, "Hal" still takes 8, "Zoe" takes 12, and the run prints 1 8 12.
Expected output
1 8 804 / Order
How do you remove duplicates and keep the order?
A Set remembers the order in which values were first added: its insertion order. A loop over a Set gives the values in that order, and so does [...set], a spread, which makes an array of the Set’s values. So [...new Set(list)] removes duplicates and keeps the first of each.
When the key differs from the value you keep, write the loop yourself: walk the list with a seen Set, and keep a value only when seen does not have its key yet. Test before you add. After seen.add(key), has(key) is always true. Below, the key is the name in small letters, and kept holds the spelling that came first.
const signUps = ["Ana", "Ben", "ana", "Cleo", "Ben"];
const seen = new Set<string>();
const kept: string[] = [];
for (const name of signUps) {
const key = name.toLowerCase();
if (!seen.has(key)) {
seen.add(key);
kept.push(name);
}
}
// kept is ["Ana", "Ben", "Cleo"]To remove duplicates and keep the order, test the seen set first, then add.
05 / Try it
Can you predict a fresh example?
Decide for each add whether the Set already holds an equal value, by its own comparison. The next lesson, Stack and heap, shows where values are stored while a program runs. Its link is at the end of the page.
const picks = new Set<string>();
picks.add("Ben");
picks.add("ben");
picks.add("Ben");
const boards = new Set<number[]>();
boards.add([1, 2]);
boards.add([1, 2]);
console.log(picks.size, boards.size, picks.has("BEN"));
What is printed?
Reveal the reasoning
2 2 false. "Ben" and "ben" are different strings, and the second "Ben" changes nothing, so picks holds 2 values. Each [1, 2] creates a new array, and a Set compares arrays by identity, so boards holds 2 members. "BEN" is a third spelling, which picks does not hold.
Practice tickets
- SET-101 · No singer is ever listed as new → Free
- SET-102 · The pool head count is higher than the number of pupils → Sign in · Pro
- SET-103 · A seat booked three times is listed twice → Sign in · Pro