Array Cart vs Map Cart
The same cart held two ways: an array, where adding an existing product is a scan, and a map keyed by product id, where it is a key lookup. Simplicity, lookup, ordering, serialisation and memory each move, and for ten items none of the movement is visible.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
Two engineers implement the same cart, one with an array and one with a map. Both pass every test. Which one is right, and what would have to change for the other to be?
I wrote the cart with an array because it was the first thing I thought of. Then I read that "you should use a hash map for lookups" and now I am not sure whether my version is naive. Rewriting it feels like the responsible thing to do, but I cannot say what would be better afterwards, only that it would look more like the article.
Rewrite it as a map. The rewrite is concrete, the article was confident, and a cart keyed by product id looks more deliberate than one that scans a list. The change is small enough to make in an afternoon and the diff is proof that something was improved.
After the rewrite the tests still pass, which is the only thing that was true before. Nothing has been measured, no operation got cheaper at cart size, and the reason for the change is still "the article said so" — an opinion moved from a browser tab into the codebase.
- After the rewrite the tests still pass, which is the only thing that was true before. Nothing has been measured, no operation got cheaper at cart size, and the reason for the change is still "the article said so" — an opinion moved from a browser tab into the codebase.
- The conversion the map needs at the JSON boundary appears —
Object.fromEntries,Array.from(map.values())— and it appears in the render path and the save path, so the "cleaner" cart now has two conversions the array version never had. The awkwardness is explained as normal rather than noticed as a cost. - Order changes. The array rendered the cart in the order things were added; the map does so in JavaScript, and would not in C++ or in an older runtime — a property the cart depended on has become a property of the language, unwritten.
- The trade-off was never laid out, so the next reader repeats the loop in reverse: "why is this a map? An array would be simpler." Without a written comparison, every representation choice is re-litigated by whoever reads it next.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Put both representations side by side and run the same operation through each, on the same example.
[ Laptop × 1 ], add Laptop. In the array, add scans for an entry with the product id, finds it at index 0 and increments; in the map, add looks up the keylaptop, finds it and increments. Same before, same after; different path. - Name the axes that actually move between them, and refuse the ones that do not. Simplicity, lookup cost, ordering, serialisation and memory move; correctness does not — both keep every rule. Score each axis honestly, and attach a caveat: at a handful of items the lookup difference is invisible, so the score is about growth, not about today.
- Annotate the cost where it lives. Beside the array's add write "O(n) scan for the existing entry"; beside the map's write "O(1) average lookup". Beside view write "O(n) both, order preserved in the array, language-dependent in the map". The annotation is what makes "the map is faster" a checkable claim instead of a mood (Complexity, Annotated Not Asserted).
- Choose by the frequent operation, the rule you most need to be structural, and the boundary the cart crosses most — and write the condition that would flip it. For the cart that condition is size (thousands of lines) or a server holding many carts keyed by owner; until then the array is the simpler thing that keeps every rule.
The axes that move, and the caveat that governs them
The matrix scores the two representations on the axes that actually differ between them and holds the others equal. Reliability, cost and security are not in it because an array and a map in the same process do not differ on them, and giving them scores would be fake precision dressed as rigour.
The caveat is not a footnote. It says when the performance column stops being a prediction about growth and becomes a fact about today — and for a cart it never does.
| Option | Simplicity | Performance | Maintainability | Note |
|---|---|---|---|---|
| Array of CartItem | Order and JSON for free; every language has one; the "one entry per product" rule is a find before the push that a reader must know is load-bearing. | |||
| Map<ProductId, CartItem> | Lookup by key is O(1) average and the key cannot repeat; a conversion at every JSON boundary and an insertion-order guarantee that belongs to the language, not to the cart. |
caveat The performance column is about growth, not about today: below roughly a thousand entries a scan and a hash lookup are both a handful of operations and cannot be told apart without a measurement. The simplicity column is about the boundaries — the map's cost is paid at every render and every save, not in the add. Memory moves too, slightly against the map, and is omitted because at cart size it is noise.
The same operation, two paths
Here is add, in language-neutral pseudocode, against each structure. Read the lines that differ: in the array the existing entry is found by walking; in the map by asking for a key. Everything else — the checks, the branch, the return — is identical, because it belongs to the operation and not to the representation.
The rule "one entry per product" is where the versions differ most instructively. In the array it is the find; delete that line and duplicates appear. In the map the key makes the duplicate impossible, and the same deletion changes nothing — which is the structural guarantee the comparison was scoring.
function addItem(cart, productId, quantity = 1):
if quantity <= 0: reject "quantity must be positive"
item = find entry in cart.items with item.productId == productId -- O(n) scan
if item exists:
item.quantity = item.quantity + quantity
else:
append { productId, quantity } to cart.items
return cartfunction addItem(cart, productId, quantity = 1):
if quantity <= 0: reject "quantity must be positive"
item = cart.items.get(productId) -- O(1) average
if item exists:
item.quantity = item.quantity + quantity
else:
cart.items.set(productId, { productId, quantity })
return cartNeither is the better version; the labels are the device's, not the lesson's. The map's lookup does not grow with the cart and its key makes "one entry per product" structural; the array's scan is invisible at cart size and it renders in order and serialises without a conversion. The line that differs is the only line the representation owns; the rest is the operation, and it survives the switch unchanged.
Same before, same after
The decisive check is that the behaviour does not move. Run the concept's own example — add-again — through either representation and the after-state is identical; only the lookup that got there differs. The Cart Lab runs every script through both engines for this reason: any disagreement is a bug, never a trade-off.
What changed is named. A state change that shows two screenshots and leaves the reader to spot the difference is not evidence; this one says which entry moved and by how much, and that the count of entries did not.
[ Laptop × 1 ]
[ Laptop × 2 ]
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Shopping Cart = A temporary collection of products the user intends to purchase, held between browsing and checkout.
- Does a cart have identity? Yes, weakly. Two carts with the same items are still two carts, because each belongs to someone and will become a different order. It needs an id once it leaves memory; in memory the variable is the identity.
- Who owns it? A shopper — a logged-in user or an anonymous session. The owner is part of the state because "my cart" has to be findable again.
- How long does it exist? From the first add until checkout or abandonment. Whether it survives a reload, a closed browser or a login is not a property of the concept; it is a persistence decision made later, and each answer changes where the cart lives.
- Should it survive reload? Usually yes for a store, usually no for a demo. V1 in memory says no; V2 browser storage says yes on one device; V3 server storage says yes everywhere the user is logged in.
- Should it survive login? Only if an anonymous cart and a logged-in cart are merged — a rule that does not exist in V1 and appears as a modification later.
- itemscollection of CartItemkeepThe cart is its items; without them nothing else means anything.
- items[].productIdidkeepThe reference to what is being bought. The catalog owns the product; the cart only points at it.
- items[].quantityinteger > 0keepTwo laptops is one entry with quantity 2, not two entries — the rule "one entry per product" needs a quantity to hold.
- owneruser id or session iddependsSo the cart can be found again by the person it belongs to.
- items[].productNamestringderiveIt would be convenient to render the cart without a catalog lookup.
- items[].pricemoneydependsThe total needs a price per item.
- totalmoneydropEvery screen shows the total.
- currencycodedependsPrices need a currency to be added.
- createdAttimestampdropAbandoned carts might be expired or emailed about.
- update Add item — the updated cart
- delete Remove item — the updated cart
- update Change quantity — the updated cart
- read View items — the list of entries — product id and quantity — for rendering
- domain Calculate total — the sum of price × quantity over the entries
- delete Clear cart — the empty cart
- • Every quantity is greater than zero.
- • One logical entry per product.
- • The total is never negative.
- • An unknown product cannot be added.
- • Quantity cannot exceed available stock — if inventory is enforced here.
How to do it
Most important first.
- Write the add operation in pseudocode against both structures before writing either in code. If one version needs a step the other does not — a conversion, a second structure for order — that step is the cost, and it belongs in the comparison (From English to Pseudocode).
- Fill a trade-off matrix across simplicity, performance and maintainability only; leave reliability, cost and security at equal, because they do not move between an array and a map in memory. Fake movement on an axis is worse than an omitted axis (The Trade-Off Matrix, Without Fake Precision).
- Write the caveat before the scores: what size the difference becomes visible at, and which operation. For the cart: "the lookup difference is invisible below roughly a thousand entries; the serialisation difference is visible on the first save".
- Check the rule the structure enforces for you. A map cannot hold the same key twice, so the "one entry per product" rule is structural; in the array it is the
findbefore thepush, and removing that line is the bug the concept's predict-the-bug case is built on (Predict the Bug). - Open the Why This Data Structure? lab with the cart preset and change only the size answer; watch the recommendation flip and read why.
Worked on a concrete problem
The move has to produce something. This is what it produced.
- The array cart from the shopping-cart concept:
items: CartItem[]; add iscart.items.find((i) => i.productId === productId)then increment orpush. Costs: add O(n) scan; remove O(n) filter; view O(n) in insertion order; total O(n). Pros: order for free, JSON for free, every language has one. Cons: the scan grows with the cart; nothing structural prevents a duplicate entry. - The map cart:
items: Map<ProductId, CartItem>; add isitems.get(productId)then increment orset. Costs: add O(1) average; remove O(1) average; view O(n), insertion order only where the language guarantees it; total O(n). Pros: "one entry per product" is structural; lookup does not grow with the cart. Cons: JSON needs a conversion; order depends on the language. - The same script through both:
[]→ add Laptop → add Laptop → add Mouse → remove Mouse. Both end at[ Laptop × 2 ], and the Cart Lab's two engines agree on every script — which is the point: the representation changed the path, not the behaviour, and any difference in the after-state would be a bug in one of them, not a trade-off. - The decision, written down: "Array, because a cart holds a handful of items, is shown in insertion order, and is saved as JSON on every change. Switch to a map when carts are large enough for the scan to show up in a measurement, or when the cart is held server-side keyed by owner and key uniqueness is the point." The concept record's
becausesays the same in one sentence.
How you know it worked
What now exists that did not before, and what question you can now ask.
- Both versions exist on paper, the same example has been run through each, and they agree on every after-state; the difference is now a cost, not a correctness question.
- Each operation has its cost annotated beside it for each structure, and the caveat says at what size the costs diverge.
- You can name the axis on which the map wins, the axis on which the array wins, and the axes that do not move — and you stopped scoring the ones that do not.
- The switch condition is written where the choice is, so the next reader finds the reason before they find the opinion.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?If I run the same example through both representations, do they agree on every after-state?
- ?Which axes actually move between these two structures, and which am I tempted to score anyway?
- ?At what size, or under which new rule, would the other structure fit better — and is that written next to the choice?
- ?What does each representation do at the boundary — JSON, rendering in order, the database — and is that cost in the comparison?
What can go wrong
- The comparison is scored on every axis including the ones that do not move, and the totals decide. A map that scores higher because reliability was given a point it did not earn is a decision made by arithmetic on invented numbers.
- The map is chosen because "lookups should be O(1)" without the size ever being asked. For a cart, the scan and the lookup are indistinguishable until the cart is far larger than any shopper's; the choice optimised a measurement nobody took (Measure Before You Optimize in Performance says why).
- The array is kept out of loyalty after the condition flips. A server holding a hundred thousand carts in an array scanned by owner is the array cart applied to a different concept, and the written switch condition existed to catch exactly that.
- The comparison is redone from scratch every time instead of being written once. The matrix and the caveat are the artefact; without them the lesson is repeated by each engineer who touches the file.
- Writing both versions, even in pseudocode, is more work than writing one; for a concept whose size can never grow, the comparison is an afternoon spent confirming the obvious.
- A matrix with a caveat is less satisfying than a verdict; it leaves the choice to judgment, which is the point, and which is also why some readers will still want the article's rule.
- Choosing the simpler structure with a switch condition accepts a future rewrite that a map today would have pre-empted — at the cost of carrying conversions and an order dependency that the cart never needed.
- "The map is the professional choice and the array is the beginner's." Both are professional when chosen for a reason; the beginner's choice is whichever one was picked without the comparison. The concept record chose the array on purpose and says why.
- "O(n) versus O(1) means the map is faster." It means the map's lookup does not grow with the cart; at ten entries a scan and a hash are both a handful of operations, and the hash may be slower. The annotation is about growth, and the caveat is not optional.
- "A JavaScript Map keeps insertion order, so ordering is not a real difference." It is not a difference in JavaScript; it is in C++ and in some languages' older runtimes, and the four-language view in the concept ladder is where that shows. A property of the language is a property the cart depends on without saying so.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- SCALE-SPECIFICThe array is the recommendation for a cart of a handful of items. At thousands of entries per collection, or many collections keyed by owner on a server, the scan shows up in a measurement and the map is the recommendation; the lesson's method is unchanged, its verdict flips.
- SIMPLIFIEDArray and map are compared as if they were the only two in-memory options; a sorted structure, a set of ids beside an array, or an array with an index map are all real and are left out so that the axes stay readable. The Why This Data Structure? lab adds them.
- ILLUSTRATIVETen items, a thousand entries, a hundred thousand carts — every number here is for the shape of the argument; the size at which the scan becomes measurable depends on the runtime and the item shape, and has to be measured, not quoted.
Where the depth lives
This domain asks the question and hands the answer off by name.