В каком случае вставка в HashMap будет выполняться с логарифмической сложностью

В каком случае вставка в HashMap будет выполняться с логарифмической сложностью

HashMap в обычных случаях имеет сложность вставки O(1) в среднем. Однако вставка может стать O(log n) только в очень специфичном случае с Java 8+ и при определённых условиях коллизий.

Обычная сложность HashMap

val map = HashMap<String, Int>()
map["key1"] = 100      // O(1) в среднем
map["key2"] = 200      // O(1) в среднем
map["key3"] = 300      // O(1) в среднем

Когда вставка становится O(log n)?

Только в Java 8+: Когда происходит много коллизий (hash conflict), HashMap использует красно-чёрное дерево (TreeNode) вместо связного списка.

// Java 8+ особенность: порог для преобразования
// TREEIFY_THRESHOLD = 8 (если в бакете 8+ элементов)
// UNTREEIFY_THRESHOLD = 6 (если уменьшилось до 6)

val map = HashMap<String, Int>()

// Если создать объекты с одинаковым hash code:
class BadKey(val value: String) {
    override fun hashCode() = 0  // Все объекты имеют одинаковый hash
    override fun equals(other: Any?) = value == (other as? BadKey)?.value
}

val badMap = HashMap<BadKey, Int>()
for (i in 0..20) {
    badMap[BadKey("key$i")] = i
    // Первые 7 вставок: O(1) — используется связный список
    // 8-я вставка: преобразование в красно-чёрное дерево
    // С 9-й вставки: O(log n) — поиск в дереве
}

Java 8 HashMap архитектура

До коллизий (нормальный случай):
bucket[0] -> [key1 -> val1]
bucket[1] -> [key2 -> val2]
             [key3 -> val3]
             
После 8+ коллизий (Java 8+):
bucket[1] -> TreeNode (красно-чёрное дерево)
              /
           key2
          /    \
       key3    key4

Пример с плохим hash code

data class UserKey(val id: Int) {
    override fun hashCode(): Int = 1  // Все объекты коллизируют!
}

val map = HashMap<UserKey, String>()

// Вставка 1-7: O(1) — связный список
for (i in 1..7) {
    map[UserKey(i)] = "User $i"
}

// Вставка 8: O(1) -> преобразование в дерево
map[UserKey(8)] = "User 8"

// Вставка 9+: O(log n) — операции в красно-чёрном дереве
for (i in 9..100) {
    map[UserKey(i)] = "User $i"  // O(log n) из-за поиска в дереве
}

Почему красно-чёрное дерево в HashMap (Java 8+)?

1. Защита от DoS атак — злоумышленник не может умышленно вызвать O(n^2)
2. Гарантированная сложность — O(log n) вместо O(n) при коллизиях
3. Лучше всего работает на практике

TreeMap: всегда O(log n)

// TreeMap ВСЕГДА использует красно-чёрное дерево
val treeMap = TreeMap<String, Int>()
for (i in 1..100) {
    treeMap["key$i"] = i  // ВСЕГДА O(log n)
}

// TreeMap требует Comparable (или Comparator)
val treeMap2 = TreeMap<Int, String>()
treeMap2[5] = "Five"      // O(log 1)
treeMap2[3] = "Three"     // O(log 2)
treeMap2[7] = "Seven"     // O(log 3)

На практике в Android

// Обычно разработчик не сталкивается с этим
val userCache = HashMap<Int, User>()  // O(1) всегда
for (user in users) {
    userCache[user.id] = user
}

// Плохой hash code может испортить производительность
data class BadUser(val id: Int) {
    override fun hashCode() = 0  // Опасно!
}

// Хороший hash code
data class GoodUser(val id: Int, val name: String) {
    override fun hashCode() = 31 * id.hashCode() + name.hashCode()
}

Выводы

HashMap:

• O(1) средняя сложность (обычно)
• O(log n) при коллизиях (Java 8+, когда бакет использует TreeNode)
• O(n) худший случай (практически невозможен в Java 8+)

TreeMap:

• O(log n) всегда (красно-чёрное дерево)
• Требует Comparable элементов
• Медленнее HashMap при нормальных операциях

Вывод: В нормальных условиях вставка в HashMap — это O(1). O(log n) возникает только при плохом hash code и в Java 8+, когда происходит деградация коллизий из связного списка в дерево.