Hash Functions: Properties & Design

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

TOTAL OPERATION COST
====================
For any hash table operation (insert, lookup, delete):
 
  Total_Time = Hash_Time + Bucket_Operation_Time
 
Where:
  Hash_Time = O(L)  for input of length L
  Bucket_Operation_Time = O(1) average with chaining/probing
 
For N operations on a hash table:
  
  Total_Time = N × (Hash_Time + Bucket_Time)
             ≈ N × Hash_Time  (when Hash_Time dominates)
 
KEY INSIGHT
===========
If you perform 1 million lookups:
  - 1 microsecond hash: 1 second total
  - 10 microseconds hash: 10 seconds total
  - 100 microseconds hash: 100 seconds total
 
A 100× slower hash function means 100× slower application!
 
WHAT MAKES HASHING SLOW
=======================
1. Processing every byte of input: O(L) minimum
2. Complex operations per byte (multiplications, divisions)
3. Memory access patterns (cache misses)
4. Branch mispredictions
5. Cryptographic strength when not needed

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
111
112
113
114
115
116
117
118
119
120
121

import time
from typing import Callable
 
def benchmark_hash(name: str, hash_fn: Callable[[str], int], 
                   test_data: list, iterations: int = 100):
    """Benchmark a hash function's speed."""
    start = time.perf_counter()
    for _ in range(iterations):
        for data in test_data:
            hash_fn(data)
    elapsed = time.perf_counter() - start
    
    total_hashes = iterations * len(test_data)
    hashes_per_sec = total_hashes / elapsed
    ns_per_hash = (elapsed / total_hashes) * 1e9
    
    print(f"{name:30} {hashes_per_sec:>12,.0f} hashes/sec  ({ns_per_hash:.1f} ns/hash)")
    return ns_per_hash
 
# SLOW: Byte-by-byte with expensive operations
def slow_hash_v1(s: str) -> int:
    """Uses division and modulo for each character."""
    h = 0
    for c in s:
        h = (h * 33 + ord(c)) % 2147483647  # Modulo is slow
    return h
 
# SLOW: Creates intermediate objects
def slow_hash_v2(s: str) -> int:
    """Creates new strings/lists (memory allocation overhead)."""
    chars = list(s)  # Allocates new list
    h = 0
    for i, c in enumerate(chars):
        substring = s[i:]  # Creates new string objects!
        h ^= hash(substring)  # Multiple hashes
    return h & 0xFFFFFFFF
 
# SLOW: Recursive (function call overhead)
def slow_hash_v3(s: str) -> int:
    """Recursive approach with function call overhead."""
    if not s:
        return 5381
    return (slow_hash_v3(s[:-1]) * 33 + ord(s[-1])) & 0xFFFFFFFF
 
# FAST: Optimized loop with cheap operations
def fast_hash_v1(s: str) -> int:
    """Simple polynomial hash with cheap operations."""
    h = 0
    for c in s:
        h = ((h << 5) + h + ord(c)) & 0xFFFFFFFF  # h*33+c without multiply
    return h
 
# FAST: Processes multiple bytes at once (conceptually)
def fast_hash_v2(s: str) -> int:
    """
    Simulates word-at-a-time processing.
    Real implementations use native integers for 4-8 bytes at once.
    """
    h = 0
    encoded = s.encode('utf-8')
    
    # Process 4 bytes at a time
    i = 0
    while i + 4 <= len(encoded):
        chunk = (encoded[i] | (encoded[i+1] << 8) | 
                (encoded[i+2] << 16) | (encoded[i+3] << 24))
        h = ((h ^ chunk) * 0x5bd1e995) & 0xFFFFFFFF
        h ^= h >> 15
        i += 4
    
    # Handle remaining bytes
    while i < len(encoded):
        h = ((h << 5) + h + encoded[i]) & 0xFFFFFFFF
        i += 1
    
    # Finalization
    h ^= h >> 16
    h = (h * 0x85ebca6b) & 0xFFFFFFFF
    h ^= h >> 13
    
    return h
 
# FAST: Uses built-in operations (often native code)
def fast_hash_v3(s: str) -> int:
    """Leverages built-in functions implemented in C."""
    import hashlib
    # hashlib is implemented in C and highly optimized
    return int(hashlib.md5(s.encode()).hexdigest()[:8], 16)
 
# Benchmark
test_strings = [f"user_{i:05d}_session_data" for i in range(1000)]
 
print("Hash Function Performance Comparison")
print("="*65)
 
results = [
    ("Slow V1 (modulo each char)", slow_hash_v1),
    ("Slow V2 (object allocation)", slow_hash_v2),
    ("Slow V3 (recursive)", slow_hash_v3),
    ("Fast V1 (shift-add)", fast_hash_v1),
    ("Fast V2 (word-at-a-time)", fast_hash_v2),
    ("Fast V3 (builtin hashlib)", fast_hash_v3),
]
 
times = []
for name, fn in results:
    try:
        t = benchmark_hash(name, fn, test_strings)
        times.append((name, t))
    except RecursionError:
        print(f"{name:30} RecursionError (too deep)")
 
# Compare slowest vs fastest
if len(times) >= 2:
    times.sort(key=lambda x: x[1])
    fastest = times[0]
    slowest = times[-1]
    print(f"
Fastest: {fastest[0]} ({fastest[1]:.1f} ns/hash)")
    print(f"Slowest: {slowest[0]} ({slowest[1]:.1f} ns/hash)")
    print(f"Difference: {slowest[1]/fastest[1]:.1f}× slower")

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

"""
Hash functions representing different speed-quality tradeoffs.
"""
 
# ULTRA-FAST: Minimal operations, acceptable quality
def ultrafast_hash(s: str) -> int:
    """
    Favors speed over quality.
    Use for: Large internal data structures with random input.
    """
    h = 5381
    for c in s:
        h = ((h << 5) + h + ord(c)) & 0xFFFFFFFF
    return h
 
# BALANCED: Good speed, good quality
def balanced_hash(s: str) -> int:
    """
    Balances speed and quality.
    Use for: Most general-purpose hash tables.
    """
    h = 0
    for c in s:
        h = (h * 31 + ord(c)) & 0xFFFFFFFF
    
    # Light finalization
    h ^= h >> 16
    h = (h * 0x85ebca6b) & 0xFFFFFFFF
    h ^= h >> 13
    return h
 
# HIGH-QUALITY: Slower but excellent distribution
def highquality_hash(s: str) -> int:
    """
    Favors quality over speed.
    Use for: External input, potential hash collision attacks.
    """
    h1 = 0
    h2 = 0
    
    for i, c in enumerate(s):
        # Two parallel hash accumulators
        h1 = (h1 * 31 + ord(c)) & 0xFFFFFFFF
        h2 = (h2 * 37 + ord(c) * (i + 1)) & 0xFFFFFFFF
    
    # Combine accumulators
    h = h1 ^ (h2 << 16) ^ (h2 >> 16)
    
    # Strong finalization (multiple rounds)
    h ^= h >> 16
    h = (h * 0x85ebca6b) & 0xFFFFFFFF
    h ^= h >> 13
    h = (h * 0xc2b2ae35) & 0xFFFFFFFF
    h ^= h >> 16
    h = (h * 0x7feb352d) & 0xFFFFFFFF
    h ^= h >> 15
    
    return h
 
# CRYPTOGRAPHIC: Secure but slowest
def crypto_hash(s: str) -> int:
    """
    Cryptographic strength hash.
    Use for: Security-critical applications, passwords, signatures.
    """
    import hashlib
    return int(hashlib.sha256(s.encode()).hexdigest(), 16) & 0xFFFFFFFFFFFFFFFF
 
# Compare all four
import time
 
def compare_hashes():
    test_data = [f"test_key_{i:07d}" for i in range(10000)]
    
    hashes = [
        ("Ultra-fast (djb2-like)", ultrafast_hash),
        ("Balanced (polynomial+finalize)", balanced_hash),
        ("High-quality (double hash)", highquality_hash),
        ("Cryptographic (SHA-256)", crypto_hash),
    ]
    
    print("Speed-Quality Tradeoff Demonstration")
    print("="*60)
    
    baseline_time = None
    for name, fn in hashes:
        start = time.perf_counter()
        for key in test_data:
            fn(key)
        elapsed = time.perf_counter() - start
        
        if baseline_time is None:
            baseline_time = elapsed
            ratio = 1.0
        else:
            ratio = elapsed / baseline_time
        
        print(f"{name:35} {elapsed*1000:>7.2f}ms  (×{ratio:.1f})")
    
    print("
💡 Observation:")
    print("   Each step up in quality costs more CPU time.")
    print("   Choose based on your threat model and performance budget.")
 
compare_hashes()

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

"""
Demonstrating CPU-friendly hash function techniques.
Note: Python adds overhead that hides these optimizations.
In C/C++/Rust, these differences are more pronounced.
"""
 
# Technique 1: Word-at-a-time processing
def word_at_a_time_hash(data: bytes) -> int:
    """
    Process 8 bytes at a time instead of 1.
    In low-level languages, this is 8× fewer loop iterations.
    """
    import struct
    
    h = 0
    
    # Process 8-byte chunks
    i = 0
    while i + 8 <= len(data):
        # Unpack 8 bytes as single 64-bit integer
        word = struct.unpack('<Q', data[i:i+8])[0]
        h ^= word
        h = (h * 0xbf58476d1ce4e5b9) & 0xFFFFFFFFFFFFFFFF
        h ^= h >> 27
        i += 8
    
    # Handle remaining bytes
    remainder = 0
    shift = 0
    while i < len(data):
        remainder |= data[i] << shift
        shift += 8
        i += 1
    h ^= remainder
    
    # Finalization
    h ^= h >> 33
    h = (h * 0xff51afd7ed558ccd) & 0xFFFFFFFFFFFFFFFF
    h ^= h >> 33
    
    return h
 
# Technique 2: Branchless operations
def branchless_clamp(value: int, min_val: int, max_val: int) -> int:
    """
    Clamp a value without branches.
    Branches cause pipeline stalls when mispredicted.
    """
    # Traditional (has branches):
    # if value < min_val: return min_val
    # if value > max_val: return max_val
    # return value
    
    # Branchless (no pipeline stalls):
    # Uses the fact that (a > b) evaluates to 0 or 1
    value = max(value, min_val)  # In C: value = value > min_val ? value : min_val
    value = min(value, max_val)
    return value
 
# Technique 3: Multiply-and-shift instead of modulo
def fast_modulo_power_of_2(h: int, table_size: int) -> int:
    """
    For power-of-2 table sizes, use bitwise AND instead of modulo.
    AND is much faster than division/modulo.
    """
    # Slow: h % table_size (involves division)
    # Fast: h & (table_size - 1) (for power-of-2 sizes only)
    
    assert (table_size & (table_size - 1)) == 0, "Must be power of 2"
    return h & (table_size - 1)
 
def fast_modulo_general(h: int, table_size: int) -> int:
    """
    For general table sizes, use multiply-and-shift.
    Pre-compute magic constants for specific table sizes.
    """
    # This is a simplified version; real implementations
    # use magic number division for specific divisors.
    
    # For demonstration, use regular modulo
    return h % table_size
 
# Technique 4: Loop unrolling
def unrolled_hash(s: str) -> int:
    """
    Process 4 characters per loop iteration.
    Reduces loop overhead by 4×.
    """
    h = 0
    length = len(s)
    i = 0
    
    # Process 4 characters at a time
    while i + 4 <= length:
        h = ((h * 31 + ord(s[i])) & 0xFFFFFFFF)
        h = ((h * 31 + ord(s[i+1])) & 0xFFFFFFFF)
        h = ((h * 31 + ord(s[i+2])) & 0xFFFFFFFF)
        h = ((h * 31 + ord(s[i+3])) & 0xFFFFFFFF)
        i += 4
    
    # Handle remaining characters
    while i < length:
        h = ((h * 31 + ord(s[i])) & 0xFFFFFFFF)
        i += 1
    
    return h
 
# Compare approaches
import time
 
def compare_techniques():
    test_str = "the quick brown fox jumps over the lazy dog" * 100
    test_bytes = test_str.encode()
    iterations = 1000
    
    print("CPU Optimization Techniques")
    print("="*50)
    
    # Regular byte-by-byte
    def regular_hash(data):
        h = 0
        for b in data:
            h = ((h * 31) + b) & 0xFFFFFFFF
        return h
    
    start = time.perf_counter()
    for _ in range(iterations):
        regular_hash(test_bytes)
    regular_time = time.perf_counter() - start
    
    # Word-at-a-time
    start = time.perf_counter()
    for _ in range(iterations):
        word_at_a_time_hash(test_bytes)
    word_time = time.perf_counter() - start
    
    # Unrolled (on string)
    start = time.perf_counter()
    for _ in range(iterations):
        unrolled_hash(test_str)
    unrolled_time = time.perf_counter() - start
    
    print(f"Regular byte-by-byte:  {regular_time*1000:.2f}ms")
    print(f"Word-at-a-time:        {word_time*1000:.2f}ms ({regular_time/word_time:.1f}× faster)")
    print(f"Unrolled loop:         {unrolled_time*1000:.2f}ms ({regular_time/unrolled_time:.1f}× faster)")
 
compare_techniques()

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

"""
Practical examples of choosing the right hash for the job.
"""
 
import hashlib
from typing import Any
 
class HashFunctionSelector:
    """
    Demonstrates choosing appropriate hash functions for different scenarios.
    """
    
    @staticmethod
    def for_in_memory_hashtable(key: Any) -> int:
        """
        For in-memory hash tables with controlled input.
        Use Python's built-in hash (fastest, good quality for runtime).
        
        Note: Python's hash is non-deterministic across runs by default.
        """
        return hash(key)
    
    @staticmethod
    def for_persistent_storage(key: str) -> int:
        """
        For hash values that need to persist across program runs.
        Use a deterministic hash function.
        """
        # FNV-1a: Simple, deterministic, fast
        h = 2166136261  # FNV offset basis
        for byte in key.encode('utf-8'):
            h ^= byte
            h = (h * 16777619) & 0xFFFFFFFF  # FNV prime
        return h
    
    @staticmethod
    def for_external_input(key: str, secret_seed: int = 0) -> int:
        """
        For hash tables that may receive adversarial input.
        Use a seeded hash to prevent collision attacks.
        """
        # SipHash or similar would be ideal; simplified version here
        h = secret_seed
        for i, c in enumerate(key):
            h = (h * 31 + ord(c) * (i + 1)) & 0xFFFFFFFF
            h ^= h >> 15
        
        # Strong finalization
        h ^= h >> 16
        h = (h * 0x85ebca6b) & 0xFFFFFFFF
        h ^= h >> 13
        h = (h * 0xc2b2ae35) & 0xFFFFFFFF
        h ^= h >> 16
        
        return h
    
    @staticmethod
    def for_content_addressing(data: bytes) -> str:
        """
        For content-addressable storage, file deduplication, etc.
        Use cryptographic hash for collision resistance.
        """
        return hashlib.sha256(data).hexdigest()
    
    @staticmethod
    def for_password(password: str, salt: bytes = None) -> str:
        """
        For password storage.
        Use a deliberately slow hash with salt.
        
        In production, use bcrypt, Argon2, or scrypt instead!
        """
        import secrets
        
        if salt is None:
            salt = secrets.token_bytes(16)
        
        # PBKDF2: Applies hash function many times to be slow
        # 100,000 iterations makes brute-force expensive
        key = hashlib.pbkdf2_hmac(
            'sha256',
            password.encode('utf-8'),
            salt,
            100000  # iterations
        )
        
        return salt.hex() + ':' + key.hex()
    
    @staticmethod
    def for_distributed_systems(key: str) -> int:
        """
        For distributed systems where hash must be consistent across machines.
        Use a well-defined, stable algorithm.
        """
        # CRC32 is standardized and consistent everywhere
        import zlib
        return zlib.crc32(key.encode('utf-8')) & 0xFFFFFFFF
 
# Demonstration
selector = HashFunctionSelector()
 
print("Hash Function Selection Examples")
print("="*60)
 
test_key = "user:12345:session"
 
print(f"
Test key: '{test_key}'")
print()
 
print("1. In-memory hash table:")
print(f"   hash() = {selector.for_in_memory_hashtable(test_key)}")
print("   (Fastest, but non-deterministic across runs)")
 
print("
2. Persistent storage:")
print(f"   FNV-1a = {selector.for_persistent_storage(test_key)}")
print("   (Deterministic, same every time)")
 
print("
3. External/adversarial input:")
print(f"   Seeded = {selector.for_external_input(test_key, secret_seed=42)}")
print("   (Resists collision attacks)")
 
print("
4. Content addressing:")
print(f"   SHA-256 = {selector.for_content_addressing(test_key.encode())[:32]}...")
print("   (Cryptographic collision resistance)")
 
print("
5. Password storage:")
print(f"   PBKDF2 = {selector.for_password('secret123')[:40]}...")
print("   (Deliberately slow)")
 
print("
6. Distributed systems:")
print(f"   CRC32 = {selector.for_distributed_systems(test_key)}")
print("   (Standardized, consistent everywhere)")

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

import time
import statistics
from typing import Callable, List, Tuple
import random
import string
 
class HashBenchmark:
    """
    Comprehensive hash function benchmarking framework.
    """
    
    def __init__(self, hash_fn: Callable[[str], int], name: str):
        self.hash_fn = hash_fn
        self.name = name
    
    def measure_throughput(self, data: List[str], duration_sec: float = 1.0) -> float:
        """Measure hashes per second."""
        count = 0
        start = time.perf_counter()
        end_time = start + duration_sec
        
        while time.perf_counter() < end_time:
            for key in data:
                self.hash_fn(key)
                count += 1
        
        elapsed = time.perf_counter() - start
        return count / elapsed
    
    def measure_latency(self, data: List[str], iterations: int = 10000) -> dict:
        """Measure hash latency statistics."""
        latencies = []
        
        for _ in range(iterations):
            key = random.choice(data)
            start = time.perf_counter()
            self.hash_fn(key)
            elapsed = (time.perf_counter() - start) * 1e9  # nanoseconds
            latencies.append(elapsed)
        
        return {
            'mean': statistics.mean(latencies),
            'median': statistics.median(latencies),
            'stdev': statistics.stdev(latencies) if len(latencies) > 1 else 0,
            'p99': sorted(latencies)[int(len(latencies) * 0.99)],
            'min': min(latencies),
            'max': max(latencies),
        }
    
    def measure_size_scaling(self, sizes: List[int]) -> List[Tuple[int, float]]:
        """Measure how performance scales with input size."""
        results = []
        
        for size in sizes:
            test_str = ''.join(random.choices(string.ascii_letters, k=size))
            
            # Time 1000 hashes
            start = time.perf_counter()
            for _ in range(1000):
                self.hash_fn(test_str)
            elapsed = time.perf_counter() - start
            
            ns_per_hash = (elapsed / 1000) * 1e9
            results.append((size, ns_per_hash))
        
        return results
 
def run_comprehensive_benchmark():
    """Run benchmarks on multiple hash functions."""
    
    # Test data - varied string lengths
    test_data = [
        f"key_{i:08d}" for i in range(1000)
    ] + [
        ''.join(random.choices(string.ascii_letters, k=random.randint(10, 100)))
        for _ in range(1000)
    ]
    
    # Hash functions to test
    def python_hash(s): return hash(s)
    def fnv1a(s):
        h = 2166136261
        for b in s.encode():
            h ^= b
            h = (h * 16777619) & 0xFFFFFFFF
        return h
    def djb2(s):
        h = 5381
        for c in s:
            h = ((h << 5) + h + ord(c)) & 0xFFFFFFFF
        return h
    
    funcs = [
        ("Python hash()", python_hash),
        ("FNV-1a", fnv1a),
        ("djb2", djb2),
    ]
    
    print("="*70)
    print("COMPREHENSIVE HASH FUNCTION BENCHMARK")
    print("="*70)
    
    for name, fn in funcs:
        bench = HashBenchmark(fn, name)
        
        print(f"
{name}")
        print("-"*40)
        
        # Throughput
        throughput = bench.measure_throughput(test_data)
        print(f"  Throughput: {throughput:,.0f} hashes/sec")
        
        # Latency
        latency = bench.measure_latency(test_data)
        print(f"  Latency (mean): {latency['mean']:.1f} ns")
        print(f"  Latency (p99):  {latency['p99']:.1f} ns")
        
        # Size scaling
        sizes = [10, 50, 100, 500, 1000]
        scaling = bench.measure_size_scaling(sizes)
        print(f"  Size scaling:")
        for size, ns in scaling:
            print(f"    {size:4} chars: {ns:.1f} ns ({ns/size:.2f} ns/char)")
 
run_comprehensive_benchmark()