Lookup tables: finding one thing quickly

Finding one record in an array means walking it until you hit a match. For a list of ten, that is nothing. For a list of ten thousand, it is ten thousand comparisons — and if you do that inside a loop over another ten thousand things, you have just asked the machine to do a hundred million comparisons for a job that should have been instant.

This is the shape of a great many slow programs, and it is almost never noticed while the test data is small. It is worth learning the fix before you meet the problem, because the fix is easy and the diagnosis is not.

The fix is a LOOKUP TABLE, sometimes called an index: an object whose property names are the ids you search by, and whose values are the records themselves. Once it is built, finding a record is one step regardless of how many records there are, because reaching for a named property does not involve searching.

A pile of letters is an array. To find the one from Ada you go through them one at a time. Two hundred letters, two hundred looks, and adding a letter to the pile makes every future search a little slower.

A phone book is a lookup table. You do not read it from the start; you go straight to the name. A phone book with ten times as many names is not ten times slower to use, and that is the whole point.

The catch is the same in both worlds: somebody had to compile the phone book. Building the index is itself one walk through the list. So a lookup table pays for itself when you will look things up more than once — and costs you slightly when you only ever look once.

An object's property names are strings. (There is one exception, symbols, which you will not need for a long time.) Anything else you put inside the square brackets is converted to a string first, before the lookup happens.

That means table[7] and table["7"] are the same property, and so are table[true] and table["true"]. It is why Object.keys on an object you indexed by number gives you ["7"] with quotation marks, and it can be genuinely confusing the first time you see it.

Most of the time this is harmless, because ids from a database or an API are text anyway. Where it matters is when two different keys flatten to the same string. The number 1 and the text "1" become one property. Two different objects used as keys both become the text "[object Object]" and collide with each other. Lesson 4 is about the tool that fixes exactly this.

A plain object is not empty even when you have put nothing in it. It inherits a handful of properties, among them toString, valueOf and constructor. So counts.toString on an object you just created does not give you undefined — it gives you a function.

This turns into a real bug the moment your keys come from data rather than from you. Counting words in a document that contains the word "constructor", or indexing users by a username someone chose, and suddenly a lookup that should have missed comes back with something bizarre, or an increment tries to add 1 to a function.

There are two clean ways out. Use Object.hasOwn(table, key) to ask specifically about the object's OWN properties, ignoring anything inherited. Or use a Map, which has no inherited keys at all and is the subject of the next lesson. Both are correct; which one you reach for depends on whether you also need the thing to be JSON-serialisable.

The check you should NOT rely on is if (table[key]), because that is also false for a stored 0, a stored empty string and a stored false. Asking whether a key EXISTS and asking whether its value is truthy are two different questions, and conflating them is a bug that hides until your data contains a zero.

Building an index is always the same three steps: start with an empty object, walk the list once, and for each record set table[record.id] = record. Object.fromEntries does the same job in one call when you already have key/value pairs, and pairs with Object.entries, which goes the other way.

Decide what a duplicate key means before you build. Assigning the same property twice means the last one wins and the earlier record is gone without a word. Sometimes that is what you want; sometimes it means the ids were not unique after all and you would rather have found out. Whichever it is, it should be a decision you made and not a surprise.

And remember that an index is a derived value: it is a second view of the same records, not a second copy of the truth. If the underlying list changes, the index is stale. Build it close to where you use it, or rebuild it when the list changes — do not let a stale index float around a program pretending to be current.

Repeatedly searching an array costs one walk per search; a lookup table turns each search into a single named-property read, paid for by one walk to build it. Property names are always strings, so numeric keys come back as text. Plain objects inherit names such as toString, so use Object.hasOwn — or a Map — when the keys come from data. Treat an index as a derived view that can go stale.