1. Поиск с использованием хеш-функции
Вот как вы можете реализовать функцию хеширования в своем поиске:
- Каждая запись имеет свое собственное доступное хэшированное значение - оно должно храниться в базе данных, чтобы сэкономить время: вам не придется вычислять его каждый раз;
- Чтобы выяснить, существует ли уже существующая запись, вычислите ее хэшированное значение, затем сравните этот хеш со списком хэшей - при совпадении используйте CompareMem, чтобы убедиться (возможны коллизии, поскольку ни одна хэш-функция не является идеальной).
У вас есть два способа сравнить хэш новой записи со списком хешей:
- Грубая сила просто перебирает все хэши и сравнивает их - быстрее, чем CompareMem, но будет O (n), то есть будет медленнее, когда вы добавляете записи;
- Используйте таблицу поиска хешей вместо списка хешей - этот размер таблицы поиска обычно равен степени двух, больше, чем основной список хешей.
Хеш-таблица поиска - лучший вариант, ИМХО. Вот как модуль Generics.Collections реализует это в современном Delphi. Используйте, если можете.
Для варианта, использующего простое содержимое record (включая строки и вложенные динамические массивы), вы можете взглянуть на нашу TDynArrayHashed оболочку.
В этом случае таблица поиска - это просто массив, содержащий 32-разрядное хеш-значение без знака и индекс элемента в массиве:
TSynHash = record
Hash: cardinal;
Index: cardinal;
end;
TSynHashDynArray = array of TSynHash;
Вот, например, как поиск по хеш-таблице заполняется с нуля:
procedure TDynArrayHashed.ReHash;
var i, n, PO2, ndx: integer;
P: PAnsiChar;
aHashCode: cardinal;
begin
// find nearest power of two for new fHashs[] size
SetLength(fHashs,0); // any previous hash is invalid
n := Capacity+1; // use Capacity instead of Count for faster process
PO2 := 256;
while PO2<n do
PO2 := PO2 shl 1;
SetLength(fHashs,PO2);
// hash all dynamic array values
P := Value^;
for i := 0 to Count-1 do begin
aHashCode := HashOne(P^);
ndx := HashFind(aHashCode,P^);
if ndx<0 then
// >=0 -> already found -> not necessary to add duplicated hash
with fHashs[-ndx-1] do begin
Hash := aHashCode;
Index := i;
end;
inc(P,ElemSize);
end;
end;
Вот как выполняется поиск элемента в таблице поиска хэшей:
function TDynArrayHashed.HashFind(aHashCode: cardinal; const Elem): integer;
var n, first: integer;
looped: boolean;
begin
looped := false;
n := length(fHashs);
result := (aHashCode-1) and (n-1); // fHashs[] has a power of 2 length
first := result;
repeat
with fHashs[result] do
if Hash=aHashCode then begin
if ElemEquals(PAnsiChar(Value^)[Index*ElemSize],Elem) then begin
result := Index;
exit; // found -> returns index in dynamic array
end;
end else
if Hash=0 then begin
result := -(result+1);
exit; // not found -> returns void index in fHashs[] as negative
end;
// hash colision -> search next item
inc(result);
if result=n then
// reached the end -> search once from fHash[0] to fHash[first-1]
if looped then
Break else begin
result := 0;
n := first;
looped := true;
end;
until false;
raise Exception.Create('HashFind'); // we should never reach here
result := -1; // mark not found
end;
Он вызывает ElemEquals для глубокого сравнения содержимого записи в случае коллизии хеша (может всегда происходить). Эта функция использует Delphi RTTI для обработки вложенных строк и (динамических) массивов в содержимом записи. Вы можете использовать CompareMem здесь, если ваша запись - просто двоичный буфер.
2. Хеш-функция
О хэш-функции, которую нужно использовать, несколько. Если вам нужна таблица поиска хеша, вам не понадобятся хэш-функции криптографического уровня (например, SHA-1, MD5 или SHA-256), поскольку вы создадите модуль по размеру таблицы поиска хеша, и эти функции очень медленнее, чем следующий.
Простое возвращение кардинала сделает свое дело - единственная проблема в этом отношении - избежать большинства столкновений. Быстрее Adler32 (или наш Hash32), но вы можете использовать классическую, но все еще быструю хеш-функцию Kernighan & Ritchie, или crc32 (она должна быть доступна в вашем коде, если вы используете, например, zip).
Вот код, возвращающий основное значение из наших библиотек с открытым исходным кодом. Каждая версия имеет оптимизированную функцию ассемблера и версию «чисто паскаль», идеально подходящую для ARM или 64-разрядных.
Хеш-функция Кернигана и Ричи
function kr32(crc: cardinal; buf: PAnsiChar; len: cardinal): cardinal;
{$ifdef PUREPASCAL}
var i: integer;
begin
for i := 0 to len-1 do
crc := ord(buf[i])+crc*31;
result := crc;
end;
{$else}
asm // eax=crc, edx=buf, ecx=len
or ecx,ecx
push edi
push esi
push ebx
push ebp
jz @z
cmp ecx,4
jb @s
@8: mov ebx,[edx] // unrolled version reading per DWORD
lea edx,edx+4
mov esi,eax
movzx edi,bl
movzx ebp,bh
shr ebx,16
shl eax,5
sub eax,esi
lea eax,eax+edi
mov esi,eax
shl eax,5
sub eax,esi
lea esi,eax+ebp
lea eax,eax+ebp
movzx edi,bl
movzx ebx,bh
shl eax,5
sub eax,esi
lea ebp,eax+edi
lea eax,eax+edi
shl eax,5
sub eax,ebp
cmp ecx,8
lea eax,eax+ebx
lea ecx,ecx-4
jae @8
or ecx,ecx
jz @z
@s: mov esi,eax
@1: shl eax,5
movzx ebx,byte ptr [edx]
lea edx,edx+1
sub eax,esi
dec ecx
lea esi,eax+ebx
lea eax,eax+ebx
jnz @1
@z: pop ebp
pop ebx
pop esi
pop edi
end;
{$endif}
Hash32 (модифицированная функция adler32)
function Hash32(Data: pointer; Len: integer): cardinal;
{$ifdef PUREPASCAL} // this code is quite as fast as the optimized asm below
function SubHash(P: PCardinalArray; L: integer): cardinal;
{$ifdef HASINLINE}inline;{$endif}
var s1,s2: cardinal;
i: PtrInt;
const Mask: array[0..3] of cardinal = (0,$ff,$ffff,$ffffff);
begin
if P<>nil then begin
s1 := 0;
s2 := 0;
for i := 1 to L shr 4 do begin // 16 bytes (4 DWORD) by loop - aligned read
inc(s1,P^[0]);
inc(s2,s1);
inc(s1,P^[1]);
inc(s2,s1);
inc(s1,P^[2]);
inc(s2,s1);
inc(s1,P^[3]);
inc(s2,s1);
inc(PtrUInt(P),16);
end;
for i := 1 to (L shr 2)and 3 do begin // 4 bytes (DWORD) by loop
inc(s1,P^[0]);
inc(s2,s1);
inc(PtrUInt(P),4);
end;
inc(s1,P^[0] and Mask[L and 3]); // remaining 0..3 bytes
inc(s2,s1);
result := s1 xor (s2 shl 16);
end else
result := 0;
end;
begin // use a sub function for better code generation under Delphi
result := SubHash(Data,Len);
end;
{$else}
asm // our simple and efficient algorithm (ADLER-32 based) is:
// while(data) do { s1 := s1+DWORD(data); s2 := s2+s1; }
// return (s1 xor (s2 shl 16));
// this asm code is very optimized for modern pipelined CPU
or eax,eax
push ebx
jz @z
mov ecx,edx // ecx = length(Data)
mov edx,eax // edx = Data
xor eax,eax // eax = s1 = 0
xor ebx,ebx // ebx = s2 = 0
push ecx
shr ecx,2
jz @n
push ecx
shr ecx,2
jz @m
nop; nop
@16:add eax,[edx] // 16 bytes (4 DWORD) by loop - aligned read
add ebx,eax
add eax,[edx+4] // both 'add' are pipelined: every DWORD is processed at once
add ebx,eax
add eax,[edx+8]
add ebx,eax
add eax,[edx+12]
add ebx,eax
dec ecx
lea edx,edx+16
jnz @16
@m: pop ecx
and ecx,3
jz @n
nop
@4: add eax,[edx] // 4 bytes (DWORD) by loop
add ebx,eax
dec ecx
lea edx,edx+4
jnz @4
@n: pop ecx
mov edx,[edx] // read last DWORD value
and ecx,3 // remaining 0..3 bytes
and edx,dword ptr [@Mask+ecx*4] // trim to DWORD value to 0..3 bytes
add eax,edx
add ebx,eax
shl ebx,16
xor eax,ebx // return (s1 xor (s2 shl 16))
@z: pop ebx
ret
nop; nop // align @Mask
@Mask: dd 0,$ff,$ffff,$ffffff // to get only relevant byte information
end;
{$endif}
функция crc32
{$define BYFOUR}
// if defined, the crc32 hashing is performed using 8 tables, for better
// CPU pipelining and faster execution
var
// tables content is created from code in initialization section below
// (save 8 KB of code size from standard crc32.obj, with no speed penalty)
crc32tab: array[0..{$ifdef BYFOUR}7{$else}0{$endif},byte] of cardinal;
function crc32(crc: cardinal; buf: PAnsiChar; len: cardinal): cardinal;
// adapted from fast Aleksandr Sharahov version
asm
{$ifdef BYFOUR}
test edx, edx
jz @ret
neg ecx
jz @ret
not eax
push ebx
@head:
test dl, 3
jz @bodyinit
movzx ebx, byte [edx]
inc edx
xor bl, al
shr eax, 8
xor eax,dword ptr [ebx*4 + crc32tab]
inc ecx
jnz @head
pop ebx
not eax
@ret:
ret
@bodyinit:
sub edx, ecx
add ecx, 8
jg @bodydone
push esi
push edi
mov edi, edx
mov edx, eax
@bodyloop:
mov ebx, [edi + ecx - 4]
xor edx, [edi + ecx - 8]
movzx esi, bl
mov eax,dword ptr [esi*4 + crc32tab + 1024*3]
movzx esi, bh
xor eax,dword ptr [esi*4 + crc32tab + 1024*2]
shr ebx, 16
movzx esi, bl
xor eax,dword ptr [esi*4 + crc32tab + 1024*1]
movzx esi, bh
xor eax,dword ptr [esi*4 + crc32tab + 1024*0]
movzx esi, dl
xor eax,dword ptr [esi*4 + crc32tab + 1024*7]
movzx esi, dh
xor eax,dword ptr [esi*4 + crc32tab + 1024*6]
shr edx, 16
movzx esi, dl
xor eax,dword ptr [esi*4 + crc32tab + 1024*5]
movzx esi, dh
xor eax,dword ptr [esi*4 + crc32tab + 1024*4]
add ecx, 8
jg @done
mov ebx, [edi + ecx - 4]
xor eax, [edi + ecx - 8]
movzx esi, bl
mov edx,dword ptr [esi*4 + crc32tab + 1024*3]
movzx esi, bh
xor edx,dword ptr [esi*4 + crc32tab + 1024*2]
shr ebx, 16
movzx esi, bl
xor edx,dword ptr [esi*4 + crc32tab + 1024*1]
movzx esi, bh
xor edx,dword ptr [esi*4 + crc32tab + 1024*0]
movzx esi, al
xor edx,dword ptr [esi*4 + crc32tab + 1024*7]
movzx esi, ah
xor edx,dword ptr [esi*4 + crc32tab + 1024*6]
shr eax, 16
movzx esi, al
xor edx,dword ptr [esi*4 + crc32tab + 1024*5]
movzx esi, ah
xor edx,dword ptr [esi*4 + crc32tab + 1024*4]
add ecx, 8
jle @bodyloop
mov eax, edx
@done:
mov edx, edi
pop edi
pop esi
@bodydone:
sub ecx, 8
jl @tail
pop ebx
not eax
ret
@tail:
movzx ebx, byte [edx + ecx]
xor bl,al
shr eax,8
xor eax,dword ptr [ebx*4 + crc32tab]
inc ecx
jnz @tail
pop ebx
not eax
{$else}
test edx, edx
jz @ret
neg ecx
jz @ret
not eax
sub edx,ecx
push ebx
@next:
movzx ebx, byte [edx + ecx]
xor bl, al
shr eax, 8
xor eax, [ebx*4 + crc32tab]
add ecx, 1
jnz @next
pop ebx
not eax
@ret:
{$endif BYFOUR}
end;
and the associated code to create the tables
procedure InitCrc32Tab;
var i,n: integer;
crc: cardinal;
begin // this code size is only 105 bytes, generating 8 KB table content
for i := 0 to 255 do begin
crc := i;
for n := 1 to 8 do
if (crc and 1)<>0 then
// $edb88320 from polynomial p=(0,1,2,4,5,7,8,10,11,12,16,22,23,26)
crc := (crc shr 1) xor $edb88320 else
crc := crc shr 1;
crc32tab[0,i] := crc;
end;
{$ifdef BYFOUR}
for i := 0 to 255 do begin
crc := crc32tab[0,i];
for n := 1 to 7 do begin
crc := (crc shr 8) xor crc32tab[0,byte(crc)];
crc32tab[n,i] := crc;
end;
end;
{$endif}
end;
С определением BYFOUR этот crc32 очень быстр и имеет меньшее столкновение, чем Hash32 или KR32.
Сравнение хеш-функций см. в этой замечательной статье .
Исходный код см. в нашем репозитории исходного кода .