Set vs map vs array: which one to use

Short answer. Pick the container by the question you ask most often. Have I seen this before? A set. What value belongs to this key? A map. What is the smallest so far? A heap. What sits at position i, and does the order matter? An array. A set or a map answers in one step on average.

Four questions

"Have I seen this before?" A set. Membership in one step, no matter the size.

"What value belongs to this key?" An associative array. Same speed, and it carries something along.

"What is the smallest so far?" A heap. Insert and take the minimum in log n.

"What is at position i, and does the order matter?" An array.

Most problems in the first half of a curriculum are one of these four in a costume.

The first two live in hash set and map.

The cost of the same operation

Finding one element:

• Unsorted array: a step per element.
• Sorted array: log n with binary search.
• Set or map: one step, on average.
• Heap: one step for the minimum. A full scan for anything else.

That first line quietly turns solutions quadratic.

A membership check inside a loop is two nested passes. On screen it looks like one loop.

When an array still wins

A set is not free. It hashes the key, follows a pointer, jumps elsewhere in memory.

Under about 100 elements, scanning an array is often faster in real time.

Modern CPU caches are built for contiguous memory.

Two more cases.

Small integer keys beat a hash map with an indexed array.

Which version is allowed is decided by the constraints.

Order, sorting, and neighbor lookups need an array or a tree. Hashing destroys order by design.

Three mistakes worth naming

Reaching for a map when a set would do. Every value is true? You wanted a set.

A set is smaller. It also says what you meant.

Object keys in JavaScript. A plain object turns every key into a string.

Object key coercion puts 1 and "1" in the same slot. An object as a key becomes "[object Object]".

A Map handles keys that are not strings.

Deleting the wrong thing. A count of zero still leaves the key in the map.

A stale zero breaks a presence check silently.

Delete the key when the count reaches zero.

How to decide in ten seconds

Before writing anything, finish this sentence: "the operation I will do thousands of times is _____."

Pick the container that does that operation in one step.

Say it out loud in an interview. Choosing a structure for a stated reason is what the question tests.

Where this sits

AlgoPath spends steps 11 to 13 on this one choice. With code you write, before any named pattern.

The cost side of the decision is in Big O explained simply.

The first 33 steps are free.