Как работает получение элемента в HashMap?

Как работает получение элемента в HashMap

HashMap — это один из самых важных контейнеров в Java/Kotlin, реализующий интерфейс Map. Её главная особенность — средняя временная сложность O(1) для получения значения по ключу. Давайте разберёмся, как достигается эта эффективность.

Структура HashMap

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

val map = hashMapOf(
    "name" to "John",
    "age" to "30",
    "city" to "Moscow"
)

val value = map["name"]  // как это работает?

Процесс получения элемента (Get)

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

Первый шаг — вычислить хеш-код ключа:

val key = "name"
val hashCode = key.hashCode()  // например, -1234567890

2. Индекс в массиве

Хеш-код преобразуется в индекс массива бакетов:

val bucketIndex = hashCode % buckets.length
// или более сложная операция для отрицательных хешей
val bucketIndex = (hashCode.absoluteValue) % buckets.size

Например, если размер массива 16, то индекс будет от 0 до 15.

3. Поиск в бакете

Полученный бакет — это связный список (в Java 8+, обычный список) узлов. HashMap ищет нужный узел:

// Псевдокод HashMap.get()
fun get(key: K): V? {
    val hash = key.hashCode()
    val bucketIndex = hash % capacity
    var node = buckets[bucketIndex]
    
    // Поиск в цепочке
    while (node != null) {
        if (node.hash == hash && node.key == key) {
            return node.value  // найдено!
        }
        node = node.next
    }
    return null  // не найдено
}

4. Проверка равенства ключей

Важно! Проверяется не только хеш-код, но и равенство самих ключей:

if (node.hash == hash && node.key == key) {
    // оба условия должны быть true
}

Это необходимо, потому что разные ключи могут иметь одинаковый хеш-код (коллизия).

Пример с коллизией

Представим, два ключа имеют одинаковый хеш:

class Person(val name: String) {
    override fun hashCode() = name.length  // плохой хеш!
    override fun equals(other: Any?) = 
        other is Person && name == other.name
}

val p1 = Person("John")  // length = 4, hash = 4
val p2 = Person("Jane")  // length = 4, hash = 4 (коллизия!)

val map = hashMapOf(
    p1 to "Person 1",
    p2 to "Person 2"
)

val result = map[p1]  // правильно найдёт Person 1

Оба объекта попадают в один бакет, но HashMap найдёт правильный через equals().

Производительность

Средний случай O(1):

• Вычисление хеша: O(1)
• Поиск в бакете: O(1) при хорошем распределении

Худший случай O(n):

• Если все ключи имеют одинаковый хеш (все в одном бакете)
• Тогда нужно проверить все элементы в цепочке

Java 8+ оптимизация

В Java 8 HashMap улучшена: когда бакет содержит много элементов (более 8), цепочка преобразуется в красно-чёрное дерево для O(log n) вместо O(n):

// Статистика HashMap (Java 8+)
HASH_THRESHOLD = 8  // коллизии → дерево
UNTREE_THRESHOLD = 6  // дерево → цепочка (при удалении)

Load Factor и реоизменение

Co временем элементы добавляются, и коллизии становятся чаще. HashMap автоматически увеличивает размер:

LOAD_FACTOR = 0.75f  // дефолт

// При размере 16: порог расширения = 16 * 0.75 = 12
// После 12-го добавления → увеличение на 32

При расширении все элементы перехешируются в новый массив.

Best Practices

• Реализуй правильный hashCode(): быстро вычисляется, равномерно распределяет
• hashCode() и equals() должны быть согласованы: если объекты равны, хеши должны совпадать
• Используй immutable ключи: изменение ключа после добавления ломает HashMap
• Избегай слабых хешей: не используй length или другие простые функции

Итого

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