Back to All Algorithms
Hashing
Category: Data Structures | Time: O(1) Average | Space: O(n)
Visualization
Visual representation of the data structure
0
empty
1
empty
2
empty
3
empty
4
empty
5
empty
6
empty
7
empty
8
empty
9
empty
About Hashing
A technique used to map data of an arbitrary size to data of a fixed size. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are used to index a fixed-size table called a hash table.
Code Editor
The code is for reference. Editing it won't affect the visualization.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Variable State
{
"status": "Initializing hash table",
"size": 10
}Hashing: How It Works
Last updated October 28, 2026
Overview
A hash table stores key-value pairs in an array of buckets. A hash function turns each key into a bucket index, so a lookup can jump straight to the right bucket instead of searching the whole collection. When two keys land in the same bucket — a collision — this implementation uses separate chaining: each bucket holds a small list of entries.
The hash function here is hash = (hash + charCode(key[i]) * i) % 10, with 10 buckets. It is deliberately simple so you can check it by hand, but it has a flaw worth noticing: the first character is multiplied by i = 0, so it never affects the result. 'cat' and 'bat' always land in the same bucket.
The default input inserts 15 fruits into 10 buckets, a load factor of 1.5, which guarantees collisions. In the dry run you can see six of them; bucket 8 ends up holding grape, peach and kiwi. Looking up 'grape' hashes to bucket 8 and finds it as the first entry in that chain.
Step by step
- Compute
index = hash(key). - To insert: if the key already exists in
table[index], update its value; otherwise append the pair to that bucket's list. - To look up: compute the same index and scan that bucket's list for the key.
- To delete: find the entry in its bucket and remove it from the list.
- In production, resize (rehash into a larger table) when the load factor passes a threshold such as 0.75.
Complexity
| Case | Cost | Why |
|---|---|---|
| Insert / lookup / delete (average) | O(1) | With a good hash and a bounded load factor, chains stay short. |
| Insert / lookup / delete (worst) | O(n) | If every key collides, one bucket holds everything. |
| Resize | O(n) | Occasional; amortised O(1) per insert when the table doubles. |
| Space | O(n + m) | n entries plus m buckets. |
When to use it
- Fast membership tests and lookups: caches, symbol tables, de-duplication, counting frequencies.
- Many interview problems (Two Sum, Group Anagrams, LRU Cache) reduce to the right hash map.
- Joining or indexing data by a key when you never need it in sorted order.
Common mistakes
- Weak hash functions, like the one shown, cluster keys and destroy the O(1) average.
- Not resizing: a fixed 10-bucket table with 1,000 keys behaves like ten linked lists.
- Using mutable objects as keys and then changing them, so their hash no longer matches their bucket.
Worked Example: Hashing Dry Run
Generated from the same trace that drives the visualizer above, using the default input.
A dry run is the best way to check your understanding of Hashing: follow each row, predict the next one, and compare. The run below takes 88 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- apple,red;banana,yellow;grape,purple;orange,orange;mango,yellow;strawberry,red;peach,orange;lemon,yellow;lime,green;cherry,red;blueberry,blue;watermelon,green;pear,green;pineapple,yellow;kiwi,green
- Lookup key
- grape
- Result
- key = grape, status = Key found!, value = purple
| Step | Line | What happens |
|---|---|---|
| 1 | 1 | status = Initializing hash table, size = 10 |
| 2 | 14 | action = set, key = apple, value = red |
| 5 | 18 | key = apple, value = red, index = 4, status = Inserting new key-value pair |
| 6 | 20 | status = Finished inserting 'apple' |
| 7 | 14 | action = set, key = banana, value = yellow |
| 10 | 18 | key = banana, value = yellow, index = 3, status = Inserting new key-value pair |
| 11 | 20 | status = Finished inserting 'banana' |
| 12 | 14 | action = set, key = grape, value = purple |
| 15 | 18 | key = grape, value = purple, index = 8, status = Inserting new key-value pair |
| 16 | 20 | status = Finished inserting 'grape' |
| 17 | 14 | action = set, key = orange, value = orange |
| 20 | 18 | key = orange, value = orange, index = 5, status = Inserting new key-value pair |
| 21 | 20 | status = Finished inserting 'orange' |
| 22 | 14 | action = set, key = mango, value = yellow |
| 25 | 18 | key = mango, value = yellow, index = 0, status = Inserting new key-value pair |
| 26 | 20 | status = Finished inserting 'mango' |
| 27 | 14 | action = set, key = strawberry, value = red |
| 30 | 18 | key = strawberry, value = red, index = 6, status = Inserting new key-value pair |
| 31 | 20 | status = Finished inserting 'strawberry' |
| 32 | 14 | action = set, key = peach, value = orange |
| 35 | 17 | key = peach, value = orange, index = 8, status = Collision detected! |
| 36 | 18 | key = peach, value = orange, index = 8, status = Inserting new key-value pair |
| 37 | 20 | status = Finished inserting 'peach' |
| 38 | 14 | action = set, key = lemon, value = yellow |
| 41 | 18 | key = lemon, value = yellow, index = 2, status = Inserting new key-value pair |
| 42 | 20 | status = Finished inserting 'lemon' |
| 43 | 14 | action = set, key = lime, value = green |
| 46 | 17 | key = lime, value = green, index = 6, status = Collision detected! |
| 47 | 18 | key = lime, value = green, index = 6, status = Inserting new key-value pair |
| 48 | 20 | status = Finished inserting 'lime' |
| 49 | 14 | action = set, key = cherry, value = red |
| 52 | 18 | key = cherry, value = red, index = 9, status = Inserting new key-value pair |
| 53 | 20 | status = Finished inserting 'cherry' |
| 54 | 14 | action = set, key = blueberry, value = blue |
| 57 | 17 | key = blueberry, value = blue, index = 2, status = Collision detected! |
| 58 | 18 | key = blueberry, value = blue, index = 2, status = Inserting new key-value pair |
| 59 | 20 | status = Finished inserting 'blueberry' |
| 60 | 14 | action = set, key = watermelon, value = green |
| 63 | 17 | key = watermelon, value = green, index = 3, status = Collision detected! |
| 64 | 18 | key = watermelon, value = green, index = 3, status = Inserting new key-value pair |
The remaining 16 key steps follow the same pattern. Press play in the visualizer to watch every step through to the result.
Frequently Asked Questions
About Hashing
What is Hashing?
Hashing is a technique used to map data of an arbitrary size to a fixed-size value, called a hash code or hash value. This is done using a hash function. It's fundamental to hash tables (hash maps), a data structure used for fast data retrieval.
What is a Hash Table?
A Hash Table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
What is a hash function and what makes a good one?
A hash function is an algorithm that takes an input (or 'key') and returns a fixed-size string of bytes, which is the hash value. A good hash function should be: 1) Fast to compute. 2) Deterministic (the same input always produces the same output). 3) It should minimize collisions by distributing keys uniformly across the buckets.
What is a collision in a hash table?
A collision occurs when two different keys hash to the same index in the array. Since two values cannot be stored in the same slot, collision resolution strategies are needed.
How can collisions be handled?
The two most common methods are: 1) Separate Chaining, where each bucket is the head of a linked list, and all keys that hash to that bucket are stored in the list. 2) Open Addressing, where if a collision occurs, the algorithm probes for the next empty slot in the array (e.g., linear probing, quadratic probing).
What is the time complexity of search, insert, and delete in a hash table?
On average, the time complexity is O(1), assuming a good hash function and minimal collisions. In the worst case (where all keys hash to the same bucket), the complexity degrades to O(n), as it becomes equivalent to a linear search through a linked list.
What is the 'load factor' of a hash table?
The load factor (α) is the ratio of the number of stored elements to the number of buckets in the hash table (α = n/k). It's a measure of how full the hash table is. A higher load factor increases the probability of collisions. To maintain performance, a hash table is often resized when the load factor exceeds a certain threshold (e.g., 0.7).
When would you use a hash table?
Hash tables are ideal when you need fast lookups, insertions, and deletions. They are used to implement caches, dictionaries (maps), and sets. For example, counting the frequency of words in a document or checking for the presence of an item in a collection.
What are some real-world applications of hashing?
Beyond hash tables, hashing is crucial for cryptography (e.g., storing password hashes instead of plain text), data integrity checks (e.g., checksums for file downloads), and building data structures like Bloom filters.
Can a hash table store duplicate keys?
A standard hash map or dictionary cannot store duplicate keys, as each key must uniquely map to a value. If you try to insert a key that already exists, you will typically overwrite the existing value. To store multiple values for one key, you would need a 'multimap', where each bucket can hold multiple values (e.g., in a list).
Where can I learn more?
You can find a more detailed explanation on GeeksforGeeks.
Related Interview Questions
Practice with real problems