Какая сложность доступа элементов в HashMap без коллизий?

HashMap: O(1) в идеальном случае

Амортизированная сложность доступа

Сложность доступа элемента в HashMap без коллизий — это O(1), амортизированное время. Это одно из главных преимуществ хеш-таблиц перед линейными структурами.

val map = hashMapOf<String, String>()
map["key1"] = "value1"

val value = map["key1"] // O(1) — прямой доступ

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

1. Хеширование ключа: key.hashCode() вычисляется за O(1) (для строк это быстро)
2. Расчёт индекса: индекс в массиве = hashCode % capacity
3. Прямой доступ: получение элемента из массива за O(1)

Отправить:     key → |hash function| → индекс → прямой доступ в массив
Время:         O(1)     O(1)             O(1)      O(1)
Всего:         O(1)

Почему O(1), а не O(n)?

Потому что HashMap использует прямую адресацию (direct addressing):

// Упрощённо
class HashMap<K, V> {
    private val buckets = Array<MutableList<Pair<K, V>>>(16)
    
    operator fun get(key: K): V? {
        val index = key.hashCode() % buckets.size // O(1)
        return buckets[index].find { it.first == key }?.second
    }
}

Если нет коллизий, в каждой ячейке один элемент, поэтому поиск O(1).

Коллизии — когда O(1) нарушается

Коллизия — когда два разных ключа имеют одинаковый хеш:

val key1 = "ab"
val key2 = "ba"

// Худший случай: оба ключа хешируются в один индекс
if (key1.hashCode() == key2.hashCode()) {
    // Коллизия! Оба в одной ячейке
}

При коллизии HashMap использует chaining (цепочки):

Индекс: [0] → Цепочка: (key1, val1) → (key2, val2) → null
        [1] → null
        [2] → (key3, val3) → null

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

Реальная сложность

Лучший случай: O(1) — нет коллизий Средний случай: O(1) — амортизированно Худший случай: O(n) — все ключи коллизируют (редко)

В практике HashMap обычно работает как O(1) благодаря:

• Хорошим хеш-функциям (Java String.hashCode() хороша)
• Коэффициенту загрузки (load factor): HashMap расширяется при 0.75 заполнения
• Балансировке: при слишком многих коллизиях используются красно-чёрные деревья (Java 8+)

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

Операция     Array    LinkedList   HashMap
─────────────────────────────────────────
Доступ       O(1)     O(n)         O(1)*
Поиск        O(n)     O(n)         O(1)*
Вставка      O(n)     O(1)         O(1)*
Удаление     O(n)     O(1)         O(1)*

* — амортизированно, при нормальных условиях

Android примеры

// Кэш с быстрым доступом
class ImageCache {
    private val cache = HashMap<String, Bitmap>()
    
    fun get(url: String): Bitmap? {
        return cache[url] // O(1) амортизированно
    }
    
    fun put(url: String, bitmap: Bitmap) {
        cache[url] = bitmap // O(1) амортизированно
    }
}

// Вместо этого (O(n)):
class BadCache {
    private val items = mutableListOf<Pair<String, Bitmap>>()
    
    fun get(url: String): Bitmap? {
        return items.find { it.first == url }?.second // O(n)
    }
}

Когда коллизии становятся проблемой

Java 8+ решила проблему плохих хеш-функций:

// Если коллизий много, HashMap конвертирует цепочку в красно-чёрное дерево
// Тогда сложность при коллизиях: O(log n) вместо O(n)

Выводы

• HashMap без коллизий: O(1)
• Амортизированная сложность: O(1) в среднем случае
• Худший случай: O(n) (теоретический, в практике редко)
• Java 8+: использует деревья для защиты от плохих хеш-функций
• Правило: используй HashMap для быстрого доступа, ArrayLists для последовательного обхода