Java Academy · Lesson

How HashMap Works

Buckets, hashing, and collisions.

How HashMap Works is a free Java Academy lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Java Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

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);
    }
}

Buckets in Action

Each bucket can hold more than one entry. When two keys map to the same bucket, that is a collision.

Collisions are normal and expected. HashMap handles them by chaining entries together in the bucket.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Collisions and Chaining

Before Java 8, all colliding entries lived in a singly linked list inside the bucket.

Lookup walks the list calling equals() until it finds the matching key.

Few collisions: still effectively O(1).
Many collisions in one bucket: degrades toward O(n) for that bucket.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Why FB and Ea Collide

The strings "FB" and "Ea" have the same hashCode() in Java. This is a classic collision example.

Even with identical hash codes, the map still keeps them separate because equals() distinguishes them inside the bucket.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Load Factor

The load factor controls how full the table gets before it grows. Default is 0.75.

Capacity 16 and load factor 0.75 means resize triggers at 12 entries.
A lower load factor wastes memory but reduces collisions.
A higher load factor saves memory but increases collisions.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Resizing the Table

When the entry count passes capacity * loadFactor, the table doubles in size.

Every existing entry is rehashed into the new, larger table. This is an expensive operation, so pre-sizing matters for large maps.

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

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Pre-sizing for Performance

If you know roughly how many entries you will store, give an initial capacity to avoid resize churn.

Rule of thumb: initial capacity = expectedSize / 0.75 + 1.

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

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Null Keys and Values

HashMap allows one null key and multiple null values.

The null key always goes to bucket 0 (its hash is treated as 0).
Use getOrDefault to avoid ambiguity between a missing key and a null value.

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

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

Iteration Order is Not Guaranteed

HashMap makes no promise about iteration order. Order depends on hash codes and bucket layout.

If you need predictable order, use LinkedHashMap (insertion order) or TreeMap (sorted order).

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

The get() Path Summarized

A lookup follows these steps:

Compute hashCode() and spread the bits.
Mask to find the bucket index.
Walk the bucket comparing keys with equals().
Return the matching value or null.

Good hashCode plus correct equals keeps every step fast.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Quick Check

Test your understanding of how HashMap finds a bucket.

Recap

You learned how HashMap works under the hood:

Keys are hashed and mapped to buckets.
Collisions are handled by chaining entries in a bucket.
The load factor (0.75) triggers doubling and rehashing.
Pre-sizing avoids costly resizes, and iteration order is not guaranteed.

Next, we will see why hashCode alone is not enough without a correct equals.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Frequently asked questions

Is the “How HashMap Works” lesson free?

Yes — the full text of “How HashMap Works” is free to read here on the web, and the Java Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Java Academy course, upgrade to CoddyKit PRO.

What will I learn in “How HashMap Works”?

Buckets, hashing, and collisions. You practise Java Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Java Academy?

No prior experience is required. Java Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “How HashMap Works” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Java Academy lesson?

Yes. Every Java Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to Java Academy