Простая функция хеширования строк

Question

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

Существуют ли более простые / быстрые методы?

Answer 1

Хэш FNV-1a является быстрым и простым в реализации.

Answer 2

См. http://www.strchr.com/hash_functions для очень хорошей панели функций хеширования.

В реализации Delphi есть несколько версий:

Первое, что приходит на ум, это то, которое используется вTStringHash.HashOf метод из официальной IniFiles.pas единицы.В том числе более быстрая версия asm:

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}

Классический хеш Кернигана и Ричи из «Языка программирования C», 3-е издание - не самый лучший, но простой и эффективный код.

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;

Быстрый "Adler" CRC, реализованный в zlib - оптимизированной версии asm здесь :

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;

Мой собственный более быстрый вариант - не реентерабельный, но более быстрый, так как он будет читаться DWORD- и еще более быстрая версия asm здесь :

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;

Классическая версия CRC32 - вы можете найти очень оптимизированную версию asm (с использованием 8 таблиц) здесь :

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;

Answer 3

Как указал Dummy00001, об этом уже спрашивали и отвечали. Взгляните на Лучший алгоритм для значений хэширования чисел? , особенно предложение использовать MurmurHash.

Я бы порекомендовал MurmurHash, потому что:

1. Это очень быстро.

2. Его распределение и лавинные характеристики превосходны для некриптографического хэша.

3. Его худшее поведение все еще довольно хорошо.

Я использовал это. Это не отстой.

1024 * редактировать *

Было много дискуссий о том, как лучше всего перенести его на Delphi, на https://forums.embarcadero.com/thread.jspa?threadID=13902&tstart=0. Полученный код доступен на https://forums.codegear.com/thread.jspa?threadID=14879

Delphi перевод

function Murmur2(const S: AnsiString; const Seed: LongWord=$9747b28c): LongWord;
var
    h: LongWord;
    len: LongWord;
    k: LongWord;
    data: Integer;
const
    // 'm' and 'r' are mixing constants generated offline.
    // They're not really 'magic', they just happen to work well.
    m = $5bd1e995;
    r = 24;
begin
    len := Length(S);

    //The default seed, $9747b28c, is from the original C library

    // Initialize the hash to a 'random' value
    h := seed xor len;

    // Mix 4 bytes at a time into the hash
    data := 1;

    while(len >= 4) do
    begin
        k := PLongWord(@S[data])^;

        k := k*m;
        k := k xor (k shr r);
        k := k* m;

        h := h*m;
        h := h xor k;

        data := data+4;
        len := len-4;
    end;

    {   Handle the last few bytes of the input array
            S: ... $69 $18 $2f
    }
    Assert(len <= 3);
    if len = 3 then
        h := h xor (LongWord(s[data+2]) shl 16);
    if len >= 2 then
        h := h xor (LongWord(s[data+1]) shl 8);
    if len >= 1 then
    begin
        h := h xor (LongWord(s[data]));
        h := h * m;
    end;

    // Do a few final mixes of the hash to ensure the last few
    // bytes are well-incorporated.
    h := h xor (h shr 13);
    h := h * m;
    h := h xor (h shr 15);

    Result := h;
end;

Проходит все самотестирования из исходной реализации C .

Answer 4

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

Мой текущий метод - это просто сложить все ASCII-числа символов вместе и взять их в качестве размера массива.1006 *

Вы отбрасываете важную информацию, которая является положением символа в строке.Это плохая идея, так как тогда строки "AB" и "BA" будут иметь одинаковое хеш-значение.

Вместо простого сложения, сохраняя его примитивным, можно использовать выражение типа hash = hash*P1 + str[i]*P2 + P3;, где P i - некоторые простые числа.Вот как я это делаю, если мне нужна быстрая хэш-функция.Я часто использую 7, 5 и 3 в качестве простых чисел, но числа должны быть явно скорректированы (а также начальное значение hash), чтобы результат хэш-функции можно было использовать в вашей задаче.

Дляподробнее читайте соответствующую (и довольно информативную) статью в Википедии .

Answer 5

Я перепробовал много быстрых хеш-функций и выбрал эту:

function StrHash(const st:string):cardinal; 
 var
  i:integer;
 begin
  result:=0;
  for i:=1 to length(st) do
   result:=result*$20844 xor byte(st[i]);
 end;

Это так же быстро, как функция K & R (на самом деле даже быстрее), но обеспечивает лучшее (более равномерное) распределение.

Answer 6

Очень простой способ - просто XOR для всех значений. Самый простой, насколько я знаю.