Происходит ли добавление элемента в HashMap за константное время

# Добавление элемента в HashMap: константное время O(1)?

Это один из самых важных вопросов об основных структурах данных Java. Краткий ответ: в идеальном случае да, но на практике это зависит от реализации хеш-функции и распределения данных.

Идеальный случай: O(1)

// HashMap работает на основе массива buckets
private static final int DEFAULT_CAPACITY = 16;
private Entry<K, V>[] buckets = new Entry[DEFAULT_CAPACITY];

public V put(K key, V value) {
    // Шаг 1: вычисляем хеш (O(1))
    int hash = key.hashCode();
    
    // Шаг 2: вычисляем индекс в массиве (O(1))
    int index = hash % buckets.length;
    
    // Шаг 3: добавляем элемент в bucket (O(1) если нет коллизий)
    buckets[index] = new Entry<>(key, value, buckets[index]);
    
    return null;
}

Если:

1. Хеш-функция хороша
2. Нет коллизий (разные ключи имеют разные индексы)
3. Нет rehashing

Тогда добавление — O(1).

На практике: O(1) амортизировано

Проблема 1: Коллизии хешей

// Если хеши совпадают — есть коллизия
HashMap<String, Integer> map = new HashMap<>();

map.put("ab", 1);  // hash = 3104
map.put("ba", 2);  // hash = 3104 (КОЛЛИЗИЯ!)

// Внутри HashMap:
// Bucket[index] = Entry("ab", 1) -> Entry("ba", 2) -> null
// Это связный список! Поиск становится O(n)

В Java 8+ при слишком много коллизиях HashMap конвертирует связный список в Red-Black дерево:

// Если коллизии: структура идет от
// O(n) в худшем случае
// к O(log n) в худшем случае (Red-Black Tree)

Проблема 2: Rehashing

Когда HashMap переполняется, происходит rehashing — пересоздание массива с большей емкостью.

public V put(K key, V value) {
    // Проверка нужен ли rehash
    if (size >= threshold) {  // threshold = capacity * loadFactor
        resize();  // O(n) операция!
    }
    // ... вставка элемента ...
}

private void resize() {
    // Создаем новый массив большего размера
    Entry<K, V>[] newBuckets = new Entry[buckets.length * 2];  // O(n)
    
    // Перемещаем все элементы
    for (Entry<K, V> entry : buckets) {  // O(n)
        while (entry != null) {
            int newIndex = entry.hash % newBuckets.length;
            newBuckets[newIndex] = new Entry<>(entry.key, entry.value, newBuckets[newIndex]);
            entry = entry.next;  // O(n) в сумме
        }
    }
    
    buckets = newBuckets;
}

Пример: когда put() медленнее

HashMap<String, String> map = new HashMap<>();

// Добавляем элементы
for (int i = 0; i < 1_000_000; i++) {
    map.put("key" + i, "value" + i);
    // Некоторые из этих операций O(n) из-за rehashing
}

Время добавления варьируется:

• Обычно: O(1)
• При rehashing: O(n)

Анализ сложности

Теоретическая сложность

// Лучший случай: O(1)
// Нет коллизий, нет rehashing
map.put("key1", "value1");

// Средний случай: O(1) амортизировано
// Статистически хеши распределяются хорошо
for (int i = 0; i < 1_000_000; i++) {
    map.put("key" + i, "value" + i);  // O(1) в среднем
}

// Худший случай: O(n)
// Все ключи имеют одинаковый хеш (плохая хеш-функция)
HashMap<BadKey, Integer> badMap = new HashMap<>();

// Все элементы в одном bucket → связный список
for (int i = 0; i < 1000; i++) {
    badMap.put(new BadKey(i), i);  // O(n) в худшем
}

class BadKey {
    int value;
    
    BadKey(int value) {
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        return 0;  // Все ключи имеют одинаковый хеш!
    }
}

Как улучшить производительность

1. Правильная инициализация емкости

// Неправильно: много rehashing
HashMap<String, String> map = new HashMap<>();  // capacity = 16
for (int i = 0; i < 10_000; i++) {
    map.put("key" + i, "value" + i);
    // Много rehashing: 16 → 32 → 64 → 128 → 256 → ...
}

// Правильно: одно rehashing
HashMap<String, String> map = new HashMap<>(16384);  // capacity = 16384
for (int i = 0; i < 10_000; i++) {
    map.put("key" + i, "value" + i);
    // Нет rehashing вообще!
}

2. Хорошая хеш-функция

// Плохая реализация hashCode()
class BadUser {
    String name;
    int id;
    
    @Override
    public int hashCode() {
        return 1;  // Все объекты имеют одинаковый хеш
    }
}

// Хорошая реализация hashCode()
class GoodUser {
    String name;
    int id;
    
    @Override
    public int hashCode() {
        // Используем значение объекта для создания хеша
        return Objects.hash(name, id);
    }
}

3. Мониторинг нагрузки

HashMap<String, String> map = new HashMap<>();

// Java 8+ можно использовать:
// LinkedHashMap для predictable order
LinkedHashMap<String, String> linkedMap = new LinkedHashMap<>();

// ConcurrentHashMap для многопоточности
ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();

Реальные измерения

public static void benchmark() {
    HashMap<String, Integer> map = new HashMap<>();
    
    // Тест 1: без rehashing
    long start = System.nanoTime();
    for (int i = 0; i < 10_000; i++) {
        map.put("key" + i, i);
    }
    long duration1 = System.nanoTime() - start;
    System.out.println("Первые 10k: " + (duration1 / 1_000_000) + " ms");
    
    // Тест 2: с rehashing
    start = System.nanoTime();
    for (int i = 10_000; i < 20_000; i++) {
        map.put("key" + i, i);
    }
    long duration2 = System.nanoTime() - start;
    System.out.println("Следующие 10k: " + (duration2 / 1_000_000) + " ms");
    
    // duration2 может быть немного больше из-за rehashing
}

Сравнение со структурами данных

Практические выводы

// Когда HashMap быстрый
HashMap<Long, Data> map = new HashMap<>(100_000);
for (int i = 0; i < 100_000; i++) {
    map.put((long) i, new Data());  // O(1) на практике
}

// Когда HashMap медленный
HashMap<WeirdObject, Data> badMap = new HashMap<>();
for (int i = 0; i < 100_000; i++) {
    badMap.put(new WeirdObject(), new Data());  // Может быть O(n)
}

// Когда нужна гарантия O(log n)
TreeMap<String, Data> treeMap = new TreeMap<>();
for (int i = 0; i < 100_000; i++) {
    treeMap.put("key" + i, new Data());  // Всегда O(log n)
}

Ответ на вопрос

Добавление в HashMap происходит за O(1) в среднем случае (амортизировано), НО:

1. Идеальный случай (нет коллизий, нет rehashing): O(1)
2. Средний случай: O(1) амортизировано
3. Худший случай (плохая хеш-функция): O(n) (Java 8+: O(log n) с Red-Black tree)
4. Во время rehashing: O(n), но это редко (амортизированно)

Практический совет: При работе с большими HashMap-ами инициализируйте с правильной емкостью и убедитесь, что hashCode() у ключей работает хорошо.