Hash Tables & Hash Functions
Hash table implementations, collision resolution strategies, hash functions, load factor, and performance characteristics.
The data
Core concepts
| Component | Purpose | Properties | Common functions | Example | Notes | Definition | Threshold | Rehashing | Time impact | Strategies | Description |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Hash Function | Maps arbitrary key to integer index in hash table array |
|
| h(k) = (a × k + b) mod m (affine hash for integers) | Cryptographic hashes (SHA, MD5) are slow; non-cryptographic preferred for hash tables | null | null | null | null | null | null |
| Load Factor (α) | null | null | null | null | Higher α → more collisions, slower lookups; lower α → wasted memory | Ratio of number of entries to number of buckets (n / m) | Typically 0.75 for separate chaining, 0.5-0.7 for open addressing | When α exceeds threshold, resize table (usually double) and rehash all entries | Amortized O(1) if resizing infrequent; worst-case O(n) during resize | null | null |
| Collision Resolution | null | null | null | null | null | null | null | null | null |
| Method to handle multiple keys mapping to same bucket index |
Collision strategies
- Separate chaining
- Structure
- Each bucket is linked list (or tree) of entries; hash(key) → bucket index → traverse list
- Complexity
- Avg search
- O(1 + α) = O(1) if α constant
- Worst search
- O(n) if all keys collide
- Insert
- O(1) (prepend to list)
- Delete
- O(1) if have pointer, else O(length of chain)
- Pros
- Simple
- Handles any load factor
- Deletion easy
- Never full (can always insert)
- Cons
- Memory overhead (pointers per node)
- Cache unfriendly (linked list scattered)
- Optimization
- Convert linked list to balanced BST (e.g., Java 8+) when chain length exceeds threshold (e.g., 8) → O(log n) worst case
- Open addressing
- Structure
- All entries stored directly in array; collision → probe sequence to find next available slot
- Probing methods
- Linear
- h(k, i) = (h'(k) + i) mod m — simple but primary clustering
- Quadratic
- h(k, i) = (h'(k) + c₁i + c₂i²) mod m — reduces clustering but secondary clustering remains
- Double hashing
- h(k, i) = (h₁(k) + i × h₂(k)) mod m — minimal clustering, best performance; h₂(k) must be relatively prime to m
- Complexity
- Avg search
- O(1 / (1 - α)) for successful, O(1 / (1 - α)²) for unsuccessful
- Worst search
- O(n) if table nearly full
- Insert
- Same as search (find empty slot)
- Delete
- Complex — cannot simply remove (breaks probe chain); use tombstone marker
- Pros
- No pointer overhead (cache friendly)
- Lower memory use
- Cons
- More sensitive to load factor
- Deletion tricky (tombstones accumulate)
- Clustering issues (linear/quadratic)
- Notes
- Table load should stay ≤ 0.5-0.7 for good performance; tombstone cleanup periodic rehash
Hash table types
| Name | Implementation | Languages | Avg operations | Notes | Use cases | Features |
|---|---|---|---|---|---|---|
| HashMap / Dictionary | Array of buckets + hash function + collision resolution |
| O(1) | Most common associative array; maintains insertion order in some implementations (Python 3.7+) | null | null |
| HashSet | Hash table storing only keys (no values) |
| null | Backed by hash table; hash of key determines bucket |
| null |
| Concurrent Hash Map | Lock striping or lock-free segments for thread-safe access |
| null | Traditional HashMap requires external synchronization (synchronized/mutex); concurrent maps scale to many threads | null |
|
Design considerations
- Choose hash function
- Integers
- Multiplicative: (a × k) >> shift or modulo prime
- Strings
- Polynomial rolling hash (h = Σ char[i] × p^i mod m) or MurmurHash3
- Objects
- Combine field hashes: hash = 31 × (31 × seed + field1.hash) + field2.hash (Java style)
- Avoid collisions
- Prime bucket count
- Use prime number of buckets (reduces clustering with mod)
- Good hash
- Uniform distribution; test with real key distribution
- Dynamic resize
- Resize when α exceeds threshold (typically 0.75)
- When not to use
- Ordered operations
- Need sorted keys → use BST (TreeMap)
- Range queries
- Need keys in range → BST or B-tree
- Memory constrained
- Hash tables have overhead (pointers/buckets)
- Extremely large keys
- Consider key interning or perfect hash
Fetch the same bytes
The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.
curl "https://yjtoon.com/api/dataset/hash-tables?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/hash-tables.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →