1。使用哈希函數
在這裏尋找的是你如何可以實現您搜索的散列函數：
- 每條記錄都可用自己的散列值 - 應存儲在數據庫中，以節省時間：你贏了每次都不必計算它;
- 要查找記錄是否已經存在，請計算其散列值，然後將此散列與散列列表進行比較 - 匹配時，請使用CompareMem（可能發生衝突，因爲沒有散列函數是完美的）。
你有新的記錄的散列比較散列表的方式有兩種：通過所有哈希只是循環
- 的蠻力，和他們比較 - 比CompareMem快，但會爲O（n ），添加記錄時速度會變慢;
- 使用散列查找表而不是散列列表 - 此查找表大小通常是2的冪，大於主散列表。
散列查找表是最好的選擇，恕我直言。這就是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 &裏奇散列函數或crc32（如果您使用zip，它應該在您的代碼中可用）。
下面是一些從我們的開源庫中返回基數值的代碼。每個版本都有一個優化的彙編函數和一個「純粹的pascal」版本，非常適合ARM或64位版本。
Kernighan的&裏奇散列函數
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相比具有更少的衝突。
有關散列函數的比較，請參閱this great article。請參考our source code repository。
可能你可以通過使用更大的緩衝區來優化從磁盤讀取數據，但最終你應該使用一個分析器來縮小你正在花費時間的地方。 –
至於散列函數，我的第一個選擇是嘗試SHA-1或MD5散列。你可以嘗試聰明並計算兩個哈希值。一個是數據的一個子集，另一個是整個記錄。對於大多數搜索，計算「快速」散列可能足以確定記錄不相等，因此您可以繼續下一步。 –
@Lieven加密級別SHA-1或MD5並不意味着用於多值比較。他們的目的是檢查數據的完整性。看到我的答案。 –