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

class IllustrativeHashTable:
    """
    A simple hash table demonstrating the fundamental mechanism.
    
    Key properties of the hash function h(k):
    1. DETERMINISTIC: h(k) always returns the same value for the same k
    2. UNIFORM: Different keys distribute evenly across the array
    3. EFFICIENT: h(k) computes in O(m) where m = len(k)
    """
    
    def __init__(self, capacity: int = 16):
        self.capacity = capacity
        self.buckets: list[list[tuple[str, any]]] = [[] for _ in range(capacity)]
        self.size = 0
    
    def _hash(self, key: str) -> int:
        """
        Compute hash index for a key.
        
        This is a simplified polynomial hash. Real implementations
        use more sophisticated functions, but the principle is identical:
        
        h(s) = Σ s[i] * p^i mod capacity
        
        Where p is some prime (31 commonly used).
        """
        hash_value = 0
        p = 31
        for i, char in enumerate(key):
            hash_value += ord(char) * (p ** i)
        return hash_value % self.capacity
    
    def insert(self, key: str, value: any) -> None:
        """Insert key-value pair. O(m) hash + O(1) average insert."""
        index = self._hash(key)  # O(m) - must read entire string
        
        # Check if key exists and update
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)
                return
        
        # Key doesn't exist, append to bucket
        self.buckets[index].append((key, value))
        self.size += 1
    
    def search(self, key: str) -> any:
        """Search for key. O(m) hash + O(1) average lookup."""
        index = self._hash(key)  # O(m) - must read entire string
        
        for k, v in self.buckets[index]:
            if k == key:  # O(m) comparison
                return v
        return None
 
# Note the hidden O(m) cost:
# - Hash computation reads all m characters
# - Comparison reads all m characters
# 
# So "O(1) lookup" is really O(m) + O(1) = O(m)
# But crucially, it's O(m) total, NOT O(n × m) like linear search

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

def naive_prefix_search_hash(hash_table: dict, prefix: str) -> list[str]:
    """
    ATTEMPT: Just hash the prefix and look it up.
    
    This fundamentally doesn't work.
    """
    hash_value = hash(prefix)
    
    # Problem: This looks for the key "prefix" itself,
    # NOT for keys that start with "prefix"
    
    result = hash_table.get(prefix)
    # If prefix="pro", this only finds "pro" if stored,
    # NOT "program", "project", "promise", etc.
    
    return [result] if result else []
 
# Why this fails:
# h("pro") = 12345      (some computed value)
# h("program") = 98765  (completely different!)
# h("project") = 54321  (completely different!)
#
# There is NO mathematical relationship between:
# - h("pro") and h("proXXX") for any suffix XXX
#
# We CANNOT determine which keys start with "pro"
# just by knowing h("pro").
#
# The only way to find all prefix matches is to
# EXAMINE EVERY KEY in the hash table - back to O(n)!

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

class AllPrefixesHashTable:
    """
    ATTEMPT: Store each string under all of its prefixes.
    
    For "apple", store under: "a", "ap", "app", "appl", "apple"
    """
    
    def __init__(self):
        # Maps prefix -> set of full strings with that prefix
        self.prefix_index: dict[str, set[str]] = {}
    
    def insert(self, word: str) -> None:
        """
        Insert word under all its prefixes.
        
        Time: O(m²) where m = len(word)
        - Generate m prefixes
        - Hash each prefix: O(1) + O(2) + ... + O(m) = O(m²)
        - Plus string copy overhead
        
        Space: O(n × m²) across all words
        - Each length-m word generates m prefix entries
        """
        for i in range(1, len(word) + 1):
            prefix = word[:i]  # O(i) to create substring
            if prefix not in self.prefix_index:
                self.prefix_index[prefix] = set()
            self.prefix_index[prefix].add(word)
    
    def prefix_search(self, prefix: str) -> list[str]:
        """
        Find all words with given prefix.
        
        Time: O(m) hash + O(k) to return k results
        This WORKS for queries!
        """
        return list(self.prefix_index.get(prefix, set()))
 
# Analysis:
# Query time: O(m + k) - actually good!
# Insert time: O(m²) - bad, quadratic per word
# Space: O(n × m_avg²) - very bad
 
# For n = 1,000,000 strings of average length 20:
# - Space overhead: 1M × 20² × ~4 bytes = 1.6 GB just for prefix indices
# - Plus the strings themselves: 1M × 20 = 20 MB
# - Overhead ratio: 80:1 !
 
# For a dictionary of 100,000 words:
# - About 15 MB for the words themselves
# - About 600 MB for the prefix index
# - Completely impractical

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

import math
 
def analyze_prefix_preserving_hash():
    """
    Mathematical analysis of why prefix-preserving hash functions
    cannot work within standard hash table constraints.
    """
    
    # Consider a prefix-aware hash where h(prefix) can be derived
    # from h(full_string)
    
    # Example: "rolling hash" approach
    # h("pro") = h("program") mod M for some M
    
    # Problem: How big must M be?
    
    alphabet_size = 26
    avg_word_length = 10
    prefix_length = 3  # "pro"
    
    # Strings starting with a 3-letter prefix
    suffix_possibilities = alphabet_size ** (avg_word_length - prefix_length)
    print(f"Possible strings with prefix of length {prefix_length}: "
          f"{suffix_possibilities:,}")  # ~8 billion
    
    # All these strings must hash to values where mod M gives same result
    # For reasonable bucket sizes (to avoid O(n) search within bucket):
    max_bucket_size = 100  # Target for O(1) average lookup
    
    # This means M must distinguish between ~80 million different prefixes
    required_m = suffix_possibilities / max_bucket_size
    print(f"Required M for reasonable bucket size: {required_m:,.0f}")
    
    # But M is bounded by available memory for the hash table
    # A hash table with 80 million buckets, 8 bytes each = 640 MB
    # Just for the buckets, before storing any data!
    
    memory_per_bucket_bytes = 8  # pointer size
    memory_required = required_m * memory_per_bucket_bytes
    print(f"Memory just for buckets: {memory_required / (1024**2):.1f} MB")
    
    # And this only handles ONE prefix length (3)!
    # For prefixes of length 1, 2, 3, 4, ..., the problem compounds
    
    total_memory = 0
    for prefix_len in range(1, avg_word_length + 1):
        prefixes_of_length = alphabet_size ** prefix_len
        total_memory += prefixes_of_length * memory_per_bucket_bytes
    
    print(f"Memory for all prefix lengths: {total_memory / (1024**3):.1f} GB")
    # This quickly exceeds terabytes!
 
analyze_prefix_preserving_hash()
 
# Output:
# Possible strings with prefix of length 3: 8,031,810,176
# Required M for reasonable bucket size: 80,318,102
# Memory just for buckets: 611.9 MB
# Memory for all prefix lengths: 5.7 GB
# (And this is for a simplified model with only lowercase letters!)

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

class RollingHashPrefixTable:
    """
    ATTEMPT: Use rolling hashes to find prefixes.
    
    Idea: Hash strings by their prefixes at each length.
    """
    
    def __init__(self, max_length: int = 100):
        # length_tables[i] maps hash(prefix[:i]) -> list of full strings
        self.length_tables: list[dict] = [{} for _ in range(max_length)]
        self.base = 31
        self.mod = 10**9 + 7
    
    def _rolling_hashes(self, word: str) -> list[int]:
        """Compute rolling hash for each prefix length."""
        hashes = []
        h = 0
        for i, char in enumerate(word):
            h = (h * self.base + ord(char)) % self.mod
            hashes.append(h)
        return hashes
    
    def insert(self, word: str) -> None:
        """Insert word with all its prefix hashes."""
        hashes = self._rolling_hashes(word)
        for i, h in enumerate(hashes):
            if h not in self.length_tables[i]:
                self.length_tables[i][h] = []
            self.length_tables[i][h].append(word)
    
    def prefix_search(self, prefix: str) -> list[str]:
        """Find words starting with prefix."""
        # Compute hash of prefix
        h = 0
        for char in prefix:
            h = (h * self.base + ord(char)) % self.mod
        
        # Look up in the table for this prefix length
        prefix_len = len(prefix)
        candidates = self.length_tables[prefix_len - 1].get(h, [])
        
        # MUST VERIFY! Hash collisions mean false positives
        return [word for word in candidates if word.startswith(prefix)]
 
# Analysis:
# 
# Space: Still O(n × m) - storing each word in m hash tables
# Time: O(m) hash + O(collisions) verification
# 
# Problems:
# 1. Hash collisions cause false positives requiring verification
# 2. All words still stored m times (by prefix length)
# 3. Memory layout is poor for cache
# 4. Enumeration of all matches still requires accessing all matches
#
# This is essentially the "store all prefixes" approach with
# hash collision risk added!

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

import bisect
 
class HybridHashSorted:
    """
    ATTEMPT: Best of both worlds - hash for exact, sorted for prefix.
    
    This actually works, but at what cost?
    """
    
    def __init__(self):
        self.hash_table: dict[str, any] = {}  # For O(1) exact lookup
        self.sorted_list: list[str] = []       # For prefix search
    
    def insert(self, word: str, value: any) -> None:
        """
        Insert into both structures.
        
        Time: O(1) hash + O(n) sorted insertion = O(n)
        """
        self.hash_table[word] = value
        bisect.insort(self.sorted_list, word)  # O(n) due to shifting!
    
    def exact_lookup(self, word: str) -> any:
        """O(1) average via hash table."""
        return self.hash_table.get(word)
    
    def prefix_search(self, prefix: str) -> list[str]:
        """O(m log n + k) via sorted list."""
        # Find first position >= prefix
        left = bisect.bisect_left(self.sorted_list, prefix)
        
        results = []
        for i in range(left, len(self.sorted_list)):
            if self.sorted_list[i].startswith(prefix):
                results.append(self.sorted_list[i])
            else:
                break
        return results
    
    def delete(self, word: str) -> None:
        """
        Delete from both structures.
        
        Time: O(1) hash + O(n) find in sorted + O(n) shift = O(n)
        """
        if word in self.hash_table:
            del self.hash_table[word]
            # Find and remove from sorted list - O(n)
            idx = bisect.bisect_left(self.sorted_list, word)
            if idx < len(self.sorted_list) and self.sorted_list[idx] == word:
                self.sorted_list.pop(idx)  # O(n) shift
 
# Analysis:
#
# Exact lookup: O(1) average ✓
# Prefix search: O(m log n + k) ✓
# Insert: O(n) ✗
# Delete: O(n) ✗
# Space: 2× storage (word in both structures) ✗
# Maintenance: Two structures to keep in sync ✗
#
# The sorted list insert/delete is O(n), making this unsuitable
# for dynamic collections.

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

class BloomFilterPrefixTable:
    """
    ATTEMPT: Bloom filters for quick 'definitely not' answers.
    
    A Bloom filter can answer:
    - "Definitely not present" (no false negatives)
    - "Possibly present" (has false positives)
    """
    
    def __init__(self, expected_size: int = 100000):
        # One Bloom filter per prefix length
        self.max_prefix_len = 20
        self.bloom_filters = [BloomFilter(expected_size) for _ in range(self.max_prefix_len)]
        self.all_strings: list[str] = []
    
    def insert(self, word: str) -> None:
        """Add word and all its prefixes to Bloom filters."""
        self.all_strings.append(word)
        for i in range(1, min(len(word) + 1, self.max_prefix_len)):
            prefix = word[:i]
            self.bloom_filters[i - 1].add(prefix)
    
    def prefix_search(self, prefix: str) -> list[str]:
        """
        Use Bloom filter to potentially skip, then scan.
        """
        prefix_len = len(prefix)
        if prefix_len >= self.max_prefix_len:
            # Can't use Bloom filter, full scan
            return [s for s in self.all_strings if s.startswith(prefix)]
        
        # Quick check: could any strings have this prefix?
        if not self.bloom_filters[prefix_len - 1].might_contain(prefix):
            return []  # Definitely no matches!
        
        # Bloom filter says "maybe" - must scan to verify
        return [s for s in self.all_strings if s.startswith(prefix)]
 
class BloomFilter:
    """Simplified Bloom filter for illustration."""
    def __init__(self, expected_size: int):
        self.size = expected_size * 10  # 10 bits per element
        self.bits = [False] * self.size
    
    def add(self, item: str) -> None:
        for h in self._hashes(item):
            self.bits[h % self.size] = True
    
    def might_contain(self, item: str) -> bool:
        return all(self.bits[h % self.size] for h in self._hashes(item))
    
    def _hashes(self, item: str) -> list[int]:
        # Multiple hash functions
        return [hash(item), hash(item + 'salt1'), hash(item + 'salt2')]
 
# Analysis:
#
# Best case: prefix doesn't exist, Bloom filter rejects in O(1)
# Worst case (common prefix): still O(n) scan
# Space: O(n × m) for Bloom filters + O(n × m) for strings
# False positive rate: ~1% means 1% of non-matching prefixes cause full scan
#
# This helps for non-existent prefixes but doesn't solve the
# fundamental problem for common prefixes.