Hashing and encoding for system design
The hashing and encoding tools that appear in designs: cryptographic versus non-cryptographic hashes, base62 and base64, short codes, collisions and the birthday bound, checksums, content addressing, HMAC signatures and password hashing.
Reading is half of it. See this used in a real interview: walk through Design a URL Shortener →
Hashes and encodings show up everywhere in system design: short URLs, cache keys, shard selection, deduplication, file integrity, signed links and stored passwords. Each use needs a different kind of hash, and mixing them up (using MD5 for passwords, or a fast hash where an attacker controls the input) is a classic mistake. This guide is the toolbox.
Kinds of hash functions
| Kind | Examples | Speed | Use for | Do not use for |
|---|---|---|---|---|
| Non-cryptographic | MurmurHash, xxHash, CityHash | very fast | sharding, hash tables, Bloom filters, consistent hashing | anything an attacker can exploit |
| Cryptographic | SHA-256, SHA-3, BLAKE3 | fast | content addressing, integrity, deduplication, signatures | passwords (too fast) |
| Broken cryptographic | MD5, SHA-1 | fast | non-security checksums only | anything security-related |
| Keyed (MAC) | HMAC-SHA256 | fast | signing tokens, webhooks, URLs | password storage |
| Password hashing | Argon2id, bcrypt, scrypt | deliberately slow | stored passwords | everything else |
| Checksums | CRC32 | very fast | detecting accidental corruption | detecting tampering |
Encodings are not hashes
Encodings turn bytes into text, reversibly:
- Base64 (and URL-safe base64): 4 characters per 3 bytes; tokens and binary data in JSON.
- Base62 (0-9, a-z, A-Z): URL-friendly without special characters; common for short codes.
- Base32 and Crockford base32: case-insensitive, avoids confusable characters; good for codes people type or read aloud.
- Hex: 2 characters per byte; hashes in logs.
An encoding hides nothing: base64 of a secret is still the secret.
Short codes and how many you need
A short code of length L over an alphabet of size A gives A^L possibilities. Base62:
| Length | Combinations |
|---|---|
| 6 | about 57 billion |
| 7 | about 3.5 trillion |
| 8 | about 218 trillion |
Two ways to generate them:
- Encode a unique counter (from a ticket server, a sequence or a unique id generator) in base62: no collisions, but sequential codes are guessable. Shuffle with a reversible permutation or encryption if guessability matters.
- Hash the input (for example SHA-256 of the long URL) and take the first characters: deterministic and deduplicating, but collisions happen and must be handled by checking and retrying with a salt.
See Design a URL Shortener and unique ids, ordering and time.
Collisions and the birthday bound
With N possible values, collisions become likely after about the square root of N items, not N. A 32-bit hash (4 billion values) has a 50 % chance of a collision after only about 77,000 items. For random short codes, check uniqueness on insert (a unique constraint) instead of assuming none. For content addressing, use 256-bit cryptographic hashes, where collisions are practically impossible.
Content addressing and deduplication
Naming data by the hash of its content (as Git, Docker images and many backup and sync systems do):
- Identical files or chunks are stored once.
- Integrity is verifiable: re-hash and compare.
- Caching is trivial, because content at a hash never changes.
Sync systems split files into chunks (often content-defined boundaries so insertions do not shift every chunk), hash each, and upload only unknown hashes. See Design Dropbox. Crawlers hash page content (and use similarity hashes like SimHash for near-duplicates) to skip duplicate pages. See Design a Web Crawler.
Hashing for distribution
Sharding and load balancing hash keys to pick a node. Use a fast, well-distributed non-cryptographic hash, and consistent hashing or rendezvous hashing so adding a node moves few keys. If users control keys and could craft collisions to overload one node, use a keyed hash (SipHash) with a secret. See consistent hashing.
Signatures with HMAC
To prove a message came from you and was not modified, send HMAC(secret, message) with it. Uses: webhook signatures, signed URLs for private files with an expiry, stateless tokens and tamper-proof cookies. Compare signatures in constant time, and include a timestamp to prevent replays. See webhooks.
Passwords
Never store passwords with plain or fast hashes. Use Argon2id (or bcrypt or scrypt) with a unique salt per password and a cost tuned to tens to hundreds of milliseconds per attempt, so offline guessing is slow. See security and auth.
Checklist
- Fast non-cryptographic hashes for distribution; keyed hashes if inputs are hostile.
- SHA-256 or BLAKE3 for integrity and content addressing.
- Base62 or base32 codes sized with the birthday bound in mind; uniqueness enforced on insert.
- HMAC for signed messages and URLs, with timestamps.
- Argon2id or bcrypt with salts for passwords.
- Encodings are reversible; never treat them as protection.