Философия Java

Фактор производительности HashMap


Для понимания проблемы необходима следующая терминология:

Емкость: Число ковшей в таблице.

Начальная емкость: Число ковшей при создании таблицы. HashMap и HashSet имеют конструкторы, который позволяют вам указать начальную емкость.

Размер: Число вхождений, имеющихся в таблице на данный момент.

Коэффициент загрузки: размер/емкость. Коэффициент загрузки пустой таблицы равен 0, для заполненной на половину равен 0,5, и т.д. мало заполненная таблица будет иметь мало коллизий, что оптимально для вставки и поиска (но это замедляет процесс обхода с помощью итератора). HashMap и HashSet имеют конструкторы, которые позволяют указать коэффициент загрузки, который означает, что когда коэффициент загрузки будет достигнут, контейнер автоматически увеличит емкость (число ковшей) грубым удвоением и перераспределит существующие объекты в новый набор ковшей (это называется повторным хешированием).

Коэффициент загрузки по умолчанию, используемый для HashMap, равен 0.75 (это означает отсутствие повторного хеширования, пока таблица не заполнена на ?). Это кажется хорошим соглашением между временем и затратами места. Больший коэффициент загрузки уменьшает требуемое место для таблицы, но увеличивает стоимость поиска, который важен, поскольку поиск - это то, что вы делаете большую часть времени (включая и get( ), и put( )).

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



Содержание раздела