Hash Tables Visualized

Hash tables are one of the most important data structures in software engineering. They power dictionaries, maps, caches, deduplication, indexing, and fast lookups across most programming languages.

At a high level, a hash table stores key-value pairs and uses a hash function to convert a key into an array index. If the table is sized well and the hash function distributes keys evenly, average operations are close to $O(1)$.

But the real story is collisions. Two different keys can map to the same index. How you handle that decides whether your hash table stays fast or turns into something much closer to $O(n)$.

Why Hash Tables Matter

Hash tables are often used in performance-critical code paths: API request caching, session stores, symbol tables, counting frequencies, de-duplication, and data pipelines. This is why understanding resizing, load factor, and collision strategies matters just as much as memorizing the definition.

Core Concepts

• Key: the identifier you want to look up (string, number, object).
• Hash function: converts a key into an integer hash value.
• Bucket/index: the array slot where the item should be stored.
• Collision: two different keys map to the same bucket.
• Load factor (α): size / capacity. Higher α usually means more collisions.
• Resizing (rehashing): when capacity grows, items must be redistributed.

Collision Handling Strategies

All hash tables must handle collisions. Below are the two most common strategies and how they behave.

Separate Chaining

Separate chaining stores multiple entries in the same bucket, usually via a linked list or dynamic array. The array index points to a small container of entries that share the bucket.

How it works:

1. Compute index = hash(key) % capacity
2. Go to that bucket
3. Search the bucket for the key
4. Insert or update within the bucket

Open Addressing

Open addressing stores all entries directly in the table array. If a collision happens, the table searches for another empty slot using a probing strategy.

How it works:

1. Compute start index
2. If occupied, probe next index based on a probe rule
3. Continue until key is found or an empty slot appears

Probing Strategies (Open Addressing)

Load Factor and Resizing

As a hash table fills up, collisions become more frequent. Most implementations resize when the load factor crosses a threshold (commonly around 0.7 to 0.8 for open addressing).

When resizing happens, the table allocates a larger array and reinserts items. This is called rehashing. It can be expensive, but amortized over many inserts it stays efficient.

Strategy Comparison

Code Examples

Hash Table with Linear Probing

#include <string>
#include <vector>
#include <optional>
#include <functional>

class HashTable {
  struct Entry {
    std::string key;
    int value;
    bool occupied = false;
    bool deleted = false;
  };

  std::vector<Entry> table;
  size_t count = 0;

  size_t indexFor(const std::string& key) const {
    return std::hash<std::string>{}(key) % table.size();
  }

  void rehash() {
    std::vector<Entry> old = table;
    table.assign(table.size() * 2, Entry{});
    count = 0;
    for (const auto& e : old) {
      if (e.occupied && !e.deleted) put(e.key, e.value);
    }
  }

public:
  HashTable(size_t cap = 16) : table(cap) {}

  void put(const std::string& key, int value) {
    if ((double)count / table.size() > 0.7) rehash();
    
    size_t i = indexFor(key);
    while (table[i].occupied && !table[i].deleted && table[i].key != key) {
      i = (i + 1) % table.size();
    }
    
    if (!table[i].occupied || table[i].deleted) count++;
    table[i] = {key, value, true, false};
  }

  std::optional<int> get(const std::string& key) const {
    size_t i = indexFor(key);
    size_t start = i;
    while (table[i].occupied) {
      if (!table[i].deleted && table[i].key == key) {
        return table[i].value;
      }
      i = (i + 1) % table.size();
      if (i == start) break;
    }
    return std::nullopt;
  }
};

The C++ example shows a simple hash table with linear probing, tombstones for deletions, and automatic resizing at 0.7 load factor. Real-world standard libraries add more optimizations.

Common Pitfalls in Real Systems

• Bad hash functions cause clustering: If many keys hash to similar values, performance degrades to $O(n)$.
• Too high load factor causes latency spikes: Always resize before the table gets too full.
• Using mutable objects as keys breaks lookups: If the key changes after insertion, it's effectively lost.
• Hash DoS attacks: Attacker-controlled keys can force collisions. Modern languages use randomized hashing.

Try It Yourself

Use the interactive visualizer below to see how different collision strategies work. Insert keys, watch collisions happen, and observe how probing finds empty slots!