Hash Tables

Interactive Visualization

Time Complexity

Key Points

• Hash function converts key → array index
• O(1) average for get, set, delete
• Collisions: when two keys hash to same index
• Collision handling: chaining (linked lists) or open addressing
• Load factor = entries / buckets (affects performance)
• JS Object and Map are both hash tables

Code Examples

// Simplified hash function
function hash(key, tableSize) {
  let hash = 0
  for (let char of String(key)) {
    hash += char.charCodeAt(0)
  }
  return hash % tableSize
}

// Example:
hash("cat", 10)  // Maybe returns 5
hash("dog", 10)  // Maybe returns 8
hash("tac", 10)  // Maybe returns 5 (collision!)

// Real hash functions are more sophisticated
// to distribute keys evenly

const map = new Map()

// Set key-value pairs - O(1)
map.set('apple', 5)
map.set('banana', 3)
map.set('orange', 8)

// Get value by key - O(1)
map.get('apple')    // 5
map.get('grape')    // undefined

// Check if key exists - O(1)
map.has('banana')   // true

// Delete by key - O(1)
map.delete('orange')

// Size
map.size            // 2

const obj = {}

// Set values - O(1)
obj['apple'] = 5
obj.banana = 3

// Get values - O(1)
obj['apple']    // 5
obj.banana      // 3

// Check existence - O(1)
'apple' in obj           // true
obj.hasOwnProperty('x')  // false

// Delete - O(1)
delete obj.apple

// ⚠️ Object keys are always strings!
obj[1] = 'one'
obj['1']  // 'one' (same key!)

// Count occurrences of each element
function frequencyCounter(arr) {
  const freq = new Map()

  for (const item of arr) {
    freq.set(item, (freq.get(item) || 0) + 1)
  }

  return freq
}

frequencyCounter(['a', 'b', 'a', 'c', 'a', 'b'])
// Map { 'a' => 3, 'b' => 2, 'c' => 1 }

// This pattern is O(n) - one pass!
// Without hash map: O(n²) with nested loops

function twoSum(nums, target) {
  const seen = new Map()  // value → index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (seen.has(complement)) {
      return [seen.get(complement), i]
    }

    seen.set(nums[i], i)
  }

  return []
}

// Without hash map: O(n²) - check all pairs
// With hash map: O(n) - one pass!

// Use Map when:
// - Keys aren't strings (numbers, objects)
// - Need to preserve insertion order
// - Frequently add/remove keys
// - Need .size property

const map = new Map()
map.set(1, 'number key')      // Works!
map.set({id: 1}, 'object key') // Works!

// Use Object when:
// - Keys are strings
// - Need JSON serialization
// - Simple key-value storage

const obj = {}
obj[1] = 'becomes string "1"'
// obj[{id:1}] = 'becomes "[object Object]"'

Common Mistakes

• Forgetting that Object keys are always strings
• Using objects as keys in regular Object (use Map instead)
• Not handling missing keys (check with has() or in)
• Assuming hash map maintains insertion order (Map does, Object mostly does)

Interview Tips

• Hash maps often turn O(n²) brute force into O(n)
• When you need "have I seen this before?", think hash set
• When you need "what was the index of X?", think hash map
• Trading space for time is a common interview pattern

Practice Problems

Related Concepts