ВУЗ:
Составители:
Рубрика:
47
function CreateRandomTree(n,m: integer): PTreeNode;
<описание
CreateRandomTree0>
begin
Result:=NewNode(Random(100),
CreateRandomTree0(n,m),nil);
end;
Наконец, для вывода дерева составим рекурсивную процедуру PrintTree:
procedure PrintTree(r: pTreeNode);
begin
while r<>nil do
begin
write(r.data,' ');
PrintTree(r.leftChild);
r:=r.rightSibling;
end
end;
5 Хеширование. Хеш-таблицы
Хеширование – это способ хранения данных, обеспечивающий быстрый по-
иск и добавление элементов. Суть его состоит в следующем. Каждому элементу,
для которого осуществляется поиск или добавление, ставится в соответствие це-
лое число, называемое его хеш-значением или хеш-кодом (англ. hash – перемеши-
вание). Тем самым все возможные элементы разбиваются на группы (классы
эк-
вивалентности). К одной группе (одному классу эквивалентности) относятся эле-
менты с одним хеш-значением.
При поиске вначале вычисляется хеш-значение элемента, после чего этот
элемент ищется только среди элементов с тем же самым хеш-значением. Напри-
мер, при поиске слова в английском словаре мы вначале определяем его первую
букву (
хеш-значение слова), после чего ищем его только среди слов на эту букву,
в результате чего поиск на первом же шаге сокращается примерно в 26 раз (коли-
чество букв в латинском алфавите). Добавление осуществляется аналогично: вы-
числяется хеш-значение добавляемого элемента, после чего он добавляется в
группу элементов с таким же хеш
-значением.
Совокупность элементов, сгруппированных по их хеш-значениям, называется
хеш-таблицей. Функция, сопоставляющая элементу его хеш-значение, называется
хеш-функцией. Обычно в качестве хеш-функции целого числа x используется сле-
дующая функция: Hash(x)=x mod N, где N – число, определяющее количество
классов эквивалентности (рекомендуется выбирать N простым числом).
Наиболее наглядным способом хранения
хеш-таблиц является массив спи-
сков. Элементы массива нумеруются от 0 до N-1 и представляют собой списки,
при этом i-й список хранит элементы с хеш-значением, равным i. Так организо-
