HashMap in Java: How It Works Internally

You put a product into a HashMap as a key, then change its price — and map.get(doll) returns null, although it is the very same object and map.size() is still 1. This is not a JDK bug: it is how a hash table works, and by the end of this lesson you will know exactly why the key got “lost” and how to avoid it.

HashMap (java.util.HashMap<K, V>) is the most widely used implementation of the Map interface in Java: it stores key–value pairs in a hash table and finds a value by its key in O(1) time on average. A HashMap allows one null key and any number of null values, does not guarantee any iteration order and is not synchronized. The class appeared in Java 1.2, and its internals were substantially reworked in Java 8.

What is HashMap in Java

HashMap in Java is a class that implements the Map interface on top of a hash table: the key’s hash code selects a cell of an internal array (a bucket), and the key–value pair is stored in that cell. That is why put(), get(), containsKey() and remove() run in constant time on average, no matter how many entries the map holds.

The class declaration:

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable

K is the key type and V is the value type. Keys are unique: a second put() with the same key replaces the value. The Map methods themselves (put, get, keySet, entrySet, getOrDefault, merge and the rest), iteration and Map.Entry are covered in the lesson Map Interface in Java. This lesson is about what happens inside a HashMap when you call them.

How to create a HashMap: constructors

You create a new HashMap in Java with new HashMap<>(), which gives an empty map with capacity 16 and load factor 0.75. If you know the number of entries in advance, the factory method HashMap.newHashMap(n) from Java 19 sizes the table for you, and new HashMap<>(map) makes a copy of another map. The variable is usually declared with the Map interface type.

Example: employee salaries, where the key is the last name and the value is the amount.

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Double> salaries = new HashMap<>();

        salaries.put("Smith", 3434.34);
        salaries.put("Johnson", 123.22);
        salaries.put("Taylor", 1378.00);

        salaries.forEach((name, salary) -> System.out.println(name + ": " + salary));
    }
}

Output:

Johnson: 123.22
Taylor: 1378.0
Smith: 3434.34

The entries come out neither in insertion order nor alphabetically: a HashMap iterates in bucket order. In a 16-bucket table "Johnson" lands in bucket 3, "Taylor" in bucket 5 and "Smith" in bucket 7 — how these numbers are computed is shown in the section on the bucket index. The literal 1378.00 is autoboxed to a Double: a HashMap stores only objects.

If you see Maps.newHashMap() in code, that is a method of the Guava library, not of the JDK: it predates the diamond operator (<>, Java 7) and simply creates an empty HashMap without repeating the type arguments. In modern code new HashMap<>() replaces it. The JDK method HashMap.newHashMap(int) is a different thing: it computes the capacity for the given number of entries. An unmodifiable map with a few entries is created with Map.of(...) — see Map Interface in Java.

HashMap methods and their complexity

The core HashMap methods — put(), get(), getOrDefault(), containsKey() and remove() — run in O(1) on average, because they look at a single bucket chosen by the key’s hash code. Methods that scan the whole table — containsValue(), iterating keySet(), values() or entrySet(), and clear() — depend on the number of entries and on the capacity.

How get() behaves with a null key and a null value:

Map<String, String> map = new HashMap<>();
map.put(null, "value for the null key");
map.put("a", null);

System.out.println(map.get(null));         // value for the null key
System.out.println(map.get("a"));          // null - the value is null
System.out.println(map.get("b"));          // null - no such key
System.out.println(map.containsKey("a"));  // true
System.out.println(map.containsKey("b"));  // false

Output:

value for the null key
null
null
true
false

Every method with examples, including the Java 8 additions (computeIfAbsent, merge, putIfAbsent), is in the lesson Map Interface in Java. If Big O notation is new to you, start with algorithm complexity and Big O.

HashMap internal structure: table and Node

Inside a HashMap there is an array Node<K,V>[] table, and its cells are the buckets. Each cell is either null (an empty bucket) or the first node of a chain. A Node stores the key’s hash, the key, the value and a reference to the next node in the same bucket.

// simplified, from the source code of java.util.HashMap
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;     // the key's hash, computed once in put()
    final K key;
    V value;
    Node<K, V> next;    // next node in the same bucket
}

transient Node<K, V>[] table;  // bucket array, length is a power of two
transient int size;            // number of entries
int threshold;                 // size at which resize() happens
final float loadFactor;        // 0.75f by default

A 16-bucket table holding the keys "Aa", "BB" and "Java", where the first two share a bucket (the bucket numbers are worked out in the next sections):

table
[0]  Node("Aa", hash=2112) -> Node("BB", hash=2112) -> null
[1]  Node("Java", hash=2301537) -> null
[2]  null
...
[15] null

Three important consequences of this design:

• The hash is stored in the node. A lookup compares the hash numbers first and calls equals() only when they match — that is cheaper.
• The array is created lazily. Since Java 8, new HashMap<>() does not allocate the table: it appears on the first put().
• A node is the Map.Entry. Iterating entrySet() hands out the table nodes themselves, so entry.setValue() changes the value directly in the map.

Since Java 8 a long chain in a bucket can be turned into a tree of TreeNode objects — see Tree bins.

How the bucket index is computed: hash() and (n - 1) & hash

HashMap computes the bucket index in two steps: the hash() method mixes the high bits of hashCode() into the low bits with h ^ (h >>> 16), and then the low bits of the result are taken: index = (n - 1) & hash, where n is the table length. A null key has hash 0, so it always lives in bucket 0.

// from the source code of java.util.HashMap (Java 8+)
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Let’s compute the bucket for the key "Java" and check the arithmetic in code:

public class BucketIndexExample {
    public static void main(String[] args) {
        String key = "Java";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);

        System.out.println(h);              // the string's hash code
        System.out.println(spread);         // after spreading
        System.out.println(h & 15);         // bucket without spreading, n = 16
        System.out.println(spread & 15);    // actual bucket, n = 16
        System.out.println(spread & 31);    // n = 32
        System.out.println(spread & 63);    // n = 64
    }
}

Output:

2301506
2301537
2
1
1
33

What happened here: "Java".hashCode() is 2301506, or 0x231E42. The upper 16 bits (0x23) are shifted down and XOR-ed with the lower ones: 0x1E42 ^ 0x0023 = 0x1E61. A 16-bucket table looks only at the 4 lowest bits: 0x1E61 & 0xF = 1. Without spreading, the key would go to bucket 2.

The same calculation explains the order in the salaries example. "Smith".hashCode() is 80004067 = 0x04C4C3E3; the lowest hex digit of the spread hash is 3 ^ 4 = 7, so “Smith” goes to bucket 7. “Johnson” and “Taylor” end up in buckets 3 and 5 the same way, and iteration walks the buckets from 0 to 15.

Why spread the bits

In a small table the index depends on just a few low bits of the hash. If keys differ only in their high bits, they all land in one bucket. Example: Integer keys 0, 65536 and 131072 (an Integer’s hash code is the number itself). Their lower 16 bits are all zero, so without hash() all three would go to bucket 0. After h ^ (h >>> 16) the hashes become 0, 65537 and 131074 — buckets 0, 1 and 2.

Why HashMap capacity is a power of two

When n is a power of two, n - 1 is all ones in binary (15 = 0b1111), and hash & (n - 1) gives the same result as hash % n for non-negative numbers, but without a division and without trouble from negative hashes. That is why HashMap always rounds the capacity up to a power of two (the internal method tableSizeFor()), and the table only ever grows by doubling. How capacity relates to the number of elements is shown with HashSet in HashSet constructors: initialCapacity and loadFactor.

How HashMap works: put() and get() step by step

HashMap put(key, value) computes the key’s hash, finds the bucket and either places a new node there or walks the chain and replaces the value of the node with an equal key. get(key) follows the same path but only reads. A key counts as found when the hashes match and the keys are equal by == or by equals().

What put() does (the putVal() method in the source code):

1. Computes hash = hash(key).
2. If the table does not exist yet, calls resize(), which creates an array of 16 buckets.
3. Finds the bucket i = (n - 1) & hash. If it is empty, puts a new Node there and jumps to step 6.
4. Otherwise walks the chain. For each node it checks p.hash == hash && (p.key == key || key.equals(p.key)). If such a node exists, it replaces the value and returns the old one; the size of the map does not change.
5. If not, it appends a new node to the tail of the chain (Java 7 inserted at the head). If the chain now has more than 8 nodes, the bucket is turned into a tree.
6. Increments size; if size > threshold, calls resize(). Returns null — there was no previous value.

get(key) repeats steps 1, 3 and 4: it computes the hash, checks the first node of the bucket, then walks the list or searches the tree. If the bucket is empty or no equal key is found, it returns null.

Collisions and the role of equals() and hashCode()

A HashMap collision happens when two different keys land in the same bucket, either because their hash codes are equal or because different hashes share the same low bits. Collisions are normal and do not break the map: the nodes of a bucket form a chain, and equals() picks the right key. Only many collisions are a problem, because lookups slow down.

The strings "Aa" and "BB" have the same hash code 2112 (65 * 31 + 97 and 66 * 31 + 66), yet the map keeps them as separate keys:

Map<String, Integer> map = new HashMap<>();
map.put("Aa", 1);
map.put("BB", 2);

System.out.println("Aa".hashCode() + " " + "BB".hashCode());
System.out.println(map.get("Aa") + " " + map.get("BB"));
System.out.println(map.size());

Output:

2112 2112
1 2
2

The upper 16 bits of 2112 are zero, so hash() leaves it unchanged. 2112 = 0x840, and its four lowest bits are 0: both keys sit in bucket 0 as one chain, and equals() tells them apart.

Why a mutable key gets “lost”

The key’s hash is computed once — in put() — and stored in the node. If you later change a field that hashCode() depends on, the new hash points to another bucket or no longer matches the stored one, and get() cannot find the key. Here is the example from the start of the lesson in full:

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class MutableKeyExample {
    static class Product {
        private final String name;
        private int cost;

        Product(String name, int cost) {
            this.name = name;
            this.cost = cost;
        }

        void setCost(int cost) {
            this.cost = cost;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Product p && cost == p.cost && name.equals(p.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name, cost);
        }
    }

    public static void main(String[] args) {
        Map<Product, String> shops = new HashMap<>();
        Product doll = new Product("Doll", 534);
        shops.put(doll, "Toy Planet");
        System.out.println(shops.get(doll));

        doll.setCost(434);
        System.out.println(shops.get(doll));
        System.out.println(shops.containsKey(doll));
        System.out.println(shops.size());

        shops.put(doll, "Kids World");
        System.out.println(shops.size());
    }
}

Output:

Toy Planet
null
false
1
2

After setCost(434), hashCode() returns a different number while the node still holds the old one, so the check p.hash == hash fails — even though the map contains that very object. A second put() of the same object creates a second node: the map now has two keys pointing to one Product, and the first entry can no longer be found or removed with remove(doll).

Capacity, load factor and resize()

Capacity is the length of the bucket array, 16 by default. The load factor (0.75 by default) sets the threshold threshold = capacity * loadFactor: as soon as the number of entries exceeds the threshold, HashMap calls resize(), creates an array twice as long and moves every node into it. For a default map that happens when the 13th entry is added.

How nodes move during a resize

When the table doubles, HashMap does not call hashCode() again: the hash is already stored in the node. The new index depends on a single bit, hash & oldCap. If that bit is 0, the node stays in the bucket with the same index j (the “lo” list); if it is 1, the node moves to bucket j + oldCap (the “hi” list). The bucket is split in two without recomputing any index.

Take the key "Java" from above: its spread hash ends in 0x61 (0b0110_0001). Growing from 16 to 32 checks bit 16 (0x10) — it is 0, so the key stays in bucket 1. Growing from 32 to 64 checks bit 32 (0x20) — it is 1, so the key moves to bucket 1 + 32 = 33. These are exactly the numbers printed by BucketIndexExample.

Since Java 8 the nodes in the lo and hi lists keep their relative order. In Java 7 the transfer reversed the chain, and two threads calling resize() at the same time could close the list into a loop — after which get() spun in an infinite loop. It is the best-known example of what using a HashMap from several threads without synchronization can do.

How to presize a HashMap

Every resize() visits all nodes, so for large maps of known size the table is allocated up front. On Java 19+ use HashMap.newHashMap(n): it takes the 0.75 load factor into account. On older versions compute the capacity by hand: new HashMap<>((int) Math.ceil(n / 0.75)). A common mistake is new HashMap<>(n): such a map resizes before n entries fit.

Map<String, Integer> a = new HashMap<>(1000);       // table 1024, threshold 768 - resize on the 769th entry
Map<String, Integer> b = HashMap.newHashMap(1000);  // Java 19+: table 2048, 1000 entries without a resize

A HashMap never shrinks: after remove() and clear() the array keeps its length.

Tree bins: what changed in Java 8

Since Java 8, HashMap turns an overly long chain into a red-black tree when a single bucket holds more than 8 nodes and the table has at least 64 buckets. A lookup in such a bucket takes O(log n) instead of O(n). If the table is smaller than 64 buckets, HashMap doubles the table instead of building a tree. The change came with JEP 180, partly as a defence against attacks that flooded servers with thousands of string keys sharing one hash code.

Tree nodes (TreeNode) are ordered by hash first. If the hashes are equal and the keys implement Comparable and belong to the same class, compareTo() decides — so String, Integer and your own Comparable classes cope best with mass collisions. For non-comparable keys with equal hashes the tree cannot choose a branch, and a lookup may have to visit most of it.

HashMap and multithreading

HashMap is not thread-safe: if several threads modify it at the same time, updates get lost and size() may not match the real number of entries. For a map shared between threads use ConcurrentHashMap; for occasional access to an existing map, the wrapper Collections.synchronizedMap(map).

Even in a single thread, HashMap iterators are fail-fast: if you call map.put() with a new key or map.remove() while iterating over keySet() or entrySet(), the next step of the loop throws ConcurrentModificationException. Replacing the value of an existing key is not a structural change. To remove entries while iterating, use iterator.remove() or map.entrySet().removeIf(...) (see Iterator in Java). Thread-safe collections and a counter on ConcurrentHashMap are compared in Thread-safe collections in Java.

HashMap vs TreeMap vs Hashtable

HashMap keeps keys in a hash table with no order and works in O(1) on average; TreeMap keeps keys sorted in a red-black tree with O(log n) operations; Hashtable is a legacy synchronized hash table from Java 1.0 that rejects null. In new code the choice is usually between HashMap (order does not matter) and TreeMap (you need sorting or a nearest-key lookup).

TreeMap methods and the SortedMap and NavigableMap interfaces are covered in TreeMap, SortedMap and NavigableMap. If you need insertion order rather than sorting, use LinkedHashMap — a subclass of HashMap that also links its nodes into a list. The Java 8 change is described in the original proposal, JEP 180: Handle Frequent HashMap Collisions with Balanced Trees.