Michael Medvedskiy 20 марта 2024

☕ Хеш-таблицы в Java: секреты производительности

Посмотрим на проблемы, которые возникают при имплементации хеш-таблицы, когда сложность добавления или удаления из нее не O(1), а линейная, и какие потенциальные атаки можно провести на эту структуру данных (и как их избегают в современных языках программирования на примере Java).
☕ Хеш-таблицы в Java: секреты производительности

Всем привет! Меня зовут Миша Рокс, я – разработчик в Яндексе, и сегодня мы глубже погрузимся в одну из основных и базовых структур данных любого языка – хеш-таблицу. Конкретно – мы посмотрим на проблемы, которые возникают при имплементации этой структуры данных, когда сложность добавления или удаления из нее не O(1), а линейная, и какие потенциальные атаки можно провести на эту структуру данных (и как их избегают в современных языках программирования на примере Java).

Как работает хеш-таблица

В общем идейном случае, хеш-таблица – это 2D-структура данных. Ее можно представить как List<List<X>>, где X – это ваш тип данных. Внешний List – изначально фиксированной длины, и раздувается, и сужается в зависимости от условия, привязанного к общему количеству элементов во всей хеш-таблице (схоже с тем, как динамический массив увеличивается и уменьшается в размере в зависимости от количества элементов в нём).

Внешний List состоит из Внутренних List-ов, которые называются «Бакетами» (вёдрами по-русски :D), и каждый из бакетов – это просто коллекция типа X, например, список.

Когда вы вызываете .add(x) на хеш-таблице, внутренности имплементации считают hashcode от переданного x (а в случае Джавы – это происходит с помощью дёрганья метода .hashcode на объекте, поэтому и рекомендуют этот метод переопределять), относительно этого хешкода будет выбран конкретный бакет, и переданный элемент x будет добавлен в этот бакет (если бакеты – листы, то просто будет .add в конец листа).

Далее, когда вы хотите найти элемент в хеш-таблице, вы делаете .get(x) (или contains, или containsKey, т. д.), и хеш-таблица берет хешкод от x, определяет бакет, в котором этот элемент будет искать (т. к. когда элемент клали, бакет определялся по хешкоду, и требуемое свойство хеш-функции – это что для одного и того же x хешкод должен быть одним и тем же), и после получения бакета, ищет этот элемент в нём (в случае бакета – динамического массива – просто проходится по всем элементам и делает .equals. И поэтому в Джаве советуют переопределять .equals – потому что дефолтная имплементация .equals сравнивает объекты через == (то есть по значению ссылки), и два объекта с равными полями но разными ссылками не будут ==).

В этом алгоритме возникает понятная проблема – если:

  1. Кол-во бакетов изначально задано константно (назовем это число C)
  2. При добавлении 1.000.000.000 элементов, в лучшем случае максимальное количество элементов в каждом массиве будет 1.000.000.000 / C – если все элементы равномерно распределены по C бакетам, а в худшем – вообще все элементы попадут в один бакет, и там будет 1.000.000.000 элементов!
  3. При поиске элемента в таких бакетах, worst-case сценарий в первом случае будет 1.000.000.000 / C операций, а во втором – вообще 1.000.000.000 операций! Это совсем не константная сложность, она прямо растёт с кол-вом элементов во всей хеш-таблице!

Но нам надо как-то гарантировать, что сложность будет константной (или хотя бы максимально приблизиться к таким гарантиям, потому что сейчас у нас Time Complexity гарантировано линейная). Этого можно достичь, расширяя внешний List – то есть, увеличивая количество бакетов.

***
«Библиотека джависта»
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека джависта»
🎓☕ «Библиотека Java для собеса»
Подтянуть свои знания по Java вы можете на нашем телеграм-канале «Библиотека Java для собеса»
🧩☕ «Библиотека задач по Java»
Интересные задачи по Java для практики можно найти на нашем телеграм-канале «Библиотека задач по Java»
***

Пусть изначально C == 10, тогда самый простой алгоритм (который не используется на практике, но имеет право на жизнь) – это увеличивать количество бакетов в 2 раза каждый раз, когда суммарное количество элементов во всей хеш-таблице достигнет C * K, где К – это тоже некая константа. При наличии «хорошей хеш-функции», которая условно говоря равномерно распределит значения .hashcode % C между всеми значениями [0; C-1], то в каждом бакете, ожидается, будет приблизительно K элементов.

Важный аспект – когда происходит увеличение количества бакетов с 10 до 20 (в этом примере мы делаем x2 бакетов), мы не можем просто оставить уже ныне имеющиеся элементы в бакетах [0, 9], потому что до «расширения» у каждого из элементов бакет определялся по функции hashcode % 10 (т. к. хешкод – это обычно значение, не ограниченное сверху, то оно может быть много больше 10, например, у какого-то из объектов функция могла быть 2523542345 % 10), а теперь C стало равно 20, и для тех же объектов значения hashcode % 10 не будут равны значениям hashcode % 20. То есть все элементы, которые уже есть во всей хеш-таблице, надо «перелить» из внешнего List-а размером 10 во внешний List размером 20.

Так как добавление одного элемента – это подсчёт хеш-кода (const Time Complexity) + добавление в бакет (если бакеты – листы – const Time Complexity), и элементов в хеш-таблице N, то вся операция «перелива» – это (const + const) * N, то есть – линейная Time Complexity относительно общего количества элементов в хеш-таблице. При добавлении еще x2 элементов в хеш-таблицу, ее еще раз надо будет раздувать, но если посмотреть на суммарное количество операций, требующихся на добавление элементов + раздувание при M-раздуваниях, будет видно, что общее количество операций = const * N, где N – это общее количество элементов в хеш-таблице, и в среднем на одно добавление требуется const операций. «Среднее количество операций over N runs» – называется Амортизационным анализом. То есть добавление в хеш-таблицу – это const Time Complexity по Амортизационному Анализу, но O(N) по ассимптотическому worst-case scenario анализу, потому что в худшем случае надо перелить N элементов.

Соответственно, если мы удаляем элементы из хеш-таблицы, надо ее обратно сдуть, например, с 20 до 10, если количество элементов стало намного меньше C * K, чтобы более оптимально использовать место внешнего List-а. Но вы уже видите проблему с этим подходом в случае нашего x2 алгоритма?) Можно найти такой «граничный» элемент, добавляя который хеш-таблица будет раздуваться, а убирая который – будет сдуваться, и каждый такой .add и .remove будет O(N) операцией, и если в хеш-таблице уже 1.000.000.000 элементов, это очень сильно ударит по перформансу программы.

Бороться с этим можно несколькими путями, один из них – делать разные «граничные числа сдувания и раздувания» так, чтобы между числом сдувания (меньшим числом) и числом раздувания для нынешнего размера внешнего Листа N, было (С / const) элементов, например, если у нас сейчас 400 бакетов в хеш-таблице (С == 400), K == 10, то есть Total элементов в хеш-таблице == 4000, чтобы граница раздутия была при 4200, а сдутия – при 3800. Когда бакетов будет 800, пусть граница раздутия будет при 8400, а сдутия – 7600, тогда худший вариант – за C операций добавления / удаления будет выполняться N * const суммарное количество операций, тогда каждая операция будет в среднем стоить K действий, а K == const, как вы помните.

Другой способ бороться с этим – это то, как сделано в дефолтных имплементациях хеш-таблиц в Java – это просто не сдувать внешний List вообще никогда. То есть если вы заполните HashSet 1.000.000.000 элементов в Java, а потом удалите все элементы, у вас останется огромный внешний List, без элементов во внутренних листах (вместо листов будут null, но внешний List будет огромным)

Хеш-таблица до и после
Хеш-таблица до и после

Вот так вот, люди, Оверрайдить equals и hashcode не обязательно, но если собираетесь класть ваш объект в структуру, использующую хеш, то это нужно, чтобы вы свой объект вообще могли из нее достать потом))

Лайк, шер, сабскрайб)

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Senior Java Developer
Москва, по итогам собеседования
Java Team Lead
Москва, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ