How HashMap Works
Buckets, hashing, and collisions.
What HashMap Stores
A HashMap stores key-value pairs and gives you average O(1) lookup, insertion, and removal.
Internally it keeps an array called the table. Each slot in this array is called a bucket.
- The key decides which bucket an entry lands in.
- The value is what you get back when you look up the key.
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);
System.out.println(ages.get("Alice"));
}
}Hashing the Key
When you call put(key, value), the map calls key.hashCode() to get an int.
HashMap then spreads those bits with an internal function so that even poor hash codes distribute across buckets.
- The final number is reduced with
hash & (table.length - 1)to get a bucket index. - Table length is always a power of two, so the mask works.
public class Main {
public static void main(String[] args) {
String key = "Alice";
int h = key.hashCode();
int spread = h ^ (h >>> 16);
int index = spread & (16 - 1);
System.out.println("hashCode: " + h);
System.out.println("bucket index: " + index);
}
}