Chaîne Simple fonction de hachage

Voir http://www.strchr.com/hash_functions pour un très bon panel de fonctions de hachage.

En Delphi mise en œuvre, voici plusieurs versions:

Le premier à venir à l'esprit est celui utilisé dans les TStringHash.HashOf méthode officielle IniFiles.pas unité. Y compris les plus rapides de l'asm version:

function HashOf(P: PByteArray; Len: integer): cardinal;
// algorithm from IniFiles.TStringHash.HashOf
{$ifdef PUREPASCAL}
var I: Integer;
begin
  Result := 0;
  for I := 1 to Len do
    Result := ((Result shl 2) or (Result shr (SizeOf(Result)*8-2))) xor P[I];
end;
{$else}
asm // faster asm version by Synopse
    or edx,edx
    jz @z
    push ebx
    mov ebx,edx     // ebx = length(Key)
    mov edx,eax     // edx = Text
    xor eax,eax     // eax = Result
    xor ecx,ecx     // ecx = Result shl 2 = 0
@1: shr eax,$1e     // eax = Result shr (SizeOf(Result) * 8 - 2))
    or ecx,eax      // ecx = ((Result shl 2) or (Result shr (SizeOf(Result)*8-2)))
    movzx eax,byte ptr [edx] // eax = ord(Key[i])
    inc edx
    xor eax,ecx     // eax = () xor ord(Key[i])
    dec ebx
    lea ecx,[eax*4] // ecx = Result shl 2
    jnz @1
    pop ebx
@z:
end;
{$endif}

Le classique Kernighan &Ritchie de hachage à partir de "The C programming Language", 3e édition - pas le meilleur, mais simple et efficace du code.

function kr32(crc: cardinal; buf: PAnsiChar; len: cardinal): cardinal;
var i: integer;
begin
  for i := 0 to len-1 do
    crc := ord(buf[i])+crc*31;
  result := crc;
end;

Le rapide "Adler" CRC mises en œuvre dans la zlib - optimisé asm version ici:

function Adler32Pas(Adler: cardinal; p: pointer; Count: Integer): cardinal;
var s1, s2: cardinal;
    i, n: integer;
begin
  s1 := LongRec(Adler).Lo;
  s2 := LongRec(Adler).Hi;
  while Count>0 do begin
    if Count<5552 then
      n := Count else
      n := 5552;
    for i := 1 to n do begin
      inc(s1,pByte(p)^);
      inc(cardinal(p));
      inc(s2,s1);
    end;
    s1 := s1 mod 65521;
    s2 := s2 mod 65521;
    dec(Count,n);
  end;
  result := word(s1)+cardinal(word(s2)) shl 16;
end;

Ma propre variante plus rapide - pas de ré-entrant, mais plus rapide car il sera lu par DWORDs - et encore plus asm version ici:

function Hash32(Data: pointer; Len: integer): cardinal;
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;

Le classique CRC32 de version, vous pouvez trouver une très optimisé asm version (à l'aide de 8 tables) ici:

function UpdateCrc32(aCRC32: cardinal; inBuf: pointer; inLen: integer) : cardinal;
var i: integer;
begin
result := aCRC32;
// if we used a dynamic table, we assume we want shorter code size
for i := 1 to inLen do begin
result := crc32Tab[byte(result xor pByte(inBuf)^)] xor (result shr 8);
inc(cardinal(inBuf));
end;
end;

OriginalL'auteur Arnaud Bouchez

Jenkins fonction de hachage devrait vous aider à obtenir commencé.

ma méthode actuelle est de simplement ajouter tous les nombres ASCII des caractères en commun et de la prise de mod la taille de la matrice.

Vous jetez importante de l'information qui est la position du caractère dans la chaîne. C'est une mauvaise idée, depuis les chaînes de "AB" et "BA" aurait même la même valeur de hachage.

Au lieu de plus simple, maintien de la primitive, on peut utiliser l'expression comme hash = hash*P1 + str[i]*P2 + P3; où Pi sont quelques-uns des nombres premiers. C'est comment je fais si j'ai besoin d'une fonction de hachage rapidement. J'utilise souvent de 7, 5 et 3, comme les nombres premiers, mais les chiffres doivent évidemment être ajusté (ainsi que la valeur initiale de hash), de sorte que le résultat de la fonction de hachage est utilisable pour votre tâche.

Pour plus d'informations lire le correspondant (et plutôt instructif) article de Wikipédia.

OriginalL'auteur Dummy00001

Une méthode très simple est juste de XOR toutes les valeurs. Le plus simple pour autant que je sais.

OriginalL'auteur AGee