Что будет, если добавить в Set два объекта с одинаковым значением hash?ios-37

Как работает Set в Swift

Set (множество) в Swift - это неупорядоченная коллекция уникальных элементов. Для определения уникальности элементов Set использует два механизма:

  1. Хэш-значение (hashValue) - вычисляется через протокол Hashable
  2. Проверка равенства (==) - через протокол Equatable

Сценарий с одинаковыми хэшами

Когда два объекта имеют одинаковое хэш-значение, но не равны между собой, происходит следующее:

  1. Set сначала проверяет хэш-значения
  2. Если хэши совпадают, Set выполняет дополнительную проверку на равенство (==)
  3. Только если оба условия выполняются (одинаковый хэш И равенство), объекты считаются одинаковыми

Пример кода:

struct Person: Hashable {
    let id: Int
    let name: String

    // Реализация Hashable
    func hash(into hasher: inout Hasher) {
        hasher.combine(id) // Используем только id для хэширования
    }

    // Реализация Equatable
    static func == (lhs: Person, rhs: Person) -> Bool {
        return lhs.id == rhs.id && lhs.name == rhs.name
    }
}

let person1 = Person(id: 1, name: "Alice")
let person2 = Person(id: 1, name: "Bob") // Тот же id, но другое имя

var peopleSet = Set<Person>()
peopleSet.insert(person1)
peopleSet.insert(person2)

print(peopleSet.count) // Что будет?

Возможные варианты:

  1. Если объекты равны (== возвращает true):

    • Второй объект не будет добавлен
    • Set останется содержать только первый объект

  2. Если объекты не равны (== возвращает false):

    • Оба объекта будут добавлены в Set
    • Возникнет хэш-коллизия, но элементы останутся разными

Что происходит при коллизии:

Swift использует метод цепочки для разрешения коллизий:

  • Элементы с одинаковым хэшем хранятся в "ведре" (bucket)
  • При поиске сначала находится нужное ведро, затем выполняется линейный поиск по ==

Производительность при коллизиях:

  • В лучшем случае: O(1) для вставки/поиска
  • При коллизиях: O(n) внутри одного ведра

Практический пример:

struct CollidingHash: Hashable {
    let value: Int

    // Намеренно создаем коллизии
    func hash(into hasher: inout Hasher) {
        hasher.combine(1) // Все объекты имеют одинаковый хэш
    }

    static func == (lhs: CollidingHash, rhs: CollidingHash) -> Bool {
        return lhs.value == rhs.value
    }
}

var set = Set<CollidingHash>()
set.insert(CollidingHash(value: 1))
set.insert(CollidingHash(value: 2)) // Добавится, т.к. != первому

print(set.count) // Выведет 2

Рекомендации по реализации Hashable:

  1. Используйте для хэширования все значимые для равенства свойства
  2. Избегайте тривиальных хэш-функций (как в примере выше)
  3. Для сложных объектов комбинируйте хэши свойств: 
    func hash(into hasher: inout Hasher) {
    hasher.combine(property1)
    hasher.combine(property2)
}

Резюмируем

  • Set использует и хэш, и проверку равенства для определения уникальности
  • Объекты с одинаковым хэшем, но разными значениями будут оба добавлены
  • Хэш-коллизии снижают производительность Set
  • Правильная реализация Hashable и Equatable критически важна
  • В нормальных условиях коллизии редки благодаря хорошей хэш-функции Swift

Главное: одинаковый хэш не означает замену элемента в Set, если объекты не равны согласно протоколу Equatable.

Вопросы

Собеседования