Hash maps

Remember what you have seen, keyed by what you will ask for later, so each lookup is one step instead of a search.

Start with the first problem

Draft. This pattern and its problems have not been reviewed by a second person yet.

Many slow solutions search the same list again and again: has this ID come up before, which earlier price completes this one, which messages look alike. A hash map turns each of those searches into one step. You pay a little memory to keep what you have seen, keyed by the question you will ask later.

The key is the design decision. To find a repeat, key by the value itself. To find a partner that adds up to a target, key by the value and look up target - value. To group things that look alike, key by a normalised form of each item, so items that should match produce the same key.

In JavaScript, use Map and Set rather than plain objects: any value can be a key, there are no inherited keys such as constructor to trip over, and the size is one property away.

A map holds one value per key, so decide what that value is: the first position, the latest one, a count, or a list. Most bugs here are storing the wrong one.

Recognise it

  • A direct solution compares every item with every earlier item.
  • The question is whether something was seen before, how often, or where.
  • Items need grouping by a property that can be turned into a key.

The shape of the code

const seen = new Map();          // key -> what you need to remember
for (let i = 0; i < items.length; i++) {
  const key = keyOf(items[i]);
  if (seen.has(key)) {
    // answer the question with seen.get(key)
  }
  seen.set(key, i);               // or a count, or a list
}

Problems

In order of difficulty
  1. Not started
  2. Not started
  3. Not started
Esc
↑ ↓ to move↵ to open