Хеширование
Cтраница 4
Этот метод называется методом открытого хеширования. Из-за своей простоты и эффективности он очень часто используется в Ассемблерах. Цикл ( Ь) - ( с) гарантирует, что если число элементов не больше, чем размер таблицы ( максимально допустимое число входов), то для каждого элемента рано или поздно место будет найдено; или же, если ищется заданный ключ, ни один элемент не будет пропущен. [46]
Другой метод, называемый упорядоченным хешированием ( ordered hashing), использует упорядочение для уменьшения затрат на безрезультатный поиск при использовании линейного зондирования, приближая их к затратам на успешный поиск. Это усовершенствование путем ввода упорядочения в таблицу аналогично достигаемому эффекту от упорядочения списков при раздельном связывании. Этот метод предназначен для приложений, в которых преобладают промахи при поиске. [47]
В качестве реализации таблиц символов хеширование предпочтительней структур бинарных деревьев, рассмотренных в главах 12 и 13, поскольку оно несколько проще и может обеспечить оптимальное ( постоянное) время поиска, если ключи относятся к стандартному типу или достаточно просты, чтобы можно было быть уверенным в разработке хорошей хеш-функции для них. Когда эти факторы не имеют значения, безусловно следует выбирать хеширование, только с одной важной оговоркой: когда ключи представляют собой длинные строки, их можно встроить в структуры данных, которые могут обеспечить методы поиска, работающие еще быстрее хеширования. [48]
 |
Эффективность алгоритма рандомизации. [49] |
Идеальный алгоритм рандомизации ( или хеширования) преобразует ключ каждого корневого сегмента в уникальный физический адрес в памяти таким образом, что все корневые сегменты распределяются равномерно по выделенной области памяти. [50]
Алгоритмы поиска, которые используют хеширование, состоят из двух отдельных частей. [51]
Расширяемое хеширование объединяет свойства методов хеширования, использования многопозиционных trie - деревьев и последовательного доступа. Для простоты в этом разделе мы будем просто считать, что ключи являются случайными строками разрядов фиксированной длины. Подобно алгоритмам с применением В-деревьев, при использовании расширяемого хеширования элементы хранятся на страницах, которые разделяются на две части при заполнении. Подобно методам индексного последовательного доступа расширяемое хеширование поддерживает каталог, указывающий, где можно найти страницу, содержащую соответствующие искомому ключу элементы. Поскольку оно объединяет эти знакомые свойства в одном алгоритме, расширяемое хеширование как нельзя более подходит для завершения знакомства с алгоритмами поиска. [52]
Обычно используется два основных метода хеширования. Думи [143] и называемый методом цепочек, предполагает наличие т списков. Если это поиск с занесением, то в случае неудачного поиска запись х добавляется к г-ому списку. [53]
Наконец, при использовании методов хеширования нужно свято верить в теорию вероятностей, ибо они эффективны лишь в среднем, а худший случай просто ужасен. Поэтому они не всегда подходят для работы в реальном масштабе времени, например, для управления движением транспорта, поскольку на карту поставлены человеческие жизни. Алгоритмы, использующие сбалансированные деревья, гораздо безопаснее, ведь они имеют гарантированную верхнюю границу времени поиска. [54]
Для решения подобных задач схемы хеширования отображают потенциально большое количество возможных ключей в относительно компактной хеш-таблице. Если в вашей компании работает 700 рабочих, вы можете объявить хеш-таблицу с 1000 записями. [55]
Во избежание подобной проблемы схема хеширования должна включать алгоритм разрешения конфликтов ( collision resolution policy), определяющий порядок действий, если ключ отображается на занятую другой записью позицию. В следующих разделах рассматривается несколько различных методов обработки конфликтных ситуаций. [56]
Страницы: 1 2 3 4