Join
P
@pascalabcnet
January 2, 2023

Хеширование или как внутри устроен HashSet

Известно, что HashSet<T> реализован крайне эффективно: на операции добавления в множество и проверки на принадлежность элемента множеству тратится в среднем O(1) операций, где n - размер множества. То есть, сложность этих операций не зависит от размера множества!

Это кажется невозможным, но это так: время проверки, есть ли элемент во множестве, не зависит от размера множества! Во множестве с 1 млн элементов и со 100 млн элементов время проверки одинаково?

Попробуем разобраться, как HashSet<T>, а вместе с ним и Dictionary<T,V> устроены внутри. В основе внутреннего представления лежит так называемая хеш-таблица и алгоритм хеширования.

Суть подхода состоит в следующем: для хранения возможных элементов заводится хеш-таблица: массив размера , заведомо превышающего будущее количество элементов множества с некоторым запасом. Например, если в множестве будет не более 900 тыс. элементов, то в качестве размера таблицы можно выбрать n=1 млн. Для эффективности алгоритма принято выбирать n простым числом. Положим скажем n=1000019.

Для хранения будущих элементов заведем таблицу 

var table := new integer[n];

Все её ячейки первоначально заполнены нулями - это значит, что во множестве нет элементов.

Пусть у нас есть элемент k, который надо добавить в хеш-таблицу. Если предположить, что все k меньше n, то сделать это просто:

table[k] := k;

И тогда проверка на принадлежность множеству - мгновенная: элемент принадлежит множеству если 

table[k] <> 0

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

function Hash(k: integer): integer;
begin
  Result := k mod n;
end;

Теперь для добавления элемента в хеш-таблицу будем вначале вычислять хеш-функцию от элемента - она-то и будет давать индекс в массиве table:

  var h := Hash(k);
  if table[h] = 0 then 
    table[h] := k
  else if table[h] = k then // уже есть такой элемент
    exit

Заметим, что если на месте h находится ровно элемент k, то во множестве уже есть такой элемент k, и ничего во множество добавлять не надо.

Проблема возникает если table[h] равно некоторому значению x, и оно не совпадает с k. Это означает, что у элементов x и k - одно хеш-значение, и называется такая ситуация конфликтом. Для разрешения конфликта мы используем модифицированную хеш-функцию

function Hash(k,i: integer): integer;
begin
  Result := (Hash(k) + i*i) mod n;
end;

где i вначале равно 1, затем 2 и т.д. Если место в таблице h=Hash(k) уже занято, то мы пытаемся добавить элемент по индексу h=Hash(k,1), а если он занят, то по индексу h=Hash(k,2) и т.д. пока не найдем свободное место. Общий алгоритм добавления выглядит так:

procedure Add(k: integer);
begin
  var h := Hash(k);
  if table[h] = 0 then // конфликтов нет
    table[h] := k
  else if table[h] = k then // уже есть такой элемент
    exit  
  else // конфликт
  begin
    var i := 0;
    repeat // разрешение конфликта
      i += 1;
      h := Hash(k,i);
    until (table[h] = 0) or (table[h] = k);
    table[h] := k; 
  end;
end;

Проверка на принадлежность элемента множеству реализуется аналогично:

var res := 0; // количество поисков

function Contains(k: integer): boolean; 
begin
  var h := Hash(k);
  if (table[h] = 0) or (table[h] = k) then
    res := 1
  else begin
    var i := 0;
    repeat 
      i += 1;
      h := Hash(k,i);
    until (table[h] = 0) or (table[h] = k);
    res := i + 1;
  end;
  if table[h] = 0 then
    Result := False
  else Result := True
end;

Здесь для наших иллюстраций в глобальной переменной res будем подсчитывать, сколько раз мы вызывали хеш-функцию и искали элемент в таблице по некоторому индексу.

Замечательное свойство хеш-таблицы и алгоритма хеширования, доказанное теоретически, состоит в том, что при менее чем 90% заполненности таблицы table требуется в среднем 2.5 поиска (!!!) независимо от количества элементов (!!).

Проверим этот замечательный факт. Для этого сформируем массив случайных чисел из n элементов:

var a := ArrRandomInteger(n,0,n*2);

Сами элементы будут в диапазоне от 0 до n*2, поэтому среди них наверняка есть повторяющиеся. Повторы не попадут в хеш-таблицу как следует из алгоритма Add.

Поместим все эти элементы в хеш-таблицу:

foreach var x in a do
  Add(x);
Println(a.Distinct.Count);

Реально в нашей хеш-таблице оказалось 

787286

значений. То есть, она заполнена почти на 80%.

Теперь сформируем другой случайный массив того же размера:

var a1 := ArrRandomInteger(n,0,n*2);

Сколько в нем элементов, совпадающих с элементами массива a? Выведем это значение:

Println((HSet(a) * HSet(a1)).Count);

Результат:

310065

То есть, примерно половина значений совпадает со значениями из a, а вторая половина - нет.

Будем искать эти элементы в хеш-таблице table и определим среднее количество поисков:

  var s := 0;
  foreach var x in a1 do
  begin
    var b := Contains(x);
    s += res;
    L.Add(res);
  end;
  Println(s / a1.Length);

Результат:

3.07435658722484

поисков на элемент. Итак, внимание: в среднем на поиск каждого элемента в хеш-таблице тратится 3 (три !) операции. Найти один элемент среди миллиона - это три действия!

А теперь - самое интересное. Увеличим размер хех-таблицы n примерно в 10 раз:

var n := 10000019;

и проделаем те же вычисления. Результат:

3.08343924146544

поисков на элемент! То есть, элементов стало в 10 раз больше, а количество поисков в среднем по-прежнему три!

В этом и состоит замечательное свойство хеш-таблицы - скорость поиска элемента в ней не зависит от размера хеш-таблицы, а зависит лишь от ее заполненности. И - мы видим, что при заполненности примерно на 80% требуется в среднем 3 поиска! Говорят также, что асимптотическое время поиска = O(1).

Следует отметить, что несмотря на то, что среднее время поиска = 3 операции, но в худшем случае может тратиться существенно больше поисков.

Посмотрим, сколько раз встречалось то или иное значение res. Для этого заведем список, будем в него добавлять все значения res, а в конце посчитаем количество каждого res:

  var s := 0;
  var L := new List<integer>;
  foreach var x in a1 do
  begin
    var b := Contains(x);
    s += res;
    L.Add(res);
  end;
  Println(s / a1.Length);
  L.EachCount.OrderBy(t->t.Key).PrintLines;

Результат:

(1,5000792)
(2,1480904)
(3,875330)
(4,605335)
(5,446648)
(6,333656)
(7,266949)
(8,205677)
(9,161970)
(10,128179)
(11,102380)
(12,80320)
(13,64785)
(14,50246)
(15,40709)
(16,32706)
(17,25692)
(18,20049)
(19,16162)
(20,12644)
(21,10242)
(22,8052)
(23,6366)
(24,5053)
(25,4190)
(26,3263)
(27,2430)
(28,1943)
(29,1576)
(30,1226)
(31,959)
(32,766)
(33,592)
(34,479)
(35,350)
(36,310)
(37,195)
(38,178)
(39,142)
(40,99)
(41,82)
(42,72)
(43,59)
(44,57)
(45,41)
(46,22)
(47,24)
(48,34)
(49,12)
(50,10)
(51,19)
(52,7)
(53,12)
(54,5)
(55,5)
(56,3)
(59,1)
(60,3)
(61,1)
(62,1)
(63,2)
(65,1)
(66,1)
(69,1)

Или в виде графика:

uses PlotWPF,GraphWPF;
...
var seq := L.EachCount.OrderBy(t->t.Key);
var xx := seq.Select(kv -> real(kv.Key));
var yy := seq.Select(kv -> (real(kv.Value)));
Window.Title := 'Сколько раз возникает количество поисков res';
LineGraphWPF.Create(xx,yy);

Результат:

Или в логарифмической шкале:

  L.EachCount.OrderBy(t->t.Key).PrintLines;
  var seq := L.EachCount.OrderBy(t->t.Key);
  var xx := seq.Select(kv -> real(kv.Key));
  var yy := seq.Select(kv -> (log(real(kv.Value))));
  Window.Title := 'Сколько раз возникает количество поисков res';
  LineGraphWPF.Create(xx,yy);

Код

uses PlotWPF,GraphWPF;

var n := 10000019; // память - простое число
var table := new integer[n];

function Hash(k: integer): integer;
begin
  Result := k mod n;
end;

function Hash(k,i: integer): integer;
begin
  Result := (Hash(k) + i*i) mod n;
end;

procedure Add(k: integer);
begin
  var h := Hash(k);
  if table[h] = 0 then // конфликтов нет
    table[h] := k
  else if table[h] = k then // уже есть такой элемент
    exit  
  else // конфликт
  begin
    var i := 0;
    repeat // разрешение конфликта
      i += 1;
      h := Hash(k,i);
    until (table[h] = 0) or (table[h] = k);
    table[h] := k; 
  end;
end;

var res := 0; // возвращает количество поисковfunction Contains(k: integer): boolean; 

function Contains(k: integer): boolean; 
begin
  var h := Hash(k);
  if (table[h] = 0) or (table[h] = k) then
    res := 1
  else begin
    var i := 0;
    repeat 
      i += 1;
      h := Hash(k,i);
    until (table[h] = 0) or (table[h] = k);
    res := i + 1;
  end;
  if table[h] = 0 then
    Result := False
  else Result := True
end;

begin
  var a := ArrRandomInteger(n,0,n*2);
  foreach var x in a do
    Add(x);
  Println(a.Distinct.Count);
  
  var a1 := ArrRandomInteger(n,0,n*2); 
  Println((HSet(a) * HSet(a1)).Count);
  
  var s := 0;
  var L := new List<integer>;
  foreach var x in a1 do
  begin
    var b := Contains(x);
    s += res;
    L.Add(res);
  end;
  Println(s / a1.Length);
  
  L.EachCount.OrderBy(t->t.Key).PrintLines;
  var seq := L.EachCount.OrderBy(t->t.Key);
  var xx := seq.Select(kv -> real(kv.Key));
  var yy := seq.Select(kv -> (log(real(kv.Value))));
  Window.Title := 'Сколько раз возникает количество поисков res';
  LineGraphWPF.Create(xx,yy);
end.

Вывод

Хеширование - замечательный быстрый алгоритм поиска элемента во множестве с асимптотической сложностью O(1), что означает, что время поиска не зависит от n - количества элементов множества. Основная расплата за это - для хранения множеств требуется память с некоторым запасом (скажем, 20% от максимального размера множества).

@pascalabcnet
January 2, 2023, 09:52
0 views
3 reactions