Hash Maps and Sets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function findInArray(list, target) {
  let steps = 0;
  for (const x of list) {
    steps++;
    if (x === target) return { found: true, steps };
  }
  return { found: false, steps };
}

function findInSet(set, target) {
  return { found: set.has(target), steps: 1 };   // one hash, one bucket check
}

const list = Array.from({ length: 10000 }, (_, i) => i);
const set = new Set(list);

console.log('array, worst case:', findInArray(list, 9999));
console.log('set,   worst case:', findInSet(set, 9999));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class TinyMap {
  #buckets;
  #count = 0;

  constructor(size = 8) {
    this.#buckets = Array.from({ length: size }, () => []);
  }

  #hash(key) {
    let h = 0;
    const s = String(key);
    for (let i = 0; i < s.length; i++) {
      h = (h * 31 + s.charCodeAt(i)) | 0;      // a classic string hash
    }
    return Math.abs(h) % this.#buckets.length;
  }

  set(key, value) {
    const bucket = this.#buckets[this.#hash(key)];
    const pair = bucket.find(p => p[0] === key);
    if (pair) pair[1] = value;
    else { bucket.push([key, value]); this.#count++; }
    return this;
  }

  get(key) {
    const pair = this.#buckets[this.#hash(key)].find(p => p[0] === key);
    return pair ? pair[1] : undefined;
  }

  has(key) { return this.get(key) !== undefined; }
  get size() { return this.#count; }

  /* Shows where things landed, including any collisions. */
  inspect() {
    return this.#buckets.map((b, i) => `${i}: ${b.map(p => p[0]).join(', ') || '-'}`);
  }
}

const m = new TinyMap(8);
for (const word of ['apple', 'banana', 'cherry', 'date', 'elderberry']) m.set(word, word.length);

console.log('get banana:', m.get('banana'), '| get missing:', m.get('nope'), '| size:', m.size);
console.log('bucket layout:');
m.inspect().forEach(line => console.log('  ' + line));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17const obj = {};
obj[1] = 'number one';
obj['1'] = 'string one';           // the same key: object keys are always strings
console.log('object keys:', Object.keys(obj), '→ only one entry:', obj);

const map = new Map();
map.set(1, 'number one');
map.set('1', 'string one');        // two distinct keys
console.log('map size:', map.size, '| get(1):', map.get(1), '| get("1"):', map.get('1'));

// A Map can key on anything, including objects and arrays by identity.
const keyObj = { id: 1 };
map.set(keyObj, 'keyed by an object');
console.log('object as key:', map.get(keyObj));

// A Map remembers insertion order and is directly iterable.
for (const [k, v] of map) console.log('entry:', typeof k, String(k).slice(0, 12), '→', v);

1
2
3
4
5
6
7
8const counts = {};
console.log('counts["toString"] is truthy:', Boolean(counts['toString']), '→', typeof counts['toString']);

const safe = Object.create(null);
console.log('with Object.create(null):', safe['toString']);

const asMap = new Map();
console.log('with a Map:', asMap.get('toString'));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29const words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple'];

// 1. Count occurrences. The single most common use.
const freq = new Map();
for (const w of words) freq.set(w, (freq.get(w) ?? 0) + 1);
console.log('counts:', [...freq]);

// 2. Group by a computed key.
const byFirstLetter = new Map();
for (const w of words) {
  const k = w[0];
  if (!byFirstLetter.has(k)) byFirstLetter.set(k, []);
  byFirstLetter.get(k).push(w);
}
console.log('grouped:', [...byFirstLetter]);

// 3. Index for instant lookup: value → where it was.
const firstIndex = new Map();
words.forEach((w, i) => { if (!firstIndex.has(w)) firstIndex.set(w, i); });
console.log('first index of each:', [...firstIndex]);

// 4. Remember what you have seen, to detect a repeat in one pass.
const seen = new Set();
let firstRepeat = null;
for (const w of words) {
  if (seen.has(w)) { firstRepeat = w; break; }
  seen.add(w);
}
console.log('first repeated:', firstRepeat);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// Naive: check every pair. O(n^2).
function twoSumSlow(nums, target) {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return [];
}

// One pass. For each number, the partner we need is target - number.
// If we have already seen that partner, we are done.
function twoSum(nums, target) {
  const seen = new Map();               // value → its index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

console.log('slow:', twoSumSlow([2, 7, 11, 15], 9), '| fast:', twoSum([2, 7, 11, 15], 9));
console.log('slow:', twoSumSlow([3, 2, 4], 6),      '| fast:', twoSum([3, 2, 4], 6));
console.log('duplicate values:', twoSum([3, 3], 6));
console.log('no answer:', twoSum([1, 2], 99));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22const grid = new Map();

// Wrong: a fresh array is a different object every time.
grid.set([1, 2], 'first');
console.log('lookup with an equal array:', grid.get([1, 2]));

// Right: a string key built from the parts.
const key = (r, c) => `${r},${c}`;
const cells = new Map();
cells.set(key(1, 2), 'first');
cells.set(key(3, 4), 'second');
console.log('string key works:', cells.get(key(1, 2)));

// For visited-cell tracking in a grid, a Set of string keys is the standard tool.
const visited = new Set();
visited.add(key(0, 0));
console.log('visited (0,0)?', visited.has(key(0, 0)), '| (0,1)?', visited.has(key(0, 1)));

// Or pack two small numbers into one, which avoids string allocation.
const packed = (r, c) => r * 1000 + c;
const fast = new Set([packed(1, 2)]);
console.log('packed key works:', fast.has(packed(1, 2)));

1
2
3
4
5
6
7
8
9
10const a = new Set([1, 2, 3, 4]);
const b = new Set([3, 4, 5, 6]);

console.log('union:       ', [...new Set([...a, ...b])]);
console.log('intersection:', [...a].filter(x => b.has(x)));
console.log('difference:  ', [...a].filter(x => !b.has(x)));
console.log('symmetric:   ', [...[...a].filter(x => !b.has(x)), ...[...b].filter(x => !a.has(x))]);

// Deduplicating an array is a one-liner, and it is O(n).
console.log('dedupe:', [...new Set([3, 1, 3, 2, 1])]);