Basic Hashing

Count once, answer many times

Suppose you are given an array and then many questions: “How many times does 2 appear? And 4? And 3?” The obvious way is to scan the whole array again for every question:

const nums = [2, 3, 2, 5, 3, 2];const queries = [2, 4, 3];// For every query, scan the whole array again: O(n × q)for (const q of queries) {  let c = 0;  for (const x of nums) if (x === q) c++;  console.log(q, "appears", c, "times");}

With n = 100,000 values and q = 100,000 questions, that is 10¹⁰ steps. The better idea is pre-computation. Pre-computation means doing some work once, before the questions come, and saving the results. Here you walk the array once and record every count. Then you answer each question with a single lookup (reading one saved value). The total work is O(n + q). Storing values so that you can find them directly, without searching, is called hashing.

Counting with an array

A counting array is an array where the position (index) is the value you count, and the number stored there is how many times that value appears. It works when the values are small whole numbers in a known range, say 0 to 1,000. count[7] holds how many 7s there are. Reading or updating it is O(1) (it takes the same short time however big the array is), because an array can jump straight to any index.

Traced: filling a counting array

▶const nums = [2, 3, 2, 5, 3, 2];2const count = new Array(6).fill(0);3for (const x of nums) {4  count[x]++;5}6console.log(count[2], count[4]);

The cost is memory. The array needs one box for every possible value, even the unused ones. That is fine for 0 to 1,000. But values up to 10⁹, or negative values, do not fit. Then you need a Map.

The 26-letter array

The most common fixed range in interviews is “lowercase English letters”. There are 26 of them. Turn each letter into an index from 0 to 25 with its character code (Lesson 9). The character code is the number that stands for a letter: "a".charCodeAt(0) is 97, so subtracting 97 gives 0 for “a”, 1 for “b”, and so on:

function letterCounts(s) {  const count = new Array(26).fill(0);  for (const ch of s) {    count[ch.charCodeAt(0) - 97]++;     // "a" → 0, "b" → 1, … "z" → 25  }  return count;}const c = letterCounts("hello");console.log(c[4], c[11], c[25]);  // 1 2 0   (e, l, z)

Two strings are anagrams (they use exactly the same letters, such as “listen” and “silent”) exactly when their 26 counts are equal. That is a fixed 26-step comparison, however long the strings are.

Counting with a Map

For anything else, such as large numbers, negative numbers or words, use the frequency map from Lesson 10. A Map is a JavaScript collection that stores key and value pairs, and it finds a value quickly from its key. A frequency map uses each item as the key and its count as the value. It stores only the values that actually appear:

function counts(items) {  const freq = new Map();  for (const x of items) freq.set(x, (freq.get(x) ?? 0) + 1);  return freq;}const freq = counts([10, -4, 10, 1000000, -4, 10]);console.log(freq.get(10));       // 3console.log(freq.get(-4));       // 2console.log(freq.get(7) ?? 0);   // 0   never seen

Highest and lowest frequency

Once the counts exist, many questions become one simple pass over the map. It is like finding the largest value in an array, but you look at the counts instead:

function mostAndLeast(nums) {  const freq = new Map();  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);  let most = null, least = null;  for (const [value, c] of freq) {    if (most === null || c > freq.get(most)) most = value;    if (least === null || c < freq.get(least)) least = value;  }  return [most, least];}console.log(mostAndLeast([4, 1, 4, 2, 4, 2]));  // [ 4, 1 ]

There are two passes: O(n) to count, and O(k) to scan the k distinct values (the different values). The comparisons use strict > and <, so when two values have the same count, the one that was seen first wins.

Inside a hash table

How can a Map find a key without searching? A Map is built on a hash table. A hash table is a data structure that stores key and value pairs in an array, and it finds a key fast. Inside, it has an ordinary array of slots called buckets. It also has a hash function, which is a function that turns any key into a bucket number:

1. To store a key, compute hash(key) (a number) and put the entry in that bucket.
2. To look a key up, compute the same hash(key) and look only in that bucket.

The hash function does the same small amount of work however many entries the table holds. So storing and finding take O(1). Here is a very simple hash for text with 5 buckets. Add up the character codes, then take the remainder after dividing by 5.

Collisions

“cat” and “act” have the same letters, so they have the same sum and the same bucket. When two keys land in one bucket, it is called a collision. You cannot avoid collisions completely, because there are far more possible keys than buckets. The usual fix is chaining: each bucket holds a short list of entries. A lookup goes to the right bucket and checks the few entries there.

class HashTable {  constructor(size = 5) {    this.buckets = Array.from({ length: size }, () => []);  }  hash(key) {                                  // text → bucket number    let h = 0;    for (const ch of key) h += ch.charCodeAt(0);    return h % this.buckets.length;  }  set(key, value) {    const bucket = this.buckets[this.hash(key)];    for (const pair of bucket) {      if (pair[0] === key) { pair[1] = value; return; }   // update    }    bucket.push([key, value]);                             // add  }  get(key) {    const bucket = this.buckets[this.hash(key)];    for (const [k, v] of bucket) if (k === key) return v;    return undefined;  }}const t = new HashTable();t.set("cat", 1);t.set("dog", 2);t.set("act", 3);console.log(t.get("act"), t.get("dog"), t.get("cow"));  // 3 2 undefined

Real hash tables keep collisions rare in two ways:

• A good hash function spreads keys evenly over the buckets. Real ones mix the characters much more than a plain sum does, so anagrams do not collide.
• Resizing. When the table gets too full (for example, more entries than buckets), it creates a bigger bucket array and moves every entry into it. This O(n) step is rare. So the average cost per operation stays O(1).

Keys in JavaScript: what counts as “the same”

Three details about keys surprise many people in interviews. The code shows each one:

const m = new Map();m.set(1, "number one");m.set("1", "text one");console.log(m.size);              // 2   — 1 and "1" are different keys in a Mapconst obj = {};obj[1] = "number one";obj["1"] = "text one";console.log(Object.keys(obj));    // [ '1' ]   — object keys are always textconst pairs = new Map();pairs.set([1, 2], "a");console.log(pairs.get([1, 2]));   // undefined — a new array is a different objectpairs.set("1,2", "a");console.log(pairs.get("1,2"));    // a         — turn the pair into a text key

• Objects turn keys into text. obj[1] and obj["1"] are the same property. A Map keeps them apart.
• Arrays and objects are compared by identity, not by contents. Identity means “is it the very same object in memory?”. Two separate [1, 2] arrays are different keys.
• To use a pair or a list as a key, turn it into a string first. Use `${r},${c}` for a grid cell (row r, column c). Use the sorted letters of a word to group anagrams (Lesson 27).

Practice questions

In each question, decide first whether the range of values is small and fixed (use an array) or not (use a Map).

function answer(nums, queries) {  return queries.map((q) => nums.filter((x) => x === q).length);}console.log(answer([2, 3, 2, 5, 3, 2], [2, 4, 3])); // [ 3, 0, 2 ]

function answer(nums, queries) {  const freq = new Map();  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);  return queries.map((q) => freq.get(q) ?? 0);}console.log(answer([2, 3, 2, 5, 3, 2], [2, 4, 3])); // [ 3, 0, 2 ]

function smallerNumbersThanCurrent(nums) {  return nums.map((x) => nums.filter((y) => y < x).length);}console.log(smallerNumbersThanCurrent([8, 1, 2, 2, 3])); // [ 4, 0, 1, 1, 3 ]

function smallerNumbersThanCurrent(nums) {  const count = new Array(101).fill(0);  for (const x of nums) count[x]++;  const smaller = new Array(101).fill(0);  let running = 0;  for (let v = 0; v <= 100; v++) {    smaller[v] = running;          // values strictly below v    running += count[v];  }  return nums.map((x) => smaller[x]);}console.log(smallerNumbersThanCurrent([8, 1, 2, 2, 3])); // [ 4, 0, 1, 1, 3 ]console.log(smallerNumbersThanCurrent([7, 7, 7]));       // [ 0, 0, 0 ]

function repeatedCharacter(s) {  const seen = new Set();  for (const ch of s) {    if (seen.has(ch)) return ch;    seen.add(ch);  }}console.log(repeatedCharacter("abccbaacz")); // cconsole.log(repeatedCharacter("abcdd"));     // d

function repeatedCharacter(s) {  const seen = new Array(26).fill(false);  for (const ch of s) {    const i = ch.charCodeAt(0) - 97;    if (seen[i]) return ch;    seen[i] = true;  }}console.log(repeatedCharacter("abccbaacz")); // c

function areOccurrencesEqual(s) {  const freq = new Map();  for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);  return new Set(freq.values()).size === 1;}console.log(areOccurrencesEqual("abacbc")); // trueconsole.log(areOccurrencesEqual("aaabb"));  // false

function mostAndLeast(nums) {  const freq = new Map();  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);  let most = null, least = null;  for (const [v, c] of freq) {    const cm = most === null ? -1 : freq.get(most);    const cl = least === null ? Infinity : freq.get(least);    if (c > cm || (c === cm && v < most)) most = v;    if (c < cl || (c === cl && v < least)) least = v;  }  return [most, least];}console.log(mostAndLeast([10, 5, 10, 15, 10, 5])); // [ 10, 15 ]console.log(mostAndLeast([2, 2, 1, 1]));           // [ 1, 1 ]

function frequencySort(s) {  const freq = new Map();  for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);  return [...freq]    .sort((a, b) => b[1] - a[1])    .map(([ch, c]) => ch.repeat(c))    .join("");}console.log(frequencySort("tree")); // eetrconsole.log(frequencySort("Aabb")); // bbAa

function frequencySort(s) {  const freq = new Map();  for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);  const buckets = Array.from({ length: s.length + 1 }, () => []);  for (const [ch, c] of freq) buckets[c].push(ch);  let out = "";  for (let c = s.length; c >= 1; c--) {    for (const ch of buckets[c]) out += ch.repeat(c);  }  return out;}console.log(frequencySort("tree")); // eetrconsole.log(frequencySort("Aabb")); // bbAa

class MyHashMap {  constructor() {    this.size = 1009;                     // a prime spreads keys more evenly    this.buckets = Array.from({ length: this.size }, () => []);  }  bucket(key) {    return this.buckets[key % this.size];  }  put(key, value) {    const b = this.bucket(key);    for (const pair of b) {      if (pair[0] === key) { pair[1] = value; return; }    }    b.push([key, value]);  }  get(key) {    for (const [k, v] of this.bucket(key)) if (k === key) return v;    return -1;  }  remove(key) {    const b = this.bucket(key);    const i = b.findIndex((pair) => pair[0] === key);    if (i !== -1) b.splice(i, 1);  }}const m = new MyHashMap();m.put(1, 1);m.put(2, 2);console.log(m.get(1)); // 1console.log(m.get(3)); // -1m.put(2, 1);console.log(m.get(2)); // 1m.remove(2);console.log(m.get(2)); // -1

Make it stick

Part 2 complete — what's next

You can now read a problem, estimate its cost with Big-O, use basic maths, write recursion, and count with arrays and Maps. These are the thinking tools for everything that follows.

Part 3 — Sorting starts with three simple sorting algorithms. Sorting means putting items in order. You will rarely write these three in an interview. But they show exactly what sorting does, and they explain why the faster ones in Lessons 17 and 18 are faster.