Overview
A Hash Table maps each key to a hash code, uses that code to choose a bucket or slot, and resolves collisions when multiple keys land in the same place.
FoundationSource checked
Hash Table
Stores key-value pairs in buckets chosen by a hash function for fast average-case lookup.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Associative Array
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 16
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Hash Map, Dictionary
Core Concepts
hash functionbucketcollision resolutionload factor
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(n)
Space
O(n)
When to Use
- Use it when fast average-case insertion, lookup, and deletion are needed.
- Use it when keys have reliable equality and hash behavior.
- Use it for frequency tables, memoization, and indexing.
When Not to Use
- Avoid it when ordered traversal or range queries are central.
- Avoid it when adversarial keys can force collisions and no mitigation exists.
- Avoid it when deterministic memory layout matters more than lookup speed.
What It Does
- Associates keys with values
- Uses hashing to reduce average lookup time
Use Cases
- Dictionaries and maps
- Sets and membership tests
- Counting frequencies
Inputs
- Keys
- Values
- Hash function
Outputs
- Stored key-value mapping
- Lookup results
Key Formulas (1)
Bucket index
index = hash(key) mod capacity
index = hash(key) mod capacityMaps a key hash into a table slot or bucket.
Pseudocode
- 1.Hash the key
- 2.Map the hash to a bucket index
- 3.Inspect the bucket for the key
- 4.Insert, update, delete, or return the value
- 5.Resize when the table becomes too full
Canonical Example
- Input
- insert ('cat', 2), insert ('dog', 5), lookup 'cat'
- Output
- 2
- Explanation
- The key 'cat' hashes to a bucket where its stored value can be found.
Implementation Notes
- Keep hash, equality, collision resolution, and resizing policies consistent.
- Resize before the load factor makes probe or chain lengths too large.
- Test deletion behavior, especially for open-addressed tables.
Common Pitfalls
- Using mutable keys whose hash value changes after insertion.
- Ignoring collision behavior and load-factor resizing.
- Confusing average-case O(1) with a guaranteed bound.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow keys hashing into buckets with collisions handled in place.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Hash the key
hash-bucketsNotes
Hash-table performance depends on the hash function, load factor, and collision strategy.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Hash Table.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsCuckoo Hash Table
Data Structures · Core
Cuckoo hash tables are hash-table variants that use multiple hash locations and displacement chains.
Compare with thisHas variantsCuckoo Hashing
Data Structures · Core
Cuckoo hashing is a hash-table collision strategy.
Compare with thisHas variantsRobin Hood Hashing
Data Structures · Core
Robin Hood hashing is an open-addressed hash-table variant that balances probe distances during insertion.
Compare with thisAlternativesBitset Operations
Data Structures · Core
Bitsets trade sparse key flexibility for compact constant-time membership over a fixed universe.
Compare with thisRelationships
View full relationship pageUsed byHash Lookup
Hash lookup queries are implemented over hash table storage.
Often paired withSipHash
SipHash can protect hash tables from adversarial collision attacks.
Related Algorithms
Tags
Data StructureHash BasedHashing