Hash Tables and HashMaps Explained

Hash tables are one of the most important data structures in computer science. They provide extremely fast lookups, insertions, and deletions with O(1) average time complexity.

What is a Hash Table? #

A hash table (also called hash map) is a data structure that maps keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

How Hash Tables Work #

Basic Concept #

Key → Hash Function → Index → Value

Example:

"apple" → hash("apple") → 3 → "red"
"banana" → hash("banana") → 7 → "yellow"

Hash Function #

A hash function takes a key and returns an integer index:

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

simpleHash("apple", 10);  // Returns index between 0-9

Hash Table Operations #

Insert #

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }

  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
}

Get #

get(key) {
  const index = this._hash(key);
  if (this.keyMap[index]) {
    for (let pair of this.keyMap[index]) {
      if (pair[0] === key) {
        return pair[1];
      }
    }
  }
  return undefined;
}

Delete #

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

Keys and Values #

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

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

Collision Handling #

When two keys hash to the same index, we have a collision. There are two main strategies:

Separate Chaining #

Store multiple key-value pairs at the same index using a linked list or array:

// Each bucket is an array of [key, value] pairs
keyMap[3] = [
  ["apple", "red"],
  ["apricot", "orange"]  // Collision handled
];

Linear Probing (Open Addressing) #

When a collision occurs, look for the next available slot:

class HashTableLinearProbing {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  set(key, value) {
    let index = this._hash(key);

    // Find next available slot
    while (this.keyMap[index] !== undefined) {
      if (this.keyMap[index][0] === key) {
        // Update existing key
        this.keyMap[index][1] = value;
        return;
      }
      index = (index + 1) % this.keyMap.length;
    }

    this.keyMap[index] = [key, value];
  }

  get(key) {
    let index = this._hash(key);
    let startIndex = index;

    while (this.keyMap[index] !== undefined) {
      if (this.keyMap[index][0] === key) {
        return this.keyMap[index][1];
      }
      index = (index + 1) % this.keyMap.length;

      // Avoid infinite loop
      if (index === startIndex) break;
    }

    return undefined;
  }
}

JavaScript Map vs Object #

Using JavaScript Map #

const map = new Map();

// Set values
map.set('name', 'Alice');
map.set('age', 25);
map.set(1, 'number key');
map.set({ id: 1 }, 'object key');

// Get values
console.log(map.get('name'));  // "Alice"

// Check existence
console.log(map.has('age'));  // true

// Delete
map.delete('age');

// Size
console.log(map.size);  // 3

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

// Get all keys
const keys = Array.from(map.keys());

// Get all values
const values = Array.from(map.values());

// Clear all
map.clear();

Using JavaScript Object #

const obj = {};

// Set values
obj['name'] = 'Alice';
obj['age'] = 25;
obj[1] = 'number converted to string';

// Get values
console.log(obj.name);  // "Alice"
console.log(obj['age']);  // 25

// Check existence
console.log('name' in obj);  // true
console.log(obj.hasOwnProperty('age'));  // true

// Delete
delete obj.age;

// Get keys
const keys = Object.keys(obj);

// Get values
const values = Object.values(obj);

// Get entries
const entries = Object.entries(obj);

// Iterate
for (const key in obj) {
  console.log(`${key}: ${obj[key]}`);
}

Map vs Object Comparison #

Feature	Map	Object
Key types	Any type	String or Symbol
Key order	Insertion order	Not guaranteed
Size	map.size	Object.keys(obj).length
Iteration	Built-in iterators	for…in or Object methods
Performance	Better for frequent add/remove	Better for simple lookups
JSON	Not serializable	JSON.stringify works

Common Hash Table Problems #

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]

Group Anagrams #

function groupAnagrams(strs) {
  const map = new Map();

  for (const str of strs) {
    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"]]

First Non-Repeating Character #

function firstUniqChar(s) {
  const map = new Map();

  // Count occurrences
  for (const char of s) {
    map.set(char, (map.get(char) || 0) + 1);
  }

  // Find first with count 1
  for (let i = 0; i < s.length; i++) {
    if (map.get(s[i]) === 1) {
      return i;
    }
  }

  return -1;
}

console.log(firstUniqChar("leetcode"));  // 0 (l)
console.log(firstUniqChar("loveleetcode"));  // 2 (v)

Subarray Sum Equals K #

function subarraySum(nums, k) {
  const map = new Map();
  map.set(0, 1);  // Base case

  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;

    // Check if (sum - k) exists
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }

    // Add current sum to map
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  return count;
}

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

Longest Substring Without Repeating Characters #

function lengthOfLongestSubstring(s) {
  const map = new Map();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    if (map.has(char) && map.get(char) >= left) {
      left = map.get(char) + 1;
    }

    map.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

console.log(lengthOfLongestSubstring("abcabcbb"));  // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb"));  // 1 ("b")

Valid Anagram #

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const map = new Map();

  for (const char of s) {
    map.set(char, (map.get(char) || 0) + 1);
  }

  for (const char of t) {
    if (!map.has(char) || map.get(char) === 0) {
      return false;
    }
    map.set(char, map.get(char) - 1);
  }

  return true;
}

console.log(isAnagram("anagram", "nagaram"));  // true
console.log(isAnagram("rat", "car"));  // false

Time Complexity #

Operation	Average	Worst Case
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Search	O(1)	O(n)
Space	O(n)	O(n)

Worst case occurs when all keys hash to the same index (all collisions).

When to Use Hash Tables #

Use hash tables when you need:

Fast lookups by key
Counting occurrences
Caching/memoization
Finding duplicates
Grouping data

Don’t use hash tables when you need:

Ordered data (use balanced tree)
Range queries (use tree)
Minimum memory usage (arrays are more compact)
Guaranteed worst-case performance

Best Practices #

Choose good hash table size - Use prime numbers
Handle collisions properly - Separate chaining is most common
Good hash function - Distributes keys evenly
Load factor - Keep it under 0.7 for good performance
Use Map over Object - For non-string keys or frequent add/delete

Hash tables are incredibly versatile and appear in countless algorithms. Mastering them is essential for coding interviews and real-world programming.