Хеш-таблица, хеш-функция в Swift

Хеш-таблица.

Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
 
Сегодня мы рассмотрим, что такое хеш-таблица, как она работает и что делает ее полезной. Допустим, вам нужно найти чей-то номер телефона в телефонной книге. Как вы это сделаете? Вы берете фамилию этого человека, ищете номер телефона по заглавной букве .
 
Хеш-таблицы делают то же самое, только вместо списка имен, отсортирванных по алфавиту, они используют нечто называемое функцией хеширования, для хранения и поиска людей. Это лучше, чем алфавит, потому что вам не нужно реорганизовывать список каждый раз, когда вы добавляете новую запись. И пока у вас есть хороший алгоритм хеширования, он работает молниеносно, вот почему хеш-таблицы являются наиболее популярной структурой для быстрого поиска информации. Давайте рассмотрим, как они работают.

Как работает хеш-функция?

Итак, построение хеш-таблицы состоит из трех частей: хеш-функция, преобразование хеша в индекс и обработка коллизий. Сначала давайте рассмотрим, что такое "хорошая" хеш-функция.

Хеш-функция (англ. hash function от hash — «превращать в фарш», «мешанина»), или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

Простыми словами: Хеш-функция - это метод, который берет любой объект и вычисляет почти уникальное числовое представление объекта, которое может быть использовано в качестве ключа для последующего поиска. Хорошая хеш-функция работает быстро. Она дает хорошее равномерное распределение чисел и минимизирует коллизии. Подробнее об этом позже. Каждый объект, который мы храним в хеш-таблице, должен иметь хеш-функцию, которая отвечает за генерацию собственного хеш-кода. Все базовые конструкции в Swift такие как String, Int, Float…и тд. уже имеют встроенную хеш-функцию, которой мы можем воспользоваться чтобы вычислить хеш-код . Например, если нам нужно хеш-значение строки “abc”, мы можем просто вызвать встроенную хеш-функцию и получить ключ для этой строки.

let stringsAreHashable = "abc".hashValue

Мы можем сделать то же самое с обычными объектами, взять почти любой объект и создать для него хеш-функцию, просто взяв атрибуты этого объекта, сложив их вместе, а затем умножив на «хорошее» простое число(Int).

struct GridPoint {
    var x: Int
    var y: Int
    
    var hashValue: Int {
        return x.hashValue ^ y.hashValue &* 16777619
    }
}
let mainBase = GridPoint(x: 131, y: 541)
let hashCode = mainBase.hashValue

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

Преобразование в Индекс.

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

Вместо этого мы берем все эти возможные хеш-коды и преобразуем их в массив гораздо меньшего размера, применяя оператор modulus(%-остаток от деления). Оператор modulus работает следующим образом: берется любое заданное число, делится на оператор modulus и возвращается остаток.

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

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

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

Работа с коллизиями.

Теперь, поскольку существует бесконечное количество объектов и очень большое, но конечное число хешей и еще меньшее число индексов модуля, иногда мы будем получать два объекта, которые хешируются в один и тот же индекс, и мы называем это коллизией. В этом случае мы берем оба объекта, которые разрешаются в один и тот же индекс, и храним их в связанном списке. Такая работа называется цепочкой(chaining).

И всякий раз, когда мы получаем два объекта, которые сходятся в одном хеше, мы добавляем их в связанный список. А затем, когда нам нужно найти их, мы приходим к этому индексу, а затем проходим по нашему связанному списку, пока не найдем искомый объект.

Время выполнения

Хеш-таблица, характеристики времени выполнения, как правило, O(1). Предположим для собеседования, что у вас есть хорошая хеш-таблица с хорошей функцией хеширования, хорошим распределением чисел, и вы можете описать характеристики времени выполнения поиска, вставки и удаления как O(1). Иногда, в худшем случае, вы можете получить много коллизий, и в этом случае время выполнения может занять больше времени, и мы бы описали его как O(n).

Заключение:

Подведем итоги. Что нужно знать для собеседования?

В хеш-таблицах очень быстро работает поиск - O(1). Но если вам придется пройтись по связанному списку, то в худшем случае это может быть O(n). Просто помните об этом различии на собеседовании.

В Swift есть встроенная хеш-функциия.

Как обрабатываются коллизии, периодически мы получаем два хеша или два объекта, которые хешируются на один и тот же индекс. Мы просто используем связный список. Мы соединяем их в цепочку. И это самый распространенный способ обработки коллизий в хеш-таблице.

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

Вот и все, если вы понимаете эти концепции, вы действительно хорошо подготовлены к той части собеседования, посвященной хеш-таблицам.