4. Хеширование

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

Установление логарифмической нижней границы в операциях динамического набора В ходе исследования выясняется, могут ли операции поиска выполняться быстрее, чем за логарифмическое время. В нем устанавливается, что в рамках ограниченной вычислительной модели любой алгоритм, разработанный для операции поиска, по своей сути требует, по крайней мере, логарифмического времени n. В пояснении приводится доказательство нижней границы, в то же время признается, что более высокая производительность может быть достигнута в моделях с меньшими ограничениями. Основное внимание уделяется включению динамических обновлений, таких как insert и delete, наряду с эффективным поиском, что подчеркивает сложность балансировки этих операций.

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

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

Корректность и логарифмическая нижняя граница при поиске на основе сравнения Выходные данные алгоритма поиска представлены в виде листьев бинарного дерева, где каждый лист соответствует либо сохраненному элементу, либо не найденному результату. Для хранения n элементов требуется, по крайней мере, n+1 листьев для корректной обработки случаев, когда ключ отсутствует. Наихудший сценарий предполагает прохождение по самому длинному пути, который равен высоте дерева, а сбалансированное дерево гарантирует, что эта высота будет логарифмической в n. Это устанавливает фундаментальную нижнюю границу логарифмических сравнений n для любого поиска, основанного на сравнении.

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

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

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

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

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

Сжатие обширного пространства для клавиш Хэш-функция сжимает большую совокупность ключей в меньший набор индексов, сопоставляя каждому ключу местоположение от 0 до m-1. Это преобразование позволяет использовать базовый массив для прямого доступа, где вычисленный индекс ключа определяет его ячейку для хранения. Процедура хэширования имеет фундаментальное значение для эффективной организации данных в памяти.

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

Методы разрешения коллизий Для устранения коллизий существуют две основные стратегии: открытая адресация и объединение в цепочки. Открытая адресация находит альтернативный слот в массиве, используя методы проверки, в то время как объединение в цепочки сохраняет ключи, с которыми столкнулись, во вторичных структурах данных, таких как связанные списки или динамические массивы. Каждый подход направлен на сохранение постоянной производительности во времени при устранении конфликтов, вызванных коллизиями.

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

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

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

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

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