Data Structures12 min read

Hash Tables: Fast Lookups and Key-Value Storage

Master hash tables - the fastest data structure for lookups. Learn how hashing works, handle collisions, and when to use hash tables. Essential for understanding databases, caches, and high-performance systems.

Robert Kim

December 18, 2025

0.0k0

Hash tables give you O(1) average time for insertions, deletions, and lookups. They're the fastest way to store and retrieve data by key. Understanding them is essential for building fast applications.

What is a Hash Table?

A hash table stores key-value pairs. It uses a hash function to convert keys into array indices. This lets you access values instantly by key, without searching through the entire structure.

How Hashing Works

A hash function takes a key and returns an index. Good hash functions distribute keys evenly and are fast to compute. I'll show you common hash functions and how to choose one.

Handling Collisions

When two keys hash to the same index, you have a collision. Common solutions are chaining (linked list at each index) or open addressing (find next available slot). I'll explain both approaches.

Time Complexity

Average case: O(1) for all operations. Worst case: O(n) if all keys hash to same index. Good hash functions and load factor management keep it close to O(1).

Real-World Applications

Hash tables are used in databases (indexing), caches (Redis, Memcached), dictionaries, sets, and anywhere you need fast lookups. They're one of the most used data structures.

#Data Structures#Hash Tables#Hashing#Key-Value

Common Questions & Answers

What is a hash table and how does it work?

A hash table stores key-value pairs using a hash function to map keys to array indices. Provides O(1) average time for insert, delete, and lookup operations. Uses a hash function to convert keys into indices, and handles collisions when multiple keys map to the same index.

javascript

Run Explain

class HashTable {
  constructor(size = 10) {
    this.buckets = new Array(size);
    this.size = size;
  }
  
  // Hash function
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i)) % this.size;
    }
    return hash;
  }
  
  // Insert - O(1) average
  set(key, value) {
    const index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    // Handle collision with chaining
    const bucket = this.buckets[index];
    const existing = bucket.find(item => item[0] === key);
    if (existing) {
      existing[1] = value;  // Update
    } else {
      bucket.push([key, value]);  // Add new
    }
  }
  
  // Get - O(1) average
  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    if (!bucket) return undefined;
    const item = bucket.find(item => item[0] === key);
    return item ? item[1] : undefined;
  }
}

How do you handle collisions in hash tables?

Collisions occur when multiple keys hash to the same index. Common solutions: 1) Chaining - store linked list at each index, 2) Open addressing - find next available slot (linear probing, quadratic probing), 3) Double hashing - use second hash function. Chaining is simpler, open addressing uses less memory.