Java Academy · Lesson

Treeification and Performance

How Java 8+ handles collisions.

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

All lessons in this course

← Back to Java Academy