What is a Hash Table?

A Hash Table is a data structure that implements an associative array, also known as a map or dictionary. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found.

The Secret to O(1) Speed:

Instead of searching through every item one by one (O(n)), a hash table uses math to calculate exactly where the data is stored instantly. It's like knowing the exact page number of a word in a book without looking at the index.

Abstract visualization of data retrieval
science

Interactive Lab: Build Your Own Hash Table

add_circle Insert Data

search Lookup / Search

Quick Presets (Try these!)

functions

Under the Hood

We are using a very simple hash function for this demo:

Index = Sum(ASCII values) % 8

Waiting for input...

Memory Array (Buckets)

Empty Occupied
Index 0 crop_free
Empty
Index 1 crop_free
Empty
Index 2 crop_free
Empty
Index 3 crop_free
Empty
Index 4 crop_free
Empty
Index 5 crop_free
Empty
Index 6 crop_free
Empty
Index 7 crop_free
Empty
psychology

How It Works

Imagine a massive library. Usually, to find a book, you'd check a catalog, find the aisle, find the shelf, then scan the books (Time: O(log n) or O(n)).

A Hash Table is different. You give the librarian the book title, and they perform a magical math calculation (the Hash Function) that tells them: "This book belongs exactly on Shelf 4, Slot 2." They walk directly there. No searching.

The Process

  1. Key Input: You provide a key (e.g., "username").
  2. Hashing: The key is converted into an integer (hash code) using a deterministic algorithm.
  3. Modulo: The hash code is compressed to fit the array size (e.g., `hash % size`).
  4. Access: This resulting number is the direct index in memory.
warning

The Problem: Collisions

What if two different keys (like "cat" and "act") result in the same index? This is called a Collision.

The demo above uses a strategy called Chaining. Notice how multiple items can live in the same bucket? The bucket becomes a Linked List.

  • Best Case (No Collisions): O(1) - Instant access.
  • Worst Case (All Collisions): O(n) - The table degrades into a single linked list, and you have to scan every item.

code Simple Implementation (JavaScript)

hashtable.js 
class HashTable {
  constructor(size = 50) {
    this.buckets = new Array(size);
    this.size = size;
  }

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

  set(key, value) {
    let index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    // Handle updates or push new
    this.buckets[index].push([key, value]); 
  }

  get(key) {
    let index = this.hash(key);
    if (!this.buckets[index]) return null;
    
    // Search the chain (collision handling)
    for (let bucket of this.buckets[index]) {
      if (bucket[0] === key) {
        return bucket[1];
      }
    }
    return null;
  }
}