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

def chaining_expected_comparisons(alpha: float) -> dict:
    """
    Calculate expected comparison counts for separate chaining.
    
    Args:
        alpha: Load factor (n/m), can exceed 1.0
        
    Returns:
        Dictionary with expected comparisons for each operation type
    """
    return {
        "unsuccessful_search": alpha,           # Must scan entire chain
        "successful_search": 1 + alpha / 2,     # On avg, half chain + target
        "insertion": alpha,                      # Same as unsuccessful (find end)
        "total_for_n_ops": lambda n: n * (1 + alpha / 2)  # n successful searches
    }
 
# Demonstration: How performance changes as table fills
print("Chaining Performance Degradation")
print("=" * 60)
print(f"{'α':>8} | {'Unsuccessful':>14} | {'Successful':>12} | {'Ratio vs α=0.5':>14}")
print("-" * 60)
 
baseline = chaining_expected_comparisons(0.5)["successful_search"]
for alpha in [0.25, 0.50, 0.75, 1.0, 1.5, 2.0, 3.0, 5.0]:
    stats = chaining_expected_comparisons(alpha)
    ratio = stats["successful_search"] / baseline
    print(f"{alpha:>8.2f} | {stats['unsuccessful_search']:>14.3f} | "
          f"{stats['successful_search']:>12.3f} | {ratio:>14.2f}x")
 
# Output:
# Chaining Performance Degradation
# ============================================================
#        α |   Unsuccessful |   Successful | Ratio vs α=0.5
# ------------------------------------------------------------
#     0.25 |          0.250 |        1.125 |           0.90x
#     0.50 |          0.500 |        1.250 |           1.00x
#     0.75 |          0.750 |        1.375 |           1.10x
#     1.00 |          1.000 |        1.500 |           1.20x
#     1.50 |          1.500 |        1.750 |           1.40x
#     2.00 |          2.000 |        2.000 |           1.60x
#     3.00 |          3.000 |        2.500 |           2.00x
#     5.00 |          5.000 |        3.500 |           2.80x

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

import math
 
def linear_probing_expected_probes(alpha: float) -> dict:
    """
    Calculate expected probe counts for linear probing.
    
    Args:
        alpha: Load factor, must be < 1.0
        
    Returns:
        Dictionary with expected probes for each operation type
    
    Based on Knuth's analysis of linear probing (TAOCP Vol 3).
    """
    if alpha >= 1.0:
        raise ValueError("Load factor must be < 1.0 for open addressing")
    
    unsuccessful = 0.5 * (1 + 1 / ((1 - alpha) ** 2))
    successful = 0.5 * (1 + 1 / (1 - alpha))
    
    return {
        "unsuccessful_search": unsuccessful,
        "successful_search": successful,
        "insertion": unsuccessful,  # Same as unsuccessful search
    }
 
def double_hashing_expected_probes(alpha: float) -> dict:
    """
    Calculate expected probe counts for double hashing.
    """
    if alpha >= 1.0:
        raise ValueError("Load factor must be < 1.0 for open addressing")
    if alpha == 0:
        return {"unsuccessful_search": 1, "successful_search": 1, "insertion": 1}
    
    unsuccessful = 1 / (1 - alpha)
    successful = (1 / alpha) * math.log(1 / (1 - alpha))
    
    return {
        "unsuccessful_search": unsuccessful,
        "successful_search": successful,
        "insertion": unsuccessful,
    }
 
# Compare both strategies
print("Open Addressing Performance Comparison")
print("=" * 75)
print(f"{'α':>6} | {'Linear (U)':>12} | {'Linear (S)':>12} | {'Double (U)':>12} | {'Double (S)':>12}")
print("-" * 75)
 
for alpha in [0.1, 0.25, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95]:
    lp = linear_probing_expected_probes(alpha)
    dh = double_hashing_expected_probes(alpha)
    print(f"{alpha:>6.2f} | {lp['unsuccessful_search']:>12.2f} | "
          f"{lp['successful_search']:>12.2f} | "
          f"{dh['unsuccessful_search']:>12.2f} | {dh['successful_search']:>12.2f}")
 
# Visualize the cliff
print("\n\nThe Performance Cliff (Linear Probing Unsuccessful Search)")
print("=" * 50)
for alpha in [0.90, 0.91, 0.92, 0.93, 0.94, 0.95, 0.96, 0.97, 0.98, 0.99]:
    probes = linear_probing_expected_probes(alpha)["unsuccessful_search"]
    bar = "█" * min(int(probes / 10), 50)
    print(f"α={alpha:.2f}: {probes:>8.1f} probes {bar}")
 
# Output excerpt:
# α=0.90:     50.5 probes █████
# α=0.95:    200.5 probes ████████████████████
# α=0.99:   5000.5 probes ██████████████████████████████████████████████████

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

def compare_strategies(alpha: float) -> None:
    """
    Compare chaining vs open addressing at given load factor.
    """
    print(f"\n{'='*60}")
    print(f"Comparison at Load Factor α = {alpha}")
    print(f"{'='*60}")
    
    # Chaining metrics
    chain_unsuccessful = alpha
    chain_successful = 1 + alpha / 2
    
    print(f"\nSEPARATE CHAINING:")
    print(f"  Unsuccessful search: {chain_unsuccessful:.2f} comparisons")
    print(f"  Successful search:   {chain_successful:.2f} comparisons")
    
    # Open addressing metrics (only valid if α < 1)
    if alpha < 1.0:
        open_unsuccessful = 0.5 * (1 + 1 / ((1 - alpha) ** 2))
        open_successful = 0.5 * (1 + 1 / (1 - alpha))
        
        print(f"\nOPEN ADDRESSING (Linear Probing):")
        print(f"  Unsuccessful search: {open_unsuccessful:.2f} probes")
        print(f"  Successful search:   {open_successful:.2f} probes")
        
        # Ratio comparison
        print(f"\nOPEN ADDRESSING OVERHEAD vs CHAINING:")
        print(f"  Unsuccessful: {open_unsuccessful / chain_unsuccessful:.1f}x worse")
        print(f"  Successful:   {open_successful / chain_successful:.1f}x worse")
    else:
        print(f"\nOPEN ADDRESSING: ⚠ NOT POSSIBLE (α ≥ 1)")
    
    # Verdict
    if alpha < 0.5:
        print(f"\n✓ VERDICT: Both strategies perform excellently")
    elif alpha < 0.7:
        print(f"\n✓ VERDICT: Both acceptable, chaining slightly safer")
    elif alpha < 0.9:
        print(f"\n⚠ VERDICT: Open addressing degrading rapidly; prefer chaining")
    else:
        print(f"\n⛔ VERDICT: Open addressing critical/impossible; chaining still viable")
 
# Compare at critical thresholds
for alpha in [0.5, 0.75, 0.9, 0.95]:
    compare_strategies(alpha)

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

import math
 
class CapacityPlanner:
    """
    Hash table capacity planning utility.
    
    Helps engineers make data-driven decisions about initial capacity
    and predict performance characteristics.
    """
    
    def __init__(self, max_load_factor: float = 0.75):
        self.max_load_factor = max_load_factor
    
    def required_capacity(self, expected_elements: int) -> int:
        """
        Calculate minimum capacity to avoid resizing.
        
        Returns the smallest power of 2 that keeps load factor below threshold.
        """
        raw_capacity = math.ceil(expected_elements / self.max_load_factor)
        # Round up to next power of 2 (common implementation choice)
        power = max(1, math.ceil(math.log2(raw_capacity)))
        return 2 ** power
    
    def actual_load_factor(self, elements: int, capacity: int) -> float:
        """Calculate actual load factor for given elements and capacity."""
        return elements / capacity
    
    def expected_performance(self, elements: int, capacity: int, strategy: str = "chaining"):
        """
        Predict expected operation costs.
        """
        alpha = self.actual_load_factor(elements, capacity)
        
        if strategy == "chaining":
            return {
                "load_factor": alpha,
                "successful_search": 1 + alpha / 2,
                "unsuccessful_search": alpha,
                "status": "healthy" if alpha < 1.0 else "overloaded"
            }
        else:  # open addressing
            if alpha >= 1.0:
                return {"error": "Load factor >= 1, open addressing impossible"}
            return {
                "load_factor": alpha,
                "successful_search": 0.5 * (1 + 1 / (1 - alpha)),
                "unsuccessful_search": 0.5 * (1 + 1 / ((1 - alpha) ** 2)),
                "status": "healthy" if alpha < 0.7 else "stressed" if alpha < 0.9 else "critical"
            }
    
    def resize_count(self, initial_capacity: int, final_elements: int) -> int:
        """
        Count resize operations needed to grow from initial to final size.
        """
        if final_elements <= initial_capacity * self.max_load_factor:
            return 0
        
        capacity = initial_capacity
        resizes = 0
        
        while capacity * self.max_load_factor < final_elements:
            capacity *= 2
            resizes += 1
        
        return resizes
 
# Example usage
planner = CapacityPlanner(max_load_factor=0.75)
 
# Planning for 10,000 elements
expected = 10000
capacity = planner.required_capacity(expected)
print(f"For {expected:,} elements:")
print(f"  Required capacity: {capacity:,} buckets")
print(f"  Actual load factor: {planner.actual_load_factor(expected, capacity):.3f}")
print(f"  Expected successful search: {planner.expected_performance(expected, capacity)['successful_search']:.3f}")
 
# Growth planning
print(f"\nGrowth from 16 buckets to 1M elements:")
print(f"  Resize operations needed: {planner.resize_count(16, 1_000_000)}")
 
# Output:
# For 10,000 elements:
#   Required capacity: 16,384 buckets
#   Actual load factor: 0.610
#   Expected successful search: 1.305
#
# Growth from 16 buckets to 1M elements:
#   Resize operations needed: 17