HashMap

Вы сдаёте пальто в гардероб и получаете номерок. Номерок — это ключ, а пальто — значение, которое по нему выдают. По номерку гардеробщик вернёт ваше пальто, а не чьё-то другое.

В Java такой гардероб — словарь Map: коллекция пар «ключ — значение», в которой значение находят по ключу. Чаще всего берут класс HashMap:

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Anna", 30);
        ages.put("Boris", 25);
        ages.put("Anna", 31);
        System.out.println(ages.get("Anna")); // 31
        System.out.println(ages.size());      // 2
        System.out.println(ages.get("Vera")); // null
    }
}

Давайте разберём программу по строкам:

1. У Map<String, Integer> два параметра типа: тип ключа String и тип значения Integer.
2. put("Anna", 30) кладёт пару: ключ "Anna", значение 30.
3. Второй put с ключом "Anna" не добавляет новую пару, а заменяет значение: было 30, стало 31.
4. get("Anna") возвращает значение по ключу — 31.
5. ages.size() возвращает 2: каждый ключ хранится один раз.
6. get("Vera") возвращает null: такого ключа в словаре нет.

Ключи в словаре не повторяются, а значения могут: у Анны и Бориса может оказаться один возраст.

getOrDefault и containsKey

Классическая задача — посчитать, сколько раз встречается каждое слово. Ключом будет слово, значением — счётчик:

String[] words = {"to", "be", "or", "not", "to", "be"};
Map<String, Integer> counts = new HashMap<>();
for (String w : words) {
    counts.put(w, counts.getOrDefault(w, 0) + 1);
}
System.out.println(counts.get("to"));         // 2
System.out.println(counts.get("not"));        // 1
System.out.println(counts.containsKey("hi")); // false

Разберём, как это работает:

1. counts.getOrDefault(w, 0) возвращает значение по ключу w, а если ключа нет — 0.
2. put записывает счётчик на единицу больше. Новое слово получает 1, а "to" при второй встрече — 2.
3. containsKey("hi") проверяет, есть ли ключ, и отвечает false.

Весь словарь тоже можно напечатать: System.out.println(counts) выводит пары «ключ=значение» в фигурных скобках, например {not=1, be=2, or=1, to=2}. Порядок пар не гарантирован, а пустой словарь печатается как {}.

Как HashMap хранит пары

Как устроен HashMap — один из самых частых вопросов на собеседовании по Java. Ответ вы отчасти уже знаете: HashSet из прошлого урока хранит свои элементы как ключи HashMap. Внутри словаря — массив корзин, это крючки нашего гардероба. Вот как HashMap с ними работает:

1. hashCode ключа превращается в номер корзины: от 0 до числа корзин минус один.
2. Если в корзине уже есть пары, новая встаёт в конец цепочки. get идёт по цепочке одной корзины: сравнивает хеш-коды, а равный ключ подтверждает equals.
3. Когда пар становится больше трёх четвертей от числа корзин, таблица удваивается и раскладывает пары заново.

Словарь new HashMap<>() получает 16 корзин при первом put и растёт, когда пар становится больше 12. В виджете таблица меньше, new HashMap<>(4), поэтому порог — 3 пары. Ключи cat, dog, owl, fox и bee получают значения от 1 до 5, а потом get("owl") ищет сову. Следите за корзиной 1: туда попадут два ключа. А на четвёртом put таблица вырастет до 8 корзин.

Разберём, что произошло:

1. Первый put создал таблицу на 4 корзины, и ключ cat попал в корзину 3.
2. У dog и owl хеш-коды разные, но номер корзины один — 1. Их пары встали в цепочку друг за другом.
3. Пара с ключом fox стала четвёртой при пороге 3, и таблица выросла до 8 корзин. Пары разложились заново: dog и owl переехали в корзину 5, fox — в 6, cat — в 7.
4. Ключ bee попал в свободную корзину 3.
5. get("owl") пошёл сразу в корзину 5. У dog хеш-код другой, и equals не понадобился. У owl хеш-код совпал, equals подтвердил ключ, и get вернул 3.

Поэтому get и put быстрые: они смотрят одну корзину, а не все пары. И поэтому у HashMap нет порядка: пары лежат не в порядке добавления, а после роста таблицы перемещаются.

Здесь картинка с гардеробом неточна. Гардеробщик не перевешивает пальто, когда открывает второй зал. А HashMap при росте перекладывает все пары, и номер корзины у ключа может смениться.

Частая ошибка

Результат get положили в int:

int n = counts.get("hi"); // ✗

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

Ключа "hi" нет, и get вернул null. За присваиванием в int прячется распаковка из темы об обёртках — вызов intValue(), а у null его не вызвать. Если нужно число, берите getOrDefault("hi", 0), а наличие ключа проверяйте через containsKey.

Главное

• HashMap хранит пары «ключ — значение»: put кладёт пару, а с уже известным ключом заменяет значение; get для отсутствующего ключа возвращает null.
• getOrDefault даёт значение по умолчанию, а containsKey проверяет, есть ли ключ.
• hashCode ключа выбирает корзину, а в цепочке корзины ключ находят по хеш-коду и equals.
• Когда пар больше трёх четвертей от числа корзин, таблица удваивается и пары раскладываются заново, поэтому порядка у HashMap нет.