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

Что такое коллизия в программировании?

Коллизия (collision) — это ситуация, когда две разные исходные данные генерируют одинаковый хеш. Это фундаментальная концепция в информатике, которая встречается повсеместно в iOS разработке при работе с Dictionary, Set и кешировании.

Коллизия в хешировании

Суть проблемы: хеш-функция преобразует исходные данные неопределённого размера в значение фиксированного размера (обычно число). Например, две разные строки могут дать одинаковый числовой хеш.

Пример на Swift:

// Простая демонстрация
func simpleHash(_ string: String) -> Int {
    var hash = 0
    for char in string {
        hash = (hash * 31 + Int(char.asciiValue ?? 0)) % 100
    }
    return hash
}

let hash1 = simpleHash("apple")  // 42
let hash2 = simpleHash("banana") // 42 — коллизия!

Почему коллизии неизбежны?

По принципу Дирихле: если входных данных больше, чем возможных хешей, то коллизии гарантированы. Если у вас есть 10 позиций в таблице, но 11 элементов — минимум два элемента совпадут по хешу.

Способы разрешения коллизий

1. Цепочки (Chaining)

• Каждая позиция хеш-таблицы содержит связный список элементов с одинаковым хешем
• Преимущества: простота, удаление элементов не проблематично
• Недостатки: дополнительная память для указателей

2. Открытая адресация (Open Addressing)

• При коллизии алгоритм ищет следующую свободную позицию
• Варианты: линейное зондирование, квадратичное хеширование, двойное хеширование
• Преимущества: лучше для кеша, нет дополнительных выделений памяти
• Недостатки: сложнее с удалением, может быть медленнее при высокой загрузке

3. Криптографические хеши

• Функции вроде MD5, SHA-1, SHA-256 минимизируют вероятность коллизий
• Используются для проверки целостности данных и в безопасности

Коллизии в Swift Dictionary

В iOS словари на основе хешей автоматически разрешают коллизии:

// Swift Dictionary использует открытую адресацию
var users = ["john": 25, "jane": 30]
users["john"] = 35 // перезапись

// Для пользовательских типов нужна реализация Hashable:
struct User: Hashable {
    let id: Int
    let name: String
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
        hasher.combine(name)
    }
    
    static func ==(lhs: User, rhs: User) -> Bool {
        lhs.id == rhs.id && lhs.name == rhs.name
    }
}

Практическое значение

• Производительность: частые коллизии замедляют Dictionary и Set (O(n) вместо O(1))
• Безопасность: в криптографии коллизия хешей — критическая уязвимость (например, MD5 считается уязвимым)
• Отладка: неправильная реализация hash() и == приводит к потере данных в словарях
• Кеширование: при проектировании систем кеша нужно учитывать распределение коллизий

Понимание коллизий необходимо для эффективной работы со структурами данных, оптимизации производительности и безопасного использования криптографических функций в iOS приложениях.