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

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

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

      11.2.1. Пусть хеш-функция принимает значения 1..k. Для каждого значения хеш-функции рассмотрим список всех элементов множества с данным значением хеш-функции. Будем хранить эти k списков с помощью переменных
      Содержание: array [1..n] of T;
      Следующий: array [1..n] of 1..n;
      ПервСвоб: 1..n;
      Вершина: array [1..k] of 1..n;

      так же, как мы это делали для k стеков ограниченной суммарной длины. Напишите соответствующие программы. (Удаление по сравнению с открытой адресацией упрощается.)

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

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

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

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

      Пусть H - семейство функций, каждая из которых отображает множество T в множество из k элементов (например, 0..k-1). Говорят, что H - универсальное семейство хеш-функций, если для любых двух различных значений s и t из множества T вероятность события "h(s)=h(t)"<p,q> для случайной функции h из семейства H равна 1/k. (Другими словами, те функции из H, для которых h(s)=h(t), составляют 1/k-ую часть всех функций в H.)

      Замечание. Более сильное требование к семейству H могло бы состоять в том, чтобы для любых двух различных элементов s и t множества T значения h(s) и h(t) случайной функции h являются независимыми случайными величинами, равномерно распределенными на 0..k-1.

      11.2.3. Пусть t[1]..t[n] - произвольная последовательность различных элементов множества T. Рассмотрим количество действий, происходящих при помещении элементов t[1]..t[n] в множество, хешируемое с помощью функции h из универсального семейства H. Доказать, что среднее количество действий (усреднение - по всем h из H) не превосходит C*n*(1+n/k).

      Решение. Обозначим через m[i] количество элементов последовательности, для которых хеш-функция равна i. (Числа m[0]..m[k-1] зависят, конечно, от выбора хеш-функции.) Количество действий, которое мы хотим оценить, с точностью до постоянного множителя равно сумме квадратов чисел m[0]..m[k-1]. (Если s чисел попадают в одну хеш-ячейку, то для этого требуется примерно 1+2+...+s действий.) Эту же сумму квадратов можно записать как число пар , для которых h[t[p]]=h[t[q]]. Последнее равенство, если его рассматривать как событие при фиксированных p и q, имеет вероятность 1/k при p<>q, поэтому среднее значение соответствующего члена суммы равно 1/k, а для всей суммы получаем оценку порядка n*n/k, а точнее n + n*n/k, если учесть члены с p=q.

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

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

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

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

      Более практичные примеры универсальных семейств могут быть построены с помощью несложных алгебраических конструкций. Через Z[p] мы обозначаем множество вычетов по простому модулю p, т.е. {0,1,...,p-1}; арифметические операции в этом множестве выполняются по модулю p. Универсальное семейство образуют все линейные функционалы на Z[p] в степени n со значениями в Z[p]. Более подробно, пусть a[1],...,a[n] - произвольные элементы Z[p]; рассмотрим отображение
      h: |-> a[1]x{1]+...+a{n]z[n]

      Мы получаем семейство из (p в степени n) отображений, параметризованное наборами a[1]...a[n].

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

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

      В следующей задаче множество B={0,1} рассматривается как множество вычетов по модулю 2.

      11.2.6. Семейство всех линейных отображений из (B в степени m) в (B в степени m) является универсальным.

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