0Pricing
Java Academy · Урок

Преобразование в дерево и производительность

Как Java 8+ обрабатывает коллизии

«Преобразование в дерево и производительность» — бесплатный урок Java Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Проблема коллизий

До Java 8 корзина с большим количеством коллизий превращалась в длинный связный список. Поиск в такой корзине замедлялся до O(n).

Злоумышленник мог использовать это, создавая специально подобранные ключи и вызывая отказ в обслуживании, при котором все ключи хешировались в одну корзину.

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

В Java 8 было добавлено преобразование в дерево. Когда в одной корзине оказывается слишком много записей, связный список преобразуется в сбалансированное красно-чёрное дерево.

После этого поиск в корзине выполняется за O(log n), а не за 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));
    }
}

Порог: TREEIFY_THRESHOLD

Константа TREEIFY_THRESHOLD равна 8. Корзина преобразуется в дерево, когда в ней становится 8 записей.

Но есть и второе условие: размер таблицы должен быть не меньше MIN_TREEIFY_CAPACITY (64), иначе вместо этого map изменяет размер.

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

Сначала изменение размера, затем преобразование в дерево

Если корзина переполняется, но таблица всё ещё мала (меньше 64), HashMap сначала изменяет размер таблицы.

Изменение размера обычно перераспределяет записи и устраняет очаг концентрации, поэтому преобразование в дерево используется только как крайняя мера при действительно плохом распределении хешей.

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

Обратное преобразование в список

Деревья не являются постоянными. Если после удалений в корзине останется меньше элементов, чем указано в UNTREEIFY_THRESHOLD (6), дерево снова преобразуется в связный список.

Разрыв между значениями 8 (преобразование в дерево) и 6 (обратное преобразование в список) предотвращает постоянное переключение на границе.

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

Деревьям нужен порядок сравнения или идентичности

Красно-чёрное дерево должно упорядочивать свои записи. Сначала HashMap сравнивает хеш-коды; при их совпадении используется Comparable, если ключи его реализуют, а иначе применяется стабильное разрешение равенства по именам классов и идентичности.

Ключи, являющиеся Comparable (например, String или целочисленный тип), обеспечивают наиболее аккуратный порядок в дереве.

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

Практические последствия

В большинстве реальных программ с хорошими хеш-кодами Вы никогда не увидите преобразования в дерево. Корзины остаются короткими.

Преобразование в дерево — это защитный механизм, ограничивающий время поиска в худшем случае значением O(log n), даже если хеширование плохое или выполняется с целью атаки.

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 вынуждает создавать деревья

Если намеренно возвращать постоянный hashCode, каждый ключ попадёт в одну корзину. При вместимости 64 и более эта корзина преобразуется в дерево.

Это демонстрирует защитный механизм, но является признаком неудачного проектирования. Вместо этого исправьте 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");
    }
}

Как избежать преобразования в дерево

Почти никогда не следует полагаться на преобразование в дерево. Избегайте его следующим образом:

  • Пишите хорошо распределённый hashCode().
  • Используйте встроенные типы или записи в качестве ключей.
  • Заранее задавайте размер map, чтобы уменьшить количество коллизий.
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)));
    }
}

Итоги производительности

Затраты на операции HashMap:

  • Хороший хеш: в среднем O(1).
  • Связная корзина: в худшем случае O(n) для одной корзины.
  • Корзина, преобразованная в дерево: O(log n) для одной корзины.

Преобразование в дерево ограничивает время работы в худшем случае, но хороший hashCode позволяет сохранять сложность O(1).

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

Быстрая проверка

Проверьте свои знания о преобразовании в дерево.

Итоги

Вы узнали, как современный HashMap обрабатывает коллизии:

  • Корзины преобразуются в деревья при наличии 8 записей, если вместимость составляет не менее 64.
  • Деревья обеспечивают поиск в худшем случае за O(log n).
  • Корзины снова преобразуются в списки, если в них меньше 6 записей.
  • Хороший hashCode означает, что этот защитный механизм срабатывает редко.

Вы завершили курс по внутреннему устройству HashMap.

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

Часто задаваемые вопросы

Урок «Преобразование в дерево и производительность» бесплатный?

Да — полный текст урока «Преобразование в дерево и производительность» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Преобразование в дерево и производительность»?

Как Java 8+ обрабатывает коллизии Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Преобразование в дерево и производительность»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Как работает HashMap
  2. Контракт equals/hashCode
  3. Реализация hashCode
  4. Преобразование в дерево и производительность
← Назад к Java Academy