Основы хеш поиска.Обход двоичных деревьев

Вопрос 1

1. Основы хеш-поиска.

2. Обход двоичных деревьев.

1.Основы хеш-поиска

Хеш-поиск – это поиск в заданной структуре данных с ключом. Хэш-таблицы предоставляют очень практичный способ реализации словарей. В них используется то , что поиск элемента массива по индексу выполняется за постоянное время.  По трудоёмкости эффективность хеш-поиска пропорциональна O(1), то есть в идеальном случае выполняется за одно сравнение и не зависит от размера входных данных.

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

Хеш-функция ставит в соответствие каждому входному ключу индекс
ячейки массива, где должен располагаться элемент с этим ключом.

Формальная запись хеш-функции:
h (аi ) = j, j = (1, m);

Основные требования к хеш-функции:

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

За время использования хеш-поиска было предложено довольно много различных хеш-функций. Самой простой и удобной для изучения метода хеш-функцией является функция взятия
остатка от деления ключа нацело на размерность массива m:
h (аi ) = (аi mod m) ;

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

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

Для примера используем заполнение ячеек массива данных при помощи самого простого метода вычисления индекса: взятия остатка от деления ключа нацело на размерность массива m:
h (аi ) = (аi mod m) ;

Имеется набор из 8 целочисленных ключей с данными и массив в 10 ячеек.
34, 19, 88, 15, 30, 11, 72,43.

Вычисляем индексы массива

34 mod 10 = 4, индекс размещения ключа 34 равен 4
19 mod 10 = 9, индекс размещения ключа 19 равен 9
88 mod 10 = 8, индекс размещения ключа 88 равен 8
15 mod 10 = 5, индекс размещения ключа 15 равен 5
30 mod 10 = 0, индекс размещения ключа 30 равен 0
11 mod 10 = 1, индекс размещения ключа 11 равен 1
72 mod 10 = 2, индекс размещения ключа 72 равен 2

43 mod 10 = 3, индекс размещения ключа 43 равен 3

Заносим ключи в массив по индексам, полученным от вычисления.

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

Если требуется найти в этой хеш-таблице ключ со значением 88, то этот
поиск выполняется ровно за одно сравнение: делим 88 на 10, берем остаток 8
обращаемся в ячейку с индексом 8, сравниваем находящееся там значение с заданным ключом и
заканчиваем поиск с признаком успешности.

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

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