Что такое Коллизия

«Что такое Коллизия» — вопрос из категории Алгоритмы и структуры данных, который задают на 29% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Коллизия возникает, когда разные данные (например, хеш-коды) дают одинаковый результат. В контексте Android это часто встречается в HashMap или HashSet, где два разных объекта имеют одинаковый hashCode(), но equals() возвращает false.

Пример:

data class User(val id: Int, val name: String) {
    override fun hashCode() = id % 2 // Упрощённый хеш (коллизия при чётных/нечётных id)
}

val map = HashMap<User, String>()
map[User(1, "Alice")] = "Admin"
map[User(3, "Bob")] = "User" // Коллизия: хеш совпадает с User(1, "Alice")

Решение:

  • Реализовать hashCode() так, чтобы минимизировать коллизии (например, используя все значимые поля).
  • В HashMap коллизии обрабатываются через связные списки или балансировку деревьев (в Java 8+).