Hashing, deep — tables, crypto, rings, passwords, Bloom

What makes a hash good

• Deterministic (within its seed), uniform (keys spread evenly over buckets), avalanche (flip 1 input bit → ∼half the output bits flip, so near-identical keys don’t cluster), fast (O(key length)).
• Table hashes: FNV, Murmur, xxHash (fast, unkeyed → floodable); SipHash (Aumasson & Bernstein 2012) is a fast keyed PRF built to stop flooding. Swift’s Hasher uses SipHash-1-3, keyed by a random per-process seed (SWIFT_DETERMINISTIC_HASHING=1 to pin it in tests).
• HashDoS (28C3, 2011): an attacker who knows an unkeyed hash posts thousands of keys that collide → every insert walks one chain → O(n²) CPU from one request. The secret seed makes the collision set unpredictable. Cost: hashValue and Set order change every launch.

Collisions — normal, then resolved

• Birthday bound: with m possible values, a collision is likely after ∼√(m) items: P ≈1 - e^-n2/2m. 23 people → 50 %; a 64-bit hash → ∼2³² (4 billion) items; UUIDv4 (122 random bits) → ∼2.7×10¹⁸. SHA-256 collision work = 2¹²⁸, not 2²⁵⁶.
• Chaining (list per bucket; Java HashMap turns a chain of ≥8 into a red-black tree). Open addressing: linear probing (cache-friendly, primary clustering), quadratic, double hashing, Robin Hood (steal the slot from a key nearer its home — evens probe lengths), cuckoo (2 tables, O(1) worst-case lookup). Deletion needs tombstones or backward shift.
• Rehash: at load α ≈ 0.75 (Swift: 3/4) double and re-insert all — O(n) once, O(1) amortised, a visible latency spike. Redis rehashes incrementally (two tables, move a few buckets per op).
• Consistent hashing: hash(key) % N remaps ∼all keys when N changes; the ring moves ∼K/N. 100–200 vnodes per server smooth load and spread a dead node’s keys over all survivors. Alternatives: rendezvous (highest random weight), jump hash (no memory, numbered buckets only).

Example — Hashable right, and a stable hash

struct User: Hashable {
  let id: Int; var displayName: String         // not identity
  static func == (a: User, b: User) -> Bool { a.id == b.id }
  func hash(into h: inout Hasher) { h.combine(id) }  // SAME fields as ==
}
// hashValue changes per launch: never persist it. A stable key:
import CryptoKit
let name = SHA256.hash(data: Data(url.absoluteString.utf8))
  .map { String(format: "%02x", $0) }.joined()  // cache file name

Cryptographic hashes

MAC: HMAC vs a plain hash

A plain hash proves integrity only against accidents — anyone can recompute it. HMAC(K,m) = H((K ⊕opad) ‖H((K ⊕ipad) ‖m)): only a key holder can make or check the tag, and the nesting defeats length extension. Compare tags in constant time (CryptoKit isValidAuthenticationCode), never with ==.

Password hashing — slow on purpose

Bloom filter

m bits, k hash functions. No false negatives, tunable false positives: p ≈(1-e^-kn/m)^k; best k = (m/n)ln2; 1 % ≈ 9.6 bits per item, k = 7. No delete (counting Bloom filter can). Use: skip a disk/network lookup for keys that surely aren’t there (LSM-tree databases, CDN caches).

Interview traps

• Persisting hashValue / asserting Set order — changes per launch.
• hash(into:) using a field == ignores, or mutating a key after insertion → lost or duplicate entries.
• SHA-256(password), even salted — too fast. And H(key ‖msg) is not a MAC.
• “A hash is encryption” — no key, no inverse. “Collision = 2²⁵⁶” — it’s 2¹²⁸.

Remember

Tables: fast + seeded. Integrity: SHA-256. Authenticity: HMAC. Passwords: Argon2id + salt. Membership at scale: Bloom.

Likely questions

1. Why is Swift’s hash seeded? — HashDoS; so never persist it.
2. Why vnodes? — even load; a dead node’s keys spread over all.
3. Bloom says yes? — maybe; says no — definitely no.
4. SHA-256 for a Dictionary? — too slow; seeded SipHash already stops flooding.
5. Why HMAC, not H(k ‖m)? — length extension forges the latter.
6. Store passwords? — Argon2id, per-user salt, PHC string; re-hash on login when params rise.