Что происходит при вставке пары ключ-значение в HashMap

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

1. Вычисление хэш-кода ключа:

   • Каждый ключ в HashMap должен быть уникальным. Для определения, куда поместить значение, HashMap использует хэш-функцию, которая преобразует ключ в хэш-код — целое число, представляющее ключ.

2. Определение индекса в массиве бакетов:

   • HashMap использует массив, называемый бакетами, для хранения данных. Индекс бакета определяется с помощью операции hashCode % (capacity - 1), где capacity — это текущий размер массива бакетов. Это позволяет равномерно распределять данные по массиву.

3. Проверка на наличие коллизий:

   • Коллизия возникает, когда два разных ключа имеют одинаковый хэш-код и, следовательно, попадают в один и тот же бакет. HashMap решает коллизии с помощью связных списков или сбалансированных деревьев (начиная с Java 8).

4. Добавление нового узла:

   • Если бакет пуст, создается новый узел, содержащий ключ, значение и ссылку на следующий узел (если он есть), и помещается в бакет.
   • Если бакет уже занят, HashMap проверяет, существует ли уже узел с таким же ключом. Если да, то значение обновляется. Если нет, новый узел добавляется в конец связного списка или в соответствующее место в дереве.

Пример кода:

import java.util.HashMap;
​
public class HashMapExample {
    public static void main(String[] args) {
        // Создаем новый объект HashMap
        HashMap<String, Integer> map = new HashMap<>();
​
        // Вставляем пару ключ-значение в HashMap
        map.put("apple", 1);
        // 1. Вычисляется хэш-код для ключа "apple".
        // 2. Определяется индекс бакета, куда будет помещена пара.
        // 3. Проверяется наличие коллизий в этом бакете.
        // 4. Если бакет пуст, создается новый узел и помещается в бакет.
        // 5. Если бакет занят, проверяется наличие узла с таким же ключом.
        // 6. Если узел с таким ключом найден, обновляется значение.
        // 7. Если узел с таким ключом не найден, новый узел добавляется в конец списка или в дерево.
​
        // Вставляем еще одну пару ключ-значение
        map.put("banana", 2);
        // Процесс аналогичен вставке первого элемента.
    }
}

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