Chapter 01 · Why hash tables?01 / 23

Searching a list, one by one

Your phone’s contacts app holds names and numbers. You type dave and want his number. How does it find him?

The simplest way is to start at the first entry and check each one. Is this dave? No. This one? No… dave is 9th, so that takes 9 comparisons. Searching for zoe, who isn’t there at all, means checking all 10 before you can say “not found”.

This is a linear scan, and its cost grows with the list. A million contacts means up to a million comparisons. In Big-O terms, it’s O(n).

contacts.jsin the real world

const contacts = [
  { name: 'carol', phone: '555-0163' },
  { name: 'alice', phone: '555-0142' },
  // ...10 contacts, or 10 million
];
 
contacts.find((c) => c.name === 'dave');   // checks them one by one