JEP 180: Handle Frequent HashMap Collisions with Balanced Trees

Аннотация

Улучшить производительность java.util.HashMap при большом числе коллизий хешей: хранить элементы отображения в сбалансированных деревьях, а не в связных списках. Реализовать такое же улучшение в классе LinkedHashMap.

Мотивация

Более ранняя работа в этой области в JDK 8, а именно альтернативная реализация хеширования строк, улучшила производительность при коллизиях только для ключей со строковыми значениями, причём ценой добавления нового (приватного) поля в каждый экземпляр String.

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

Описание

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

Этот приём уже реализован в последней версии класса java.util.concurrent.ConcurrentHashMap, включение которой в JDK 8 также запланировано в рамках JEP 155. Части этого кода будут повторно использованы, чтобы реализовать ту же идею в классах HashMap и LinkedHashMap. Изменятся только реализации; ни интерфейсы, ни спецификации изменены не будут. Некоторые видимые пользователю особенности поведения, например порядок итерации, изменятся в рамках их текущих спецификаций.

Мы не будем реализовывать этот приём в устаревшем классе Hashtable. Этот класс входит в платформу с Java 1.0, и известно, что часть унаследованного кода, который его использует, зависит от порядка итерации. Hashtable будет возвращён в состояние, в котором он был до появления альтернативной реализации хеширования строк, и сохранит свой исторический порядок итерации.

Мы также не будем реализовывать этот приём в WeakHashMap. Такая попытка была, но из-за сложности учёта слабых ключей производительность в микробенчмарках упала до неприемлемого уровня. WeakHashMap также будет возвращён в прежнее состояние.

Реализовывать этот приём в классе IdentityHashMap не нужно. Он использует System.identityHashCode() для генерации хеш-кодов, поэтому коллизии, как правило, редки.

Тестирование

• Запуск тестов Map из CVS-репозитория JSR 166 Дуга Ли (Doug Lea), включая пару микробенчмарков
• Запуск тестов производительности на стандартных рабочих нагрузках
• Возможно, разработка новых микробенчмарков

Риски и допущения

Это изменение добавит некоторые накладные расходы на добавление сбалансированных деревьев и управление ими; мы ожидаем, что эти расходы будут пренебрежимо малы.

Это изменение, скорее всего, приведёт к изменению порядка итерации класса HashMap. Спецификация HashMap явно не даёт никаких гарантий относительно порядка итерации. Порядок итерации класса LinkedHashMap будет сохранён.