An array of buckets indexed by the key's hash: O(1) average get/put, as long as hashCode spreads keys well and keys never change while inside.

How `put(k, v)` works

Hash the key
h = key.hashCode(), then spread it: h ^ (h >>> 16) so the high bits influence the bucket too. A null key always hashes to 0.
Pick the bucket
index = (n - 1) & hash — n (the table length) is always a power of two, so this is a fast hash % n.
Empty bucket?
Store a new node there.
Collision
Walk the bucket: if a node has the same hash and (== or equals) key, replace its value and return the old one. Otherwise append a new node.
Treeify
If one bucket reaches 8 nodes (and the table has at least 64 buckets) the list becomes a red-black tree → worst case O(log n) instead of O(n). It turns back into a list at 6.
Resize
If size > capacity × loadFactor (16 × 0.75 = 12 by default), the table doubles and entries are split between index i and i + oldCap.

Parameter	Default	Meaning
Initial capacity	16 (allocated lazily on first `put`)	Always rounded up to a power of two
Load factor	0.75	Time/space trade-off: resize when 75% full
`TREEIFY_THRESHOLD`	8	Bucket list → tree (Java 8+)
`UNTREEIFY_THRESHOLD`	6	Tree → list after shrinking
`MIN_TREEIFY_CAPACITY`	64	Below this, resize instead of treeifying

Seeing the bucket index

Java

public class Main {
    static int spread(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public static void main(String[] args) {
        int n = 16;
        for (Object k : new Object[]{"Aa", "BB", 17, 33, null}) {
            int h = spread(k);
            System.out.println(k + " hashCode=" + (k == null ? 0 : k.hashCode()) + " bucket=" + ((n - 1) & h));
        }
    }
}

Output

Aa hashCode=2112 bucket=0
BB hashCode=2112 bucket=0
17 hashCode=17 bucket=1
33 hashCode=33 bucket=1
null hashCode=0 bucket=0

The modern Map API

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> count = new TreeMap<>();     // TreeMap only to print in sorted order
        for (String w : "to be or not to be".split(" ")) {
            count.merge(w, 1, Integer::sum);             // insert 1, or add 1 to the old value
        }
        System.out.println(count);
        System.out.println(count.getOrDefault("xyz", 0));

        Map<String, List<String>> groups = new TreeMap<>();
        for (String w : List.of("apple", "avocado", "banana")) {
            groups.computeIfAbsent(w.substring(0, 1), k -> new ArrayList<>()).add(w);
        }
        System.out.println(groups);

        System.out.println(count.putIfAbsent("be", 100) + " " + count.putIfAbsent("new", 100));
        count.computeIfPresent("or", (k, v) -> null);   // returning null removes the entry
        System.out.println(count);

        for (Map.Entry<String, Integer> e : count.entrySet()) {
            if (e.getValue() > 1) System.out.print(e.getKey() + " ");
        }
        System.out.println();
    }
}

Output

{be=2, not=1, or=1, to=2}
0
{a=[apple, avocado], b=[banana]}
2 null
{be=2, new=100, not=1, to=2}
be new to

Method	Does
`getOrDefault(k, d)`	Value, or `d` if absent
`putIfAbsent(k, v)`	Put only if absent; returns the existing value (or `null`)
`computeIfAbsent(k, fn)`	Create the value lazily — perfect for multimaps `Map<K, List<V>>`
`computeIfPresent(k, fn)`	Update an existing value; `null` result removes it
`merge(k, v, fn)`	Put `v`, or combine with the old value — counters: `merge(k, 1, Integer::sum)`
`entrySet()`	Iterate keys and values together — cheaper than `keySet()` + `get`

Trap: mutating a key

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<List<Integer>, String> map = new HashMap<>();
        List<Integer> key = new ArrayList<>(List.of(1, 2));
        map.put(key, "found");
        key.add(3);                                  // hashCode of the key changes
        System.out.println(map.get(key));            // looks in the wrong bucket
        System.out.println(map.get(List.of(1, 2)));  // right bucket, but equals fails
        System.out.println(map.size());              // the entry is stuck in the map
    }
}

Output

null
null
1

`equals` / `hashCode` contract

If a.equals(b) then a.hashCode() == b.hashCode() — required. Break it and lookups miss.
Equal hash codes do not imply equals (collisions are legal, just slower).
Override both or neither. hashCode must be stable while the object is used as a key.

What happens on a hash collision in HashMap?

Why is HashMap capacity always a power of two?

HashMap vs Hashtable vs ConcurrentHashMap?

What is the time complexity of HashMap get?

How put(k, v) works

Seeing the bucket index

The modern Map API

Trap: mutating a key

equals / hashCode contract

How `put(k, v)` works

`equals` / `hashCode` contract