Day 4: Hash Tables

What You'll Learn Today

• How hash tables work
• The role of hash functions
• Collision resolution strategies
• JavaScript's Map and Set

---

What Is a Hash Table?

A hash table stores key-value pairs and provides O(1) average-time lookups by key.

flowchart LR
    K1["key: 'name'"] --> HF["Hash Function"]
    HF --> I["index: 3"]
    I --> B["Bucket[3]"]
    B --> V["value: 'Alice'"]
    style HF fill:#3b82f6,color:#fff
    style B fill:#22c55e,color:#fff

How It Works

1. Pass the key to a hash function
2. The hash function produces an index (number)
3. Store the data at that index position

---

Hash Functions

A hash function converts arbitrary data into a fixed-size number. A good hash function must be:

• Deterministic: Same input always produces the same output
• Uniformly distributed: Outputs spread evenly across buckets
• Fast: Quick to compute

function hash(key, tableSize) {
  let total = 0;
  for (let i = 0; i < key.length; i++) {
    total += key.charCodeAt(i);
  }
  return total % tableSize;
}

console.log(hash("name", 10));
console.log(hash("age", 10));

A Better Hash Function

function betterHash(key, tableSize) {
  const PRIME = 31;
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * PRIME + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

---

Hash Table Implementation

class HashTable {
  constructor(size = 53) {
    this.table = new Array(size);
    this.size = size;
    this.count = 0;
  }

  _hash(key) {
    const PRIME = 31;
    let hash = 0;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      hash = (hash * PRIME + key.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  set(key, value) {
    const index = this._hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    const existing = this.table[index].find(pair => pair[0] === key);
    if (existing) {
      existing[1] = value;
    } else {
      this.table[index].push([key, value]);
      this.count++;
    }
  }

  get(key) {
    const index = this._hash(key);
    if (!this.table[index]) return undefined;
    const pair = this.table[index].find(pair => pair[0] === key);
    return pair ? pair[1] : undefined;
  }

  delete(key) {
    const index = this._hash(key);
    if (!this.table[index]) return false;
    const pairIndex = this.table[index].findIndex(pair => pair[0] === key);
    if (pairIndex === -1) return false;
    this.table[index].splice(pairIndex, 1);
    this.count--;
    return true;
  }

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

  keys() {
    const result = [];
    for (const bucket of this.table) {
      if (bucket) {
        for (const [key] of bucket) {
          result.push(key);
        }
      }
    }
    return result;
  }
}

const ht = new HashTable();
ht.set("name", "Alice");
ht.set("age", 30);
console.log(ht.get("name")); // "Alice"
console.log(ht.has("age"));  // true

---

Collisions

A collision occurs when different keys map to the same index.

flowchart TB
    subgraph Collision["Collision Example"]
        K1["'abc'"] --> H["hash()"] --> I3["index: 3"]
        K2["'cab'"] --> H2["hash()"] --> I3
    end
    style Collision fill:#ef4444,color:#fff

Solution 1: Separate Chaining

Store multiple entries at the same index using a list (used in the implementation above).

flowchart TB
    subgraph Table["Hash Table"]
        B0["[0]"] --> L0["null"]
        B1["[1]"] --> P1["('name','Alice')"] --> P2["('email','alice@example.com')"]
        B2["[2]"] --> L2["null"]
        B3["[3]"] --> P3["('age', 30)"]
    end
    style Table fill:#3b82f6,color:#fff

Solution 2: Open Addressing

When a collision occurs, probe for the next available slot.

class OpenAddressingHashTable {
  constructor(size = 53) {
    this.table = new Array(size);
    this.size = size;
  }

  _hash(key) {
    const PRIME = 31;
    let hash = 0;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      hash = (hash * PRIME + key.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  set(key, value) {
    let index = this._hash(key);
    while (this.table[index] !== undefined && this.table[index][0] !== key) {
      index = (index + 1) % this.size;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this._hash(key);
    while (this.table[index] !== undefined) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.size;
    }
    return undefined;
  }
}

---

Load Factor and Resizing

Load Factor = number of entries / table size

As the load factor increases, collisions become more frequent and performance degrades. Typically, resize when the load factor exceeds 0.7–0.75.

Load Factor	Performance
< 0.5	Fast
0.5 – 0.75	Good
> 0.75	Collisions increase, resize recommended

---

JavaScript's Map and Set

Map

const map = new Map();

map.set("name", "Alice");
map.set(42, "answer");
map.set(true, "boolean key");

console.log(map.get("name")); // "Alice"
console.log(map.has(42));     // true
map.delete(true);
console.log(map.size);        // 2

for (const [key, value] of map) {
  console.log(`${key}: ${value}`);
}

Set

const set = new Set();

set.add(1);
set.add(2);
set.add(2); // Duplicate ignored
set.add(3);

console.log(set.has(2)); // true
console.log(set.size);   // 3

set.delete(2);

const unique = [...new Set([1, 2, 2, 3, 3, 4])];
console.log(unique); // [1, 2, 3, 4]

Object vs. Map

Feature	Object	Map
Key types	String/Symbol	Any type
Order	Insertion order (limited)	Insertion order
Size	Object.keys(o).length	map.size
Iteration	Indirect	Direct (for...of)
Perf (frequent add/remove)	Lower	Higher

---

Practical Examples

1. Frequency Count

function countFrequency(arr) {
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) || 0) + 1);
  }
  return freq;
}

const fruits = ["apple", "banana", "apple", "cherry", "banana", "apple"];
console.log(countFrequency(fruits));
// Map { 'apple' => 3, 'banana' => 2, 'cherry' => 1 }

2. Two Sum

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

3. Anagram Check

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const char of s) {
    count.set(char, (count.get(char) || 0) + 1);
  }
  for (const char of t) {
    const c = count.get(char);
    if (!c) return false;
    count.set(char, c - 1);
  }
  return true;
}

console.log(isAnagram("listen", "silent")); // true
console.log(isAnagram("hello", "world"));   // false

---

Hash Table Time Complexities

Operation	Average	Worst
Lookup	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

The worst case occurs when all elements hash to the same bucket. A good hash function and proper resizing keep operations effectively O(1).

---

Summary

Concept	Description
Hash Table	Data structure providing O(1) key-value lookups
Hash Function	Converts keys into numeric indices
Collision	Different keys mapping to the same index
Chaining	Resolves collisions using linked lists
Load Factor	Performance metric; resize above 0.75

Key Takeaways

1. Hash tables provide O(1) average-time lookups, inserts, and deletes
2. A good hash function minimizes collisions
3. JavaScript provides built-in Map and Set
4. Prefer Map over Object for frequent additions and deletions

---

Practice Problems

Problem 1: Basic

Implement a function that finds the first non-repeating character in a string.

Problem 2: Intermediate

Implement a function that returns the intersection of two arrays using a Set.

Challenge

Find the length of the longest substring without repeating characters (hint: sliding window + hash map).

---

References

• MDN - Map
• MDN - Set
• Wikipedia - Hash table

---

Next up: In Day 5, we'll explore "Recursion & Divide and Conquer" — a powerful technique for breaking problems into smaller pieces.