Хеширование и хеш-таблицы

Январь 7, 2017 — Шарахов А.П.

Рассмотрим особенности реализации в Delphi 7 класса хеш-таблицы с открытой адресацией и линейным опробованием для хранения данных со строковыми и двоичными ключами

Хеш-функции

Назначение хеш-функции - преобразовать идентификатор объекта в число, которое впоследствии можно использовать для поиска объекта. Простейшая строковая 32-битная хеш-функция (Robert Sedgewick) содержит всего два умножения и одно сложение:

function RSHash(const s: RawByteString): integer;
var
  coef, i: integer;
begin;
  Result:=0;
  coef:=63689;
  for i:=0 to Length(s)-1 do begin;
    Result:=Result * coef + ord(s[i+1]);
    coef:=coef * 378551;
    end;
  end; 

Она дает очень мало коллизий для английских слов и работает довольно быстро.
Для русских слов лучшие результаты можно получить с другим начальным значением множителя, например:

function ShaStringDictionaryHash(const s: RawByteString): integer;
var
  coef, i: integer;
begin;
  Result:=0;
  coef:=-1240289303;
  for i:=0 to Length(s)-1 do begin;
    Result:=(Result+ord(s[i+1])) * coef;
    coef:=coef * 378551;
    end;
//Result:=Result * 1443687719;
  end;

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

У пытливого читателя наверняка возник вопрос, почему нельзя просто пронумеровать все слова, считая буквы 32-ричными цифрами. Очевидно, что при таком почти идеальном хешировании гарантированно не возникнет ни одной коллизии для слов одинаковой длины в интервале от 1 до 6. Идея заманчивая, но для слов большей длины это совсем не так. К счастью, лекарством в данном случае является дополнительное слагаемое:

function ShaPerfectHashStr(const s: RawByteString): integer;
var
  i: integer;
begin;
  Result:=0;
  for i:=0 to Length(s)-1 do Result:=(Result + ord(s[i+1]) + 1507220783) * 1041204193;
//Result:=Result * -1463368345;
  end;

Пусть множители не смущают читателя: первый - это обратный элемент для 33, второй - тасующий.

Две последние хеш-функции не имеют коллизий на словаре Лопатина (более 150000 русских слов) и дают хорошее распределение слов по 2^18=262144 ячейкам хеш-таблицы (более 48000 кластеров, максимальный размер кластера в зависимости от тасующих множителей составляет примерно 40 занятых ячеек).

На первый взгляд кажется, что алгоритм ShaPerfectHash представляет собой одну длинную цепь зависимых вычислений, и его почти невозможно заметно ускорить. Однако это не так. Ассемблерная версия алгоритма на компьютере с процессором E6850/3.0GHz вычисляет хеш со скоростью более 2.2*10^9 байтов в секунду, которая достигнута благодаря тому, что для суммирования выделено 4 регистра.

У пытливого читателя наготове еще вопрос: что делать, если идентификаторы объекта не являются строками? Преобразовать в строку? А если идентификатор целое число? Преобразовать целое в строку, чтобы потом функция хеширования вернула опять же целое? Зачем? Действительно, незачем. Ничего другого, кроме коллизий хеш-кодов, так не добиться. Если, например, мы имеем дело с последовательными значениями, то можно вообще ничего не делать. С другой стороны, если идентификаторы это цвета точек, или координаты пересечения окружностей с границами прямоугольника, или последовательные значения, полученные от любителей разбивать яйца с другого конца, то не помешает избавиться от возможной регулярности значений идентификаторов, взболтав их как следует. Функция "взбалтывания" - любое взаимно-однозначное преобразование, при котором младшие биты результата становятся похожи на случайные, например:

 
function Shake(Id: integer): integer;
begin;
  Id:=Id * 1443687719;
  Id:=Id shr 16 xor Id;
  Id:=Id shr 8 xor Id;
  Id:=Id * -1866451833;
  Result:=Id;
  end;

Взаимная однозначность функции "взбалтывания" позволяет нам при необходимости восстановить идентификатор объекта по хеш-коду:

function Stir(Shaken: integer): integer;
begin;
  Shaken:=Shaken * -1262857929; //-1866451833^-1
  Shaken:=Shaken shr 8 xor Shaken;
  Shaken:=Shaken * 630043287; //1443687719^-1
  Result:=Shaken;
  end;

В других случаях, например, когда ключом является буфер с двоичными данными, совместно с хеш-таблицей можно использовать любую известную универсальную хеш-функцию, которая работает достаточно быстро, например Murmur3. Ее ассемблерная версия на E6850 работает приблизительно на 10% быстрее ассемблерной версии ShaPerfectHash.

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

function ShaLinearHash(const Tag): integer;
const
  c1= 1158345749;
  c2= integer(int64(c1) * c1);
  c3= integer(int64(c2) * c1);
  c4= integer(int64(c3) * c1);
begin;
  with TCoordinates(Tag) do Result:=c1*x1 + c2*y1 + c3*x2 + c4*y2;
  end;

Разумеется, выбор не ограничивается только упомянутыми функциями.

А теперь таблицы

Теория известна, но есть нюанс. И не один. Первый - это размер. В отношении него имеются разные мнения. Если размер таблицы равен простому числу, то для вычисления индекса данных будут использованы все биты хеш-кода. Если же размер является степенью двойки, используется только часть битов хеш-кода в зависимости от размера таблицы. При этом упрощаются вычисления по модулю и копирование данных при увеличении размера таблицы. Минимальный размер таблицы должен оставаться ненулевым, чтобы не обрабатывать особый случай в критичных по времени процедурах.

Как правило, в качестве начального индекса для размещения данных берется значение хеш-кода по модулю равному размеру таблицы (не самый лучший способ). Если ячейка занята, то проверяется ячейка с большим индексом и т.д. по кругу, пока не будет найдена свободная (тоже не самый лучший способ). Аналогично поступают и при поиске: переходят к следующей ячейке, пока не совпадает хеш-код и ключ или пока не найдут пустую ячейку. Вопрос в том, как именно помечать пустую ячейку.

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

Когда в таблице остается слишком мало пустых ячеек, ее размер автоматически удваивается, чтобы коэффициент заполнения не превышал 3/4. Довольно плотное заполнение таблицы может представлять проблему при поиске данных, т.к. в худшем случае нам придется проверить все занятые ячейки, если при вставке данных их размещение не оптимизировалось. Мы нивелируем эту проблему, применив известный способ ускорения поиска за счет замедления вставки. А именно, будем поддерживать "кольцевую" упорядоченность данных в таблице так, чтобы при вставке и удалении все данные, имеющие меньший начальный индекс, размещались до данных, имеющих больший начальный индекс. Очевидно, что в случае упорядоченных данных поиск можно прекратить досрочно на ячейке, содержащей хеш-код, соответствующий большему начальному индексу.

Надо ли хранить идентификатор объекта в хеш-таблице? Понятно, что для целочисленных идентификаторов этот вопрос не актуален, т.к. их всегда можно преобразовать в хеш-код и обратно функцией "взбалтывания". В отношении строковых идентификаторов все несколько сложнее: с одной стороны хранение в таблице упрощает код, с другой стороны с увеличением размера элемента хеш-таблицы падает скорость работы с ней. Вероятно, все же лучше не дублировать данные и хранить строковый идентификатор только в объекте, пусть даже из-за этого код станет несколько сложнее. При этом сослаться на идентификатор объекта можно двумя способами: через смещение поля в структуре класса или через Getter. Первый чуть быстрее, второй более общий и отличается от первого несколькими строчками кода. Если же идентификатором является буфер с произвольными двоичными данными, то удобнее использовать обратные вызовы и для хеширования, и для сравнения данных.

Ну, вот и все. Теперь вы сами можете написать правильный класс для работы с хеш-таблицами, используя Open addressing Hash table, Linear probing, Robin Hood hashing, Backward shift deletion.

Шутка. К статье прилагается исходный текст модуля ShaDictionaries.pas

Как бонус, кроме хеш-таблицы для хранения объектов со строковыми и двоичными ключами, исходник содержит еще два класса: хеш-таблицу для хранения объектов с целочисленными ключами-идентификаторами и хеш-таблицу целых чисел.

Как это работает

давайте посмотрим на примере класса TShaTaggedObjectDictionary. Центральное место в нем занимает функция FindHashed, которая ищет элемент по хеш-коду и тегу:

function TShaTaggedObjectDictionary.FindHashed(HashCode: integer; const Tag): integer;
var
  c, d: integer;
begin;
  Result:=HashCode;
  d:=0;
  while true do begin;
    Result:=(Result+1) and FLast;
    c:=FItems[Result].Key;
    inc(d);                                                    //inc our distance
    if (Result-c) and FLast<d then break;                      //if empty or current distance less than our distance
    if c<>HashCode then continue;
    if FCompare(Tag, FItems[Result].Obj)<>0 then continue;
    Result:=not Result;                                        //found
    break;
    end;
  Result:=not Result;
  end;

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

Поиск начинается с позиции (HashCode+1) and FLast, где Flast - индекс последнего элемента таблицы, и продолжается по кругу, пока не будет обнаружен элемент, имеющий нужный хеш-код и нужный тег. Поиск может прекратиться досрочно, если мы зашли слишком далеко, т.е. если дистанция между начальной позицией поиска и текущей позицией превышает расстояние между расчетной начальной позицией текущего элемента и текущей позицией.

Может показаться странным, что функция FCompare сравнивает тег с объектом. Ее параметры были выбраны таким образом, чтобы не увеличивать количество вызовов функций, когда тег или адрес тега хранится в объекте, а не в хеш-таблице.

Еще один центр притяжения - функция AddHashed:

function TShaTaggedObjectDictionary.AddHashed(HashCode: integer; const Tag; AObject: pointer): integer;
begin;
  if FCount>=FMaxCount then SetCapacity(0);
  Result:=not FindHashed(HashCode, Tag);
  if Result>=0 then with FItems[Result] do begin;              //if not found then add
    if Key<>Result then ShiftItems(@FItems[0], Result, FLast); //if not empty then shift
    Key:=HashCode;
    Obj:=AObject;
    inc(FCount);
    end;
  end;

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

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

Остальные функции опираются на описанные выше.

Все любят примеры

Пусть требуется сгенерировать миллион различных случайных отрезков с концами (x,y)=(0..39,0..39).

Понятно, что для миллиона отрезков попарное сравнение друг с другом работает недостаточно быстро. Размеры квадрата, в который вписаны отрезки, специально выбраны достаточно малыми, чтобы задача имела очевидное решение с использованием битовой карты. Второе решение - с использованием хеш-таблицы. Есть и другие (например, сортировка), но мы рассматривать их не будем.

В нашем случае объектом будет отрезок, тегом - координаты концов отрезка. Добавим цвет отрезка просто для того, чтобы объект содержал еще хоть что-то, кроме тега, и разница между объектом и его тегом была заметнее:

type
  TCoordinates= record
    x1, y1, x2, y2: integer;
    end;
  TColoredLine= record
    Color: TColor;
    Coord: TCoordinates;
    end;
  PColoredLine= ^TColoredLine; 

Хеш-функция должна хаотично разбрасывать биты координат по всему целочисленному диапазону:

function MyHashFunc(const Tag): integer;
const
  c1= 1158345749;
  c2= integer(int64(c1) * c1);
  c3= integer(int64(c2) * c1);
  c4= integer(int64(c3) * c1);
begin;
  with TCoordinates(Tag) do Result:=c1*x1 + c2*y1 + c3*x2 + c4*y2;
  end;

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

function MyCompareFunc(const Tag; AObject: pointer): integer;
begin;
  with TCoordinates(Tag), PColoredLine(AObject)^ do
  Result:=(x1 xor Coord.x1)
       or (y1 xor Coord.y1)
       or (x2 xor Coord.x2);
//     or (y2 xor Coord.y2); //если совпали хеши и 3 координаты, то и четвертые координаты обязательно совпадут
  end;

Чтобы упростить сравнение отрезков и обеспечить однозначное вычисление хеша отрезка необходимо использовать нормализованное представление отрезков. Первой точкой отрезка будем считать точку с меньшей x-координатой, а при их равенстве - с меньшей y-координатой:

procedure GenerateLine(var ColoredLine: TColoredLine; RandMod: integer);
var
  z: integer;
begin;
  with ColoredLine do begin;
    Color:=Random(256*256*256);
    Coord.x1:=Random(RandMod);
    Coord.y1:=Random(RandMod);
    Coord.x2:=Random(RandMod);
    Coord.y2:=Random(RandMod);
    if (Coord.x2<Coord.x1)
    or (Coord.x2=Coord.x1) and (Coord.y2<Coord.y1) then begin;
      z:=Coord.x1; Coord.x1:=Coord.x2; Coord.x2:=z;
      z:=Coord.y1; Coord.y1:=Coord.y2; Coord.y2:=z;
      end;
    end;
  end;

Два решения (с использованием битовой карты и хеш-таблицы) позволяют выполнить взаимную проверку:

procedure TForm1.bLinesClick(Sender: TObject);
const
  RandMod= 40; //max=256 because 32-bit calculation
  Count= 1000*1000;
var
  ColoredLines: array of TColoredLine;
  map: array of byte;
  OD: TShaTaggedObjectDictionary;
  seed, i, u, v, total: integer;
  ticks: cardinal;
begin;
  Randomize; seed:=RandSeed;
  SetLength(ColoredLines, Count);
 
  SetLength(map, (int64(RandMod)*RandMod*RandMod*RandMod+7) shr 3);
  FillChar(map[0], Length(map), 0);
  ticks:=GetTickCount;
  total:=0;
  for i:=0 to Count-1 do begin;
    repeat;
      GenerateLine(ColoredLines[i], RandMod);
      inc(total);
      with ColoredLines[i].Coord do u:=x1*(RandMod*RandMod*RandMod) + y1*(RandMod*RandMod) + x2*RandMod + y2;
      v:=1 shl (u and 7);
      u:=u shr 3;
      until map[u] and v=0;
    map[u]:=map[u] or v;
    end;
  ticks:=GetTickCount-ticks;
  Memo1.Lines.Add(Format('Memory map:  %d msec,  %d lines,  %d tests,  RandMod=%d', [ticks, Count, total, RandMod]));
 
  RandSeed:=seed;
  OD:=TShaTaggedObjectDictionary.Create(Count, false, MyCompareFunc, MyHashFunc);
  ticks:=GetTickCount;
  total:=0;
  for i:=0 to Count-1 do begin;
    repeat;
      GenerateLine(ColoredLines[i], RandMod);
      inc(total);
      until OD.Add(ColoredLines[i].Coord, @ColoredLines[i])>=0;
    end;
  ticks:=GetTickCount-ticks;
  Memo1.Lines.Add(Format('Dictionary:  %d msec,  %d lines,  %d tests,  RandMod=%d', [ticks, OD.Count, total, RandMod]));
  OD.Free;
 
  ticks:=GetTickCount;
  total:=0;
  for i:=0 to Count-1 do begin;
    with ColoredLines[i].Coord do u:=x1*(RandMod*RandMod*RandMod) + y1*(RandMod*RandMod) + x2*RandMod + y2;
    v:=1 shl (u and 7);
    u:=u shr 3;
    if map[u] and v<>0 then begin;
      map[u]:=map[u] xor v;
      inc(total);
      end;
    end;
  ticks:=GetTickCount-ticks;
  Memo1.Lines.Add(Format('Validation:  %d msec,  %d equal pairs', [ticks, total]));
  end;

Еще несколько простых примеров использования хеш-таблиц.

Создание и наполнение хеш-таблиц различных типов:

var
  D0: TShaIntegerBox;
  D1: TShaObjectDictionary;
  D2: TShaNamedObjectDictionary;
  D3: TShaTaggedObjectDictionary;
 
type
  TMyObject= class(TObject)
    public
      Id: integer;
      Name: string;
      constructor Create(AId: integer; const AName: string);
    end;
 
function TaggedCompare(const Tag; AObject: pointer): integer;
begin;
  Result:=ord(string(Tag)<>TMyObject(AObject).Name);
  end;
 
function TaggedHash(const Tag): integer;
begin;
  Result:=ShaPerfectHash(string(Tag));
  end;
 
constructor TMyObject.Create(AId: integer; const AName: string);
begin;
  inherited Create;
  Id:=AId;
  Name:=AName;
  end;
 
procedure TForm1.bFillClick(Sender: TObject);
var
  i: integer;
  o: TMyObject;
begin;
  D0:=TShaIntegerBox.Create;
  D1:=TShaObjectDictionary.Create;
  D2:=TShaNamedObjectDictionary.Create(0, false, @TMyObject(nil).Name-pchar(nil));
  D3:=TShaTaggedObjectDictionary.Create(0, false, TaggedCompare, TaggedHash);
  for i:=0 to 7 do begin;
    o:=TMyObject.Create(73+i, chr(i+ord('a')));
    ListBox1.AddItem(o.Name, o);
    D0.Add(o.Id);
    D1.Objects[o.Id]:=o;
    D2.Objects[o.Name]:=o;
    D3.Objects[o.Name]:=o;
    end;
  end;

Поиск в хеш-таблицах:

procedure TForm1.bFindClick(Sender: TObject);
var
  i, id, cnt: integer;
  name: string;
  o: TMyObject;
begin;
  cnt:=0;
  for i:=0 to 7 do begin;
    id:=73+i;
    name:=chr(i+ord('a'));
    if D0.Find(id)>=0 then inc(cnt);
    o:=D1.Objects[id]; if (o<>nil) and (o.Id=id) then inc(cnt);
    o:=D2.Objects[name]; if (o<>nil) and (o.Name=name) then inc(cnt);
    o:=D3.Objects[name]; if (o<>nil) and (o.Name=name) then inc(cnt);
    end;
  Memo1.Lines.Add(Format('----- cnt=%d', [cnt]));
  end;

Удаление из хеш-таблиц:

procedure TForm1.bRemoveClick(Sender: TObject);
var
  s: string;
begin;
  D0.Remove(77);
  D1.Remove(77);
  D2.Remove('e');
  s:='e'; D3.Remove(s);
  end;

Добавление в хеш-таблицы:

procedure TForm1.bAddClick(Sender: TObject);
var
  o: TMyObject;
begin;
  pointer(o):=ListBox1.Items.Objects[5];
  D0.Add(o.Id);
  D1.Add(o.Id, o);
  D2.Add(o.Name, o);
  D3.Add(o.Name, o);
  end;

Получение количества хранимых элементов и итерация:

procedure TForm1.bShowClick(Sender: TObject);
var
  i, j: integer;
  o: TMyObject;
begin;
  Memo1.Lines.Add(Format('----- D0.Count=%d', [D0.Count]));
  j:=0; 
  for i:=0 to D0.Count-1 do
    Memo1.Lines.Add(Format('%d', [D0.GetNext(j)]));
 
  Memo1.Lines.Add(Format('----- D1.Count=%d', [D1.Count]));
  j:=0; 
  for i:=0 to D1.Count-1 do begin;
    o:=D1.GetNext(j); Memo1.Lines.Add(Format('%d %s', [o.Id, o.Name]));
    end;
 
  Memo1.Lines.Add(Format('----- D2.Count=%d', [D2.Count]));
  j:=0; 
  for i:=0 to D2.Count-1 do begin;
    o:=D2.GetNext(j); Memo1.Lines.Add(Format('%d %s', [o.Id, o.Name]));
    end;
 
  Memo1.Lines.Add(Format('----- D3.Count=%d', [D3.Count]));
  j:=0; 
  for i:=0 to D3.Count-1 do begin;
    o:=D3.GetNext(j); Memo1.Lines.Add(Format('%d %s', [o.Id, o.Name]));
    end;
 
  end;

Как всегда, в погоне за скоростью была утеряна читаемость кода и совместимость с классами TDictionary, TObjectDictionary. Хочется надеяться, что все это работает достаточно быстро по сравнению с другими похожими компонентами.

на главную

Прикрепленный файлРазмер
ShaDictionaries.pas34.09 кб