В 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:

  1. Хэширование: когда к HashMap добавляется пара ключ-значение, хеш-код ключа вычисляется с использованием метода hashCode() ключа. Полученный хэш-код используется для определения индекса в базовом массиве, где должна храниться пара ключ-значение.
  2. Массив сегментов: HashMap использует массив связанных списков (известных как сегменты) для обработки коллизий. Каждое ведро представляет собой слот в массиве, где можно хранить несколько пар ключ-значение. Если несколько пар ключ-значение имеют одинаковый хэш-код, они сохраняются в одном сегменте.
  3. Вычисление индекса: рассчитанный хэш-код преобразуется в допустимый индекс в пределах диапазона массива сегментов путем применения побитовой операции И с маской, которая обычно определяется как hash & (capacity - 1). Емкость массива сегментов обычно равна степени двойки для оптимизации расчета индекса.
  4. Обработка конфликтов: если две или более пар ключ-значение имеют одинаковый индекс (из-за конфликтов хэш-кода), они сохраняются как узлы в связанном списке в соответствующем сегменте. Каждый узел в связанном списке содержит ключ, значение и ссылку на следующий узел в списке.
  5. Операция размещения: когда пара ключ-значение добавляется к HashMap с помощью метода put(key, value), хэш-код ключа используется для вычисления индекса. Если индекс пуст, создается новый узел и добавляется в корзину. Если в ведре есть существующие узлы, выполняется поиск, чтобы проверить, существует ли уже ключ. Если ключ существует, существующее значение обновляется. Если ключ не существует, в начало связанного списка добавляется новый узел.
  6. Операция получения: при извлечении значения из HashMap с использованием метода get(key) для вычисления индекса используется хеш-код ключа. Связанный список в корзине по этому индексу затем последовательно просматривается, чтобы найти узел с совпадающим ключом. Если найдено, возвращается соответствующее значение. Если он не найден, возвращается null, чтобы указать, что ключ отсутствует в HashMap.
  7. Изменение размера: по мере увеличения количества пар ключ-значение, хранящихся в HashMap, может возникнуть необходимость изменить размер базового массива сегментов для поддержания эффективной производительности. Когда коэффициент загрузки (отношение количества пар ключ-значение к емкости) превышает определенный порог, размер HashMap изменяется путем создания нового массива большего размера и повторного хэширования всех существующих пар ключ-значение в новый массив.

Как хэш-функция определяет индекс в HashMap:

Допустим, у нас есть HashMap с начальной емкостью 8, и мы хотим добавить пару ключ-значение, где ключ — «яблоко», а значение — 5.

  1. Хеширование ключа: хеш-код ключа «яблоко» вычисляется с использованием метода hashCode(). Предположим, он возвращает значение 970785.
  2. Вычисление индекса: затем хеш-код преобразуется в действительный индекс в пределах диапазона массива. В данном случае емкость равна 8, поэтому мы выполняем операцию побитового И с маской (7 в двоичном формате: 00000111): 970785 & 7. В результате получается 1 (00000001), то есть индекс, в котором должна храниться пара ключ-значение в файле HashMap.
  3. Вставка: поскольку индекс 1 в массиве пуст, пара ключ-значение («яблоко», 5) вставляется по этому индексу. Теперь массив выглядит так:
  4. Индекс 0: Пусто Индекс 1: («яблоко», 5) Индекс 2: Пусто … Индекс 7: Пусто

Если мы добавим еще одну пару ключ-значение с ключом «банан» и значением 8, процесс будет аналогичен:

  1. Хэширование ключа: вычисляется хэш-код ключа «банан». Предположим, он возвращает значение 831527.
  2. Вычисление индекса: мы выполняем побитовую операцию И с маской (7 в двоичном формате: 00000111): 831527 & 7. Результат равен 7 (00000111), что является индексом, в котором должна храниться пара ключ-значение.
  3. Обработка конфликтов: индекс 7 не пуст, потому что там уже хранится пара ключ-значение («яблоко», 5). Это столкновение. HashMap использует отдельную цепочку для обработки коллизий, поэтому связанный список создается в индексе 7 для хранения нескольких записей.
  4. Индекс 0: Пусто Индекс 1: («яблоко», 5) Индекс 2: Пусто… Индекс 7: («банан», 8) -> («яблоко», 5)

Связанный список в индексе 7 теперь содержит две записи, причем последняя добавленная запись находится в начале списка.

Что произойдет, если мы дважды вставим один и тот же ключ с разными значениями в HashMap'?

  1. Хеширование и расчет индекса: будет рассчитан хэш-код ключа, и индекс в массиве HashMap, где должна храниться пара ключ-значение, будет определен с использованием хэш-кода и процесса расчета индекса.
  2. Обработка коллизий: если в вычисляемом индексе уже есть запись, указывающая на коллизию, HashMap проверит, имеет ли какая-либо существующая запись в этом сегменте тот же ключ, что и вставляемый. Эта проверка выполняется путем сравнения ключей методом equals().
  • Если ключ уже существует в HashMap, существующее значение, связанное с этим ключом, будет обновлено до нового значения. Ключ остается прежним, но значение заменяется.
  • Если ключ не существует в HashMap, в корзину будет добавлена ​​новая запись, создающая связанный список записей для этого индекса. Новая пара ключ-значение будет добавлена ​​в начало связанного списка.