Hash Map
Last updated
A hash map stores key-value pairs and lets you look up a value by its key in O(1) on average. It works exactly like a hash table, but each bucket entry carries both a key and its associated value. To store or fetch a pair, the key is hashed to a bucket index, then the bucket's chain is scanned for the matching key. Press play above to watch pairs get placed by hashed bucket and a value retrieved by its key.
This is the structure behind Python's dict, Java's HashMap, and JavaScript's Map/objects. Collisions are handled the same way as in a hash table - here, by separate chaining - so performance depends on a good hash function and a low load factor.
Time complexity
| Operation | Average | Worst case |
|---|---|---|
| Put (insert/update) | O(1) | O(n) |
| Get (lookup) | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Space | O(n) | O(n) |
Hash map in common languages
| Language | Type |
|---|---|
| Python | dict |
| Java | HashMap |
| JavaScript | Map / object |
| C++ | std::unordered_map |
| Go | map |
Worked example
Inserting the pairs ("cat", 3), ("dog", 5), ("cat", 9), ("emu", 7) into a map with 8 buckets, using hash(key) % 8. Assume hash("cat") % 8 = 2, hash("dog") % 8 = 5, hash("emu") % 8 = 2:
| Step | Structure | Action |
|---|---|---|
Put ("cat", 3) | bucket 2: [("cat", 3)] | Hash to bucket 2; empty chain, so append the pair. |
Put ("dog", 5) | bucket 2: [("cat", 3)], bucket 5: [("dog", 5)] | Hash to bucket 5; empty chain, so append the pair. |
Put ("cat", 9) | bucket 2: [("cat", 9)], bucket 5: [("dog", 5)] | Hash to bucket 2; key "cat" already in chain, so update its value to 9. |
Put ("emu", 7) | bucket 2: [("cat", 9), ("emu", 7)], bucket 5: [("dog", 5)] | Hash to bucket 2; collides with "cat", key not found, so append the pair. |
Get "emu" | bucket 2: [("cat", 9), ("emu", 7)] | Hash to bucket 2; scan the chain, skip "cat", match "emu", return 7. |
When to use a hash map
| Use it when | Avoid it when |
|---|---|
You need O(1) average lookup, insert, and delete by an exact key. | You need keys kept in sorted order or range queries - use a balanced BST or sorted map. |
| Keys are hashable and equality is well defined (strings, ints, tuples). | Keys are mutable and can change after insertion, which corrupts their bucket. |
| You are counting, deduplicating, caching, or indexing by an identifier. | You need worst-case O(log n) guarantees rather than amortized average bounds. |
| Iteration order does not matter, or an insertion-ordered map suffices. | Memory is very tight - buckets, load-factor headroom, and pointers add overhead. |
Hash Map code
A clean, runnable Hash Map implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Hash Map code in Python
Python
1# Python's built-in dict is a hash map: O(1) average2# insert, lookup, and delete.3inventory = {"apple": 3, "banana": 7}4
5# Insert and update6inventory["cherry"] = 57inventory["apple"] += 28
9# Lookup, with .get for a safe default on missing keys10print("apple: ", inventory["apple"])11print("mango: ", inventory.get("mango", 0))12
13# Membership test and delete14print("banana in stock:", "banana" in inventory)15del inventory["banana"]16print("banana in stock:", "banana" in inventory)17
18# Iterate over key-value pairs19for fruit, count in sorted(inventory.items()):20 print(f"{fruit}: {count}")21
22# Classic hash map use case: counting frequencies23words = "the quick brown fox jumps over the lazy dog the end".split()24freq = {}25for word in words:26 freq[word] = freq.get(word, 0) + 127
28print("Occurrences of the:", freq["the"])29print("Most common word: ", max(freq, key=freq.get))Hash Map code in JavaScript
JavaScript
1// The built-in Map is the idiomatic hash map in JavaScript:2// any key type, insertion-ordered iteration, O(1) average lookups.3const ages = new Map();4
5ages.set("Alice", 30);6ages.set("Bob", 25);7ages.set("Carol", 35);8ages.set("Bob", 26); // set on an existing key updates the value9
10console.log("Bob:", ages.get("Bob"));11console.log("Has Dave?", ages.has("Dave"));12console.log("Size:", ages.size);13
14ages.delete("Carol");15console.log("Size after delete:", ages.size);16
17for (const [name, age] of ages) {18 console.log(`${name} is ${age}`);19}20
21console.log("Keys:", [...ages.keys()].join(", "));Hash Map code in Java
Java
1import java.util.HashMap;2import java.util.Map;3
4public class Main {5 public static void main(String[] args) {6 Map<String, Integer> ages = new HashMap<>();7 ages.put("Alice", 30);8 ages.put("Bob", 25);9 ages.put("Carol", 35);10
11 System.out.println("Bob -> " + ages.get("Bob"));12 System.out.println("contains Carol: " + ages.containsKey("Carol"));13 System.out.println("Dave or default: " + ages.getOrDefault("Dave", -1));14
15 // getOrDefault makes frequency counting a one-liner16 String[] words = {"apple", "banana", "apple", "cherry", "apple"};17 Map<String, Integer> counts = new HashMap<>();18 for (String w : words) {19 counts.put(w, counts.getOrDefault(w, 0) + 1);20 }21 System.out.println("apple count: " + counts.get("apple"));22
23 ages.remove("Bob");24 System.out.println("size after remove: " + ages.size());25
26 for (Map.Entry<String, Integer> entry : ages.entrySet()) {27 System.out.println(entry.getKey() + " is " + entry.getValue());28 }29 }30}Hash Map code in C++
C++
1#include <algorithm>2#include <iostream>3#include <string>4#include <unordered_map>5#include <vector>6
7int main() {8 std::unordered_map<std::string, int> ages;9
10 // Insert and update11 ages["alice"] = 30; // operator[] inserts or overwrites12 ages.insert({"bob", 25}); // insert keeps an existing value13 ages.emplace("carol", 41);14 ages["alice"] = 31;15
16 // Lookup17 auto it = ages.find("bob");18 if (it != ages.end()) {19 std::cout << "bob is " << it->second << "\n";20 }21 std::cout << "has dave: " << ages.count("dave") << "\n";22
23 // Remove24 ages.erase("carol");25
26 // Iterate (sort keys first: unordered_map has no defined order)27 std::vector<std::string> keys;28 for (const auto& entry : ages) keys.push_back(entry.first);29 std::sort(keys.begin(), keys.end());30 for (const std::string& name : keys) {31 std::cout << name << " = " << ages[name] << "\n";32 }33 std::cout << "size: " << ages.size() << "\n";34 return 0;35}Hash Map code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4#include <string.h>5
6#define BUCKETS 167
8typedef struct Node {9 char key[24];10 int value;11 struct Node* next;12} Node;13
14// A small string -> int hash map with a reusable put/get/remove API15typedef struct {16 Node* buckets[BUCKETS];17 int size;18} HashMap;19
20unsigned int hashKey(const char* key) {21 unsigned int h = 5381;22 for (; *key; key++) h = h * 33 + (unsigned char)*key;23 return h % BUCKETS;24}25
26void mapPut(HashMap* map, const char* key, int value) {27 unsigned int i = hashKey(key);28 for (Node* n = map->buckets[i]; n != NULL; n = n->next) {29 if (strcmp(n->key, key) == 0) {30 n->value = value;31 return;32 }33 }34 Node* n = malloc(sizeof(Node));35 strcpy(n->key, key);36 n->value = value;37 n->next = map->buckets[i];38 map->buckets[i] = n;39 map->size++;40}41
42bool mapGet(const HashMap* map, const char* key, int* out) {43 for (Node* n = map->buckets[hashKey(key)]; n != NULL; n = n->next) {44 if (strcmp(n->key, key) == 0) {45 *out = n->value;46 return true;47 }48 }49 return false;50}51
52void mapRemove(HashMap* map, const char* key) {53 Node** link = &map->buckets[hashKey(key)];54 while (*link != NULL) {55 if (strcmp((*link)->key, key) == 0) {56 Node* old = *link;57 *link = old->next;58 free(old);59 map->size--;60 return;61 }62 link = &(*link)->next;63 }64}65
66int main(void) {67 HashMap map = {0};68 mapPut(&map, "alice", 30);69 mapPut(&map, "bob", 25);70 mapPut(&map, "carol", 41);71 mapPut(&map, "alice", 31); // updates the existing key72 int age;73 if (mapGet(&map, "bob", &age)) printf("bob is %d\n", age);74 printf("has dave: %s\n", mapGet(&map, "dave", &age) ? "yes" : "no");75 mapRemove(&map, "carol");76 printf("size: %d\n", map.size);77 return 0;78}Hash Map FAQ
What is the difference between a hash map and a hash table?
They're essentially the same structure - an array of buckets addressed by a hash of the key. In common usage "hash table" often refers to a set of keys or the general technique, while "hash map" emphasizes storing key-value pairs. Some languages also draw a thread-safety distinction (e.g. Java's Hashtable vs HashMap), but the core algorithm is identical.
What is the time complexity of a hash map?
Put, get, and delete are
O(1) on average with a good hash function and a low load factor. In the pathological case where all keys collide into one bucket, they degrade to O(n), which is why resizing and good hashing matter.How does a hash map handle two keys that hash to the same bucket?
It resolves the collision. This visualization uses separate chaining: each bucket holds a small list, and a new pair whose key hashes there is appended to that list. On lookup, the map scans the short chain for the matching key. The alternative technique is open addressing, which probes for another slot in the array.
Hash map vs binary search tree: which should I use?
Use a hash map when you only need lookup by exact key and want
O(1) average operations. Use a balanced binary search tree (like a TreeMap or std::map) when you need keys in sorted order, range queries, or predecessor/successor lookups, which cost O(log n). The BST trades a bit of speed for ordering guarantees a hash map cannot provide.What is the load factor and why does it trigger resizing?
The load factor is the ratio of stored entries to buckets. As it rises, chains grow longer and average lookups slow down, so most implementations resize (typically double the buckets and rehash everything) once it passes a threshold like
0.75. Resizing is O(n) but rare, so it is amortized away and keeps average operations O(1).Can I use a mutable object like a list as a hash map key?
Usually no. Keys must be hashable and their hash must stay constant while they are in the map - Python raises
TypeError: unhashable type for a list, for example. If you mutate a key after inserting it, its hash changes and the map can no longer find it in the right bucket, silently losing the entry. Use immutable keys such as strings, numbers, or tuples.Related resources
More visualizations
