Overview#

A hash table is a data structure that quickly locates values by key. It maps keys to array positions through a hash function, achieving O(1) lookup, insertion, and deletion on average.

In JavaScript / TypeScript, the commonly used hash structures are Map, Set, and plain objects. They are widely used for deduplication, counting, caching, index building, and algorithmic problems like two sum.

The core idea of a hash table is: trade space for time.

Prerequisites

• Hash function: maps a key to a bucket position
• Array / bucket: the underlying storage is usually an array holding elements
• Collision handling: different keys may land in the same bucket

Problem Definition#

If we frequently need to answer “has this value appeared before” or “what data does this key correspond to,” linear scanning will be slow.

For example, searching in an array:

1
[12, 7, 9, 20, 31]

Each time it may scan the entire array, with complexity O(n). A hash table aims to turn this problem into:

1
key -> hash -> bucket -> value

Common needs include:

Core Principle: Step-by-Step Illustration#

The logical flow of a hash table can be broken into three steps:

1
key -> hash(key) -> index -> bucket

Suppose the capacity is 8, and the hash value of a certain key is 18:

1
index = 18 % 8 = 2

So it is placed into the bucket at index 2.

1
hash("a") % 8 = 2
2
hash("b") % 8 = 2

Basic Operations and Complexity#

In real engineering, the built-in Map / Set already handle resizing and collisions. Prefer using them rather than writing a hash table by hand.

TypeScript Implementation#

1
function countBy<T>(items: T[]): Map<T, number> {
2
  const counter = new Map<T, number>();
3

4
  for (const item of items) {
5
    counter.set(item, (counter.get(item) ?? 0) + 1);
6
  }
7

8
  return counter;
9
}
10

11
console.log(countBy(['a', 'b', 'a']));

1
function twoSum(nums: number[], target: number): [number, number] | null {
2
  const seen = new Map<number, number>();
3

4
  for (let i = 0; i < nums.length; i++) {
5
    const need = target - nums[i];
6

7
    if (seen.has(need)) {
8
      return [seen.get(need)!, i];
9
    }
10

11
    seen.set(nums[i], i);
12
  }
13

14
  return null;
15
}

1
function groupBy<T, K>(items: T[], getKey: (item: T) => K): Map<K, T[]> {
2
  const groups = new Map<K, T[]>();
3

4
  for (const item of items) {
5
    const key = getKey(item);
6
    const group = groups.get(key);
7

8
    if (group) {
9
      group.push(item);
10
    } else {
11
      groups.set(key, [item]);
12
    }
13
  }
14

15
  return groups;
16
}

Engineering Optimization: Map, Set, and Object#

General recommendations:

• When keys are not fixed fields, use Map;
• When only checking existence, use Set;
• When representing a clear object structure, use a plain object or Record.

Applications and Limitations#

Summary#

• Hash tables improve lookup efficiency through key-to-position mapping.
• Map and Set are the most commonly used hash structures in TypeScript.
• Hashing is suitable for existence checks, counting, indexing, and caching.
• It trades extra space for average O(1) query speed.
• When choosing keys, ensure stable semantics, especially for object keys and caching scenarios.