В Java класс HashMap
реализован в виде хэш-таблицы, которая представляет собой структуру данных, позволяющую эффективно вставлять, удалять и извлекать пары ключ-значение. Он является частью Java Collections Framework и находится в пакете java.util
.
Вот пример, демонстрирующий основные операции HashMap
в Java:
import java.util.HashMap; public class HashMapExample { public static void main(String[] args) { // Create a new HashMap HashMap<String, Integer> hashMap = new HashMap<>(); // Adding key-value pairs hashMap.put("apple", 5); hashMap.put("banana", 8); hashMap.put("orange", 3); hashMap.put("grape", 10); // Accessing values System.out.println("Value of apple: " + hashMap.get("apple")); // Output: Value of apple: 5 // Updating values hashMap.put("apple", 7); // Checking if a key exists System.out.println("Contains key 'banana': " + hashMap.containsKey("banana")); // Output: Contains key 'banana': true System.out.println("Contains key 'mango': " + hashMap.containsKey("mango")); // Output: Contains key 'mango': false // Removing a key-value pair hashMap.remove("orange"); // Size of the HashMap System.out.println("Size of the HashMap: " + hashMap.size()); // Output: Size of the HashMap: 3 // Iterating over key-value pairs for (String key : hashMap.keySet()) { int value = hashMap.get(key); System.out.println(key + ": " + value); } /* Output: grape: 10 apple: 7 banana: 8 */ // Clearing the HashMap hashMap.clear(); System.out.println("After clearing the HashMap: " + hashMap); // Output: After clearing the HashMap: {} } }
Вот ключевые компоненты HashMap
:
- Массив:
HashMap
использует массив для хранения своих элементов. Массив разделен на сегменты, и каждый сегмент может содержать несколько пар ключ-значение. Размер массива определяется начальной емкостью, установленной при созданииHashMap
. - Запись:
Entry
— это внутренний класс вHashMap
, представляющий пару ключ-значение. Каждая запись содержит ключ, значение и ссылку на следующую запись в случае коллизий. - Хеширование:
HashMap
использует хеш-код ключа для определения индекса в массиве, где должна храниться запись. Хэш-код получается путем вызова методаhashCode()
для ключевого объекта. - Вычисление индекса: хэш-код преобразуется в действительный индекс в пределах диапазона массива с использованием побитовой операции И с маской. Маска обычно определяется как
hash & (capacity - 1)
, где емкость — это размер массива. - Обработка коллизий: в случае коллизий хэш-кода, когда два или более ключа создают один и тот же индекс,
HashMap
использует отдельную цепочку для обработки коллизий. Отдельная цепочка означает, что каждая корзина содержит связанный список записей. Новые записи с тем же индексом добавляются в связанный список. - Коэффициент загрузки: Коэффициент загрузки — это параметр, который определяет, когда
HashMap
должен изменять размер своего базового массива. Это показатель того, насколько заполненHashMap
. Когда количество пар ключ-значение превышает коэффициент загрузки, умноженный на текущую емкость, размерHashMap
изменяется для поддержания производительности. - Хэш-функция:
HashMap
использует хэш-функцию для преобразования хэш-кода в действительный индекс. Хеш-функция отвечает за равномерное распределение ключей по массиву, снижение вероятности коллизий и обеспечение эффективного поиска.
Общий обзор того, как HashMap
реализован в Java:
- Хэширование: когда к
HashMap
добавляется пара ключ-значение, хеш-код ключа вычисляется с использованием методаhashCode()
ключа. Полученный хэш-код используется для определения индекса в базовом массиве, где должна храниться пара ключ-значение. - Массив сегментов:
HashMap
использует массив связанных списков (известных как сегменты) для обработки коллизий. Каждое ведро представляет собой слот в массиве, где можно хранить несколько пар ключ-значение. Если несколько пар ключ-значение имеют одинаковый хэш-код, они сохраняются в одном сегменте. - Вычисление индекса: рассчитанный хэш-код преобразуется в допустимый индекс в пределах диапазона массива сегментов путем применения побитовой операции И с маской, которая обычно определяется как
hash & (capacity - 1)
. Емкость массива сегментов обычно равна степени двойки для оптимизации расчета индекса. - Обработка конфликтов: если две или более пар ключ-значение имеют одинаковый индекс (из-за конфликтов хэш-кода), они сохраняются как узлы в связанном списке в соответствующем сегменте. Каждый узел в связанном списке содержит ключ, значение и ссылку на следующий узел в списке.
- Операция размещения: когда пара ключ-значение добавляется к
HashMap
с помощью методаput(key, value)
, хэш-код ключа используется для вычисления индекса. Если индекс пуст, создается новый узел и добавляется в корзину. Если в ведре есть существующие узлы, выполняется поиск, чтобы проверить, существует ли уже ключ. Если ключ существует, существующее значение обновляется. Если ключ не существует, в начало связанного списка добавляется новый узел. - Операция получения: при извлечении значения из
HashMap
с использованием методаget(key)
для вычисления индекса используется хеш-код ключа. Связанный список в корзине по этому индексу затем последовательно просматривается, чтобы найти узел с совпадающим ключом. Если найдено, возвращается соответствующее значение. Если он не найден, возвращаетсяnull
, чтобы указать, что ключ отсутствует вHashMap
. - Изменение размера: по мере увеличения количества пар ключ-значение, хранящихся в
HashMap
, может возникнуть необходимость изменить размер базового массива сегментов для поддержания эффективной производительности. Когда коэффициент загрузки (отношение количества пар ключ-значение к емкости) превышает определенный порог, размерHashMap
изменяется путем создания нового массива большего размера и повторного хэширования всех существующих пар ключ-значение в новый массив.
Как хэш-функция определяет индекс в HashMap
:
Допустим, у нас есть HashMap
с начальной емкостью 8, и мы хотим добавить пару ключ-значение, где ключ — «яблоко», а значение — 5.
- Хеширование ключа: хеш-код ключа «яблоко» вычисляется с использованием метода
hashCode()
. Предположим, он возвращает значение 970785. - Вычисление индекса: затем хеш-код преобразуется в действительный индекс в пределах диапазона массива. В данном случае емкость равна 8, поэтому мы выполняем операцию побитового И с маской (7 в двоичном формате: 00000111):
970785 & 7
. В результате получается 1 (00000001), то есть индекс, в котором должна храниться пара ключ-значение в файлеHashMap
. - Вставка: поскольку индекс 1 в массиве пуст, пара ключ-значение («яблоко», 5) вставляется по этому индексу. Теперь массив выглядит так:
- Индекс 0: Пусто Индекс 1: («яблоко», 5) Индекс 2: Пусто … Индекс 7: Пусто
Если мы добавим еще одну пару ключ-значение с ключом «банан» и значением 8, процесс будет аналогичен:
- Хэширование ключа: вычисляется хэш-код ключа «банан». Предположим, он возвращает значение 831527.
- Вычисление индекса: мы выполняем побитовую операцию И с маской (7 в двоичном формате: 00000111):
831527 & 7
. Результат равен 7 (00000111), что является индексом, в котором должна храниться пара ключ-значение. - Обработка конфликтов: индекс 7 не пуст, потому что там уже хранится пара ключ-значение («яблоко», 5). Это столкновение.
HashMap
использует отдельную цепочку для обработки коллизий, поэтому связанный список создается в индексе 7 для хранения нескольких записей. - Индекс 0: Пусто Индекс 1: («яблоко», 5) Индекс 2: Пусто… Индекс 7: («банан», 8) -> («яблоко», 5)
Связанный список в индексе 7 теперь содержит две записи, причем последняя добавленная запись находится в начале списка.
Что произойдет, если мы дважды вставим один и тот же ключ с разными значениями в HashMap'
?
- Хеширование и расчет индекса: будет рассчитан хэш-код ключа, и индекс в массиве
HashMap
, где должна храниться пара ключ-значение, будет определен с использованием хэш-кода и процесса расчета индекса. - Обработка коллизий: если в вычисляемом индексе уже есть запись, указывающая на коллизию,
HashMap
проверит, имеет ли какая-либо существующая запись в этом сегменте тот же ключ, что и вставляемый. Эта проверка выполняется путем сравнения ключей методомequals()
.
- Если ключ уже существует в
HashMap
, существующее значение, связанное с этим ключом, будет обновлено до нового значения. Ключ остается прежним, но значение заменяется. - Если ключ не существует в
HashMap
, в корзину будет добавлена новая запись, создающая связанный список записей для этого индекса. Новая пара ключ-значение будет добавлена в начало связанного списка.