На хеш-функцию с k значениями можно смотреть как на способ свести вопрос о хранении одного большого множества к вопросу о хранении нескольких меньших. Именно, если у нас есть хеш-функция с k значениями, то любое множество разбивается на k подмножеств (возможно, пустых), соответствующих возможным значениям хэш-функции. Вопрос о проверке принадлежности, добавлении или удалении для большого множества сводится к такому же вопросу для одного из меньших (чтобы узнать, для какого, надо посмотреть на значение хеш-функции).
Эти меньшие множества удобно хранить с помощью ссылок; их суммарный размер равен числу элементов хешируемого множества. Следующая задача предлагает реализовать этот план.
11.2.1. Пусть хеш-функция принимает значения .Для каждого значения хеш-функции рассмотрим список всех
элементов множества с данным значением хеш-функции. Будем
хранить эти k списков с помощью переменн
ых
Содержание: array [1..n] of T; Следующий: array [1..n] of 1..n; ПервСвоб: 1..n; Вершина: array [1..k] of 1..n;так же, как мы это делали для k стеков ограниченной суммарной длины. Напишите соответствующие программы. (Удаление по сравнению с открытой адресацией упрощается.) Решение. Перед началом работы надо положить для всех , и связать все места в список свободного пространства, положив и для , а также .
function принадлежит (t: T): boolean; | var i: integer; begin | i := Вершина[h(t)]; | {осталось искать в списке, начиная с i} | while (i <> 0) and (Содержание[i] <> t) do begin | | i := Следующий[i]; | end; {(i=0) or (Содержание [i] = t)} | принадлежит := (i<>0) and (Содержание[i]=t); end; procedure добавить (t: T); | var i: integer; begin | if not принадлежит(t) then begin | | i := ПервСвоб; | | {ПервСвоб <> 0 - считаем, что не переполняется} | | ПервСвоб := Следующий[ПервСвоб] | | Содержание[i]:=t; | | Следующий[i]:=Вершина[h(t)]; | | Вершина[h(t)]:=i; | end; end; procedure исключить (t: T); | var i, pred: integer; begin | i := Вершина[h(t)]; pred := 0; | {осталось искать в списке, начиная с i; pred - | предыдущий, если он есть, и 0, если нет} | while (i <> 0) and (Содержание[i] <> t) do begin | | pred := i; i := Следующий[i]; | end; {(i=0) or (Содержание [i] = t)} | if i <> 0 then begin | | {Содержание[i]=t, элемент есть, надо удалить} | | if pred = 0 then begin | | | {элемент оказался первым в списке} | | | Вершина[h(t)] := Следующий[i]; | | end else begin | | | Следующий[pred] := Следующий[i] | | end; | | {осталось вернуть i в список свободных} | | Следующий[i] := ПервСвоб; | | ПервСвоб:=i; | end; end;`
11.2.2. (Для знакомых с теорией вероятностей.) Пусть хеш-функция с
k значениями используется для хранения множества, в котором в
данный момент n элементов. Доказать, что математическое
ожидание числа действий в предыдущей задаче не превосходит
C(1+n/k) , если добавляемый (удаляемый,
искомый) элемент t выбран случайно, причем все значения h(t)
имеют равные вероятности (равные 1/k ).
Эта оценка основана на предположении о равных вероятностях. Однако в конкретной ситуации все может быть совсем не так, и значения хеш-функции могут << скучиваться>>: для каждой конкретной хеш-функции есть << неудачные>> ситуации, когда число действий оказывается большим. Прием, называемый универсальным хешированием, позволяет обойти эту проблему. Идея состоит в том, что берется семейство хеш-функций, причем любая ситуация оказывается неудачной лишь для небольшой части этого семейства.
Пусть H -- семейство функций, каждая из которых отображает множество T в множество из k элементов (например, ). Говорят, что H -- универсальное семейство хеш-функций, если для любых двух различных значений s и t из множества T вероятность события h(s)=h(t) для случайной функции h из семейства H равна 1/k . (Другими словами, те функции из H , для которых h(s)=h(t) , составляют 1/k -ую часть всех функций в H .)
Замечание. Более сильное требование к семейству H могло бы состоять в том, чтобы для любых двух различных элементов s и t множества T значения h(s) и h(t) случайной функции h являются независимыми случайными величинами, равномерно распределенными на .
11.2.3. Пусть -- произвольная последовательность
различных элементов множества T . Рассмотрим количество
действ
ий, происходящих при помещении элементов в множество, хешируемое с помощью функции h из универсального
семейства H . Доказать, что среднее количество действий
(усреднение -- по всем h из H ) не превосходит
Cn(1+n/k) .
Эта задача показывает, что на каждый добавляемый элемент приходится в среднем C(1+n/k) операций. В этой оценке дробь n/k имеет смысл << коэффициента заполнения>> хеш-таблицы.
11.2.4. Доказать аналогичное утверждение для произвольной
последовательности операций добавления, поиска и удаления (а не
только для добавления, как в предыдущей задаче).
Теперь приведем примеры универсальных семейств. Очевидно, для любых конечных множеств A и B семейство всех функций, отображающих A в B , является универсальным. Однако этот пример с практической точки зрения бесполезен: для запоминания случайной функции из этого семейства нужен массив, число элементов в котором равно числу элементов в множестве A . (А если мы можем себе позволить такой массив, то никакого хеширования не требуется!)
Более практичные примеры универсальных семейств могут быть построены с помощью несложных алгебраических конструкций. Через мы обозначаем множество вычетов по простому модулю p , т.е. ; арифметические операции в этом множестве выполняются по модулю p . Универсальное семейство образуют все линейные функционалы на со значениями в . Более подробно, пусть -- произвольные элементы ;рассмотрим отображение -4mm-1mmМы получаем семейство из pn отображений параметризованное наборами .
11.2.5. Доказать, что это семейство является универсальным.
В следующей задаче множество
рассматривается как множество вычетов по модулю 2.
11.2.6. Семейство всех линейных отображений из в
является универсальным.
Родственные хешированию идеи неожиданно оказываются
полезными в следующей ситуации (рассказал Д. Варсанофьев).
Пусть
мы хотим написать программу, которая обнаруживала (большинство)
опечаток в тексте, но не хотим хранить список всех правильных
словоформ. Предлагается поступить так: выбрать некоторое N и
набор функций , отображающих русские слова в
. В массиве из N битов положим все биты равными нулю,
кроме тех, которые являются значением какой-то функции набора на
какой-то правильной словоформе. Теперь приближенный тест на
правильность словоформы таков: проверить, что значения всех
функций набора на этой словоформе попадают на места, занятые
единицами. (Этот тест может не заметить некоторых ошибок,
но все правильные словоформы будут одобрены.)