# Set

## 1. What a Set Is

`Set` is a collection of **unique values** — any attempt to add a value already present is silently ignored. Equality uses the same "SameValueZero" comparison as `Map` (like `===`, except `NaN` equals itself).

```js
const set = new Set([1, 2, 2, 3, 3, 3]);
console.log(set); // Set(3) { 1, 2, 3 } — duplicates automatically dropped
console.log(set.size); // 3
```

## 2. Basic Operations

```js
const set = new Set();
set.add("a").add("b").add("a"); // chainable, "a" added only once
set.has("a");    // true
set.delete("b");
set.size;         // 1
set.clear();
```

## 3. The Fastest Way to Deduplicate an Array

```js
const nums = [1, 2, 2, 3, 3, 3, 4];
const unique = [...new Set(nums)]; // [1, 2, 3, 4]
```

This is the idiomatic, single-line way to remove duplicates — far simpler than manually tracking seen values with `filter` + `indexOf`.

## 4. Iterating a Set

```js
const tags = new Set(["js", "web", "js"]);
for (const tag of tags) console.log(tag);   // "js", "web" — insertion order, guaranteed
tags.forEach(tag => console.log(tag));
[...tags];                                    // ["js", "web"]
```

## 5. Set Algebra (Union, Intersection, Difference)

JavaScript doesn't provide these as built-in `Set` methods in most current runtimes (a newer proposal adds them natively in some engines), but they're trivial to implement with spread and `filter`:

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

const union = new Set([...a, ...b]);                    // {1, 2, 3, 4}
const intersection = new Set([...a].filter(x => b.has(x))); // {2, 3}
const difference = new Set([...a].filter(x => !b.has(x)));  // {1} — in a but not b
```

## 6. Set vs Array — When to Use Which

| Need | Use |
|---|---|
| Fast membership checks (`.has()`) on many elements | `Set` — O(1) average, vs `Array.includes` O(n) |
| Order matters and duplicates are meaningful | `Array` |
| Deduplication | `Set` |
| Need indexed access (`arr[2]`) | `Array` |

```js
// Checking membership in a large collection repeatedly:
const validIds = new Set(largeIdArray); // build once
if (validIds.has(someId)) { /* O(1) */ } // vs largeIdArray.includes(someId), which is O(n) EVERY call
```

## 7. Objects and Arrays in a Set

`Set` compares object/array values **by reference**, just like `Map` keys — two structurally identical objects are still treated as distinct members.

```js
const set = new Set();
set.add({ id: 1 });
set.add({ id: 1 }); // a DIFFERENT object, even though it looks the same
console.log(set.size); // 2, not 1
```

To deduplicate objects by *value* (e.g. by an `id` field), dedupe manually with a `Map` keyed by that field instead.

## 8. Under the Hood: How Set Actually Stores Data

![The index table hashes values to bucket indices; the entries table holds just values in insertion order](diagrams/01-ordered-hash-set.svg)

`Set` uses the **exact same ordered-hash-table design as `Map`** (see the Map topic's "Under the Hood" section for the full diagram and mechanics) — the only structural difference is that each entry stores just a key, with no associated value. In V8, `Set` is literally implemented as `OrderedHashSet`, a near-identical sibling class to `OrderedHashMap`, reusing the same index-table + entries-table pattern.

```
index table (hash -> entry index)         entries table (insertion order, values only)
┌───────────────────────────┐              ┌─────┬────────┐
│ bucket 0: -> entry 1        │              │ idx │ value   │
│ bucket 1: -> entry 0        │              ├─────┼────────┤
│ bucket 2: empty              │              │  0  │ "js"    │
└───────────────────────────┘              │  1  │ "web"   │
                                              └─────┴────────┘
```

### `.add()` on a duplicate is a hash lookup, not a scan

```js
set.add("js"); // hash("js") -> bucket -> already points to an entry with value "js" -> no-op
```

This is precisely why `Set` membership checks and duplicate rejection are O(1) average, not O(n) — `.add()` doesn't scan every existing member to check for a duplicate; it hashes the incoming value and checks whether that bucket already resolves to a matching entry, exactly like `Map.prototype.has`.

### Resize, tombstones, and object identity hashing

All three mechanics from the Map topic apply identically here:
- **Resize/rehash** — capacity roughly doubles and every live entry gets rehashed into a bigger index table once load factor crosses a threshold; amortized O(1) per `.add()`.
- **Tombstones on delete** — `.delete()` marks the entries-table slot as a hole rather than shifting everything after it; a resize later compacts these away.
- **Object identity hash** — adding an object to a `Set` triggers the same lazily-generated, GC-stable identity hash used by `Map` object keys, so the object's membership survives the garbage collector relocating it in memory.

### Why Set Beats Array for Membership Checks, Concretely

```js
const bigArray = [...]; // 100,000 items
const bigSet = new Set(bigArray);

bigArray.includes(x); // O(n) — engine scans element by element until found or exhausted
bigSet.has(x);          // O(1) average — one hash computation + one bucket lookup, regardless of size
```

This difference is invisible for small collections and dominant for large ones — exactly the kind of Big-O gap the Time and Space Complexity topic describes.

## 9. Common Pitfalls

1. **Expecting Set to deep-compare objects** — it only compares primitives by value; objects are always compared by reference.
2. **Using `set[0]` for indexed access** — Sets have no indices; convert to an array (`[...set]`) first if you need positional access.
3. **Forgetting `Set` is not JSON-serializable directly** — `JSON.stringify(new Set([1,2]))` gives `"{}"`; convert with `[...set]` first.
4. **Re-adding an existing value expecting an error or a return signal** — `.add()` on a duplicate is a silent no-op; check with `.has()` beforehand if you need to know whether it was new.

## 10. Quick Reference

```
new Set(iterable)     [...new Set(arr)] → dedupe
set.add(v).has(v).delete(v).clear()
set.size
[...a].filter(x => b.has(x))  → intersection
[...a, ...b] as a Set          → union
```