Hash Table Insert Operation — O(1) Average, O(n) Worst Case - Hash Table Operations & Amortized Cost Model | OneNoughtOne

0/361

Data Structures & AlgorithmsHash Table Operations & Amortized Cost Model

Hash Table Operations & Amortized Cost Model

LevelIntermediate

Duration60 mins

TopicHash Table Operations & Amortized Cost Model

1 / 4

Hash Table Insert Operation — O(1) Average, O(n) Worst Case

The Insert Operation: Deceptively Simple, Subtly Complex

Of all the operations a hash table supports, insertion appears the most straightforward: compute a hash, find the bucket, store the data. Yet this apparent simplicity conceals a fascinating landscape of complexity analysis, probability theory, and engineering trade-offs. When computer scientists claim hash table insertion is O(1), they're telling a nuanced truth—one that requires understanding what 'average' truly means and when 'worst case' actually occurs.

This page provides an exhaustive examination of the insert operation, exploring the mathematical foundations of its performance, the mechanisms that can degrade it, and the engineering decisions that separate production-grade hash tables from naive implementations. By the end, you will possess a rigorous understanding of why insertion is simultaneously O(1) and O(n)—and precisely when each characterization applies.

What You Will Learn

By the end of this page, you will understand: the mechanics of hash table insertion in both chaining and open addressing; why average-case O(1) is a probabilistic statement; how worst-case O(n) emerges and why it's not just theoretical; the role of load factor, hash function quality, and collision resolution; and how amortized analysis accounts for dynamic resizing.

The Anatomy of Hash Table Insertion

Before analyzing complexity, we must understand precisely what insertion entails. The operation decomposes into discrete, measurable steps, each with its own time characteristics.

The Fundamental Insertion Algorithm:

Compute the hash: Apply the hash function to the key, producing an integer
Compute the index: Reduce the hash to a valid bucket index (typically via modulo)
Access the bucket: Navigate to the identified location in the underlying array
Handle any collision: If the bucket is occupied, resolve according to the strategy
Store the key-value pair: Write the data to the appropriate location

Each step contributes to the total insertion time, but their relative costs vary dramatically depending on circumstances.

insertion_anatomy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class HashTableWithChaining:
    """
    Hash table implementation demonstrating insertion anatomy.
    Each step is annotated with its time complexity contribution.
    """
    
    def __init__(self, initial_capacity=16):
        self.capacity = initial_capacity
        self.size = 0
        self.buckets = [[] for _ in range(initial_capacity)]  # Array of lists
        self.max_load_factor = 0.75
    
    def _hash(self, key) -> int:
        """
        Step 1: Compute the hash value.
        Time: O(k) where k is the key size (for strings), O(1) for fixed-size types.
        
        For most practical purposes, we treat this as O(1) since keys have
        bounded size in typical applications.
        """
        return hash(key)  # Python's built-in hash function
    
    def _get_bucket_index(self, hash_value: int) -> int:
        """
        Step 2: Reduce hash to valid bucket index.
        Time: O(1) - single modulo operation.
        
        The modulo ensures the index falls within [0, capacity - 1].
        """
        return hash_value % self.capacity
    
    def insert(self, key, value):
        """
        Complete insertion operation with detailed step analysis.
        """
        # Step 1: Compute hash - O(1) for fixed-size keys
        hash_value = self._hash(key)
        
        # Step 2: Compute bucket index - O(1)
        bucket_index = self._get_bucket_index(hash_value)
        
        # Step 3: Access the bucket - O(1) array indexing
        bucket = self.buckets[bucket_index]
        
        # Step 4: Handle collision - O(k) where k is bucket length
        # This is where O(n) worst case emerges
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                # Key exists: update value
                bucket[i] = (key, value)
                return  # No size increase
        
        # Step 5: Store the new key-value pair - O(1)
        bucket.append((key, value))
        self.size += 1
        
        # Step 6: Check for resize (amortized consideration)
        if self.size / self.capacity > self.max_load_factor:
            self._resize()
    
    def _resize(self):
        """
        Dynamic resizing when load factor exceeds threshold.
        Time: O(n) for rehashing all elements.
        Amortized contribution: O(1) per insertion.
        """
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        
        # Rehash all existing elements
        for bucket in old_buckets:
            for key, value in bucket:
                self.insert(key, value)

The Critical Insight

Steps 1-3 and 5 are all O(1). The entire O(n) risk hides in Step 4—collision handling. If all n elements land in the same bucket (the absolute worst case), we must traverse all n elements before inserting. This is why understanding collision resolution isn't optional—it's the key to understanding hash table performance.

Understanding Average-Case O(1): A Probabilistic Guarantee

When we claim hash table insertion is O(1) on average, we're making a probabilistic statement that relies on specific assumptions about the hash function and key distribution. This is fundamentally different from data structures with deterministic O(1) operations like array indexing.

The Simple Uniform Hashing Assumption (SUHA):

Theoretical analysis of hash tables typically invokes the Simple Uniform Hashing Assumption, which states:

Each key is equally likely to hash to any of the m buckets, independently of where any other key has hashed.

Under SUHA, if we have n elements distributed across m buckets, the expected number of elements per bucket is α = n/m (the load factor). This is the average chain length we must traverse during insertion.

Expected Chain Length Under Different Load Factors
Load Factor (α)	Expected Chain Length	Expected Insertion Time	Memory Efficiency
0.25	0.25 elements	~1.25 probes	25% utilized (wasteful)
0.50	0.50 elements	~1.50 probes	50% utilized (balanced)
0.75	0.75 elements	~1.75 probes	75% utilized (typical threshold)
1.00	1.00 element	~2.00 probes	100% utilized (high collision)
2.00	2.00 elements	~3.00 probes	200% overfilled (degraded)

The Mathematical Foundation:

For a hash table with chaining, the expected time for a successful insertion (when checking for duplicates) is:

T(insert) = 1 + α/2

For an unsuccessful search followed by insertion at the end of the chain:

T(insert_new) = 1 + α

When the load factor α is kept constant (e.g., by resizing when α > 0.75), both expressions become O(1) because α is bounded by a constant.

Why This Matters:

The O(1) claim is contingent on:

A hash function that approximates uniform distribution
A load factor kept below a constant threshold
Keys that don't exhibit pathological patterns

Violate any of these assumptions, and the O(1) guarantee evaporates.

Average ≠ Every Case

Average-case O(1) means that if we insert n random elements, the total time is O(n), giving O(1) per insertion on average. It does NOT mean every individual insertion completes in O(1) time. Some insertions may take much longer—but they're rare enough that they don't affect the average. This distinction matters enormously for latency-sensitive applications.

average_case_demonstration.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import random
import time
from typing import List, Tuple
 
def measure_insertion_times(n: int, capacity: int) -> Tuple[float, float, List[float]]:
    """
    Demonstrates average-case behavior by measuring actual insertion times.
    
    Returns:
        - Average insertion time
        - Maximum insertion time (worst individual case)
        - List of all insertion times for analysis
    """
    
    class SimpleHashTable:
        def __init__(self, cap):
            self.capacity = cap
            self.buckets = [[] for _ in range(cap)]
        
        def insert(self, key, value):
            bucket_idx = hash(key) % self.capacity
            bucket = self.buckets[bucket_idx]
            
            # Check for existing key
            for i, (k, _) in enumerate(bucket):
                if k == key:
                    bucket[i] = (key, value)
                    return len(bucket)  # Return chain length traversed
            
            bucket.append((key, value))
            return len(bucket)  # Return final chain length
    
    table = SimpleHashTable(capacity)
    insertion_times = []
    chain_lengths = []
    
    # Generate random keys
    keys = [random.randint(0, 10**9) for _ in range(n)]
    
    for key in keys:
        start = time.perf_counter_ns()
        chain_length = table.insert(key, f"value_{key}")
        end = time.perf_counter_ns()
        
        insertion_times.append(end - start)
        chain_lengths.append(chain_length)
    
    avg_time = sum(insertion_times) / len(insertion_times)
    max_time = max(insertion_times)
    avg_chain = sum(chain_lengths) / len(chain_lengths)
    max_chain = max(chain_lengths)
    
    print(f"Inserted {n} elements into {capacity} buckets")
    print(f"Load factor: {n/capacity:.2f}")
    print(f"Average insertion time: {avg_time:.0f} ns")
    print(f"Maximum insertion time: {max_time:.0f} ns")
    print(f"Max/Avg ratio: {max_time/avg_time:.1f}x")
    print(f"Average chain length: {avg_chain:.2f}")
    print(f"Maximum chain length: {max_chain}")
    
    return avg_time, max_time, insertion_times
 
# Demonstrate with good load factor
print("=" * 50)
print("CASE 1: Load Factor 0.75 (Good)")
measure_insertion_times(n=10000, capacity=13333)
 
print()
 
# Demonstrate with poor load factor
print("=" * 50)
print("CASE 2: Load Factor 5.0 (Poor - no resizing)")
measure_insertion_times(n=10000, capacity=2000)
 
# Expected output shows that even with random keys:
# - Average insertion time remains roughly constant
# - Maximum insertion time can be significantly higher
# - Higher load factor increases both average and variance

How Worst-Case O(n) Emerges: When Theory Meets Reality

The O(n) worst case for hash table insertion isn't a theoretical curiosity—it's a genuine failure mode that occurs in production systems. Understanding exactly how it emerges is crucial for designing robust applications.

The Degenerate Case:

The absolute worst case occurs when all n keys hash to the same bucket. With chaining, this creates a single linked list of length n. Each insertion must traverse the entire list to check for duplicates before appending, yielding:

T(n insertions) = 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²) total = O(n) per insertion

How can all keys land in the same bucket? Three primary mechanisms:

Mechanisms That Trigger Worst-Case Performance

•Pathological Key Patterns — Keys with structure that defeats the hash function. Example: if using hash(key) = key % m, inserting keys 0, m, 2m, 3m, ... all land in bucket 0.
•Hash Function Weaknesses — Poor hash functions may cluster outputs for certain input distributions. String hashes that only use the first few characters, for instance, cluster strings with common prefixes.
•Adversarial Input (Hash-DoS) — An attacker deliberately crafts keys that collide, exploiting knowledge of the hash function to force worst-case behavior. This has been used in real denial-of-service attacks.
•Insufficient Entropy — Keys drawn from a small domain (e.g., user IDs 1-1000 with a million-bucket table) don't utilize the hash space effectively.
•Identity Hash Functions — Some systems use identity hashes for integers (hash(x) = x), making collision patterns trivially predictable.

worst_case_demonstration.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import time
 
class VulnerableHashTable:
    """
    Demonstrates how worst-case O(n) insertion emerges.
    Uses a weak hash function susceptible to pathological inputs.
    """
    
    def __init__(self, capacity=1000):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]
        self.collision_count = 0
    
    def _weak_hash(self, key: str) -> int:
        """
        Intentionally weak hash function for demonstration.
        Only uses first 3 characters - easily defeated.
        """
        if len(key) < 3:
            return sum(ord(c) for c in key)
        return ord(key[0]) * 100 + ord(key[1]) * 10 + ord(key[2])
    
    def insert(self, key, value):
        bucket_idx = self._weak_hash(key) % self.capacity
        bucket = self.buckets[bucket_idx]
        
        # Check for existing key (this is where O(n) happens)
        for i, (k, _) in enumerate(bucket):
            self.collision_count += 1
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
    
    def get_longest_chain(self) -> int:
        return max(len(bucket) for bucket in self.buckets)
 
 
def demonstrate_worst_case():
    """Compare normal vs adversarial insertion performance."""
    
    # CASE 1: Random keys (average case)
    print("CASE 1: Random Keys (Average Case)")
    table1 = VulnerableHashTable(capacity=1000)
    
    # Random-looking keys
    random_keys = [f"user_{i}_data_{i*7}" for i in range(1000)]
    
    start = time.perf_counter()
    for key in random_keys:
        table1.insert(key, "value")
    end = time.perf_counter()
    
    print(f"  Time: {(end-start)*1000:.2f} ms")
    print(f"  Longest chain: {table1.get_longest_chain()}")
    print(f"  Collision checks: {table1.collision_count}")
    print()
    
    # CASE 2: Adversarial keys that exploit the weak hash
    print("CASE 2: Adversarial Keys (Worst Case)")
    table2 = VulnerableHashTable(capacity=1000)
    
    # All keys start with "aaa" - they ALL hash to the same bucket!
    adversarial_keys = [f"aaa_{i}" for i in range(1000)]
    
    start = time.perf_counter()
    for key in adversarial_keys:
        table2.insert(key, "value")
    end = time.perf_counter()
    
    print(f"  Time: {(end-start)*1000:.2f} ms")
    print(f"  Longest chain: {table2.get_longest_chain()}")
    print(f"  Collision checks: {table2.collision_count}")
    print()
    
    print(f"Worst case was {table2.collision_count / max(1, table1.collision_count):.1f}x more collision checks!")
 
# Run demonstration
demonstrate_worst_case()
 
# Expected output:
# CASE 1: Random Keys (Average Case)
#   Time: ~1-5 ms
#   Longest chain: ~5-10
#   Collision checks: ~500
#
# CASE 2: Adversarial Keys (Worst Case)
#   Time: ~100-500 ms
#   Longest chain: 1000
#   Collision checks: ~500,000

Real-World Impact: Hash Collision Attacks

In 2011, researchers demonstrated 'HashDoS' attacks against web servers. By sending HTTP requests with carefully crafted POST parameter names that all collided, attackers could exhaust server CPU with relatively few requests. This led to emergency patches in PHP, Java, Ruby, Python, and other languages—all adding hash randomization or switching to collision-resistant data structures.

Insertion with Open Addressing: A Different Trade-Off

Open addressing stores all elements directly in the hash table array, handling collisions by probing for alternative slots. This changes the complexity dynamics in subtle but important ways.

Linear Probing Insertion:

When a collision occurs, linear probing checks slots i+1, i+2, i+3, ... until finding an empty slot. While conceptually simple, this creates primary clustering—collisions create clusters that grow over time, degrading performance.

For linear probing with load factor α, the expected number of probes for insertion is:

E[probes] ≈ 1/(1-α) for insertion

As α approaches 1, probe counts explode:

α = 0.5: ~2 probes
α = 0.75: ~4 probes
α = 0.9: ~10 probes
α = 0.95: ~20 probes
α = 0.99: ~100 probes

open_addressing_insertion.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class OpenAddressingHashTable:
    """
    Hash table using open addressing with linear probing.
    Demonstrates insertion complexity characteristics.
    """
    
    EMPTY = None
    DELETED = "<DELETED>"  # Tombstone marker
    
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.slots = [self.EMPTY] * capacity
        self.probe_counts = []  # Track probes for analysis
    
    def _hash(self, key) -> int:
        return hash(key)
    
    def insert(self, key, value) -> int:
        """
        Insert using linear probing.
        Returns number of probes required.
        
        Time Complexity:
        - Average case: O(1/(1-α)) where α is load factor
        - Worst case: O(n) when table is nearly full or clustered
        """
        if self.size >= self.capacity * 0.75:
            self._resize()
        
        probes = 0
        index = self._hash(key) % self.capacity
        original_index = index
        
        while True:
            probes += 1
            current = self.slots[index]
            
            # Found empty slot or tombstone - can insert
            if current is self.EMPTY or current is self.DELETED:
                self.slots[index] = (key, value)
                self.size += 1
                self.probe_counts.append(probes)
                return probes
            
            # Key already exists - update value
            if current[0] == key:
                self.slots[index] = (key, value)
                self.probe_counts.append(probes)
                return probes
            
            # Collision - probe next slot
            index = (index + 1) % self.capacity
            
            # Full cycle - table is full (shouldn't happen with proper resizing)
            if index == original_index:
                raise RuntimeError("Hash table is full!")
    
    def _resize(self):
        """
        Double capacity and rehash all elements.
        This O(n) operation is amortized to O(1).
        """
        old_slots = self.slots
        self.capacity *= 2
        self.slots = [self.EMPTY] * self.capacity
        self.size = 0
        
        for slot in old_slots:
            if slot is not self.EMPTY and slot is not self.DELETED:
                self.insert(slot[0], slot[1])
    
    def get_probe_statistics(self):
        if not self.probe_counts:
            return 0, 0, 0
        return (
            sum(self.probe_counts) / len(self.probe_counts),  # Average
            max(self.probe_counts),  # Max
            len([p for p in self.probe_counts if p > 5]) / len(self.probe_counts)  # % > 5 probes
        )
 
 
def analyze_clustering_effect():
    """Demonstrate how clustering affects insertion performance."""
    import random
    
    print("Analyzing clustering effect at different load factors:")
    print("-" * 60)
    
    for target_load in [0.25, 0.50, 0.75, 0.90]:
        # Fixed capacity, varying number of elements
        capacity = 10000
        n = int(capacity * target_load)
        
        table = OpenAddressingHashTable(capacity=capacity)
        
        # Disable auto-resize to study raw clustering
        table._resize = lambda: None
        table.capacity = capacity
        table.slots = [OpenAddressingHashTable.EMPTY] * capacity
        
        # Insert random keys
        for i in range(n):
            table.insert(random.randint(0, 10**9), f"value_{i}")
        
        avg, max_probe, pct_high = table.get_probe_statistics()
        print(f"Load {target_load:.0%}: Avg probes={avg:.1f}, Max={max_probe}, "
              f">5 probes={pct_high:.1%}")
 
analyze_clustering_effect()

Open Addressing Advantages

•Better cache locality—elements stored contiguously
•No pointer overhead—more memory efficient
•Simpler memory allocation—single array
•Faster for low to moderate load factors

Open Addressing Disadvantages

•Performance degrades sharply above 70% load
•Deletion is complex (requires tombstones)
•Clustering can cause severe performance drops
•Cannot exceed 100% load (chaining can)

The Role of Hash Function Quality

The gap between O(1) average and O(n) worst case hinges critically on hash function quality. A perfect hash function would eliminate collisions entirely; a terrible one could make every key collide.

Properties That Affect Insertion Performance:

Uniformity: Does the hash function distribute outputs evenly across buckets? Non-uniform distribution concentrates elements in fewer buckets, increasing collision chain lengths.
Avalanche Effect: Do small input changes cause large output changes? Functions lacking this property may map similar keys to similar buckets (e.g., sequential integers to sequential buckets).
Resistance to Patterns: Does the function handle structured input well? Keys often follow patterns (sequential IDs, common prefixes, IP addresses) that can defeat naive hash functions.
Computational Cost: Hash computation is part of insertion time. Cryptographic hashes have excellent distribution but high computation cost—usually overkill for hash tables.

Hash Function Quality Comparison
Hash Function Type	Uniformity	Speed	Pattern Resistance	Use Case
Identity (h(x) = x)	Poor for structured data	Instant	None	Never use directly
Modular (h(x) = x % p, p prime)	Moderate	Very Fast	Low	Simple examples only
Multiplicative (h(x) = ⌊m(xA mod 1)⌋)	Good	Fast	Moderate	Educational implementations
MurmurHash3	Excellent	Very Fast	Good	General purpose (non-crypto)
xxHash	Excellent	Extremely Fast	Good	Performance-critical paths
SipHash	Excellent	Fast	Excellent (keyed)	DoS-resistant tables
SHA-256	Perfect	Slow	Perfect	Overkill—don't use for tables

Modern Best Practice: Randomized Hashing

Post-HashDoS, many languages/runtimes now use randomized hash functions. Python, Ruby, Perl, and others inject a random seed at startup, making the hash function's behavior unpredictable to attackers. This doesn't improve average-case performance, but it makes worst-case attacks computationally infeasible.

Dynamic Resizing and Amortized Analysis

Practical hash tables maintain performance by dynamically resizing when the load factor exceeds a threshold. Each resize operation is expensive—O(n) to rehash all elements—but it happens rarely enough that the cost, spread across insertions, remains O(1) per operation.

The Amortized Argument:

Consider a hash table that doubles capacity when full. Starting with capacity 1:

After 1 insertion: resize (1 element rehashed)
After 2 insertions: resize (2 elements rehashed)
After 4 insertions: resize (4 elements rehashed)
After 8 insertions: resize (8 elements rehashed)
...
After n insertions: log₂(n) resizes total

Total rehashing work: 1 + 2 + 4 + 8 + ... + n/2 = n - 1 = O(n)

Total insertions: n

Amortized cost per insertion: O(n)/n = O(1)

Each insertion 'pays' a constant amount toward future resizing, like putting coins in a piggy bank that occasionally funds an expensive operation.

amortized_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class AmortizedAnalysisDemo:
    """
    Demonstrates amortized O(1) insertion despite O(n) resizing.
    Tracks cumulative work to prove the amortized bound.
    """
    
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.buckets = [[]]
        
        # Cost tracking
        self.total_insert_cost = 0    # Simple insertions
        self.total_resize_cost = 0    # Rehashing during resize
        self.resize_count = 0
    
    def insert(self, key, value):
        """
        Insert with automatic resizing.
        Tracks computational cost for amortized analysis.
        """
        # Check if resize needed
        if self.size >= self.capacity:
            self._resize()
        
        # Perform insertion (cost = 1 for the simple case)
        bucket_idx = hash(key) % self.capacity
        self.buckets[bucket_idx].append((key, value))
        self.size += 1
        self.total_insert_cost += 1
    
    def _resize(self):
        """
        Double capacity and rehash.
        Cost = O(n) where n is current size.
        """
        self.resize_count += 1
        old_buckets = self.buckets
        old_size = self.size
        
        # Double capacity
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        
        # Rehash all elements (this is the expensive part)
        rehash_cost = 0
        for bucket in old_buckets:
            for key, value in bucket:
                bucket_idx = hash(key) % self.capacity
                self.buckets[bucket_idx].append((key, value))
                self.size += 1
                rehash_cost += 1
        
        self.total_resize_cost += rehash_cost
        
    def analyze(self):
        total_cost = self.total_insert_cost + self.total_resize_cost
        return {
            "elements": self.size,
            "capacity": self.capacity,
            "resize_operations": self.resize_count,
            "total_insert_cost": self.total_insert_cost,
            "total_resize_cost": self.total_resize_cost,
            "total_cost": total_cost,
            "amortized_cost_per_insert": total_cost / self.size if self.size > 0 else 0,
        }
 
 
def demonstrate_amortization():
    """Show that amortized cost remains constant as n grows."""
    print("Demonstrating Amortized O(1) Insertion")
    print("=" * 60)
    
    for n in [10, 100, 1000, 10000, 100000]:
        table = AmortizedAnalysisDemo()
        
        for i in range(n):
            table.insert(f"key_{i}", f"value_{i}")
        
        stats = table.analyze()
        print(f"n = {n:>6}: Resizes = {stats['resize_operations']:>2}, "
              f"Total cost = {stats['total_cost']:>7}, "
              f"Amortized = {stats['amortized_cost_per_insert']:.2f}")
    
    print()
    print("Observation: Amortized cost stays near 2.0 regardless of n")
    print("(1.0 for the insertion + ~1.0 for amortized resize contribution)")
 
demonstrate_amortization()

Amortized vs. Individual Operations

Amortized O(1) means the average over a sequence of operations is O(1). Individual insertions that trigger resizing take O(n). For most applications, this is fine—total time is what matters. For real-time systems requiring consistent per-operation latency, traditional hash tables may be unsuitable; consider structures with incremental rehashing or bounded worst-case operations.

Summary: The Complete Picture of Hash Table Insertion

We've dissected the insert operation from every angle. Let's consolidate the essential insights:

Key Takeaways

•O(1) average is probabilistic — It relies on hash functions distributing keys uniformly and load factors remaining bounded. It describes expected behavior over many operations, not guarantees for individual ones.
•O(n) worst case is real — All keys colliding in one bucket forces linear traversal. This can happen through poor hash functions, pathological key patterns, or deliberate adversarial attack.
•Collision strategy affects constants — Chaining has simpler analysis; open addressing has better cache performance but degrades sharply above 70% load.
•Hash function quality is paramount — The choice of hash function determines whether average-case assumptions hold. Modern systems use randomized, high-quality functions like SipHash.
•Resizing is amortized O(1) — Doubling capacity when load threshold is exceeded spreads O(n) rehashing cost across future insertions, maintaining O(1) amortized insertion.
•Real-time constraints require care — For latency-sensitive applications, the O(n) resizing spike may be unacceptable. Consider incremental rehashing or alternative structures.

What's Next:

Insert is just one operation. The next page examines lookup—where O(1) versus O(n) has even more dramatic practical implications. We'll see how the same factors affecting insertion also govern search performance, and why hash tables are revered for lookup-heavy workloads.

Page Complete

You now understand hash table insertion at a rigorous, professional level. You can explain why O(1) is an average not a guarantee, precisely how O(n) worst case emerges, and what engineering decisions prevent performance degradation. Next, we'll apply this same analytical rigor to the lookup operation.