Резюме
В этом спринте вы познакомились с хеш-функциями. Эти функции преобразуют входное значение в число по определённому алгоритму.
При работе с целыми числами в качестве хеш-функции можно брать остаток от деления или применить метод умножения.
Если на вход приходят строки, можно воспользоваться полиномиальным хешированием.
Также вы познакомились с хеш-таблицами. Эта структура данных, которая хранит пары вида ключ-значение. Индекс ключа в массиве вычисляется с помощью хеш-функции.
Используемые при этом хеш-функции должны обладать такими свойствами:
- Детерминизм. Для одних и тех же данных функция всегда должна возвращать одно и то же значение.
- Эффективность. Хеш-функции, используемые в хеш-таблицах, должны вычисляться быстро. Иначе не будет пользы от того, что после вычисления хеша можно быстро получить значение ключа.
- Ограниченность. Результат вычисления функции должен принадлежать определенному диапазону. Этот диапазон равен размеру массива хеш-таблицы.
- Равномерность. Данные в хеш-таблице должны быть распределены равномерно. Иначе операции с хеш-таблицей не будут эффективными, так как будут образовываться кластера.
- Лавинность. Небольшое изменение во входных данных должно способствовать значительному изменению результата. Отсутствие этого свойства также будет способствовать образованию кластеров.
- Необратимость. Не должно быть возможности восстановить ключ по значению хеша. Иначе можно было бы, например, узнать пароль, получив доступ к базе данных, в которой записан хеш от пароля.
Иногда хеш-функция возвращает одно и то же значение для разных данных. Такая ситуация называется коллизией. Коллизии — довольно частое явление при работе с хеш-таблицами. Поэтому важно уметь с ними бороться. Существуют два основных метода борьбы с коллизиями: метод цепочек и метод открытой адресации.
В методе цепочек данные, для которых хеш-функция вернула одно и то же значение, выстраиваются в связный список. При поиске элемента в худшем случае нужно проверить все элементы в цепочке. У метода цепочек есть недостатки: нужно выделять и освобождать память при добавлении и удалении данных; требуется более длительное время для прохода по списку, ведь данные в памяти компьютера записаны в разных местах.
В методе открытой адресации при возникновении коллизии данные записываются в свободную ячейку таблицы. Попытки записи элемента в таблицу называются пробированием. Существуют несколько стратегий пробирования. Мы рассмотрели линейное, квадратичное пробирование и двойное хеширование. При линейном методе попытка записи производится в следующую ячейку. При квадратичном разные итерации пробирования двух элементов шагают по-разному. В методе двойного хеширования шаг зависит от ключа.
Вы узнали, как устроены операции побитового сдвига влево и вправо. Также познакомились с некоторыми важными понятиями теории чисел. Вы научились эффективно определять, является ли заданное число простым, и находить все простые числа, не превосходящие
n.