Какая временная сложность операции get() в HashMap?

Временная сложность операции get() в HashMap

Ответ: Средняя временная сложность — O(1), но в худшем случае может быть O(n).

Это один из самых частых вопросов на собеседованиях, и важно понимать оба сценария.

Оптимальный случай: O(1)

Когда HashMap работает идеально:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 100);
map.put("key2", 200);

Integer value = map.get("key1");  // O(1) — прямой доступ

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

Шаг 1: Вычислить hash код
hashCode = "key1".hashCode()  → 3355346

Шаг 2: Найти bucket
index = hashCode % capacity = 3355346 % 16 = 2

Шаг 3: Получить значение из bucket
value = buckets[2]  → 100

Всё просто — O(1)!

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

Когда все ключи хешируются в один bucket (коллизии):

HashMap<String, Integer> map = new HashMap<>();
// Представим, что у нас плохая хеш-функция
// и все ключи хешируются в одно место
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.put("d", 4);
// ... 1000000 элементов в одном bucket

Integer value = map.get("a");  // O(n) — нужно пройтись по цепочке

Визуально:

Без коллизий (O(1)):
buckets[0] → null
buckets[1] → null
buckets[2] → Entry(key1, val1) → null
buckets[3] → null
buckets[4] → null

Множество коллизий (O(n)):
buckets[0] → Entry(key1) → Entry(key2) → Entry(key3) → ... → Entry(keyN) → null
buckets[1] → null
buckets[2] → null
buckets[3] → null
buckets[4] → null

Внутренняя структура HashMap

public class HashMap<K, V> {
    // Массив bucket'ов
    Node<K, V>[] table;
    int size;
    int threshold;
    float loadFactor;  // Обычно 0.75
    
    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;  // Для разрешения коллизий (chaining)
    }
}

Как работает get()

public V get(Object key) {
    Node<K, V> e = getNode(hash(key), key);
    return e == null ? null : e.value;
}

final Node<K, V> getNode(int hash, Object key) {
    Node<K, V>[] tab;
    Node<K, V> first, e;
    int n;
    K k;
    
    // Шаг 1: Найти bucket
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // Шаг 2: Проверить первый элемент
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // Шаг 3: Если есть коллизии, пройтись по цепочке
        if ((e = first.next) != null) {
            // Если это TreeNode (Java 8+), используется бинарный поиск O(log n)
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
            
            // Иначе линейный поиск по цепочке O(n)
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

Оптимизация в Java 8+: Tree Buckets

С Java 8, HashMap использует красно-чёрные деревья для решения коллизий:

Если в одном bucket более 8 элементов:
buckets[0] → TreeNode (красно-чёрное дерево) → O(log n)

Если менее 8 элементов:
buckets[0] → LinkedList → O(n)

Это означает:

• Лучший случай: O(1)
• Средний случай: O(1) (если хеш-функция хорошая)
• Худший случай: O(log n) вместо O(n) начиная с Java 8

Факторы, влияющие на производительность

1. Load Factor

HashMap<String, Integer> map = new HashMap<>();
// Default load factor = 0.75

// Когда size / capacity > 0.75, происходит resize
map.put("1", 1);
map.put("2", 2);
// ... 12 элементов в HashMap c capacity=16
// Resize! capacity = 32

Почему 0.75?

• Меньше — тратим память впустую
• Больше — больше коллизий
• 0.75 — оптимальный баланс

2. Качество hashCode()

// Плохая хеш-функция
public class BadKey {
    @Override
    public int hashCode() {
        return 1;  // Все объекты хешируются в один bucket!
    }
}

// Хорошая хеш-функция
public class GoodKey {
    private String value;
    
    @Override
    public int hashCode() {
        return Objects.hash(value);  // Распределяет хорошо
    }
}

3. Equals() метод

// ОБЯЗАТЕЛЬНО переопредели equals если переопределяешь hashCode
public class Key {
    private String value;
    
    @Override
    public int hashCode() {
        return Objects.hash(value);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Key)) return false;
        Key other = (Key) obj;
        return Objects.equals(this.value, other.value);
    }
}

Без правильного equals() — HashMap не сможет найти ключ!

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

Пример 1: Нормальное использование

HashMap<String, User> userCache = new HashMap<>();
userCache.put("user123", new User("Alice", 25));

User user = userCache.get("user123");  // O(1) — быстро

Пример 2: Риск коллизий

// Если используешь Integer как ключ с плохой функцией
HashMap<Integer, String> map = new HashMap<>();
for (int i = 1; i <= 1000000; i++) {
    map.put(i * 16, "value" + i);  // Много коллизий!
}

String value = map.get(16000000);  // Может быть O(log n) или даже O(n)

Сравнение со строками ключей

Integer key:     O(1) в худшем case
String key:      O(1) в худшем case (Java 8+: O(log n))
Custom Object:   O(1) при хорошей хеш-функции

Summary таблица

Best Practices

1. Всегда переоприделяй hashCode() и equals() вместе
2. hashCode() должен быть распределён равномерно — используй Objects.hash()
3. Помни про Load Factor — 0.75 обычно оптимально
4. Используй типизированные ключи — String, Integer, UUID
5. Избегай изменяемых объектов как ключи — если изменить, найти не сможешь
6. Знай про Tree buckets в Java 8+ — худший случай улучшен
7. Для частых операций get() — рассмотри кэширование результатов