Хеширование со списками

На хеш-функцию с k значениями можно смотреть как на способ свести вопрос о хранении одного большого множества к вопросу о хранении нескольких меньших. Именно, если у нас есть хеш-функция с k значениями, то любое множество разбивается на k подмножеств (возможно, пустых), соответствующих возможным значениям хэш-функции. Вопрос о проверке принадлежности, добавлении или удалении для большого множества сводится к такому же вопросу для одного из меньших (чтобы узнать, для какого, надо посмотреть на значение хеш-функции).    

Эти меньшие множества удобно хранить с помощью ссылок; их суммарный размер равен числу элементов хешируемого множества. Следующая задача предлагает реализовать этот план.


$\scriptstyle{\blacktriangleright}$ 11.2.1. Пусть хеш-функция принимает значения ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$.Для каждого значения хеш-функции рассмотрим список всех элементов множества с данным значением хеш-функции. Будем хранить эти k списков с помощью переменн ых 

     Содержание: array [1..n] of T;
     Следующий: array [1..n] of 1..n;
     ПервСвоб: 1..n;
     Вершина: array [1..k] of 1..n;
так же, как мы это делали для k стеков ограниченной суммарной длины. Напишите соответствующие программы. (Удаление по сравнению с открытой адресацией упрощается.)

Решение. Перед началом работы надо положить ${\hbox{\tt Вершина[i]}}={\hbox{\tt 0}}$ для всех ${\hbox{\tt i}}={\hbox{\tt 1}}\ldots{\hbox{\tt k}}$, и связать все места в список свободного пространства, положив ${\hbox{\tt ПервСвоб}}={\hbox{\tt 1}}$ и ${\hbox{\tt Следующий[i]}}={\hbox{\tt i+1}}$ для ${\hbox{\tt i}}={\hbox{\tt 1}}\ldots{\hbox{\tt n-1}}$, а также ${\hbox{\tt Следующий[n]}}={\hbox{\tt 0}}$.
  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;`


$\scriptstyle{\blacktriangleright}$ 11.2.2. (Для знакомых с теорией вероятностей.) Пусть хеш-функция с k значениями используется для хранения множества, в котором в данный момент n элементов. Доказать, что математическое ожидание числа действий в предыдущей задаче не превосходит C(1+n/k) , если добавляемый (удаляемый, искомый) элемент t выбран случайно, причем все значения h(t) имеют равные вероятности (равные 1/k ).

 

Решение. Если l(i) -- длина списка, соответствующего хеш-значению i , то число операций не превосходит C(1+l(h(t))) ; усредняя, получаем искомый ответ, так как $\sum_i l(i) = n$.$\scriptstyle\blacktriangleleft$

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

Пусть H -- семейство функций, каждая из которых отображает множество T в множество из k элементов (например,   $0\ldots k-1$). Говорят, что 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 являются независимыми случайными величинами, равномерно распределенными на $0\ldots k-1$.


$\scriptstyle{\blacktriangleright}$ 11.2.3. Пусть $t_1,\ldots,t_n$ -- произвольная последовательность различных элементов множества T . Рассмотрим количество действ ий, происходящих при помещении элементов $t_1,\ldots,t_n$в множество, хешируемое с помощью функции h из универсального семейства H . Доказать, что среднее количество действий (усреднение -- по всем h из H ) не превосходит Cn(1+n/k) .

Решение. Обозначим через mi количество элементов последовательности, для которых хеш-функция равна i . (Числа $m_0,\ldots,m_{k-1}$ зависят, конечно, от выбора хеш-функции.) Количество действий, которое мы хотим оценить, с точностью до постоянного множителя равно $m_0^2+m_1^2+\ldots+m_{k-1}^2$.(Если s чисел попадают в одну хеш-ячейку, то для этого требуется примерно $1+2+\ldots+s$ действий.) Эту же сумму квадратов можно записать как число пар $\langle p, q\rangle$, для которых h(tp)=h(tq) . Последнее равенство, если его рассматривать как событие при фиксированных p и q , имеет вероятность 1/k при $p\ne q$, поэтому среднее значение соответствующего члена суммы равно 1/k , а для всей суммы получаем оценку порядка n2/k , а точнее n+n2/k , если учесть члены с p=q .$\scriptstyle\blacktriangleleft$

Эта задача показывает, что на каждый добавляемый элемент приходится в среднем C(1+n/k) операций. В этой оценке дробь n/k имеет смысл << коэффициента заполнения>> хеш-таблицы.


$\scriptstyle{\blacktriangleright}$ 11.2.4. Доказать аналогичное утверждение для произвольной последовательности операций добавления, поиска и удаления (а не только для добавления, как в предыдущей задаче).

[Указание. Будем представлять себе, что в ходе поиска, добавления и удаления элемент проталкивается по списку своих коллег с тем же хеш-значением, пока не найдет своего двойника или не дойдет до конца списка. Будем называть i -j -столкновением столкновение ti с tj . (Оно либо произойдет, либо нет -- в зависимости от h .) Общее число действий примерно равно числу всех происшедших столкновений плюс число элементов. При $t_i\ne t_j$вероятность i -j -столкновения не превосходит 1/k . Осталось проследить за столкновениями между равными элементами. Фиксируем некоторое значение x из множества T и посмотрим н а связанные с ним операции. Они идут по циклу: добавление -- проверки -- удаление -- добавление -- проверки -- удаление -- ... Столкновения происходят между добавляемым элементом и следующими за ним проверками (до удаления включительно), поэтому общее их число не превосходит числа элементов, равных x .]$\blacktriangleleft$

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

Более практичные примеры универсальных семейств могут быть построены с помощью несложных алгебраических конструкций. Через ${\Bbb Z}_p$ мы обозначаем множество вычетов по простому модулю p , т.е. $\{0,1,\ldots,p-1\}$; арифметические операции в этом множестве выполняются по модулю p . Универсальное семейство образуют все линейные функционалы на со значениями в ${\Bbb Z}_p$. Более подробно, пусть $a_1,\ldots,a_n$ -- произвольные элементы ${\Bbb Z}_p$;рассмотрим отображение -4mm\begin{displaymath} h: \langle x_1\ldots x_n \rangle \mapsto a_1x_1+\ldots+a_nx_n\end{displaymath}-1mmМы получаем семейство из pn отображений ${\Bbb Z}^n_p \to {\Bbb Z}_p$параметризованное наборами $\langle a_1\ldots a_n \rangle$.


$\scriptstyle{\blacktriangleright}$ 11.2.5. Доказать, что это семейство является универсальным.

[Указание. Пусть x и y -- различные точки пространства . Какова вероятность того, что случайный функционал принимает на них одинаковые значения? Другими словами, какова вероятность того, что он равен нулю на их разности x-y ? Ответ дается таким утверждением: пусть u -- ненулевой вектор; тогда все значения случайного функционала на нем равновероятны.]$\blacktriangleleft$

В следующей задаче множество ${\Bbb B}=\{0,1\}$

рассматривается как множество вычетов по модулю 2.


$\scriptstyle{\blacktriangleright}$ 11.2.6. Семейство всех линейных отображений из в ${\Bbb B}^m$ является универсальным.$\scriptstyle\blacktriangleleft$


Родственные хешированию идеи неожиданно оказываются полезными в следующей ситуации (рассказал Д. Варсанофьев).  Пусть мы хотим написать программу, которая обнаруживала (большинство)     опечаток в тексте, но не хотим хранить список всех правильных словоформ. Предлагается поступить так: выбрать некоторое N и набор функций $f_1,\ldots,f_k$, отображающих русские слова в $1\ldots N$. В массиве из N битов положим все биты равными нулю, кроме тех, которые являются значением какой-то функции набора на какой-то правильной словоформе. Теперь приближенный тест на правильность словоформы таков: проверить, что значения всех функций набора на этой словоформе попадают на места, занятые единицами. (Этот тест может не заметить некоторых ошибок, но все правильные словоформы будут одобрены.)


pvv
1/8/1999