Hashing & Hash Functions

Metadata

1. Overview

What problem does it solve?

How do you take an input of any size (a 5-byte word or a 5-gigabyte video file) and deterministically map it to a fixed-size, semi-random string of characters? Hashing.

Hashing solves the problem of identification, distribution, and lookup. Instead of comparing huge files or searching through millions of servers, you calculate a hash and use that hash as a rapid index or identifier.

What breaks without it?

Without hash functions:

• Load balancers couldn't route the same user to the same server (sticky sessions).
• Databases couldn't partition data evenly across disks.
• Caches (Redis/Memcached) couldn't O(1) lookup keys.
• Passwords would have to be stored in plain text.
• File downloads couldn't be verified for corruption.

2. Motivation

Why were Hash Functions invented?

In the 1950s, engineers needed a way to search large datasets quickly. Scanning an entire array took O(N) time. Hans Peter Luhn (IBM) invented the concept of a hash table in 1953: by mathematically transforming a search key into an array index, lookups could drop to O(1).

As distributed systems emerged, the problem shifted: we didn't just need to find data in an array; we needed to distribute data across thousands of servers evenly. Hashing provided the perfect mathematical mechanism for random but deterministic distribution.

3. Real-World Usage

4. Prerequisites

None. This is a foundational Tier 1 block.

5. Visual Explanation

The Hashing Concept

graph LR
    A["Input 1: 'apple'"] --> H(Hash Function)
    B["Input 2: 'banana'"] --> H
    C["Input 3: [10 GB Video]"] --> H
    
    H --> D["0x8F43..."]
    H --> E["0x2A99..."]
    H --> F["0x77B1..."]
    
    style H fill:#f9f,stroke:#333,stroke-width:2px

The 4 Properties of a Good Hash Function

1. Deterministic: The same input always produces the exact same output.
2. Fixed Size: A 1-byte input and a 1-TB input both produce a 256-bit hash.
3. Uniform Distribution: Inputs should map evenly across the output space (no clustering).
4. Avalanche Effect: Changing just 1 bit of the input should change ~50% of the output bits.

6. Internal Working

6.1 Cryptographic vs Non-Cryptographic Hashes

System design interviews often blur these together, but using the wrong one in production is disastrous.

Non-Cryptographic Hashes

• Goal: Speed and uniform distribution (avoiding collisions in hash tables).
• Security: Weak. Easily reversible or vulnerable to collision attacks.
• Examples: MurmurHash3, CityHash, xxHash, SipHash, CRC32.
• Use Cases: Hash tables, database indexing, load balancing, Bloom filters.

Cryptographic Hashes

• Goal: Security. Computationally infeasible to reverse (pre-image resistance) or find two inputs that produce the same output (collision resistance).
• Security: Strong, but computationally slow by design.
• Examples: SHA-256, SHA-3, MD5 (broken), SHA-1 (broken), bcrypt (for passwords).
• Use Cases: Password storage, digital signatures, blockchain (Bitcoin mining), Git commits.

6.2 The Collision Problem

Because the input space is infinite (any possible file) and the output space is finite (e.g., 256 bits), collisions are mathematically guaranteed (Pigeonhole Principle).

If two different inputs produce the same hash: hash(A) == hash(B).

• In a Hash Table: Solved via chaining (linked lists) or open addressing.
• In Cryptography: A disaster (allows spoofing digital signatures).

Note: For a 256-bit hash, the number of possible outputs is 2^256 (more than the number of atoms in the observable universe). So while collisions are mathematically guaranteed, they are statistically impossible to find by accident.

6.3 Hashing for Distribution (Modulo Hashing)

In distributed systems, you have N servers and you need to assign data to them.

server_index = hash(key) % N

If you have 4 servers, and hash("user123") = 105, then 105 % 4 = 1. This user's data goes to Server 1. (Warning: This naive approach breaks when N changes. See Consistent Hashing).

7. Implementation

Why Python? Python's standard library includes excellent hashing implementations (hashlib). We'll implement a simple distributed router that uses non-cryptographic hashing to route requests to servers.

"""
005 - Hashing for Data Distribution
Demonstrates the Avalanche effect and how hashing is used 
to distribute load across a cluster of servers.
"""
import hashlib
import binascii

# ── 1. The Avalanche Effect ──

def sha256_hash(text: str) -> str:
    """Returns the SHA-256 hex digest of a string."""
    return hashlib.sha256(text.encode('utf-8')).hexdigest()

print("--- The Avalanche Effect ---")
# Changing one single character drastically changes the entire hash
hash1 = sha256_hash("System Design is fun!")
hash2 = sha256_hash("System Design is fun.")

print(f"Input 1: {hash1}")
print(f"Input 2: {hash2}")
print()


# ── 2. Simple Modulo Load Balancer ──

class NaiveLoadBalancer:
    def __init__(self, num_servers: int):
        self.servers = [f"Server-{i}" for i in range(num_servers)]
        
    def _murmur_hash_mock(self, key: str) -> int:
        """
        Python's built-in hash() is randomized per-process for security.
        For deterministic routing, we need a stable hash.
        We'll use CRC32 here as a stand-in for a fast non-crypto hash (like Murmur3).
        """
        return binascii.crc32(key.encode('utf-8'))
        
    def route_request(self, user_id: str) -> str:
        """Route a user to a server deterministically based on their ID."""
        h = self._murmur_hash_mock(user_id)
        # The Modulo operation bounds the hash to our server count
        server_index = h % len(self.servers)
        return self.servers[server_index]

print("--- Modulo Distribution ---")
lb = NaiveLoadBalancer(num_servers=4)

# Test routing for 10 users
server_counts = {s: 0 for s in lb.servers}

for i in range(1, 11):
    user_id = f"user_{i}"
    server = lb.route_request(user_id)
    server_counts[server] += 1
    print(f"{user_id:<10} routed to -> {server}")

print("\nDistribution across servers:")
for s, count in server_counts.items():
    print(f"{s}: {count} requests")

Sample Output

--- The Avalanche Effect ---
Input 1: 3b40096e4ed9f9449f8bb80b719be6a86c757ed4a742ea3dbedb53298c56fa74
Input 2: ed7ed8c0cda1113c06d88b6883fa0ceeaefb0be62817d3d191295fc74301d006

--- Modulo Distribution ---
user_1     routed to -> Server-0
user_2     routed to -> Server-3
user_3     routed to -> Server-2
user_4     routed to -> Server-1
user_5     routed to -> Server-0
user_6     routed to -> Server-3
user_7     routed to -> Server-2
user_8     routed to -> Server-1
user_9     routed to -> Server-0
user_10    routed to -> Server-3

Distribution across servers:
Server-0: 3 requests
Server-1: 2 requests
Server-2: 2 requests
Server-3: 3 requests

8. Complexity

Speed Differences (Approximate on modern CPU)

• xxHash / MurmurHash3: ~10-20 GB/sec (Extremely fast, used for DBs/Caches)
• SHA-256: ~500 MB/sec (Slower, used for crypto/integrity)
• bcrypt: Configurable intentionally to be very slow (~10 hashes/sec) to prevent brute force.

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. You are designing a distributed cache. How do you decide which cache server stores which key? Hint: Hash the key to get an integer, then map that integer to a server.

2. Why shouldn't you use SHA-256 for a hash table implementation? Hint: It's cryptographically secure, which means it requires heavy math. It's orders of magnitude slower than MurmurHash, slowing down basic map lookups.

3. In Kafka, how does the system ensure all messages for user_123 are processed in order? Hint: The producer hashes the partition key (user_123). The hash modulo the number of partitions guarantees the user always hits the exact same partition queue.

4. What is a Hash-DoS attack and how is it mitigated? Hint: Sending thousands of API parameters designed to collide in the server's hash map, locking up the CPU. Mitigated by randomizing the hash seed per process.

13. Used By (Downstream Blocks)

• 006 UUIDs — Often generated using hashes of MAC addresses or timestamps.
• 015 Bloom Filters — Relies heavily on multiple independent hash functions.
• 016 Consistent Hashing — Solves the modulo scaling problem.
• 017 Data Partitioning — Distributing database load evenly.
• 038 Merkle Tree — Tree of hashes used in Dynamo, Cassandra, and Blockchain.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Hash Collision Generator

While finding a SHA-256 collision is impossible, try finding a collision for a very weak hash. Write a function that takes a string, calculates the MD5 hash, but only returns the first 3 hex characters (12 bits). Write a loop to find two different strings that produce the exact same 3-character output.

Website Metadata