Быстрый поиск с помощью Hashable

1. Вы уже встречали это раньше, просто под другим углом

До этого мы говорили про равенство и порядок. Но ещё раньше в курсе вы уже работали с Set и Dictionary. И там, даже если вы не замечали этого, язык опирался на ещё одну важную способность типов.

Когда вы создаёте Set<Int>, всё работает. Когда делаете словарь [String: Int], тоже всё работает. Это не просто удача. Базовые типы Int, String и Bool уже умеют быть хорошими элементами множества и хорошими ключами словаря.

Посмотрите на знакомые примеры:

var visitsByUser: [String: Int] = [:]
visitsByUser["ann"] = 3
visitsByUser["bob"] = 1

let ids: Set<Int> = [10, 10, 20, 30]

print(visitsByUser["ann"] ?? 0) // 3
print(ids.count)                // 3

В словаре ключом выступает String, и это возможно потому, что строка имеет нужную для словаря способность. Значение словаря при этом может быть любым подходящим типом, потому что словарь ищет именно по ключу. В Set ситуация ещё проще: там сам элемент и есть то, что нужно быстро искать и отличать от других.

Позже, когда мы дойдём до темы протоколов, вы увидите формальное имя этой способности — Hashable. Пока же полезно держать в голове очень приземлённую мысль: если тип хорошо подходит для Set и для роли ключа в Dictionary, в языке это отдельная важная договорённость, а не случайная поблажка компилятора.

2. Почему одного == часто мало

После прошлой лекции может появиться честный вопрос: если у нас уже есть ==, зачем нужно что-то ещё? Разве нельзя просто каждый раз пройти по всем элементам и проверить равенство?

Можно. Именно так и делает обычный массив, когда вы вызываете contains.

let arrayCatalog = ["Dune", "1984", "Foundation"]
print(arrayCatalog.contains("Foundation")) // true

Но такой поиск в массиве идёт по элементам подряд. В худшем случае придётся проверить почти всё. Для маленьких данных это нормально. Для больших — уже не очень приятно.

Теперь сравним с множеством:

let setCatalog: Set<String> = ["Dune", "1984", "Foundation"]
print(setCatalog.contains("Foundation")) // true

Снаружи вопрос тот же самый. Ответ тоже тот же самый. Но внутри путь к ответу другой. Set и Dictionary не хотят каждый раз честно обходить всё подряд. Они устроены так, чтобы быстро находить нужное место для значения по специальному «отпечатку» — хешу.

Именно здесь появляется мотивация для Hashable. Равенство отвечает на вопрос «это одно и то же значение?». Хеширование помогает быстро понять «где вообще искать кандидата на совпадение?».

Если говорить очень грубо, массив больше похож на длинный список, который приходится просматривать. А Set и Dictionary больше похожи на систему ячеек, где сначала выбирается нужный отсек, и только потом делается точная проверка.

3. Что такое хеш и почему он не заменяет ==

Слово «хеш» иногда звучит как что-то слишком техническое, но полезнее представлять его очень бытово. У значения можно посчитать специальный служебный результат, который помогает быстро отправить это значение в подходящую «корзину» внутри коллекции.

Когда вы делаете set.contains(x), коллекция не обязана сравнивать x со всеми элементами подряд. Она сначала вычисляет хеш x, по нему идёт в нужную корзину, а уже потом делает финальную проверку через ==.

Упрощённая схема выглядит так:

flowchart TD
    A[Ищем значение x] --> B[Считаем hash от x]
    B --> C[Переходим в нужную корзину]
    C --> D{Есть кандидат?}
    D -- нет --> E[Ответ false]
    D -- да --> F[Проверяем через ==]
    F --> G{Значения равны?}
    G -- да --> H[Ответ true]
    G -- нет --> I[Ищем дальше в корзине или отвечаем false]

Здесь важно не сделать неправильный вывод. Хеш не заменяет равенство. Он не говорит «это точно то же самое значение». Он лишь помогает быстро сузить область поиска.

Почему всё равно нужен ==? Потому что разные значения иногда могут попасть в одну и ту же корзину. Это называется коллизией. Для вас на этом уровне достаточно понимать простую вещь: хеш — это быстрый адрес, а == — финальная проверка личности.

Из-за этого Hashable и равенство связаны очень тесно. Быстрый поиск без финальной проверки был бы небезопасен. Финальная проверка без быстрого поиска была бы честной, но медленной.

4. У этой способности есть имя: Hashable

Теперь можно назвать увиденное. Способность типа участвовать в хешировании в Swift называется протокол Hashable.

В стандартной библиотеке он объявлен так:

public protocol Hashable: Equatable {
    func hash(into hasher: inout Hasher)
}

На первый взгляд запись выглядит технически, но идея внутри довольно простая.

Она говорит следующее: тип, который поддерживает Hashable, умеет передавать свои данные в специальный механизм хеширования. Для этого у него есть метод hash(into:), который получает служебный объект hasher. Внутрь этого hasher тип «складывает» те части своих данных, которые определяют его как значение.

Если перевести на обычный язык, получается такая мысль: тип умеет сообщить коллекции достаточно информации, чтобы та могла быстро вычислить хеш и использовать его для поиска.

Полезно заметить и другую важную деталь: Hashable наследуется от Equatable. Это не случайно. Если тип участвует в хешировании, он обязан уметь и сравниваться на равенство.

Логика здесь очень важная: если два значения считаются равными через ==, то они должны и хешироваться согласованно. Иначе Set и Dictionary не смогут надёжно искать, хранить и сравнивать элементы.

Как и в предыдущих двух лекциях, пока не нужно слишком глубоко вникать в формальный синтаксис протоколов. На этом этапе достаточно рабочей модели: Hashable — это имя для типов, которые умеют быть ключами Dictionary и элементами Set так, чтобы эти коллекции могли быстро искать значения.

И снова связь с базовыми типами здесь особенно важна. Вам не пришлось ничего дополнительно делать, чтобы использовать Int в Set<Int>. Вам не пришлось отдельно «включать поддержку хеша» для String, чтобы он стал ключом словаря. Эти типы уже поддерживают такое поведение.

Так что Hashable — это не отдельный остров и не «магия словаря». Он стоит рядом с Equatable и опирается на него. Равенство отвечает на вопрос «это одно и то же значение?», а хеширование помогает быстро понять, где вообще искать это значение внутри коллекции.

5. Ключи словаря должны быть согласованы

Здесь начинается очень практичная часть. Часто проблема не в словаре и не в множестве, а в том, как мы выбрали ключ.

Возьмём строковые имена пользователей. Для языка строки "Bob" и "bob" — разные значения.

print("Bob" == "bob") // false

Значит, и как ключи словаря это будут разные записи:

var score: [String: Int] = [:]
score["Bob"] = 10
score["bob"] = 12

print(score.count)        // 2
print(score["Bob"] ?? 0)  // 10
print(score["bob"] ?? 0)  // 12

Если по смыслу приложения это один и тот же человек, то проблема не в Dictionary. Проблема в том, что мы кормили словарь несогласованными ключами.

Лечится это так же, как и в прошлой лекции со строковым равенством: нормализацией. Мы заранее приводим ключ к общей форме и только потом используем его в Set или Dictionary.

import Foundation

func normalizeKey(_ raw: String) -> String {
    raw.trimmingCharacters(in: .whitespacesAndNewlines).lowercased()
}

var score: [String: Int] = [:]

let key = normalizeKey("  Bob ")
score[key] = 10

print(score["bob"] ?? 0) // 10

Здесь очень хорошо видно, как тема хеширования связана с предыдущей лекцией про равенство. Словарь работает корректно только тогда, когда ваши ключи выражают один и тот же смысл одинаковыми данными. Если смысл один, а данные вы даёте разные, коллекция будет честно считать их разными ключами.

6. Мини-приложение: уникальный каталог книг

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

Тогда Set<String> поможет хранить уникальные книги, а словарь [String: Int] — считать, сколько уникальных книг у каждого автора.

import Foundation

func normalize(_ s: String) -> String {
    s.trimmingCharacters(in: .whitespacesAndNewlines).lowercased()
}

func makeBookID(title: String, author: String) -> String {
    "\(normalize(title))|\(normalize(author))"
}

func addBook(
    title: String,
    author: String,
    library: inout Set<String>,
    booksByAuthor: inout [String: Int]
) {
    let bookID = makeBookID(title: title, author: author)
    let authorKey = normalize(author)

    let inserted = library.insert(bookID).inserted

    if inserted {
        booksByAuthor[authorKey, default: 0] += 1
        print("Добавили книгу: \(title)")
    } else {
        print("Такая книга уже есть: \(title)")
    }
}

Проверим на дубликате, который отличается только регистром и пробелами:

import Foundation

var library: Set<String> = []
var booksByAuthor: [String: Int] = [:]

addBook(
    title: "Dune",
    author: "Frank Herbert",
    library: &library,
    booksByAuthor: &booksByAuthor
)

addBook(
    title: "  dune  ",
    author: " frank herbert ",
    library: &library,
    booksByAuthor: &booksByAuthor
)

print(library.count)                       // 1
print(booksByAuthor["frank herbert"] ?? 0) // 1

В этом примере Hashable работает на нас сразу в двух местах. Set не даёт хранить одинаковую книгу дважды. Dictionary быстро находит запись по автору и обновляет счётчик.

Обратите внимание на маленькую, но важную деталь: статистику по автору мы увеличиваем только если книга действительно была вставлена в множество. Иначе пользователь смог бы ввести одну и ту же книгу три раза, а мы бы трижды увеличили счётчик автора. Это уже была бы не ошибка хеширования, а ошибка нашей прикладной логики.

7. Хеш — это служебный адрес внутри коллекции

На этом этапе иногда возникает соблазн думать так: если у значения есть хеш, значит это почти готовый ID, который можно хранить в файле, показывать пользователю и использовать как постоянный идентификатор.

Это плохая идея.

Хеш нужен Set и Dictionary для внутренней организации поиска. Он не обязан быть красивым, человекочитаемым или стабильным между разными запусками программы. Поэтому в нашем мини-приложении идентификатор книги — это строка из нормализованных данных, а не «какой-то хеш от книги».

Из той же серии ещё одна полезная мысль: Set существует ради уникальности и быстрого поиска, а не ради порядка. Если вы печатаете множество и видите какой-то порядок элементов, не стоит считать его частью контракта. Для упорядоченного вывода потом обычно делают отдельный массив и сортируют его.

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

8. Типичные ошибки

Ошибка №1: ожидать, что Set хранит порядок элементов.
Когда вы печатаете Set, он может выглядеть «как-то отсортированным» или «как-то стабильным», и это ловушка. Порядок элементов не является контрактом множества: хеш-таблица перестраивается, и результат обхода может меняться. Если вам нужен порядок — это уже задача массива (или отдельного массива, полученного из множества), но сам Set про скорость и уникальность, а не про «красивую последовательность».

Ошибка №2: путать «равенство по смыслу» и «равенство по данным».
Частая ситуация: вы хотите, чтобы "Bob", " bob " и "BOB" считались одним пользователем, но используете их как есть в качестве ключа Dictionary. Словарь в этом не виноват: для него это три разных строки, значит три разных ключа. Лечится нормализацией (обрезать пробелы, привести регистр) до помещения в ключ.

Ошибка №3: считать, что хеш гарантирует уникальность.
Хеш — не паспорт, а «примерный адрес». Коллизии возможны: два разных значения могут иметь одинаковый хеш. Поэтому внутри Set/Dictionary всегда существует финальная проверка через ==: это как сверить фамилию на двери, когда вы уже нашли нужный подъезд. В бытовом коде вам не нужно «бороться с коллизиями вручную», но важно понимать, почему Hashable всегда идёт вместе с Equatable.

Ошибка №4: использовать hashValue как постоянный идентификатор или сохранять его.
Иногда хочется «сэкономить» и вместо строки-ключа сохранить hashValue. В следующем запуске программы (или на другом устройстве, или после обновления Swift) это может перестать работать, потому что хеши не обязаны быть стабильными между запусками. Хеш — инструмент коллекций, а не формат хранения.

Ошибка №5: не различать «ключ отсутствует» и «значение равно нулю».
Если вы делаете частотную карту и используете dict[key] ?? 0, то это нормально. Но логически «нет ключа» и «ключ есть, значение 0» — разные состояния. В учебных задачах это редко критично, но в реальном коде (например, «пользователь не найден» vs «у пользователя 0 очков») это влияет на логику. Привычка: где важно различать, используйте if let value = dict[key] { ... } else { ... }, а ?? оставляйте для честных дефолтов.