0Pricing
Java Academy · Урок

Как работает HashMap

Корзины, хеширование и коллизии

«Как работает HashMap» — бесплатный урок Java Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Что хранит HashMap

HashMap хранит пары ключ-значение и обеспечивает в среднем операции поиска, вставки и удаления сложности O(1).

Внутри он хранит массив, называемый таблицей. Каждый элемент этого массива называется корзиной.

  • Ключ определяет, в какую корзину попадёт запись.
  • Значение — это то, что вы получаете при поиске по ключу.
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("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Хеширование ключа

При вызове put(key, value) отображение вызывает key.hashCode(), чтобы получить значение типа int.

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

  • Итоговое число уменьшается с помощью hash & (table.length - 1), чтобы получить индекс корзины.
  • Длина таблицы всегда является степенью двойки, поэтому такая маска работает.
public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Работа корзин

В каждой корзине может находиться несколько записей. Когда два ключа отображаются в одну корзину, возникает коллизия.

Коллизии — это нормальное и ожидаемое явление. HashMap обрабатывает их, объединяя записи в цепочку внутри корзины.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Коллизии и цепочки

До Java 8 все записи с коллизиями хранились в односвязном списке внутри корзины.

При поиске список просматривается с вызовом equals(), пока не будет найден подходящий ключ.

  • При небольшом числе коллизий сложность по-прежнему фактически составляет O(1).
  • При большом числе коллизий в одной корзине она приближается к O(n) для этой корзины.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Почему FB и Ea дают коллизию

Строки "FB" и "Ea" имеют в Java одинаковый hashCode(). Это классический пример коллизии.

Даже при одинаковых хеш-кодах отображение хранит их отдельно, поскольку equals() различает их внутри корзины.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Коэффициент заполнения

Коэффициент заполнения определяет, насколько полной может стать таблица до увеличения её размера. Значение по умолчанию — 0.75.

  • При вместимости 16 и коэффициенте заполнения 0.75 изменение размера запускается после добавления 12 записей.
  • Меньший коэффициент заполнения расходует больше памяти, но уменьшает число коллизий.
  • Больший коэффициент заполнения экономит память, но увеличивает число коллизий.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Изменение размера таблицы

Когда количество записей превышает значение capacity * loadFactor, размер таблицы удваивается.

Каждая существующая запись повторно хешируется и помещается в новую, увеличенную таблицу. Это затратная операция, поэтому для больших отображений важно заранее задать размер.

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

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Предварительное задание размера для повышения производительности

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

Практическое правило: начальная вместимость = expectedSize / 0.75 + 1.

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

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Ключи и значения null

HashMap допускает один ключ null и несколько значений null.

  • Ключ null всегда попадает в корзину 0, поскольку его хеш считается равным 0.
  • Используйте getOrDefault, чтобы различать отсутствующий ключ и значение null.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

Порядок перебора не гарантируется

HashMap не гарантирует порядок перебора. Порядок зависит от хеш-кодов и расположения корзин.

Если нужен предсказуемый порядок, используйте LinkedHashMap (порядок вставки) или TreeMap (отсортированный порядок).

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Краткий обзор пути get()

Поиск выполняется в несколько шагов:

  • Вычисляется hashCode(), после чего его биты перемешиваются.
  • С помощью маски определяется индекс корзины.
  • Корзина просматривается, а ключи сравниваются с помощью equals().
  • Возвращается соответствующее значение или нулевое значение.

Хороший hashCode и корректный equals обеспечивают быстроту каждого шага.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Быстрая проверка

Проверьте, насколько хорошо Вы понимаете, как HashMap находит корзину.

Итоги

Вы узнали, как HashMap работает внутри:

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

Далее Вы узнаете, почему одного hashCode недостаточно без корректного equals.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Часто задаваемые вопросы

Урок «Как работает HashMap» бесплатный?

Да — полный текст урока «Как работает HashMap» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Как работает HashMap»?

Корзины, хеширование и коллизии Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Как работает HashMap»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Как работает HashMap
  2. Контракт equals/hashCode
  3. Реализация hashCode
  4. Преобразование в дерево и производительность
← Назад к Java Academy