Вопрос 2. Бинарный поиск, хеширование

Внимание! Гулаков сказал что различие бинарного поиска от поиска деления–пополам в том, что бинарный применятся на деревьях, а делением пополам в массивах.

Наиболее эффективным методом поиска в упорядоченном массиве без использования вспомогательных индексов или таблиц является бинарный поиск. При поиске значения Х в упорядоченном по возрастанию значений массиве A(1)<A(2)<,..,Х, все элементы, имеющие номера с S по n также больше Х в силу упорядоченности массива по возрастанию значений. Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае - левую, во втором случае - правую половину.

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

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

Х еширование В идеале желательна такая организация таблицы, при которой бы отсутствовали лишние сравнения. Наиболее эффективным способом организации такой таблицы является массив.

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

В идеале в одно и то же число не должно преобразовыватся два различных ключа.

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

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

Если h является некоторой хеш функцией, а key-некоторый ключ, то h(key) называется хеш функцией от ключа key и является индексом, по которому должна быть помещена запись с ключом key. Если мы обозначим остаток от деления x на y как mod(x,y), то хеш функция для вышеприведенного примера есть h(key)=mod(key,1000). Желательно иметь таблицу размером больше числа вставляемых записей.

Этот метод имеет один недостаток. Если существуют два ключа K₁ и К₂, такие что h(K₁)=h(K₂), то при введении записей с этими ключами, они претендуют на одно и тоже место. Такая ситуация называется коллизией при хешировании или столкновением.

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

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

В общем случае функция повторного хеширования rh воспринимает один индекс в массиве и выдает другой индекс. Если ячейка массива h(key) уже занята, то применяется функция rh к значению h(key) для поиска другой ячейки. Если ячейка rh(h(key)) занята, то хеширование повторяется rh(rh(h(key))). Этот процесс повторяется до тех пор пока не будет найдена пустая ячейка.

Может случится, что цикл повторного хеширования будет выполнятся бесконечно. Возможны две причины : 1) таблица может быть полной, т.е. вставить новые записи невозможно; 2) зацикливание возможно при наличии пустых позиций из-за плохой хеш функции (например она работает только с четными позициями).

Свойство хорошей функции повторного хеширования состоит в том, что для любого индекса i последовательно выполняемые повторные хеширования rh(i), rh(rh(i)), ... располагаются на максимально возможное число целых чисел от 0 до m-1(m- число элементов в таблице).Функция повторного хеширования rh(i)=mod (i+1,1000) обладает этим свойством. Любая функция rh(i)=mod(i+c, m), где константа c и m являются взаимно простыми числами выдает последовательные значения, распространяющиеся на всю таблицу.

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

Одним из способов исключения скучивания является использование двойного хеширования, которое состоит в использовании двух хеш-функций h1(key) и h2(key).

Функция h1(key), называется первичной хеш-функцией используется первой при определении той позиции, в которую должна быть помещена запись. Если эта позиция занята, то последовательно используется функция повторного хеширования rh(i)=mod(i+h2(key), m) до тех пор, пока не будет найдена пустая позиция.

В оптимальном случае функция h1 и h2 должны быть выбраны так, чтобы они выполняли хеширование и повторное хеширование равномерно в интервале от 0 до m-1, а также минимизировали скучивание.

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

В этом случае rh является некоторой функцией двух аргументов.

Функция rh(i,j) выполняет повторное хеширование целого числа i, если для данного ключа повторное хеширование выполняется j-тый раз.

Хорошая хеш функция должна создавать как можно меньше коллизий при хешировании.

Наиболее известная хеш функция использует метод деления, при котором некоторый целый ключ делится на размер таблицы и остаток от деления берется в качестве значения хеш функции. Эта функция обозначается h(key)=mod(key, m). Наилучшие результаты для метода деления получаются тогда, когда размер таблицы m является простым числом. Другой метод известен как метод середины квадрата : ключ умножается сам на себя и в качестве индекса используется несколько цифр этого квадрата. Другой метод- метод свертки, при котором ключ разбивается на несколько сегментов, над которыми выполняются операции сложения или нетождественности для формирования хеш функций.

Операция нетождественности двух разрядов дает 1, если значения этих двух разрядов различны, и 0, если значения их равны(логическое вычитание).