Hash Tables

What is a Hash Table?

A hash table (also called hash map) is a data structure that implements an associative array, mapping keys to values. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found. Hash tables offer average O(1) time complexity for search, insert, and delete operations!

How Hash Tables Work

// Simple hash table example
Key: "apple"  → Hash Function → Index: 3
Key: "banana" → Hash Function → Index: 7
Key: "orange" → Hash Function → Index: 2

Array:
[0] → null
[1] → null
[2] → "orange" = 5
[3] → "apple" = 10
[4] → null
[5] → null
[6] → null
[7] → "banana" = 3

Hash Functions

A good hash function should:

• Be deterministic (same input always gives same output)
• Distribute keys uniformly across the table
• Be fast to compute
• Minimize collisions

Simple Hash Function

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

console.log(simpleHash("apple", 10));   // Index in 0-9
console.log(simpleHash("banana", 10));  // Index in 0-9

Better Hash Function (djb2)

function djb2Hash(key, tableSize) {
  let hash = 5381;
  
  for (let i = 0; i < key.length; i++) {
    // hash * 33 + char
    hash = ((hash << 5) + hash) + key.charCodeAt(i);
  }
  
  return Math.abs(hash % tableSize);
}

Collision Handling

Collisions occur when two keys hash to the same index. Two main methods:

1. Chaining (Separate Chaining)

Each bucket stores a linked list of all elements that hash to that index.

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

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

  set(key, value) {
    const index = this._hash(key);
    
    // Initialize bucket if empty
    if (!this.table[index]) {
      this.table[index] = [];
    }
    
    // Check if key exists and update
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    
    // Add new key-value pair
    this.table[index].push([key, value]);
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.table[index];
    
    if (!bucket) return undefined;
    
    // Search in bucket
    for (let pair of bucket) {
      if (pair[0] === key) {
        return pair[1];
      }
    }
    
    return undefined;
  }

  remove(key) {
    const index = this._hash(key);
    const bucket = this.table[index];
    
    if (!bucket) return false;
    
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        return true;
      }
    }
    
    return false;
  }

  keys() {
    const keys = [];
    for (let bucket of this.table) {
      if (bucket) {
        for (let pair of bucket) {
          keys.push(pair[0]);
        }
      }
    }
    return keys;
  }

  values() {
    const values = [];
    for (let bucket of this.table) {
      if (bucket) {
        for (let pair of bucket) {
          values.push(pair[1]);
        }
      }
    }
    return values;
  }
}

// Usage
const ht = new HashTableChaining();
ht.set("apple", 10);
ht.set("banana", 5);
ht.set("orange", 8);
console.log(ht.get("apple"));    // 10
console.log(ht.keys());          // ['apple', 'banana', 'orange']

2. Open Addressing (Linear Probing)

If a collision occurs, search for the next empty slot.

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

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

  set(key, value) {
    if (this.count / this.size > 0.7) {
      this._resize();
    }
    
    let index = this._hash(key);
    
    // Linear probing - find next empty slot
    while (this.table[index] !== undefined) {
      // Update if key exists
      if (this.table[index][0] === key) {
        this.table[index][1] = value;
        return;
      }
      index = (index + 1) % this.size;
    }
    
    this.table[index] = [key, value];
    this.count++;
  }

  get(key) {
    let index = this._hash(key);
    const startIndex = index;
    
    while (this.table[index] !== undefined) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.size;
      
      // Wrapped around - not found
      if (index === startIndex) break;
    }
    
    return undefined;
  }

  _resize() {
    const oldTable = this.table;
    this.size = this.size * 2;
    this.table = new Array(this.size);
    this.count = 0;
    
    for (let item of oldTable) {
      if (item !== undefined) {
        this.set(item[0], item[1]);
      }
    }
  }
}

Common Hash Table Problems

1. Two Sum (Using Hash Map)

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 null;
}

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

2. Group Anagrams

function groupAnagrams(strs) {
  const map = new Map();
  
  for (let str of strs) {
    // Sort string as key
    const sorted = str.split('').sort().join('');
    
    if (!map.has(sorted)) {
      map.set(sorted, []);
    }
    
    map.get(sorted).push(str);
  }
  
  return Array.from(map.values());
}

console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

3. First Non-Repeating Character

function firstNonRepeating(str) {
  const charCount = new Map();
  
  // Count frequencies
  for (let char of str) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }
  
  // Find first with count 1
  for (let char of str) {
    if (charCount.get(char) === 1) {
      return char;
    }
  }
  
  return null;
}

console.log(firstNonRepeating("leetcode"));  // 'l'

4. Subarray Sum Equals K

function subarraySum(nums, k) {
  const map = new Map([[0, 1]]);
  let sum = 0;
  let count = 0;
  
  for (let num of nums) {
    sum += num;
    
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }
    
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  
  return count;
}

console.log(subarraySum([1, 1, 1], 2));  // 2

JavaScript Map vs Object

Time Complexity