Что может произойти если у двух объектов одинаковый хэш?

Проблема коллизий хэшей в iOS (Objective-C/Swift)

Когда у двух объектов одинаковый хэш, возникает коллизия хэшей — ситуация, когда разные объекты возвращают одинаковое хэш-значение. В контексте iOS-разработки это имеет серьёзные последствия для коллекций, использующих хэширование.

Ключевые проблемы и последствия

1. Снижение производительности коллекций Основные коллекции Foundation (NSDictionary, NSSet, Swift.Dictionary, Swift.Set) используют хэширование для быстрого доступа. При коллизиях:

struct ProblematicKey: Hashable {
    let id: Int
    
    // Плохая реализация - всегда возвращает одинаковый хэш
    func hash(into hasher: inout Hasher) {
        hasher.combine(1) // Всегда одинаковый хэш!
    }
    
    static func == (lhs: Self, rhs: Self) -> Bool {
        return lhs.id == rhs.id
    }
}

var dictionary = [ProblematicKey: String]()
// Все ключи будут иметь хэш = 1
// Доступ O(1) превращается в O(n)

1. Деградация до линейного поиска Коллекции вырождаются из хэш-таблиц в связные списки внутри бакетов. В худшем случае операции contains, insert, remove становятся O(n) вместо ожидаемых O(1).

2. Проблемы с уникальностью в Set Set использует хэши для обеспечения уникальности. При коллизиях:

// Objective-C пример
@interface BadObject : NSObject
@property (nonatomic) NSInteger uniqueId;
@end

@implementation BadObject
- (NSUInteger)hash {
    return 42; // Все объекты имеют одинаковый хэш
}

- (BOOL)isEqual:(id)object {
    if (![object isKindOfClass:[BadObject class]]) return NO;
    return self.uniqueId == [(BadObject *)object uniqueId];
}
@end

NSSet *set = [NSSet setWithObjects:
    [[BadObject alloc] init], 
    [[BadObject alloc] init], 
    nil];
// Set может работать некорректно, хотя объекты разные по isEqual:

Правильная реализация Hashable

struct GoodKey: Hashable {
    let id: Int
    let name: String
    let date: Date
    
    func hash(into hasher: inout Hasher) {
        // Комбинируем ВСЕ значимые для равенства поля
        hasher.combine(id)
        hasher.combine(name)
        hasher.combine(date)
    }
    
    static func == (lhs: Self, rhs: Self) -> Bool {
        // Соответствие между hash и == критически важно
        return lhs.id == rhs.id &&
               lhs.name == rhs.name &&
               lhs.date == rhs.date
    }
}

Важные требования контракта Hashable

1. Детерминированность: Одинаковые объекты → одинаковый хэш
2. Инвариантность: Хэш не меняется в течение жизни объекта
3. Соответствие с ==: Если a == b, то a.hashValue == b.hashValue Обратное НЕ обязательно: одинаковые хэши ≠ равенство объектов

Реальные сценарии возникновения проблем

• Плохие реализации hashValue в legacy Objective-C коде
• Случайные коллизии при использовании слабых хэш-функций
• Намеренное злоупотребление в DoS-атаках (hash flooding)

Решения и лучшие практики

1. Используйте автоматическую синтезацию Hashable в Swift, когда возможно
2. Тестируйте распределение хэшей для больших наборов данных
3. Мониторьте производительность коллекций в продакшене
4. Для кастомных объектов комбинируйте хэши всех значимых полей:

// Автоматическая синтезация в Swift
struct AutoHashable: Hashable {
    let field1: String
    let field2: Int
    let field3: [String]
    // Компилятор сам сгенерирует корректные hash(into:) и ==
}

Производительность в цифрах

При 1000 элементов с уникальными хэшами:

• Dictionary.lookup: ~0.001 ms
• При коллизиях у всех элементов: ~0.5 ms (в 500 раз медленнее!)

Вывод: Коллизии хэшей — не просто теоретическая проблема, а реальная угроза производительности приложения. Всегда реализуйте Hashable корректно, обеспечивая хорошее распределение хэш-значений и строгое соответствие между hash(into:) и ==.