Hash Tables & Hash Functions
Hash table implementations, collision resolution strategies, hash functions, load factor, and performance characteristics.
How hash tables work: hash functions, load factor and collision resolution by chaining or open addressing, the common hash table types in programming languages, and design considerations for choosing a hash function and avoiding collisions.
Use it when
- You are explaining or implementing a hash table.
- You need to reason about collisions and load factor.
Watch out for
- Average O(1) lookup depends on a good hash function and a bounded load factor; adversarial inputs can degrade it.
- Hash tables do not keep keys ordered; use a tree-based map when order matters.
The data
Core concepts
3 rows
| 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
3 rows
| 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
Fields
The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.
| Section | Field | Type | Example |
|---|---|---|---|
| core_concepts | component | string | Hash Function |
| core_concepts | purpose | string | Maps arbitrary key to integer index in hash tab… |
| core_concepts | properties | array | [4 items] |
| core_concepts | common_functions | array | [5 items] |
| core_concepts | example | string | h(k) = (a × k + b) mod m (affine hash for integ… |
| core_concepts | notes | string | Cryptographic hashes (SHA, MD5) are slow; non-c… |
| core_concepts | definition | string | Ratio of number of entries to number of buckets… |
| core_concepts | threshold | string | Typically 0.75 for separate chaining, 0.5-0.7 f… |
| core_concepts | rehashing | string | When α exceeds threshold, resize table (usually… |
| core_concepts | time_impact | string | Amortized O(1) if resizing infrequent; worst-ca… |
| core_concepts | strategies | array | [2 items] |
| core_concepts | description | string | Method to handle multiple keys mapping to same … |
| collision_strategies | * | object | {separate_chaining,open_addressing} |
| hash_table_types | name | string | HashMap / Dictionary |
| hash_table_types | implementation | string | Array of buckets + hash function + collision re… |
| hash_table_types | languages | array | [5 items] |
| hash_table_types | avg_operations | string | O(1) |
| hash_table_types | notes | string | Most common associative array; maintains insert… |
| hash_table_types | use_cases | array | [3 items] |
| hash_table_types | features | array | [3 items] |
| design_considerations | * | object | {choose_hash_function,avoid_collisions,when_not_to_use} |
Fetch the same bytes
The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.
curl "https://yjtoon.yunusemrevurgun.com/api/dataset/hash-tables?format=toon"
const res = await fetch( "https://yjtoon.yunusemrevurgun.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 →