HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени.HashMap представляет из себя массив ссылок на цепочки пар ключ/значение: Node
Структура HashMap
Ёмкость по умолчанию – 16.Помимо ёмкости HashMap имеет такой параметр как коэффициент загрузки (loadFactor), а также threshold - предельное количество элементов, при достижении которого размер хэш-таблицы увеличивается вдвое.
Значение по умолчанию loadFactor - 0,75. threshold рассчитывается по формуле capacity * loadFactor.
Добавление элементов:
1. Если значение ключа равно null, он записывается в первую ячейку поля table, выстраиваясь в цепочку, если там уже есть элемент с ключом null.
2. На основе key.hashCode() генерируется хэш.
3. В зависимости от полученного хэша и размера массива table определяется ячейка, в которую будет помещён элемент.
4. Если в этой ячейке уже располагается какая-то запись, то существует 2 варианта: если ключ совпадает, тогда следует заменить значение, если совпал хэшкод (произошла коллизия), тогда первым элементом этого массива устанавливается новая запись, у которой есть поле, ссылающееся на старую запись. Таким образом, в следующий раз для просмотра записей в этом элементе необходимо будет пройти связанный список ключ/значение.
Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Для каждого элемента рассчитывается новая ячейка, в которую он будет помещён.
У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет.
HashMap имеет встроенные итераторы: entrySet() - даёт доступ ко всем парам ключ/значение; keySet() - даёт доступ ко всем ключам; values() - даёт доступ ко всем значениям элементов. Если в ходе работы итератора объект HashMap был изменен без использования собственных методов итератора, можно получить непредсказуемый результат.
Лучшее время выполнения операций поиск/удаление HashMap показывает в том случае, если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Вставка всегда производится за константное время, т.к. новые элементы вставляются в начало цепочки.
HashMap не синхронизирован. Для синхронизации нужно использовать Collections.synchronizedMap().
Подробная статья о HashMap.
