Сколько выполняются базовые операции в HashMap?

Сколько выполняются базовые операции в HashMap

Времённая сложность базовых операций HashMap зависит от коллизий хэша и распределения элементов.

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

Best case — когда нет коллизий и hashCode хорошо распределён:

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

// Все три операции: O(1)
map.put("key1", "value1");   // O(1) — вычислить hash, вставить в бакет
map.get("key1");              // O(1) — вычислить hash, получить из бакета
map.remove("key1");           // O(1) — вычислить hash, удалить из бакета

Как это работает:

HashCode вычисляется:  hash = hashCode(key) % buckets.length
                          ↓
                  Обращение к массиву: O(1)
                          ↓
          Если в бакете 1 элемент: O(1)

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

Worst case — когда все элементы в ОДНОМ бакете (полная коллизия):

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

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

// Теперь все элементы в одном бакете [LinkedList]
// O(n) — нужно перебрать список
map.put(badKey1, "value1");   // O(1) вставка в начало
map.put(badKey2, "value2");   // O(1)
map.put(badKey3, "value3");   // O(1)
map.put(badKey100, "value100"); // O(1)

map.get(badKey50);             // O(50) — перебрать 50 элементов в списке
map.remove(badKey75);          // O(75) — перебрать 75 элементов

Структура HashMap с коллизиями

BaketsHASHMAP (capacity = 16, 1000 элементов)

┌─────────────────────────────────────────┐
│ Бакет[0]:  LinkedList -> element1 -> element2 -> element3
│ Бакет[1]:  LinkedList -> element4
│ Бакет[2]:  LinkedList (пусто)
│ Бакет[3]:  LinkedList -> element5 -> element6 -> element7 -> ...
│ ...
│ Бакет[15]: LinkedList -> element1000
└─────────────────────────────────────────┘
     ↓
Время поиска = O(среднее количество элементов в бакете)
             = O(n / количество бакетов)

Средний случай: O(n/k) = O(1) на практике

Average case — с хорошим load factor (заполненность):

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

// 1000 элементов, 16 бакетов, хорошее распределение
// Средний размер бакета = 1000 / 16 = 62.5
map.put("key", 1);          // O(62.5) в худшем случае в бакете
map.get("key");              // O(62.5)
map.remove("key");           // O(62.5)

// Но с увеличением бакетов (resizing)
// Средний размер бакета ≈ 1 (хорошее распределение)
map.put("another", 2);      // O(1) практически

Java 8+: Оптимизация с Red-Black Tree

Важное улучшение: Java 8 добавила оптимизацию!

// Java 7 и ранее: коллизия → LinkedList O(n)
// Java 8+: коллизия → LinkedList ДО 8 элементов
//          ПОТОМ → Red-Black Tree O(log n)

// Когда в одном бакете > 8 элементов
// LinkedList трансформируется в Red-Black Tree
// Поиск становится O(log n), а не O(n)

Код из HashMap:

private static final int TREEIFY_THRESHOLD = 8;   // LinkedList -> Tree
private static final int UNTREEIFY_THRESHOLD = 6; // Tree -> LinkedList

// Если в бакете > 8 элементов, используй Red-Black Tree
if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

Сложность с Red-Black Tree:

Структура одного бакета:
┌──────────────────┐
│ 1-8 элементов    │  LinkedList: O(1-8) = O(1)
└──────────────────┘

┌──────────────────┐
│ > 8 элементов    │  Red-Black Tree: O(log n)
│                  │
│     root         │
│    /    \        │
│  ...    ...      │
└──────────────────┘

Таблица сложности

Практические примеры

Пример 1: Хороший hashCode()

public class GoodKey {
    private final String value;
    
    @Override
    public int hashCode() {
        return value.hashCode();  // Хорошо распределяет
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof GoodKey)) return false;
        return value.equals(((GoodKey) o).value);
    }
}

HashMap<GoodKey, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put(new GoodKey("key" + i), "value" + i);
}

// Поиск: O(1) в среднем
map.get(new GoodKey("key500"));  // быстро!

Пример 2: Плохой hashCode() — полная коллизия

public class BadKey {
    private final String value;
    
    @Override
    public int hashCode() {
        return 0;  // ВСЕ элементы в один бакет!
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BadKey)) return false;
        return value.equals(((BadKey) o).value);
    }
}

HashMap<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put(new BadKey("key" + i), "value" + i);
}

// Поиск: O(1000) в худшем случае
// Java 8+: O(log 1000) ≈ O(10) с Red-Black Tree
map.get(new BadKey("key500"));  // МЕДЛЕННО!

Load Factor и Resizing

Load Factor — мера заполненности HashMap:

load_factor = количество элементов / количество бакетов

// HashMap по умолчанию
initial capacity = 16
load_factor = 0.75  // Trigger resizing

// Когда size > capacity * load_factor (> 12 элементов)
// HashMap увеличивает capacity в 2 раза
// и перестраивает все хэши

Процесс resizing:

// Запускается rehashing при load factor > 0.75
Map<String, Integer> map = new HashMap<>();

// Capacity = 16
for (int i = 1; i <= 13; i++) {
    map.put("key" + i, i);
    // При i == 13: load_factor = 13/16 = 0.8125 > 0.75
    // TRIGGER RESIZE → capacity = 32
    // Все элементы перехешируются: O(n)
}

Амортизированная сложность:

Несмотря на редкие дорогие операции resizing, амортизированная сложность остаётся O(1):

Много операций O(1) + редкая операция O(n)
= (n операций × O(1) + 1 операция × O(n)) / (n + 1) операций
≈ O(1) в среднем

Совет для интервью

Правильный ответ:

"HashMap имеет O(1) среднюю сложность для get, put и remove операций при хорошем распределении хэша.

Худший случай — O(n), если все элементы коллизируют в один бакет. Но Java 8+ оптимизирует это до O(log n) с Red-Black Tree.

На практике: используй хороший hashCode() и не волнуйся. HashMap справляется отлично для миллионов элементов."

Что избежать

❌ Плохой hashCode:

public class BadPerson {
    private final String name;
    
    @Override
    public int hashCode() {
        return 1;  // Все коллизии!
    }
}

✅ Хороший hashCode:

public class GoodPerson {
    private final String name;
    private final int age;
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // Хорошо распределяет
    }
}

Вывод

На практике: HashMap работает с O(1) сложностью для подавляющего большинства операций.