Maps and How HashMap Works

A phone book lets you find a number from a name without reading every entry. That is the central idea of a map: you provide a key and get back its value, ideally without looking at everything you have stored. Maps are everywhere in real programs: a user id mapped to a user, a word to its count, a country code to a currency, a cache of results.

HashMap is the most used collection in Java after ArrayList, and "how does HashMap work?" is probably the most asked Java interview question. In this article you will not just read the answer: you will build a small hash map yourself, so that the answer is something you can reason about, not memorise.

• What a Map is, and the methods you will use every day.
• The idea of hashing, buckets, collisions and resizing.
• How to build a working hash map in about forty lines.
• How the real HashMap differs, including treeification.
• LinkedHashMap, TreeMap and immutable maps.
• The rules for good keys.

A Map<K, V> stores unique keys, each associated with exactly one value. (Putting a value under an existing key replaces the old one.) The everyday operations are put, get, remove, containsKey, size and iteration. Newer methods remove a lot of boilerplate.

// File: Main.javaimport java.util.ArrayList;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;import java.util.TreeMap;public class Main {    public static void main(String[] args) {        Map<String, Integer> stock = new LinkedHashMap<>();        stock.put("pen", 40);        stock.put("book", 12);        stock.put("pen", 45);                       // replaces the old value        System.out.println(stock + " get(pen)=" + stock.get("pen") + " get(ink)=" + stock.get("ink"));        System.out.println(stock.getOrDefault("ink", 0) + " " + stock.containsKey("book"));        System.out.println(stock.putIfAbsent("book", 99) + " " + stock.putIfAbsent("ink", 5));        // Counting: the modern way        String text = "to be or not to be";        Map<String, Integer> counts = new TreeMap<>();        for (String word : text.split(" ")) {            counts.merge(word, 1, Integer::sum);     // insert 1, or combine with the existing count        }        System.out.println(counts);        // Grouping: a list per key        Map<Integer, List<String>> byLength = new TreeMap<>();        for (String word : List.of("a", "to", "be", "or", "not", "cat")) {            byLength.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);        }        System.out.println(byLength);        for (Map.Entry<String, Integer> entry : stock.entrySet()) {            System.out.println(entry.getKey() + " -> " + entry.getValue());        }        stock.remove("ink");        stock.forEach((item, qty) -> System.out.println(item + "=" + qty));    }}

{pen=45, book=12} get(pen)=45 get(ink)=null0 true12 null{be=2, not=1, or=1, to=2}{1=[a], 2=[to, be, or], 3=[not, cat]}pen -> 45book -> 12ink -> 5pen=45book=12

What these methods save you:

• get returns null when the key is missing, which is ambiguous if null can also be a stored value. getOrDefault(key, fallback) avoids the null check.
• putIfAbsent puts only when the key is not already there, and returns the existing value or null.
• merge(key, value, function) is the idiom for counting and summing: if the key is absent it stores the value, otherwise it combines the old and new values with the function. It replaces the old "get, check for null, add one, put back" dance.
• computeIfAbsent(key, function) creates a value on demand and stores it, which is how you build a map of lists ("group by").
• entrySet() gives you key-value pairs in one pass. Iterating keySet() and calling get for each key does a lookup per key and is less efficient. values() gives just the values.

(The -> expressions are lambdas, covered in article 15. Read k -> new ArrayList<>() as "given the key, make a new list".)

How would you build a map yourself? The obvious way is a list of key-value pairs, scanning for the key every time. That takes time proportional to the number of entries: a million entries means up to a million comparisons per lookup. We want a way to go directly to the right place.

Hashing provides it. The idea has three steps:

1. Compute a number from the key, its hash code. (You wrote this in article 7.)
2. Turn the number into an index in an array: the array's slots are called buckets.
3. Look only in that bucket.

If different keys always went to different buckets, a lookup would be a single array access. They do not: two keys can land in the same bucket, which is called a collision. The common remedy is separate chaining: each bucket holds a small linked list of the entries that landed there. Looking up a key means going to its bucket and walking the short list, comparing with equals to find the exact key.

Two numbers keep the chains short. The array must be large enough compared to the number of entries, so when the table gets too full, it is resized (made bigger) and everything is redistributed. The load factor is how full the table may get before that happens. And the hash codes should spread keys out evenly, which is the job of a good hashCode.

Here is a complete, working hash map with chaining and resizing. It is deliberately simple. It exists to teach, not to replace HashMap.

// File: SimpleHashMap.javaimport java.util.Objects;public class SimpleHashMap<K, V> {    private static class Node<K, V> {        final K key;        V value;        Node<K, V> next;        Node(K key, V value, Node<K, V> next) {            this.key = key;            this.value = value;            this.next = next;        }    }    private Node<K, V>[] table;    private int size;    private int resizes;    @SuppressWarnings("unchecked")    public SimpleHashMap() {        table = (Node<K, V>[]) new Node[4];          // start small, to show resizing    }    private static int indexFor(Object key, int tableLength) {        int h = (key == null) ? 0 : key.hashCode();        h ^= (h >>> 16);                              // mix high bits into low bits        return h & (tableLength - 1);                 // works because the length is a power of two    }    public V put(K key, V value) {        int i = indexFor(key, table.length);        for (Node<K, V> n = table[i]; n != null; n = n.next) {            if (Objects.equals(n.key, key)) {         // same key: replace                V old = n.value;                n.value = value;                return old;            }        }        table[i] = new Node<>(key, value, table[i]);  // new key: add to the front of the chain        size++;        if (size > table.length * 3 / 4) {            // load factor 0.75            resize();        }        return null;    }    public V get(Object key) {        for (Node<K, V> n = table[indexFor(key, table.length)]; n != null; n = n.next) {            if (Objects.equals(n.key, key)) {                return n.value;            }        }        return null;    }    @SuppressWarnings("unchecked")    private void resize() {        Node<K, V>[] old = table;        table = (Node<K, V>[]) new Node[old.length * 2];        for (Node<K, V> head : old) {            for (Node<K, V> n = head; n != null; ) {                Node<K, V> next = n.next;                int i = indexFor(n.key, table.length);   // the index changes with the new length                n.next = table[i];                table[i] = n;                n = next;            }        }        resizes++;    }    public int size() {        return size;    }    public int bucketCount() {        return table.length;    }    public int resizeCount() {        return resizes;    }    public int longestChain() {        int longest = 0;        for (Node<K, V> head : table) {            int length = 0;            for (Node<K, V> n = head; n != null; n = n.next) {                length++;            }            longest = Math.max(longest, length);        }        return longest;    }}

Read it with the three steps in mind. indexFor computes the hash, mixes the high bits into the low bits (a trick the real HashMap also uses, because the table index only looks at the low bits), and masks it to a valid index. Masking with length - 1 is a fast way to take the remainder, and it only works because the table length is always a power of two. put walks the chain to see whether the key already exists (using equals), and otherwise adds a new node. When size passes three quarters of the table length, resize doubles the array and re-places every node, because an entry's bucket depends on the table length, so every index must be recomputed.

Now use it, and compare good keys with a deliberately bad one:

// File: Main.javaimport java.util.Objects;public class Main {    static final class GoodKey {        private final int id;        GoodKey(int id) {            this.id = id;        }        @Override        public boolean equals(Object o) {            return o instanceof GoodKey g && g.id == id;        }        @Override        public int hashCode() {            return Objects.hash(id);        }    }    static final class BadKey {        private final int id;        BadKey(int id) {            this.id = id;        }        @Override        public boolean equals(Object o) {            return o instanceof BadKey b && b.id == id;        }        @Override        public int hashCode() {            return 42;                                // legal, but every key collides        }    }    public static void main(String[] args) {        SimpleHashMap<String, Integer> ages = new SimpleHashMap<>();        ages.put("asha", 30);        ages.put("ravi", 25);        ages.put("asha", 31);        System.out.println(ages.get("asha") + " " + ages.get("ravi") + " " + ages.get("meena") + " size=" + ages.size());        SimpleHashMap<GoodKey, String> good = new SimpleHashMap<>();        SimpleHashMap<BadKey, String> bad = new SimpleHashMap<>();        for (int i = 0; i < 50; i++) {            good.put(new GoodKey(i), "v" + i);            bad.put(new BadKey(i), "v" + i);        }        System.out.println("good: buckets=" + good.bucketCount() + " resizes=" + good.resizeCount()                + " longest chain=" + good.longestChain());        System.out.println("bad:  buckets=" + bad.bucketCount() + " resizes=" + bad.resizeCount()                + " longest chain=" + bad.longestChain());        System.out.println(good.get(new GoodKey(7)) + " " + bad.get(new BadKey(7)));    }}

31 25 null size=2good: buckets=128 resizes=5 longest chain=1bad:  buckets=128 resizes=5 longest chain=50v7 v7

With 50 entries, the table grew from 4 buckets to 128 buckets through five doublings. For the good keys, the longest chain is short, so each lookup touches a handful of nodes at most. The bad key class is perfectly legal (it keeps the hashCode contract: equal objects have equal hash codes), and it puts all 50 entries in one bucket, a chain of length 50, so every operation degrades to a linear scan: the map has become a linked list with extra steps. That is the practical meaning of "constant time on average": it assumes the hash function spreads keys out. Oracle's documentation says exactly this: HashMap provides constant-time performance for get and put, assuming the hash function disperses the elements properly among the buckets.

The real java.util.HashMap is the same idea with refinements. The facts below come from the documentation and the OpenJDK source for JDK 21. Those marked implementation detail are not guaranteed by the specification, and can change.

• Capacity and load factor. The documentation defines capacity as the number of buckets and the load factor as how full the table may get before it grows. The default load factor of 0.75 "offers a good tradeoff between time and space costs". When the number of entries exceeds the load factor times the capacity, the table is rehashed to roughly twice the buckets. The default initial capacity is 16 (implementation detail).
• Hash spreading. Like the toy, it spreads the high bits of the hash into the low bits, h ^ (h >>> 16) (implementation detail), so that keys whose hash codes differ only in high bits do not all collide.
• Treeification (since Java 8). If a single bucket accumulates many colliding keys (at least 8 in the source) and the table has at least 64 buckets, that chain is converted into a balanced tree, making the worst-case lookup logarithmic instead of linear. If the bucket shrinks to 6 or fewer, it turns back into a list (implementation detail). Tree bins use the keys' compareTo when keys are Comparable, so Comparable keys help in a pathological case. The documentation does not mention this, because it is an optimisation and not a promise.
• Nulls. HashMap permits one null key and any number of null values. Map.of and ConcurrentHashMap do not.
• No order. The documentation says that HashMap makes no guarantees about order, and that the order may change over time. Do not depend on it.
• Not synchronised. It is not thread-safe. Concurrent structural modification can corrupt it. Use ConcurrentHashMap (article 20) for shared maps.
• Fail-fast iterators. As for lists, structural modification during iteration throws ConcurrentModificationException.
• Iteration cost. The documentation notes that iterating over a map's views takes time proportional to the capacity plus the size, so an enormous, mostly empty map is slow to iterate.

1. Keys must have consistent equals and hashCode, as in article 7.
2. Keys should be immutable. If a key changes in a way that affects its hash code while it is in the map, it is stored in the wrong bucket and can no longer be found.
3. Prefer value types as keys: String, Integer, Long, enums, UUID, records.
4. Make hash codes well spread. Objects.hash(...) is fine for most uses.

LinkedHashMap links its entries in a list as well as hashing them. It can be told to order entries by access instead of insertion, and offers a hook, removeEldestEntry, that makes a small least-recently-used (LRU) cache easy. TreeMap keeps keys in sorted order in a balanced tree and offers navigation methods:

// File: Main.javaimport java.util.LinkedHashMap;import java.util.Map;import java.util.TreeMap;public class Main {    static class LruCache<K, V> extends LinkedHashMap<K, V> {        private final int capacity;        LruCache(int capacity) {            super(16, 0.75f, true);                   // true: order by most recent access            this.capacity = capacity;        }        @Override        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {            return size() > capacity;                 // evict the least recently used        }    }    public static void main(String[] args) {        LruCache<String, Integer> cache = new LruCache<>(2);        cache.put("a", 1);        cache.put("b", 2);        cache.get("a");                               // a becomes most recently used        cache.put("c", 3);                            // evicts b        System.out.println(cache.keySet());        TreeMap<Integer, String> grades = new TreeMap<>();        grades.put(0, "F");        grades.put(40, "D");        grades.put(60, "C");        grades.put(75, "A");        System.out.println(grades.floorEntry(68).getValue());   // greatest key <= 68        System.out.println(grades.firstKey() + " " + grades.lastKey() + " " + grades.ceilingKey(41));        System.out.println(grades.headMap(60) + " " + grades.tailMap(60));        Map<String, Integer> fixed = Map.of("x", 1, "y", 2);        try {            fixed.put("z", 3);        } catch (UnsupportedOperationException e) {            System.out.println("Map.of is immutable");        }    }}

[a, c]C0 75 60{0=F, 40=D} {60=C, 75=A}Map.of is immutable

The LRU cache evicted b because a had just been read. floorEntry(68) found the grade for a score of 68 by taking the greatest key not exceeding it, a pattern HashMap cannot offer because it has no order. Use TreeMap when you need "nearest key" or "all keys between" questions, and pay the logarithmic cost.

• Mutable keys that change after insertion.
• Missing or wrong hashCode on key classes.
• Assuming iteration order for a HashMap.
• Using get and a null check where getOrDefault, merge or computeIfAbsent fit.
• Modifying a map while iterating over it (use removeIf on the views, or an iterator).
• Sharing a HashMap between threads.
• Treating null return from get as "absent" when null values are allowed. Use containsKey if the difference matters.
• Using Hashtable in new code.
• Confusing a HashMap with a hash table you can resize at will. Pre-size with an initial capacity only when you know you will store many entries.

Map<String, Integer> counts = new TreeMap<>();for (String word : sentence.toLowerCase().split("\\s+")) {    counts.merge(word, 1, Integer::sum);}counts.forEach((word, n) -> System.out.println(word + ": " + n));

Map<Character, List<String>> byLetter = new LinkedHashMap<>();for (String name : names) {    byLetter.computeIfAbsent(name.charAt(0), k -> new ArrayList<>()).add(name);}

• Next: Ordering, Queues and Choosing a Collection covers sorting, queues and a decision guide.
• For shared maps between threads: Executors, Futures, Concurrent Collections and Virtual Threads.
• For the interview version of this topic: Interview Concepts, Part 1.