You probably used a HashMap today without thinking about it. But what actually happens when you call map.put("apple", 3)? Let's open the box, with plain words and a small Java program you can run yourself.
The idea in one minute
A HashMap is an array of buckets. When you store something:
- The key goes through
hashCode(), which turns it into a number. - That number is reduced to a bucket index (in our model:
hash % 8). - The key and value are stored in that bucket.
Two different keys can land on the same bucket. That is a collision, and the bucket simply keeps them as a small chain. Finding a value means: hash the key, jump to the bucket, walk the short chain comparing keys.
Watch the flow
The animation walks three moments: storing apple in an empty bucket, storing mango which collides with apple and joins its chain, then finding apple again by walking that chain. (It shows a simplified 8-bucket teaching model - the same one the code below runs.)
Run it yourself
This tiny hash map prints every step, so you can see the hashing, the bucket choice, the collision and the chain walk:
import java.util.HashMap;
public class HashMapDemo {
// A tiny hand-rolled hash map so we can watch every step
static class SimpleHashMap {
static final int BUCKETS = 8;
static class Node {
String key; int value; Node next;
Node(String k, int v) { key = k; value = v; }
}
Node[] table = new Node[BUCKETS];
int bucketIndex(String key) {
return (key.hashCode() & 0x7fffffff) % BUCKETS;
}
void put(String key, int value) {
int i = bucketIndex(key);
for (Node n = table[i]; n != null; n = n.next) {
if (n.key.equals(key)) {
System.out.println("put(" + key + ", " + value + ") -> bucket " + i + ": key exists, value overwritten");
n.value = value;
return;
}
}
Node n = new Node(key, value);
n.next = table[i];
table[i] = n;
System.out.println("put(" + key + ", " + value + ") -> hash " + (key.hashCode() & 0x7fffffff)
+ " -> bucket " + i + (n.next != null ? " (collision: added to chain)" : ""));
}
Integer get(String key) {
int i = bucketIndex(key);
int steps = 0;
for (Node n = table[i]; n != null; n = n.next) {
steps++;
if (n.key.equals(key)) {
System.out.println("get(" + key + ") -> bucket " + i + ", found after " + steps + " step(s): " + n.value);
return n.value;
}
}
System.out.println("get(" + key + ") -> bucket " + i + ": not in chain, returns null");
return null;
}
void printTable() {
System.out.println("\nFinal table (" + BUCKETS + " buckets):");
for (int i = 0; i < BUCKETS; i++) {
StringBuilder sb = new StringBuilder("bucket " + i + ": ");
if (table[i] == null) sb.append("(empty)");
for (Node n = table[i]; n != null; n = n.next) sb.append(n.key).append("=").append(n.value).append(" -> ");
if (sb.toString().endsWith(" -> ")) sb.setLength(sb.length() - 4);
System.out.println(sb);
}
}
}
public static void main(String[] args) {
SimpleHashMap map = new SimpleHashMap();
map.put("cat", 1);
map.put("dog", 2);
map.put("apple", 3);
map.put("banana", 4);
map.put("mango", 5);
map.put("cat", 9); // same key again: overwrite
map.printTable();
System.out.println();
map.get("dog");
map.get("apple");
map.get("zebra");
System.out.println("\n-- The real java.util.HashMap --");
HashMap<String, Integer> real = new HashMap<>();
real.put("cat", 1);
real.put("dog", 2);
real.put("apple", 3);
real.put(null, 99); // null key is allowed
System.out.println("real.get(\"cat\") = " + real.get("cat"));
System.out.println("real.get(null) = " + real.get(null));
System.out.println("iteration order: " + real.keySet() + " (not guaranteed, do not rely on it)");
}
}
What it actually printed (JDK 21)
put(cat, 1) -> hash 98262 -> bucket 6
put(dog, 2) -> hash 99644 -> bucket 4
put(apple, 3) -> hash 93029210 -> bucket 2
put(banana, 4) -> hash 751128421 -> bucket 5
put(mango, 5) -> hash 103662530 -> bucket 2 (collision: added to chain)
put(cat, 9) -> bucket 6: key exists, value overwritten
Final table (8 buckets):
bucket 0: (empty)
bucket 1: (empty)
bucket 2: mango=5 -> apple=3
bucket 3: (empty)
bucket 4: dog=2
bucket 5: banana=4
bucket 6: cat=9
bucket 7: (empty)
get(dog) -> bucket 4, found after 1 step(s): 2
get(apple) -> bucket 2, found after 2 step(s): 3
get(zebra) -> bucket 6: not in chain, returns null
-- The real java.util.HashMap --
real.get("cat") = 1
real.get(null) = 99
iteration order: [null, apple, cat, dog] (not guaranteed, do not rely on it)
Three things to notice:
-
mangoandappleboth hash to bucket 2, so they sit in one chain.get("apple")checksmangofirst, then findsappleon step 2. - Storing
catagain does not add a second entry; it overwrites the value (1 becomes 9). -
zebrahashes to bucket 6, which holdscat. The map walks that chain, finds no match, and returnsnull- a wrong bucket is never even looked at.
The real HashMap adds a few upgrades
Our 8-bucket model keeps the moving parts visible. Per the Java 21 HashMap documentation, the real one:
- Gives constant-time
getandput, assuming the hash function spreads keys well across buckets. - Grows automatically: when entries exceed capacity x load factor (default 0.75), it rehashes to roughly twice the buckets.
- Permits one
nullkey and any number ofnullvalues. - Makes no order guarantees - do not rely on iteration order.
- Is not synchronized; for concurrent access wrap it with
Collections.synchronizedMap(or use a concurrent map). - Can use comparison order to break ties when many keys share a hash code (in practice, very long chains are turned into trees to keep lookups fast).
Sources
Written with AI assistance; code examples were compiled and run on JDK 21 before publishing.
Top comments (0)