← Back to DevBytes
Developer Tutorial July 10, 2026 13 min read

Hash Tables: Implementation and Time Complexity Analysis

What is a Hash Table?

A hash table (also called a hash map, dictionary, or associative array) is a data structure that stores key-value pairs and enables fast lookup, insertion, and deletion. It achieves this by using a hash function to compute an index (or "bucket") from the key, mapping each key to a specific location in an underlying array.

Conceptually, a hash table transforms a potentially large or complex key space into a compact, integer-based address space. When you want to retrieve a value, the hash table re-runs the hash function on the provided key to determine exactly where the value resides, avoiding the need to scan every element.

Here is the high-level flow:

Why Hash Tables Matter

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

Hash tables are one of the most impactful data structures in modern computing. Their significance stems from their exceptional performance characteristics:

Understanding how hash tables work under the hood transforms you from a developer who merely uses dictionaries into one who can reason about performance pitfalls, design custom hash functions, and debug collisions that degrade O(1) guarantees.

Core Components of a Hash Table

1. The Hash Function

A hash function takes a key of any type and returns an integer. This integer is then mapped to a valid bucket index within the array (typically via hash_value % capacity). A good hash function exhibits three properties:

For strings, a classic polynomial rolling hash (like the "djb2" or "siphash" algorithms) works well. For integers, a simple modulo by a prime often suffices. In production, languages use sophisticated hash functions that defend against algorithmic complexity attacks (where an attacker crafts keys that deliberately collide).

2. The Storage Array

The backing array — often called the bucket array — holds the actual entries. Its size is usually chosen as a prime number to help the modulo operation spread keys evenly. Each bucket either contains the key-value entries directly (open addressing) or serves as a pointer to a separate collection of entries (chaining).

3. Collision Resolution Strategy

A collision occurs when two different keys produce the same bucket index. Since hash tables cannot avoid collisions entirely (due to the pigeonhole principle), they must handle them gracefully. The two dominant strategies are:

In this tutorial, we will implement separate chaining — it is the most intuitive approach and forms the conceptual foundation for understanding all hash tables.

Full Implementation: Hash Table with Separate Chaining

Below is a complete, production-style implementation in Python. Each bucket uses a Python list to store (key, value) tuples. The table automatically resizes when the load factor exceeds a threshold, keeping operations efficient.


class HashTable:
    """
    A hash table implementation using separate chaining
    with automatic resizing when load factor exceeds 0.75.
    """

    def __init__(self, initial_capacity=8):
        # Use a prime or power-of-2; here we keep it simple.
        self.capacity = initial_capacity
        self.size = 0          # Number of stored key-value pairs
        self.buckets = [[] for _ in range(self.capacity)]

    def _hash(self, key):
        """
        Compute a bucket index for the given key.
        Uses Python's built-in hash() and maps it to [0, capacity).
        """
        # abs() ensures non-negative; built-in hash() can return negative.
        return abs(hash(key)) % self.capacity

    def _load_factor(self):
        """Return the current load factor (entries / total buckets)."""
        return self.size / self.capacity

    def put(self, key, value):
        """
        Insert or update a key-value pair.
        If the key exists, its value is overwritten.
        """
        index = self._hash(key)
        bucket = self.buckets[index]

        # Check if key already exists in the bucket chain.
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)  # Update existing entry
                return

        # Key not found in chain; append new entry.
        bucket.append((key, value))
        self.size += 1

        # Resize if load factor exceeds threshold.
        if self._load_factor() > 0.75:
            self._resize(self.capacity * 2)

    def get(self, key, default=None):
        """
        Retrieve the value for a key.
        Returns default (None) if the key is not present.
        """
        index = self._hash(key)
        bucket = self.buckets[index]

        for existing_key, value in bucket:
            if existing_key == key:
                return value

        return default

    def remove(self, key):
        """
        Delete a key-value pair from the table.
        Raises KeyError if the key does not exist.
        """
        index = self._hash(key)
        bucket = self.buckets[index]

        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                del bucket[i]
                self.size -= 1
                return

        raise KeyError(f"Key '{key}' not found in hash table.")

    def _resize(self, new_capacity):
        """
        Create a new bucket array with the given capacity
        and re-insert all existing entries.
        """
        old_buckets = self.buckets
        self.capacity = new_capacity
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0  # Reset; put() will increment correctly.

        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)  # Re-insert with new hash distribution

    def __len__(self):
        """Return the number of stored key-value pairs."""
        return self.size

    def __contains__(self, key):
        """Support 'key in table' syntax."""
        return self.get(key, None) is not None

    def __getitem__(self, key):
        """Support table[key] syntax for lookups."""
        result = self.get(key, None)
        if result is None and key not in self:
            raise KeyError(f"Key '{key}' not found.")
        return result

    def __setitem__(self, key, value):
        """Support table[key] = value syntax for inserts/updates."""
        self.put(key, value)

    def __delitem__(self, key):
        """Support 'del table[key]' syntax."""
        self.remove(key)

    def __str__(self):
        """Return a readable representation of the table."""
        pairs = []
        for bucket in self.buckets:
            for key, value in bucket:
                pairs.append(f"{repr(key)}: {repr(value)}")
        return "{" + ", ".join(pairs) + "}"

Let's exercise the implementation with a practical example that demonstrates insertion, collision handling, updates, and deletion:


# Create a hash table and insert several entries.
ht = HashTable()

# Insert distinct key-value pairs.
ht["apple"]  = 1.29
ht["banana"] = 0.59
ht["cherry"] = 2.49
ht["date"]   = 3.99
ht["elderberry"] = 4.50

print("After inserts:", ht)
print("Size:", len(ht))

# Look up an existing key.
print("Price of 'cherry':", ht["cherry"])   # Output: 2.49

# Update the value for an existing key.
ht["apple"] = 1.49
print("Updated price of 'apple':", ht["apple"])  # Output: 1.49

# Delete a key.
del ht["banana"]
print("After deleting 'banana':", ht)
print("Size:", len(ht))

# Check membership.
print("Is 'banana' in table?", "banana" in ht)  # Output: False
print("Is 'date' in table?", "date" in ht)      # Output: True

# Demonstrate automatic resizing by inserting many entries.
print("\nInserting many entries to trigger resize...")
for i in range(50):
    ht[f"item_{i}"] = i * 10
print("Size after bulk insert:", len(ht))
print("Capacity after resize:", ht.capacity)

Time Complexity Analysis

Average Case: The O(1) Promise

Under ideal conditions — a good hash function, uniform key distribution, and a load factor kept below the threshold — hash tables deliver constant-time performance for all core operations:

The average chain length is the load factor λ = n / m, where n is the number of entries and m is the number of buckets. With a load factor of 0.75 and separate chaining, the average chain length is 0.75, meaning each lookup inspects fewer than one element on average before finding the correct key — effectively constant time.

Worst Case: The O(n) Degradation

The worst case occurs when a poor hash function (or an adversarial key set) maps all keys to the same bucket. In separate chaining, this degenerates the hash table into a single linked list, making every operation O(n). Similarly, in open addressing, a cluster of consecutive occupied slots forces long probe sequences.

Worst-case scenarios arise from:

Load Factor and Resizing Cost

The load factor (λ) is the critical tuning knob for hash table performance. Most implementations trigger a resize when λ exceeds 0.75 (for chaining) or 0.5–0.7 (for open addressing). Resizing itself is an O(n) operation because every existing entry must be re-hashed into the new, larger array. However, resizing occurs infrequently — amortized across many O(1) insertions, the cost per insertion remains O(1).

Here's a breakdown of how resizing amortization works:


# Amortized analysis of insertion with resizing.
#
# Starting capacity: 8
# Resize threshold: 0.75 (trigger at 6 entries)
#
# Insertions 1–6:  O(1) each  → total O(6)
# Resize at 6:     O(6) to rehash all entries into capacity 16
# Insertions 7–14: O(1) each  → total O(8)
# Resize at 14:    O(14) to rehash into capacity 32
#
# Over n insertions, the total rehashing cost is:
#   O(n + n/2 + n/4 + ...) = O(2n) = O(n)
# Amortized per insertion: O(n) / n = O(1)

Alternative Implementation: Open Addressing

For completeness, here is a compact open addressing implementation using linear probing. Instead of chains, each bucket stores either a (key, value) tuple or a sentinel None for empty slots. Lookup probes linearly until the key is found or an empty slot is encountered.


class OpenAddressingHashTable:
    """
    Hash table using open addressing with linear probing.
    Uses a sentinel object to mark deleted slots (tombstones).
    """

    _TOMBSTONE = object()  # Unique sentinel for deleted entries

    def __init__(self, initial_capacity=8):
        self.capacity = initial_capacity
        self.size = 0
        self.buckets = [None] * self.capacity

    def _hash(self, key):
        return abs(hash(key)) % self.capacity

    def _probe(self, index):
        """Linear probe: simply move to the next slot."""
        return (index + 1) % self.capacity

    def put(self, key, value):
        index = self._hash(key)

        # Probe until we find the key, an empty slot, or a tombstone.
        first_tombstone = None
        while self.buckets[index] is not None:
            existing = self.buckets[index]

            if existing is self._TOMBSTONE:
                if first_tombstone is None:
                    first_tombstone = index
                index = self._probe(index)
                continue

            existing_key, _ = existing
            if existing_key == key:
                # Update existing entry.
                self.buckets[index] = (key, value)
                return
            index = self._probe(index)

        # Prefer placing into a tombstone slot if we passed one.
        target = first_tombstone if first_tombstone is not None else index
        self.buckets[target] = (key, value)
        self.size += 1

        if self.size / self.capacity > 0.7:
            self._resize(self.capacity * 2)

    def get(self, key, default=None):
        index = self._hash(key)

        while self.buckets[index] is not None:
            existing = self.buckets[index]
            if existing is not self._TOMBSTONE:
                existing_key, value = existing
                if existing_key == key:
                    return value
            index = self._probe(index)

        return default

    def remove(self, key):
        index = self._hash(key)

        while self.buckets[index] is not None:
            existing = self.buckets[index]
            if existing is not self._TOMBSTONE:
                existing_key, _ = existing
                if existing_key == key:
                    self.buckets[index] = self._TOMBSTONE
                    self.size -= 1
                    return
            index = self._probe(index)

        raise KeyError(f"Key '{key}' not found.")

    def _resize(self, new_capacity):
        old_buckets = self.buckets
        self.capacity = new_capacity
        self.buckets = [None] * self.capacity
        self.size = 0

        for entry in old_buckets:
            if entry is not None and entry is not self._TOMBSTONE:
                key, value = entry
                self.put(key, value)

Open addressing offers better cache locality (all data lives in one contiguous array) but suffers from primary clustering in linear probing, where consecutive occupied slots merge into long runs that degrade probe performance. Quadratic probing and double hashing mitigate clustering at the cost of slightly more complex index computation.

Built-in Hash Table Implementations

Every modern programming language ships with highly optimized hash table implementations. You should prefer these over custom implementations for production code, but understanding internals helps you use them effectively:

Best Practices for Hash Tables

Conclusion

Hash tables are the gold standard for associative data storage, offering average O(1) performance that underpins countless systems — from in-memory caches to database indexes. Their elegance lies in the synergy between a well-designed hash function, a sensible collision resolution strategy, and automatic resizing that keeps the load factor in check. By implementing a hash table from scratch with separate chaining, you have gained insight into the mechanics that production-grade implementations build upon: hash computation, bucket management, collision handling, and amortized resizing. You've also seen how open addressing trades pointer overhead for better cache behavior while introducing probing complexity.

Whether you're building a caching layer, designing a frequency counter, or simply relying on your language's built-in dict or Map, understanding the internals transforms you from a passive user into an informed engineer who can diagnose performance anomalies, choose appropriate key types, and reason about worst-case guarantees. Keep these principles close — they will serve you in system design interviews, performance optimization sprints, and every time you reach for that ubiquitous curly-brace data structure.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles