Линейное зондирование

Cтраница 2

Создайте программу, которая вставляет 105 случайных неотрицательных чисел, меньших чем 106, в таблицу размером 105, использующую линейное зондирование. Программа должна в графическом виде выводить количество зондирований, используемых для каждой из 103 последовательных вставок. [16]

Для 1 миллиона целочисленных ключей вычислите размер хеш-таблицы, при которой каждый из трех методов хеширования ( раздельное связывание, линейное зондирование и двойное хеширование) использует для обнаружения промаха при вставке в среднем столько же сравнений с ключами, как и BST-деревья, подсчитывая вычисление хеш-функции как сравнение. [17]

Другой метод, называемый упорядоченным хешированием ( ordered hashing), использует упорядочение для уменьшения затрат на безрезультатный поиск при использовании линейного зондирования, приближая их к затратам на успешный поиск. Это усовершенствование путем ввода упорядочения в таблицу аналогично достигаемому эффекту от упорядочения списков при раздельном связывании. Этот метод предназначен для приложений, в которых преобладают промахи при поиске. [18]

Точность этих выражений уменьшается с приближением значения а к 1, но в данном случае это не важно, поскольку в любом случае линейное зондирование не следует использовать в почти заполненной таблице. Для меньших значений а уравнения достаточно точны. [19]

Например, для обеспечения, чтобы среднее количество зондирований для поиска было меньшим 10, необходимо сохранять таблицу пустой по меньшей мере на 32 процента при использовании линейного зондирования, но лишь на 10 процентов при использовании двойного хеширования. При необходимости обработки 105 элементов, чтобы иметь возможность выполнить безрезультатный поиск менее чем за 10 зондирований, требуется свободное пространство всего для 104 дополнительных элементов. [20]

Имея заданную таблицу, можно быстро вычислить средние затраты на безуспешный поиск в этой таблице ( см. упражнение 14.28), но кластеры образуются в результате сложного динамического процесса ( алгоритма линейного зондирования), который трудно охарактеризовать аналитически. [21]

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

Приведите содержимое хеш-таблицы, образованной в результате вставки элементов с ключами EASYQUTIONs указанном порядке в первоначально пустую таблицу, имевшую начальный размер М 4, которая увеличивается вдвое при ее заполнении наполовину, при разрешении конфликтов методом линейного зондирования. Воспользуйтесь хеш-функцией НА; mod M для преобразования А: - той буквы алфавита в индекс таблицы. [23]

На рис. 14.9 показан процесс построения небольшой таблицы методом двойного хеширования; из рис. 14.10 видно, что двойное хеширование приводит к образованию значительно меньшего количества кластеров ( которые вследствие этого значительно короче), чем в результате линейного зондирования. [24]

Исходя из самого способа образования таблицы, ключи в таблице, построенной линейным зондированием, размещаются в случайном порядке. Поэтому линейное зондирование не подходит для приложений, в которых эти операции выполняются часто. [25]

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

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

Эти относительные значения ВРЕМЕНИ построения и поиска в таблицах состоящих из случайных последовательностей 32-разрядных ц & лых ч нее л h ПОДТВЕРЖДАЕТ, что для ключей, которые легко поддастся хешированию, кэширование работает значительно быстрее, ЧЕМ поиск с использованием дерева. Двоимое леширо-яэние работает медлвннвд, чем раздельное связывание и линейное зондирование для разреженных таблиц ( нэ-эа необходимости вычисления второй кеш-функции), но значительна быстрее линейного зондирования, ядгдн таблица заполняется; кроме того, этот метод - ЕДИНСТВЕННЫЙ, который МОЖЕТ обеспечить быстрый поиск с использованием лишь небольшого дополнительного объема памяти, Динамические хеш-таблицы, построенный с использованием линейного аондироаания и расширения путем удвоения, требуют больших затрат времени при конструировании, чем другие лзш-гзблнцы, из за необходимости распределений памяти н повторного хеширования, но несомненно обеспечивают наиболее быстрый поиск. [28]

Данные экспериментального исследования реализаций хеш-таблиц. [29]

Эти относительные значения времени построения и поиска в таблицах символов, состоящих из случайных последовательностей 32-разрядных целых чисел, подтверждают, что для ключей, которые легко поддаются хешированию, хеширование работает значительно быстрее, чем поиск с использованием дерева. Двойное хеширование работает медленнее, чем раздельное связывание и линейное зондирование для разреженных таблиц ( из-за необходимости вычисления второй хеш-функции), но значительно быстрее линейного зондирования, когда таблица заполняется; кроме того, этот метод - единственный, который может обеспечить быстрый поиск с использованием лишь небольшого дополнительного объема памяти. Динамические хеш-таблицы, построенные с использованием линейного зондирования и расширения путем удвоения, требуют больших затрат времени при конструировании, чем другие хеш-таблицы, из-за необходимости распределения памяти и повторного хеширования, но несомненно обеспечивают наиболее быстрый поиск. Этот метод является предпочтительным, когда чаще всего выполняется поиск, и когда заранее нельзя точно предвидеть количество ключей. [30]

Страницы: 1 2 3 4