В данной части мы немного подробнее поговорим о вычислительной скорости (О большое) и о том, как там всё происходит под капотом.
👉 Ранее мы рассматривали бинарный поиск по телефонному справочнику. Хоть он работает достаточно быстро, но всё равно занимает время
O(log n). Теперь представьте, что есть человек с феноменальной памятью, который смог запомнить все записи из этого справочника и вместо того, чтобы искать телефон в книге — вам достаточно назвать имя и фамилию, а этот человек мгновенно предоставит номер телефона. Получается, что в этом случае он может назвать номер телефона за время О(1), независимо от размера справочника. То есть этот алгоритм работает еще быстрее, чем бинарный поиск.❓ Но при чем тут хеш-таблица?
Продолжим рассматривать пример из предыдущего поста. Представим, что у нас есть пустой массив
$phones = []; В котором и будут храниться все номера телефонов. Передаём "Sam Doe" в нашу хеш-функцию, получаем 998, сохраняем номер телефона в элементе массива с индексом 998:$phones = [];По аналогии добавим туда и других абонентов, пока наш массив не будет заполнен всеми номерами справочника.
$index = someHashFunction('Sam Doe');
$phones[$index] = '+1-555-5030';
👍 Теперь, когда вам понадобится номер телефона, искать в массиве ничего не нужно — просто передайте строку в хеш функцию и она укажет вам, что номер хранится в массиве с определенным индексом:
$index = someHashFunction('Lisa Smith'); // 1
$phone = $phones[$index];
Соответственно мы сразу знаем где находится элемент, а значит, что скорость выполнения операции поиска (а также вставки и удаления) равна O(1). Но сразу оговорюсь, что это не совсем так. ❗️ Так как количество элементов в хеш-таблице ограничено (в нашем примере адресное пространство от 0 до 999), а множество всех возможных ключей — бесконечно, то не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (когда для разных значений получается один и тот же хеш). Такую ситуацию принято называть коллизией.
$index = someHashFunction('Sam Doe'); // 234
$index = someHashFunction('Jack Duck'); // 234 👌 Для решения подобных ситуаций можно использовать метод цепочек:
Суть этого способа заключается в том, что каждая ячейка хеш-таблицы является ссылкой на связный список. Каждый новый элемент добавляется в конец этого списка. Коллизии приводят к тому, что в таблице появляются списки, которые содержат несколько элементов.
То есть, если ячейка с хешем уже занята, но новый ключ отличается от уже имеющегося, то новый элемент вставляется в список в виде пары ключ-значение.
Если выбран метод цепочек, то вставка нового элемента происходит за
O(1), а время поиска зависит от длины списка и в худшем случае равно O(n). Если количество ключей n, а распределяем по m-ячейкам, то соотношение n/m будет коэффициентом заполнения.😅 Cтруктур хэш-таблиц огромное множество, и ни один из них не совершенен, в каждом есть компромиссы. Одни варианты лучше при добавлении данных, другие — при поиске и т. д. Выбирайте реализацию в зависимости от того, что для вас важнее.
