Устройство java.util.HashMap. Часть 1.

Одним из важнейших классом в Java Collections Framework является java.util.HashMap. Этой структура данных и ее реализация заслуживает отдельного разговора. В данном посте я хочу разобрать назначение HashMap и некоторые его особенности без погружения в исходный код. В основном, это будет перевод javadocs к классу java.util.HashMap.

java.util.HashMap - это реализация интерфейса java.util.Map на основе хеш-таюлицы. Эта реализация поддерживает также null-значения в качестве значений, а также и в качестве ключей. Не дается никаких гарантий по поводу внутреннего порядка данных. Особенно, не гарантируется, что порядок членов коллекции будет все время один и тот же.

Данная реализация обеспечивает постоянное время выполнения для базовых операций - get и put, т.е. время порядка O(1). При этом делается предположение, что хеш-функция равномерно распределяет элементы по бакетам (buckets). Бакет - элемент хеш-таблицы, который содержит список данных, положенных в хеш-таблицу. Остаток от деления хеш-кода каждого из этих данных на размер хеш-таблицы (точнее, на количество бакетов) один и тот же.

Итерация по хеш-таблице пропорционально количеству бакетов + их размер. Поэтому, если важна производительность итерации, важно не делать количество бакетов (т.е. емкость хеш-таблицы) очень большим.

Каждый экземпляр класса java.util.HashMap имеет два параметра для настройки производительности - начальная емкость (initial capacity) и фактор загрузки (load factor). Емкость хеш-таблицы - это количество бакетов в ней, а начальная емкость - это то количество бакетов, с которым хеш-таблица создается. Фактор загрузки определяет, насколько должна быть заполнена хеш-таблица перед тем, как автоматически увеличить ее емкость.

По умолчанию, начальная емкость равна 16, а фактор загрузки = 0.75. Начальная емкость должна быть всегда степенью двойки. Если в конструктор передается начальная емкость, которая не является степенью двойки, то устанавливается не эта неправильная емкость, а ближайшая степень двойки, которая больше этого числа. Это все легко посмотреть по исходникам. Степень двойки для емкости хеш-таблица позволяет некоторые оптимизации, которые положительно влияют на производительность хеш-таблицы.

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

Если несколько потоков используют java.util.HashMap одновременно, и хотя бы один из них структурно модифицирует хеш-таблицу, то такое использование должно быть внешне синхронизированно. Структурная модификация - это модификация, которая добавляет или удаляет один или несколько мэппингов из хеш-таблицы. Простое изменение значения, ассоциированного с ключом, не является структурной модификацией.

Если нет внешнего объекта, по которому синхронизируется такое совместное использование хеш-таблицы, то следует "обернуть" ее следующим методом:

Map m = Collections.synchronizedMap(new HashMap(...));

Итераторы, которые возвращаются в таком случае, имеют поведение fail-fast: если хеш-таблица структурно модифицируется иным образом, кроме как через методы remove или add этого итератора, то итератор выкидывает ConcurrentModificationException.

Устройство java.util.HashMap. Часть 2.
Устройство java.util.HashMap. Часть 3.
Устройство java.util.HashMap. Часть 4.