How Hashing Works Internally
Quick Reference: Consistent Hashing | Load Balancing
Quick Reference
| Hash Function | Collision Handling | Time Complexity | Use Case |
|---|---|---|---|
| MD5 | Chaining | O(1) avg | Checksums (deprecated) |
| SHA-256 | N/A (cryptographic) | O(1) | Security |
| MurmurHash | Chaining | O(1) avg | General purpose |
| CRC32 | Chaining | O(1) avg | Fast checksums |
Clear Definition
Hashing maps data of arbitrary size to fixed-size values. Hash functions should be fast, deterministic, and distribute values uniformly to minimize collisions.
š” Key Insight: Good hash functions have uniform distribution and handle collisions efficiently (chaining or open addressing).
Core Concepts
Hash Functions
- Deterministic: Same input ā same output
- Uniform Distribution: Even spread of hash values
- Fast Computation: O(1) average time
- Collision Resistance: Minimize collisions
Collision Handling
Chaining: Linked list at each bucket
Open Addressing: Probe for next available slot
Cuckoo Hashing: Multiple hash functions
Best Practices
- Choose Right Function: Cryptographic vs non-cryptographic
- Handle Collisions: Use chaining or open addressing
- Monitor Distribution: Check for clustering
Quick Reference Summary
Hashing: Map data to fixed-size values for fast lookups.
Collision Handling: Chaining (linked lists) or open addressing (probing).
Performance: O(1) average, O(n) worst case with collisions.
Previous Topic: Consistent Hashing ā
Next Topic: Proxy & Reverse Proxy ā
Back to: Step 6 Overview | Main Index