Data Structures & Algorithms·Reason about cost and structure

Hash maps and frequency counting

Hash maps trade memory for fast keyed lookup and are behind many one-pass solutions.

Intermediate 14 min read Lesson 9 of 300 Challenge included

What you will be able to do

Count frequencies in one pass with a Map.
Look up the complement to avoid a nested loop.
Remember that worst-case hash collisions can degrade performance.

In plain English

A hash map stores key-value pairs with expected O(1) lookup. It is ideal for frequency counts, seen sets and complement lookups. Hashing does not preserve order; use a separate iteration order when the UI needs one.

frequencies.jsJavaScript

function topTopic(topics) {
  const counts = new Map()
  for (const topic of topics) {
    counts.set(topic, (counts.get(topic) ?? 0) + 1)
  }

  let best = null
  let bestCount = 0
  for (const [topic, count] of counts) {
    if (count > bestCount) {
      best = topic
      bestCount = count
    }
  }
  return best
}

Your turn

Find a pair sum

Medium

Use a Map or Set to find whether any two values add to a target in one pass.

JS · starter

function hasPair(values, target) {}

Check your understanding before moving on.

Knowledge checkQuestion 1

What is the expected average lookup complexity of a hash map?

Select an answer to continue

Study tools

Make it yours.

Keep a private note for this lesson, then turn the key ideas into flashcards you can revisit.

Sign in to save notes and flashcards.Both are private to your account and stay with your progress.

Finished reading?

Lock in what you just learned.

Mark this lesson complete to save your place and move one step closer to the certificate.

Next: Trees, graphs and traversal

Lesson 9 of 300 · 0% of course