0Pricing
Java Academy · Lesson

Treeification and Performance

How Java 8+ handles collisions.

Treeification and Performance is a free Java Academy lesson on CoddyKit — lesson 4 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.

The Collision Problem

Before Java 8, a bucket with many collisions became a long linked list. Lookup in that bucket degraded to O(n).

An attacker could exploit this with crafted keys to cause a denial of service, all hashing to one bucket.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Java 8 Treeification

Java 8 added treeification. When a single bucket holds too many entries, the linked list converts into a balanced red-black tree.

Lookup in that bucket then becomes O(log n) instead of O(n).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

The Threshold: TREEIFY_THRESHOLD

The constant TREEIFY_THRESHOLD is 8. A bucket converts to a tree when it reaches 8 entries.

But there is a second condition: the table must also be at least MIN_TREEIFY_CAPACITY (64) in size, otherwise the map resizes instead.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Resize First, Treeify Later

If a bucket overflows but the table is still small (under 64), HashMap resizes the table first.

Resizing usually redistributes the entries and removes the hot spot, so treeification is only the last resort for genuinely bad hash distributions.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Untreeification

Trees are not permanent. If removals shrink a bucket below UNTREEIFY_THRESHOLD (6), the tree reverts to a linked list.

The gap between 8 (treeify) and 6 (untreeify) avoids thrashing back and forth at the boundary.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

Trees Need Comparable or Identity Order

A red-black tree must order its entries. HashMap first compares hash codes; ties are broken by Comparable if the keys implement it, otherwise by a stable tie-break on class names and identity.

Keys that are Comparable (like String or Integer) give the cleanest tree ordering.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Practical Impact

For most real programs with decent hash codes, you will never see treeification. Buckets stay short.

Treeification is a safety net that bounds worst-case lookup at O(log n) even when hashing is poor or adversarial.

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("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

A Constant hashCode Forces Trees

If you deliberately return a constant hashCode, every key lands in one bucket. With 64+ capacity, that bucket treeifies.

This demonstrates the safety net, but it is a design smell. Fix the hashCode instead.

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

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Memory Cost of Trees

Tree nodes are larger than plain linked-list nodes because they store parent, left, right, and color references.

This is another reason treeification is a fallback, not the default: trees trade memory for worst-case speed.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

How to Avoid Treeification

You almost never want to rely on treeification. Avoid it by:

  • Writing a well-distributed hashCode().
  • Using built-in types or records as keys.
  • Pre-sizing the map to reduce collisions.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Performance Summary

HashMap operation costs:

  • Good hash: O(1) average.
  • Linked bucket: O(n) per bucket worst case.
  • Treeified bucket: O(log n) per bucket.

Treeification bounds the worst case, but a good hashCode keeps you in O(1) land.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Quick Check

Test your treeification knowledge.

Recap

You learned how modern HashMap handles collisions:

  • Buckets treeify at 8 entries when capacity is at least 64.
  • Trees give O(log n) worst-case lookup.
  • Buckets untreeify below 6 entries.
  • A good hashCode means you rarely trigger this safety net.

You have completed the HashMap internals course.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Frequently asked questions

Is the “Treeification and Performance” lesson free?

Yes — the full text of “Treeification and Performance” 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 “Treeification and Performance”?

How Java 8+ handles 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 4 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Treeification and Performance” 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

  1. How HashMap Works
  2. The equals/hashCode Contract
  3. Implementing hashCode
  4. Treeification and Performance
← Back to Java Academy