Нет лучше способа в чем-то разобраться, чем написать свою реализацию.
Создадим базовую версию хеш-таблицы, выясним, когда операция добавления, удаления и получения значения по ключу выполняется не за константное время.
Для большей наглядности можешь посмотреть на YT :-]
Задача: реализовать поиск номера контакта по имени.
Представим, что хеш-таблицу еще не изобрели. В нашем распоряжении есть только массив.
В айфоне может быть до 50 000 контактов, поэтому простой перебор явно не подходит. На помощь приходит хеш-функция.
В Интернетах хеш-функцию часто представляют как черный ящик, в который лучше не заглядывать. Мы же рискнем. А чтобы не было так страшно, возьмем совсем простой, игрушечный пример.
В нашем случае хеш-функция это обычная функция, которая на вход принимает имя, а возвращает загадочный хеш.
--name-->| hash func | --->hashValue
Необходимо вызвать контакт Аня. На вход "черной коробки" передаем имя.
Внутри хеш-функции, каждой букве подбирается порядковый номер в алфавите:
А - 1
н - 15
я - 33
Суммируются все значения 1 + 15 + 33.
На выходе получаем 49.
HashValue используется для записи и получения номера.
Создаем пустой массив, содержащий 4 "нулевых" элемента.
var contacts: [Int] = [0, 0, 0, 0]
Берем остаток от деления HashValue на количество элементов в массиве: 49 % 4 = 1
Получаем необходимый индекс.
Согласитесь, лучше чем перебор :-]
Представим, что в записной книжке есть контакт Яна. Хеш-функция вернет 49, абсолютно такое же значение как было у Аня. О-оу /звук из аськи/, беда...а если точнее - коллизия.
Коллизия - ситуация, когда для разных ключей вычисляется одинаковых хеш.
Возникновение коллизий обычное явление. Это не баг, но лучше бы их не было.
Уменьшить возникновение коллизий может хорошая хеш-функция (именно поэтому "черная коробка" не так проста, как кажется).
Существует несколько способов борьбы с коллизиями. Рассмотрим самый простой - метод цепочек.
Переделаем массив contacts в двумерный массив.
var contacts: [[(name: String, number: Int)]] = [ [("", 0)], [("Аня", 8900), ("Яна", 8999)], [("", 0)], [("", 0)] ]
Теперь недостаточно хранить только номер, иначе непонятно кому он принадлежит.
Что происходит при вызове Яна:
хеш-функция возвращает 49;
высчитываем индекс (1);
по индексу получаем массив;
ищем необходимое имя.
Действий стало больше, но это по-прежнему лучше перебора 50 000 контактов.
Возможны различные реализации. Самый яркий пример - замена массива с контактами связным списком, чтобы удаление первого элемента занимало не линейное, а константное время.
Чем обширнее ваши знания в алгоритмах и структурах данных, тем проще и оптимальнее вы сможете решить проблему. Для расширения технического горизонта предлагаю подписаться на телеграм-канал :-]
Мы познакомились с ситуацией, когда получение значения по ключу выполняется не за константное время. Теперь разберемся с операциями вставки и удаления. Чтобы сделать это максимально эффективно, напишем код.
struct HashTable<Key: Hashable, Value> { private typealias Element = (key: Key, value: Value) private var buckets: [[Element]] private(set) var count = 0 init(capacity: Int = 16) { self.buckets = Array(repeating: [], count: capacity) } }
buckets - массив, содержащий пары "ключ - значение".
count - отвечает за количество реальных пар.
Не можем использовать buckets.count, т.к. он забит "нулевыми" элементами
Изначально создаем buckets с количеством элементов, кратных степени 2.
Напишем функцию для получения индекса.
private func index(for key: Key) -> Int { abs(key.hashValue) % buckets.count }
Мы убедились в сложности хеш-функции, поэтому используем hashValue из-под капота.
hashValue может быть отрицательным. Берем абсолютное значение (по модулю).
Добавление пары "Ключ-значение" и изменение значения по ключу имеет одинаковый синтаксис. Учитываем это при создании функции.
mutating func set(_ value: Value, for key: Key) { let index = index(for: key) for i in 0..<buckets[index].count { if buckets[index][i].key == key { buckets[index][i].value = value return } } buckets[index].append((key, value)) count += 1 }
Получаем массив по индексу (строка 3). Проходимся по нему. Если ключ совпадает с именем, обновляем значение. Если нет — добавляем пару в массив.
Если добавили пару «ключ‑значение», увеличиваем количество реальных элементов.
Далее напишем метод для получения значения по ключу.
func get(_ key: Key) -> Value? { let index = index(for: key) for element in buckets[index] { if element.key == key { return element.value } } return nil }
Здесь никаких премудростей:
получили индекс;
получили массив по индексу;
проходимся, сравнивая ключ с именем;
совпадение есть — вернули значение, нет — nil.
Осталось научиться удалять элементы.
mutating func remove(_ key: Key) { let index = index(for: key) for i in 0..<buckets[index].count { if buckets[index][i].key == key { buckets[index].remove(at: i) count -= 1 return } } }
Все как в функции выше, только теперь удаляем пару, не забывая уменьшить количество реальных элементов (строка 7).
В хеш-таблице квадратные скобки имеют важное значение:
hashMap[1] = "first" - создание пары / установка значения
hashMap[1] = nil - удаление пары
А чем мы хуже? Напишем subscript.
subscript(key: Key) -> Value? { get { get(key) } set { if let value = newValue { set(value, for: key) } else { remove(key) } } }
get - возвращает значение по ключу.
set:
передали значение — создает новую пару / устанавливает значение
передали nil — удаляет пару.
А теперь самое интересное!
Создали хеш-таблицу, добавили 3 контакта.
Можно сказать, что хеш-функция работает неоптимально. Мы это знаем и просто закроем глаза на ее работу.
Для простоты представим, что изначальный объем buckets равен 4, следовательно, buckets заполнен на 75% (3/4).
Учитываем buckets.count, т.к. цепочки нежелательны. Стремимся к равномерному распределению.
var buckets: [[(name: String, number: Int)]] = [ [("", 0)], [("Аня", 8900), ("Яна", 8999), ("Д", 8800)], [("", 0)], [("", 0)] ]
Самое подходящее время увеличить размер buckets.
Создаем свойство maxLoadFactor (строка 6), которое определяет уровень загрузки.
Как только buckets заполнится более чем на 75%, увеличиваем capacity.
struct HashTable<Key: Hashable, Value> { private typealias Element = (key: Key, value: Value) private var buckets: [[Element]] private(set) var count = 0 private let maxLoadFactor: Double = 0.75 ...
При увеличении объема buckets, необходимо пересчитывать hashValue значений.
Зачем это необходимо?
Индекс высчитывается как: abs(key.hashValue) % buckets.count
При изменении buckets.count необходимо делать перерасчет, иначе будем получать неверные данные.
НО! В этом процессе есть и плюсы: Распределение станет более равномерным.
После увеличения capacity в 2 раза, произойдет следующие изменения:
Аня и Яна располагаются по индексу 49 % 8 = 1.
Д располагается по индексу 5 % 8 = 5.
buckets выглядит следующим образом:
var buckets: [[(name: String, number: Int)]] = [ [("", 0)], [("Аня", 8900), ("Яна", 8999)], [("", 0)], [("", 0)], [("", 0)], [("Д", 8800)], [("", 0)], [("", 0)], ]
Цепочка уменьшилась.
Напишем метод:
private mutating func resizeIfNeeded() { let loadFactor = Double(count) / Double(buckets.count) guard loadFactor > maxLoadFactor else { return } let newCapacity = buckets.count * 2 var newBuckets = Array(repeating: [(key: Key, value: Value)](), count: newCapacity) for bucket in buckets { for element in bucket { let newIndex = abs(element.key.hashValue) % newCapacity newBuckets[newIndex].append(element) } } buckets = newBuckets }
строка 2 - Определяем уровень загрузки.
Если значение больше 0.75, увеличиваем buckets.
строка 5-6 - Создаем новый buckets с увеличенным размером.
строка 9-14 - Пересчитываем индексы для пар с учетом newCapacity. Записываем значения по актуальным индексам.
строка 16 - обновляем buckets.
Не забываем вызывать resizeIfNeeded при добавлении элементов (строка 2):
mutating func set(_ value: Value, for key: Key) { resizeIfNeeded() let index = index(for: key) for i in 0..<buckets[index].count { if buckets[index][i].key == key { buckets[index][i].value = value return } } buckets[index].append((key, value)) count += 1 }
resize выполняется за линейное время O(n), а сложность метода set называется амортизированная сложность. В данном случае амортизированная константная сложность.
Амортизированная сложность - средняя стоимость одной операции на длинной последовательности операций, даже если отдельные операции могут быть дорогими.
Жизненный пример:
Вы не успеваете готовить еду каждый день после работы, поэтому по воскресеньям проводите несколько часов на кухне и готовите сразу на всю неделю. Да, это долго и трудоемко, зато в будни ужин готов за пять минут.
Удаление элементов работает по тому же принципу. Попробуйте написать метод самостоятельно или же посмотрите готовую реализацию здесь.
Спасибо за внимание :-]
