تحويل الأشجار والأداء

مشكلة التصادم

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

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

الحد الفاصل: TREEIFY_THRESHOLD

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

غيّر الحجم أولًا، ثم حوّل إلى شجرة

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

التحويل من شجرة

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

تحتاج الأشجار إلى Comparable أو ترتيب الهوية

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

الأثر العملي

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

يفرض hashCode الثابت التحويل إلى أشجار

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

تكلفة الأشجار من الذاكرة

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

كيفية تجنّب التحويل إلى شجرة

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

ملخص الأداء

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

اختبار سريع

مراجعة

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