while (*str) {

hi = Rand8[h1 л *str]; h2 = Rand8[h2 л *str];

/* h is in range 0..65535 */

h = ((hashIndexType)hl << 8)(hashIndexType)h2; /* use division method to scale */ return h % hashTableSize

Размер хеш-таблицы должен быть достаточно велик, чтобы в ней оставалось разумное число пустых мест. Как видно из таблицы 3.1, чем меньше таблица, тем больше среднее время поиска ключа в ней. Хеш-таблицу можно рассматривать как совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается. Пусть количество элементов равно n. Если размер таблицы равен 1, то таблица вырождается в один список длины n. Если размер таблицы равен 2 и хеширование идеально, то нам придется иметь дело с двумя списками по n/100 элементов в каждом. Как мы видим в таблице 3.1, имеется значительная свободы в выборе длины таблицы.

size 1

time 869

432 214 106 54

size 128

256 512 1024 2048 4096 8192

Таблица 0.1: Зависимость среднего времени поиска (us) от

Сортируются 4096 элементов.

hashTableSize.

Рис. 0.2: Двоичное дерево

Чтобы найти в дереве какое-то значение, мы стартуем из корня и движемся вниз. Например, для поиска числа 15, мы замечаем, что 16 < 20, и потому идем влево. При втором сравнении имеем 16 > 7, так что мы движемся вправо. Третья попытка успешна - мы находим элемент с ключом, равным 15.

Каждое сравнение вдвое уменьшает количество оставшихся элементов. В этом отношении алгоритм похож на двоичный поиск в массиве. Однако, все это верно только в случаях, когда наше дерево сбалансировано. На рис. 3.3 показано другое дерево, содержащее те же элементы. Несмотря

Реализация алгоритма на Си находится в разделе 4.5. Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. Для работы программы следует также определить hashTableSize и отвести место под hashTable. В хеш-функции hash использован метод деления. Функция insertNode отводит память под новый узел и вставляет его в таблицу. Функция deleteNode удаляет узел и освобождает память, где он располагался. Функция findNode ищет в таблице заданный ключ.

3.2 Поиск в бинарных деревьях

В разделе 1 мы использовали двоичный поиск для поиска данных в массиве. Этот метод чрезвычайно эффективен, поскольку каждая итерация вдвое уменьшает число элементов, среди которых нам нужно продолжать поиск. Однако, поскольку данные хранятся в массиве, операции вставки и удаления элементов не столь эффективны. Двоичные деревья позволяют сохранить эффективность всех трех операций - если работа идет с "случайными" данными. В этом случае время поиска оценивается как O(lg n). Наихудший случай - когда вставляются упорядоченные данные. В этом случае оценка время поиска - O(n). Подробности вы найдете в работе Кормена [2].

Двоичное дерево - это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рис. 3.2. Предполагая, что Key содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем Key, у всех узлов, расположенных справа от него, - больше. Вершину дерева называют его корнем, узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева на рис. 3.2 содержит 20, а листья - 4, 16, 37 и 43. Высота дерева - это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2.

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