На чем основан HashMap

На чем основан HashMap

HashMap — это одна из самых важных структур данных в Java Collections Framework. Она основана на концепции хеширования (hash-based storage) и представляет собой реализацию интерфейса Map с массивом в качестве внутреннего хранилища.

Основные компоненты

1. Хеш-таблица (Hash Table)

Внутри HashMap находится массив bucket'ов (корзин):

// Упрощённо: внутренняя структура
transient Node<K,V>[] table;  // Массив бакетов
private static final int DEFAULT_INITIAL_CAPACITY = 16;

Каждый bucket может содержать одну или несколько пар ключ-значение.

2. Хеш-функция

Для преобразования ключа в индекс массива используется хеш-код:

// Упрощённый алгоритм
int hash = key.hashCode();
int index = hash & (table.length - 1);  // Эквивалент modulo

Идеальный случай: O(1) время доступа, если нет коллизий (collisions).

3. Разрешение коллизий через связные списки

Если два ключа имеют одинаковый хеш, они хранятся в одном bucket'е в виде связного списка:

// До Java 8
class Node<K,V> {
    K key;
    V value;
    Node<K,V> next;  // Ссылка на следующий элемент
}

// Внутри одного bucket'а
bucket[3] -> Node(key1, value1) -> Node(key2, value2) -> null

Временная сложность в худшем случае: O(n), если все элементы имеют одинаковый хеш.

4. Оптимизация: красно-чёрное дерево (Java 8+)

Начиная с Java 8, если размер связного списка превышает порог TREEIFY_THRESHOLD (обычно 8), список преобразуется в красно-чёрное дерево (TreeNode):

// Java 8+
static final int TREEIFY_THRESHOLD = 8;

// Если в одном bucket'е больше 8 элементов
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(table, hash);  // Превратить список в дерево
}

Это улучшает производительность при коллизиях:

• Связный список: O(n)
• Красно-чёрное дерево: O(log n)

Основной алгоритм операций

put() — Вставка элемента

public V put(K key, V value) {
    int hash = hash(key);
    int index = hash & (table.length - 1);
    
    // Проверить существование ключа в bucket'е
    Node<K,V> node = table[index];
    while (node != null) {
        if (node.hash == hash && node.key.equals(key)) {
            V oldValue = node.value;
            node.value = value;  // Обновить значение
            return oldValue;
        }
        node = node.next;
    }
    
    // Добавить новый элемент
    addNode(hash, key, value, index);
    return null;
}

get() — Получение элемента

public V get(Object key) {
    int hash = hash(key);
    int index = hash & (table.length - 1);
    
    // Поиск в bucket'е
    Node<K,V> node = table[index];
    while (node != null) {
        if (node.hash == hash && node.key.equals(key)) {
            return node.value;  // Найдено
        }
        node = node.next;
    }
    return null;  // Не найдено
}

Ёмкость и переполнение (Resizing)

Когда количество элементов превышает load factor (по умолчанию 0.75), HashMap увеличивает ёмкость в 2 раза и перестраивает все бакеты:

static final float DEFAULT_LOAD_FACTOR = 0.75f;
private static final int DEFAULT_INITIAL_CAPACITY = 16;

// Переполнение происходит когда: size > capacity * 0.75
if (size > table.length * 0.75) {
    resize();  // Увеличить размер таблицы
}

Зачем это нужно:

• Поддерживать амортизированную сложность O(1)
• Снизить количество коллизий
• Предотвратить деградацию производительности

Сложность операций

Java 8+: O(log n) в худшем случае благодаря красно-чёрному дереву.

Особенности и требования

Хороший хеш-код должен:

• Распределять ключи равномерно по массиву
• Минимизировать коллизии
• Быть быстрым в вычислении

// Пример хорошего hashCode
@Override
public int hashCode() {
    return Objects.hash(id, name, email);
}

// Правило: если equals возвращает true, hashCode должен быть одинаковым
if (obj1.equals(obj2)) {
    assert obj1.hashCode() == obj2.hashCode();
}

Заключение

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