We need a deterministic way to convert arbitrary-sized keys (strings, numbers) into fixed-size array indices for O(1) lookup.
A hash function maps keys to integer values (array indices) such that equal keys always produce the same hash value, and the distribution is as uniform as possible.
- Take input key (string, number, object)
- Apply mathematical transformation (e.g., modulo, multiplication, bit shifting)
- Output is an integer in range [0, table_size-1]
- Good hash functions minimize collisions
- Deterministic: same key → same hash always
- Uniform distribution minimizes collisions
- Fast to compute (shouldn’t be slower than the data structure it serves)
- Examples: division method, multiplication method, universal hashing
- Built from: Hashing
- Builds into: Separate Chaining, Linear Probing
- Related: Collision Resolution, Load Factor
- Contrasts with: Random Number Generator (hash is deterministic, not random)
- Poor hash functions cause clustering (many collisions)
- String hashing must handle variable lengths
- Cryptographic hash functions are overkill for hash tables (too slow)
- Changing hash function requires rehashing entire table