Chapter 14: Hash Table vs Tree

Part IV: Data Structures & Algorithms

"O(1) is just O(n) that got lucky." — Anonymous

The O(1) That Wasn't

A startup was building a real-time bidding system that needed to look up advertiser data by ID. The initial implementation used a hash table—the obvious choice for O(1) lookups. Everything worked perfectly in testing.

In production, disaster struck. Under high load, the system would occasionally freeze for hundreds of milliseconds. Debugging revealed that when the hash table needed to resize, it triggered a massive rehashing operation that blocked the main thread. Worse, during a targeted attack, malicious requests with crafted IDs caused hash collisions, degrading the "O(1)" lookups to O(n).

The team switched to a Red-Black tree. The lookups were now O(log n)—technically "slower"—but performance became predictable. The worst-case latency dropped from 500ms to 2ms. The lesson: average-case complexity isn't the whole story.

Theoretical Complexity Review

This is the classic O(1) vs O(log n) battle, but the "constant" in O(1) can be surprisingly expensive.

Hash Table Deep Dive

The Hidden Costs of O(1)

The O(1) of hash tables includes:

1. Computing the hash code
2. Handling collisions
3. (Occasionally) Resizing the entire table

Hash function complexity: For simple integer keys, hashing is trivial. For long strings, computing a good hash can require examining every character—potentially hundreds of operations before the "O(1)" lookup even begins.

Collision Handling

Chaining (separate chaining): Each bucket contains a linked list of colliding elements. When collisions are frequent, the hash table degrades into multiple linked lists—losing both O(1) complexity and cache locality.

Open addressing (linear probing, quadratic probing): Collisions are resolved by probing subsequent slots. Better cache locality than chaining, but performance degrades rapidly as load factor approaches 1.0.

Load Factor and Rehashing

Hash tables maintain a load factor (elements / buckets). When this exceeds a threshold (typically 0.75), the table must:

1. Allocate a new, larger backing array
2. Recompute hashes for ALL existing elements
3. Insert everything into the new array

This operation is O(n) and causes latency spikes. In latency-sensitive applications, these spikes can be catastrophic.

Hash Collision Attacks

Balanced trees (like Red-Black trees) provide stable O(log n) performance regardless of data distribution. Hash tables are vulnerable to algorithmic complexity attacks: an attacker who knows the hash function can craft inputs that all collide, turning O(1) into O(n).

This vulnerability led to security incidents in web frameworks (PHP, Python, Ruby) that used predictable hash functions for request parameters. Many modern languages and libraries mitigate this by using randomized hash functions or stronger default hashers, which makes these attacks harder in practice. The underlying worst-case behavior of hash tables, however, has not changed.

Tree Structures

Balanced Trees (Red-Black, AVL)

Self-balancing binary search trees guarantee O(log n) operations by maintaining height invariants.

Advantages:

• Predictable worst-case performance
• Natural ordering (in-order traversal gives sorted sequence)
• Efficient range queries

Cache behavior: Traditional BSTs have poor cache locality—each node comparison may trigger a cache miss. For N = 1 million elements, log₂(N) ≈ 20 comparisons, potentially 20 cache misses.

B-Trees: Cache-Friendly Trees

B-Trees store multiple keys per node, designed for systems where node access is expensive (originally disk, but now relevant for cache):

B-Tree node (order 4):
┌─────┬─────┬─────┐
│ K1  │ K2  │ K3  │  ← Multiple keys in one cache line
└──┬──┴──┬──┴──┬──┘
   ↓     ↓     ↓
 children...

A B-Tree with 64-byte nodes can store ~15 integer keys per node. For 1 million elements, height ≈ 5, meaning only 5 cache misses worst case (vs. 20 for a binary tree).

Benchmarking Comparison

Key Type Matters

Integer keys: Hash tables shine. Computing a hash is trivial (often just a modulo or multiplication), and comparison is a single instruction.

String keys: The gap narrows. Hash computation requires examining the entire string. Trees only compare until a difference is found (often early).

Data Distribution Effects

Hash table performance depends heavily on key distribution:

Typical Results (N = 100,000, random keys)

These measurements are representative of a particular hardware and standard-library implementation. Treat them as directional guidance rather than universal constants: the exact numbers will vary, but the trade-offs they illustrate are robust.

Measuring Hash vs Tree Performance

Here's how to benchmark the key operations:

#include <chrono>
#include <map>
#include <unordered_map>
#include <random>
#include <iostream>

template<typename Map>
void benchmark_lookup(Map& m, const std::vector<int>& keys,
                      const std::string& name) {
    volatile int sink = 0;  // Prevent optimization

    auto start = std::chrono::high_resolution_clock::now();
    for (int key : keys) {
        auto it = m.find(key);
        if (it != m.end()) sink = it->second;
    }
    auto end = std::chrono::high_resolution_clock::now();

    auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end - start).count();
    std::cout << name << ": " << ns / keys.size() << " ns/lookup\n";
}

int main() {
    constexpr int N = 100000;
    std::vector<int> keys(N);
    std::iota(keys.begin(), keys.end(), 0);
    std::shuffle(keys.begin(), keys.end(), std::mt19937{42});

    std::unordered_map<int, int> hash_map;
    std::map<int, int> tree_map;

    for (int k : keys) {
        hash_map[k] = k;
        tree_map[k] = k;
    }

    // Warmup then measure
    benchmark_lookup(hash_map, keys, "unordered_map");
    benchmark_lookup(tree_map, keys, "map");
}

Measuring Latency Distribution

Average latency hides the story. For latency-sensitive applications, measure the distribution:

# Using perf to capture latency distribution
perf record -e cycles:u ./hash_vs_tree_benchmark
perf report

# Or capture timing histogram in code:
# Track min, max, P50, P99, P99.9 per operation

When to Use Each

Use Hash Tables When

• Average-case performance matters more than worst-case
• Keys have good hash distribution (or you control the hash function)
• Order is irrelevant
• Range queries are not needed
• Latency spikes from rehashing are acceptable

Use Trees When

• Ordered traversal is needed (logs, time-series data)
• Latency stability is critical (avoid rehashing spikes)
• Range queries are common (find all items between X and Y)
• Data comes from untrusted sources (security)
• Memory allocation must be predictable

The std::map vs std::unordered_map Decision

In C++, this is a common choice:

• Default to std::unordered_map for simple key-value lookups
• Use std::map when you need ordering or predictable performance
• Consider sorted std::vector for read-heavy workloads (binary search with excellent cache locality). For small to medium, mostly-read tables, a sorted vector often outperforms both std::map and std::unordered_map thanks to tiny constant factors and contiguous storage.

Real-World Implementation Notes

Why std::unordered_map Can Be Slow

The C++ standard's std::unordered_map is often criticized for performance. Reasons include:

• Required to use chaining (linked lists for buckets)
• Iterator stability requirements limit optimization
• Node-based allocation (each element is separately allocated)

Alternatives like absl::flat_hash_map (Google) or robin_hood::unordered_map use open addressing with better cache behavior.

Summary

• Hash tables trade predictability for average-case speed. The O(1) comes with hidden costs and worst-case risks.
• Trees provide guarantees. O(log n) may be "slower" but is always O(log n).
• Consider your requirements: Need ordering? Use trees. Need range queries? Use trees. Need raw speed with controlled inputs? Use hash tables.
• Measure with realistic data. Adversarial or clustered data can devastate hash table performance.