Рассмотрим особенности реализации в Delphi 7 класса хеш-таблицы с открытой адресацией и линейным зондированием для хранения данных с целочисленными, строковыми и двоичными ключами, а также для работы с множествами и мультимножествами целых чисел. Исходники и текст статьи обновлены 12.05.2021.
Хеш-функции
Назначение хеш-функции - преобразовать идентификатор объекта в число, которое впоследствии можно использовать для поиска объекта. Простейшая строковая 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 ShaDictionaryHash(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; end;
Пусть множитель не смущает читателя: это обратный элемент для 33.
Две последние хеш-функции не имеют коллизий на словаре Лопатина (более 150000 русских слов) и дают хорошее распределение слов по 2^18=262144 ячейкам хеш-таблицы (более 48000 кластеров, максимальный размер кластера в зависимости от тасующих множителей составляет примерно 40 занятых ячеек).
На первый взгляд кажется, что алгоритм ShaPerfectHash представляет собой одну длинную цепь зависимых вычислений, и его почти невозможно заметно ускорить. Однако это не так. Ассемблерная версия алгоритма на компьютере с процессором E6850/3.0GHz вычисляет хеш со скоростью более 2.2*10^9 байтов в секунду, которая достигнута благодаря тому, что для раздельного суммирования выделено 4 регистра.
У пытливого читателя наготове еще вопрос: что делать, если идентификаторы объекта не являются строками? Преобразовать в строку? А если идентификатор целое число? Преобразовать целое в строку, чтобы потом функция хеширования вернула опять же целое? Зачем? Действительно, незачем. Ничего другого, кроме коллизий хеш-кодов, так не добиться. Если, например, мы имеем дело с последовательными значениями, то можно вообще ничего не делать. С другой стороны, если идентификаторы это цвета точек, или координаты пересечения окружностей с границами прямоугольника, или последовательные значения, полученные от любителей разбивать яйца с другого конца, то не помешает избавиться от возможной регулярности значений идентификаторов, взболтав их как следует. Функция "взбалтывания" - любое взаимно-однозначное преобразование, при котором младшие биты результата становятся похожи на случайные, например:
function ShaMix(i: integer): integer; begin; i:=i * 1443687719; i:=i shr 4 xor i; i:=i shr 12 xor i; i:=i shr 15 xor i; i:=i * -1866451833; Result:=i; end;
Взаимная однозначность функции "взбалтывания" позволяет нам при необходимости восстановить идентификатор объекта по хеш-коду:
function ShaUnmix(i: integer): integer; begin; i:=i * -1262857929; //-1866451833^-1 i:=i shr 15 xor i; i:=i shr 30 xor i; i:=i shr 12 xor i; i:=i shr 24 xor i; i:=i shr 4 xor i; i:=i shr 8 xor i; i:=i shr 16 xor i; i:=i * 630043287; //1443687719^-1 Result:=i; 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 специальных значения для каждой ячейки. Удивительно, что этот прием до сих пор остается не известен сторонникам "надгробий" - специальных значений, которыми после удаления данных из хеш-таблицы помечаются освободившиеся ячейки. В нашем коде "надгробия" не используются, все незанятые ячейки таблицы должны быть свободны. Для ликвидации образующихся при удалении данных дыр в кластерах мы используем обратный сдвиг данных.
Когда в таблице остается слишком мало пустых ячеек, ее размер автоматически удваивается, чтобы коэффициент заполнения не превышал 5/8, обеспечивая быструю вставку новых элементов.
Довольно плотное заполнение таблицы также может представлять проблему при поиске данных, т.к. в худшем случае нам придется проверить все занятые ячейки кластера, если при вставке данных их размещение не оптимизировалось. Мы нивелируем эту проблему, поддерживая "кольцевую" упорядоченность данных в таблице так, чтобы при вставке и удалении все данные, имеющие меньший начальный индекс, размещались до данных, имеющих больший начальный индекс. Очевидно, что в случае упорядоченных данных поиск можно прекратить досрочно на той ячейке кластера, которая содержит хеш-код, соответствующий большему начальному индексу.
Надо ли хранить идентификатор объекта в хеш-таблице? Понятно, что для целочисленных идентификаторов этот вопрос не актуален, т.к. их всегда можно преобразовать в хеш-код и обратно функцией "взбалтывания". В отношении строковых идентификаторов все несколько сложнее: с одной стороны хранение в таблице упрощает код, с другой стороны с увеличением размера элемента хеш-таблицы падает скорость работы с ней. Вероятно, все же лучше не дублировать данные и хранить строковый идентификатор только в объекте, пусть даже из-за этого код станет несколько сложнее. При этом сослаться на идентификатор объекта можно двумя способами: через смещение поля в структуре класса или через Getter. Первый чуть быстрее, второй более общий и отличается от первого несколькими строчками кода. Если же идентификатором является буфер с произвольными двоичными данными, то удобнее использовать обратные вызовы и для хеширования, и для сравнения данных.
Ну, вот и все. Теперь вы сами можете написать правильный класс для работы с хеш-таблицами, используя Open addressing Hash table, Linear probing, Robin Hood hashing, Backward shift deletion.
Шутка. К статье прилагается исходный текст модуля ShaDictionaries.pas
Как бонус, кроме хеш-таблиц для хранения объектов со целочисленными, строковыми и двоичными ключами, исходник содержит еще два класса: хеш-таблицы для работы с множествами и мультимножествами целых чисел.
Все хеш-таблицы могут работать с десятками миллионов элементов без потери производительности. Время любой операции (за исключением операций, приводящих к изменению размера таблицы) не превышает 50 нсек на i7-7700. Однако, в погоне за скоростью пришлось частично пожертвовать совместимостью с классами TDictionary, TObjectDictionary.
Как это работает
давайте посмотрим на примере класса TShaTaggedObjectDictionary. Центральное место в нем занимает функция IndexOfHashed, которая ищет элемент по хеш-коду и тегу:
function TShaTaggedObjectDictionary.IndexOfHashed(HashCode: integer; const Tag): integer;
var
c, d: integer;
begin;
Result:=HashCode;
d:=0;
while true do begin;
Result:=(Result+1) and FLast;
with FItems[Result] do begin;
c:=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, Obj)<>0 then continue;
Result:=not Result; //found
break;
end;
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 Grow;
Result:=not IndexOfHashed(HashCode, Tag);
if Result>=0 then with FItems[Result] do begin; //if not found then add
if Key<>Result then ShiftDictionaryItems(@FItems[0], Result, FLast); //if not empty then shift
Key:=HashCode;
Obj:=AObject;
inc(FCount);
end;
end;Если в хеш-таблице отсутствует элемент с указанными хеш-кодом и тегом, то функция добавляет в таблицу соответствующий элемент и возвращает его индекс (неотрицательный результат), а если такой элемент уже имеется, то возвращается побитно инвертированный индекс позиции, в которой он находится (отрицательный результат).
Сначала проверяется достаточно ли свободного места в таблице, и при необходимости таблица расширяется. Затем вызывается функция IndexOfHashed, и ее результат инвертируется, чтобы добавить элемент только в случае его отсутствия в таблице. В качестве места вставки функция IndexOfHashed может "предложить" уже занятое место, в этом случае перед вставкой элемента занятое место освобождается при помощи сдвига по кругу "мешающих" элементов.
Остальные функции опираются на описанные выше.
Все любят примеры
Пусть требуется сгенерировать миллион различных случайных отрезков с концами (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;
TOD: 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;
TOD:=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 TOD.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, TOD.Count, total, RandMod]));
TOD.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;Еще несколько простых примеров
Создание и наполнение хеш-таблиц различных типов:
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:=ShaPerfectHashStr(string(Tag));
end;
constructor TMyObject.Create(AId: integer; const AName: string);
begin;
inherited Create;
Id:=AId;
Name:=AName;
end;
var
IB: TShaIntegerBox;
IM: TShaIntegerMultibox;
OD: TShaObjectDictionary;
NOD: TShaNamedObjectDictionary;
TOD: TShaTaggedObjectDictionary;
procedure TForm1.bFillClick(Sender: TObject);
var
i: integer;
o: TMyObject;
begin;
IB:=TShaIntegerBox.Create;
IM:=TShaIntegerMultibox.Create;
OD:=TShaObjectDictionary.Create;
NOD:=TShaNamedObjectDictionary.Create(0, false, @TMyObject(nil).Name-pchar(nil));
TOD:=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);
IB.Add(o.Id);
IM.Sum[o.Id]:=1;
OD.Objects[o.Id]:=o;
NOD.Objects[o.Name]:=o;
TOD.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 IB.IndexOf(id)>=0 then inc(cnt);
if IM.Sum[id]<>0 then inc(cnt);
o:=OD.Objects[id]; if (o<>nil) and (o.Id=id) then inc(cnt);
o:=NOD.Objects[name]; if (o<>nil) and (o.Name=name) then inc(cnt);
o:=TOD.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;
IB.Remove(77); IB.Remove(78);
IM.Remove(77); IM.Remove(78);
OD.Remove(77); OD.Remove(78);
NOD.Remove('e');
NOD.Remove('f');
s:='e'; TOD.Remove(s);
s:='f'; TOD.Remove(s);
end;Добавление в хеш-таблицы:
procedure TForm1.bAddClick(Sender: TObject); var o: TMyObject; begin; pointer(o):=ListBox1.Items.Objects[5]; IB.Add(o.Id); IM.AddAndGetSum(o.Id, 1); OD.Add(o.Id, o); NOD.Add(o.Name, o); TOD.Add(o.Name, o); end;
Получение количества хранимых элементов и итерация:
procedure TForm1.bShowClick(Sender: TObject);
var
i, j, sum: integer;
o: TMyObject;
begin;
j:=0; Memo1.Lines.Add(Format('----- IB.Count=%d', [IB.Count]));
for i:=0 to IB.Count-1 do
Memo1.Lines.Add(Format('%d', [IB.GetNextId(j)]));
j:=0; Memo1.Lines.Add(Format('----- IM.Count=%d', [IM.Count]));
for i:=0 to IM.Count-1 do
Memo1.Lines.Add(Format('%d', [IM.GetNextId(j,sum)]));
j:=0; Memo1.Lines.Add(Format('----- OD.Count=%d', [OD.Count]));
for i:=0 to OD.Count-1 do begin;
o:=OD.GetNextObject(j); Memo1.Lines.Add(Format('%d %s', [o.Id, o.Name]));
end;
j:=0; Memo1.Lines.Add(Format('----- NOD.Count=%d', [NOD.Count]));
for i:=0 to NOD.Count-1 do begin;
o:=NOD.GetNextObject(j); Memo1.Lines.Add(Format('%d %s', [o.Id, o.Name]));
end;
j:=0; Memo1.Lines.Add(Format('----- TOD.Count=%d', [TOD.Count]));
for i:=0 to TOD.Count-1 do begin;
o:=TOD.GetNextObject(j); Memo1.Lines.Add(Format('%d %s', [o.Id, o.Name]));
end;
end;| Прикрепленный файл | Размер |
|---|---|
| ShaDictionaries.pas | 43.42 кб |