Недостатки хеширования:

1. табличный порядок имен обычно не связан с их естественным порядком.

2. худший случай может оказаться хуже, чем при последовательном поиске.

3. таблицы, основанные на вычислении адреса, расширить динамически непросто: это может приводить к потере памяти, если таблица слишком велика, или к малой производительности, если таблица слишком мала.

Процедура занесения элемента делится на три этапа: вычисление хеш-адреса (по хеш-функции); уточнение хеш-адреса (в случае коллизии); размещение ключа (и/или элемента).

Требования при выборе хеш-функции:

- минимальная сложность ее вычисления;

- равномерность распределения значений хеш-функции по хеш-таблице, что позволяет: сократить число коллизий; не допустить скучивания значений ключей в отдельных частях таблицы.Если ключи не являются числами, то они должны быть преобразованы в целые числа перед применением хеш-функций.

Хеш-функция не может вычислять адреса больше чем размер хеш-таблицы, причем для всех ключей К 0 < h(K) < m, где m – размер хеш-таблицы.

Классы хеш-функций:

1)Идеальные (см. 62)

2)Универсальные - метод деления (H=mod(k, m),

где k- целый ключ, m-размер хеш-таблицы); метод умножения (h(K) =ém * ((C * K) mod 1)ù, где С[0..1], é ù возвращает наибольшее целое, которое меньше аргумента); метод "середины квадрата"; метод свертки (слияния); метод преобразования системы счисления; метод деления многочленов; хеш-функция для строковых ключей, и другие.

3)Специальные - Известны различные подходы к формированию специальных хеш функций:

1) Поразрядный анализ, адреса формируются путем выбора и сдвига цифр или битов исходного ключа.2) Кусочно-линейная функция. Пространство ключей, состоящее из целых величин в замкнутом интервале [a, d], делится на j равных подинтервалов длины L.

62. Идеальной хеш-функцией является такая hash-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса. Или идеальной (perfect hash function) или «минимальной совершенной» хеш-функцией

называется такая хеш функция, когда:

- не возникает коллизий;

- размер хеш таблицы и количество ключей одинаково

Алгоритмы поиска идеальных хеш-функций:

1)Метод проб и ошибок, Дж. Чикелли

С огласно этому методу, h вычисляется как сумма кодов букв ключа. Обозначим через Сj код, соответствующий j-й букве ключа k, Тогда можно записать

Значения C(L) для различных L не обязательно должны быть различными, т. е. хотя все буквы множества L₁ ..., L_l различны, среди соответствующих им кодов С₁, С₂, .., С_l могут быть и одинаковые.

2)Метод обратных чисел, Дж. Джеске

3)Алгоритм, основанный на случайных графах,С. Ботело

63. см. также 62

Коллизия – это ситуация, когда h(K1) = h(K2), в то время как K1 ≠ K2. В этом случае, очевидно, необходимо найти новое место для хранения данных. Количество коллизий необходимо минимизировать.

Метод цепочек(многомерное хеширование). Хеш-таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Элемент данных вставляется в соответствующий список в качестве нового узла. Чтобы обнаружить элемент данных, нужно применить хеш-функцию для определения нужного связанного списка и выполнить там последовательный поиск. Метод цепочек быстрее открытой адресации, так как просматривает только те ключи, которые попадают в один и тот же табличный адрес. Здесь элементы таблицы создаются динамически, а длина списка ограничена лишь количеством памяти. Списки образуются по мере необходимости по одному на каждый возможный хеш-адрес таблицы. Сами списки могут размещаться как в памяти, принадлежащей хеш-таблице, так и в отдельной памяти. В первом случае цепочки называются внутренними, а во втором случае — внешними.

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

1)Метод линейного опробования. каждая ячейка таблицы помечена как незанятая. Поэтому при добавлении нового ключа всегда можно определить, занята ли данная ячейка таблицы или нет. Если да, алгоритм осуществляет перебор по кругу, пока не встретится «открытый адрес» (свободное место). Если размер таблицы велик относительно числа хранимых там ключей, метод работает хорошо, поскольку хеш-функция будет равномерно распределять ключи по всему диапазону и число коллизий будет минимальным.

По мере того как коэффициент заполнения таблицы приближается к 1, эффективность процесса заметно падает.

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

Генерируется случайная последовательность позиций в отличие от упорядоченной последовательности, для метода линейного опробования. Генерируемая случайная последовательность должна содержать все целые числа от 1 до m в точности по одному разу. Таблица считается заполненной, если встречается первое дублирование случайного числа. Для метода случайного опробования проблема удаления записей становится более сложной, чем в случае линейного опробования. Поэтому в случае часто меняющейся таблицы для устранения коллизий следует использовать другие методы.

3) Квадратичное опробование. Это схема открытой адресации, при которой h_i(k)=h₀(k)+c_i+d_i², где с и d — константы. Благодаря нелинейности этой адресации удается избежать увеличения числа проб при числе коллизий более 2. Однако в случае почти заполненной таблицы не удается избежать «вторичного скучивания». Это связано с тем, что при большом числе ключей коллизии одной группы вступают в коллизию с другими ключами. С одной стороны, этот метод дает хорошее распределение по таблице, а с другой занимает больше времени для просчета.

4) Двойное хеширование - Один из способов преодоления вторичного скучивания состоит в использовании второй функции хеширования, не зависящей от первой. Предположим, например, что первой функцией хеширования является h₁, такая, что h₁(x₁) = h₁(х₂) = i, где x₁ ≠ х₂. Теперь, если мы имеем вторую функцию хеширования h₂ такую, что h₂(x₁) ≠ h₂(х₂) при x₁≠ х₂, то в качестве значения параметра с можно использовать значение h₂(х₁) или h₂(х₂). Если h₁ и h₂ являются независимыми, две случайные последовательности адресов, сгенерированные с помощью такого метода, будут различными. Следовательно, мы избавляемся от вторичного скучивания. Такая вариация метода открытой адресации называется двойным хешированием.

64. Характеристика методов исчерпывающего поиска. • предполагают генерацию всех решений и выбор из них решения с требуемыми свойствами.

• С учѐтом быстродействия ЭВМ и.п.эффективен в множестве, состоящем не более чем из 108 элементов. Поэтому для того, чтобы эти методы были полезны, к ним нужно относиться как к схемам, с которыми следует подходить к задаче.

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

Задачи: • Комбинаторика • Теория графов • Теория расписания • грамматический разбор, • игры и т. д.,

• Т. е. там, где альтернативы перебору нет

Методы и.п.:

– метод проб и ошибок или поиск с возвращением;

– метод ветвей и границ;

– динамическое программирование;

– методы решета;

– приближения исчерпывающего поиска

- эвристические алгоритмы;

- жадные алгоритмы.

Метод проб и ошибок или поиск с возвращением

Идею поиска с возвращением легче всего понять в связи с задачей прохода через лабиринт. Один из способов прохода через лабиринт — это двигаться из начального квадрата в соответствии с двумя правилами: 1. В каждом квадрате выбирать еще не исследованный путь. 2. Если из исследуемого в данный момент квадрата ведут исследованные пути, то нужно вернуться на один квадрат назад по последнему пройденному пути, по которому вы пришли в данный квадрат и выполнить п.1.

• Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило — о том, как выходить из тупика.

Постановка задачи - проход через лабиринт

• Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером

M*N. Элемент матрицы A[i, j]=1, если клетка (i, j) проходима. В противном случае A[i,j]=0.

• Требуется найти кратчайший путь из клетки (1, 1) в клетку (M1, N1).

• Фактически лабиринт представляет собой граф с соответствующей матрицей смежности.

• Заметим, что алгоритм можно усовершенствовать, если не позволять, чтобы длина пути (Way) была больше или равна длине оптимального пути (OptimalWay).

Задача о n ферзях • Задача заключается в размещении n ферзей на шахматной доске размером n n так, чтобы никакие два ферзя не угрожали друг другу, находясь на одной горизонтали, вертикали или диагонали.

• Для n = 1 задача имеет тривиальное решение; легко убедиться, что для n= 2 и n = 3 решений не существует. Поэтому начнем с задачи с четырьмя ферзями и решим ее с помощью поиска с возвратом. Поскольку каждый ферзь должен находиться на собственной горизонтали, все, что надо, — это указать вертикаль для каждого ферзя на доске. Соответсвенно если на очередной горизонтали нельзя разместить ферзя, то задача нерешаема.

Еще применение: маршрут шахматного коня, раскраска карты, укладка рюкзака, расстановка знаков.