Fast hash functions??

[User137]

At the beginning variable hash is not initialized, because at that point len has no value. Variables that are defined in a procedure are not automatically reset to 0, they can have any imaginary random value.

hash := len;

[chronozphere]

Thanks for pointing that out.

[Jimmy Valavanis]

Here is a version with very little changes that runs at least twice as faster (compiled with Delphi 7)

program testhash;

{$APPTYPE CONSOLE}


uses Windows, SysUtils;


function getWord(const data: PChar): Word;
begin
  Result := PWord( data )^;
end;

function SuperFastHash(const str: String): Cardinal;
var
  data:         PChar;
  hash, tmp:    Cardinal;
  rem, len:     Integer;
begin
  Result := 0;
  if str = '' then Exit;

  len  := Length(str);
  hash := len;

  data := PChar(str);

  rem := len and 3;
  len := len shr 2;

  //Main loop
  while len > 0 do
  begin
    hash := hash + getWord( data );
    tmp := (getWord( data+2 ) shl 11) xor hash;
    hash := (hash shl 16) xor tmp;
    data := data + 2 * sizeof(Word);
    hash := hash + (hash shr 11);
    dec(len);
  end;

  //Handle end cases
  case rem of
  3:  begin
        hash := hash + getWord(data);
        hash := hash xor (hash shl 16);
        hash := hash xor (byte(data[ sizeof(Word) ]) shl 18);
        hash := hash + (hash shr 11);
      end;
  2:  begin
        hash := hash + getWord(data);
        hash := hash xor (hash shl 11);
        hash := hash + (hash shr 17);
      end;
  1:  begin
        hash := hash + PByte(data)^;
        hash := hash xor (hash shl 10);
        hash := hash + (hash shr 1);
      end;
  end;

  //Force avalanching of final 127 bits
  hash := hash xor (hash shl 3);
  hash := hash +   (hash shr 5);
  hash := hash xor (hash shl 4);
  hash := hash +   (hash shr 17);
  hash := hash xor (hash shl 25);
  hash := hash +   (hash shr 6);

  Result := hash;
end;



function SuperFastHash2(const str: String): Cardinal;
var
  data:         PChar;
  hash, tmp:    Cardinal;
  rem, len:     Integer;
begin
  Result := 0;
  if str = '' then Exit;
  len  := Length(str);
  hash := len;

  data := @str[1];

  rem := len and 3;
  len := len shr 2;

  //Main loop
  while len > 0 do
  begin
    hash := hash + PWord( data )^;
    inc(data, 2);
    tmp := (PWord( data )^ shl 11) xor hash;
    hash := (hash shl 16) xor tmp;
    inc(data, 2);
    hash := hash + (hash shr 11);
    dec(len);
  end;

  //Handle end cases
  case rem of
  3:  begin
        hash := hash + PWord( data )^;
        hash := hash xor (hash shl 16);
        hash := hash xor (byte(data[ sizeof(Word) ]) shl 18);
        hash := hash + (hash shr 11);
      end;
  2:  begin
        hash := hash + PWord( data )^;
        hash := hash xor (hash shl 11);
        hash := hash + (hash shr 17);
      end;
  1:  begin
        hash := hash + PByte(data)^;
        hash := hash xor (hash shl 10);
        hash := hash + (hash shr 1);
      end;
  end;

  //Force avalanching of final 127 bits
  hash := hash xor (hash shl 3);
  hash := hash +   (hash shr 5);
  hash := hash xor (hash shl 4);
  hash := hash +   (hash shr 17);
  hash := hash xor (hash shl 25);
  hash := hash +   (hash shr 6);

  Result := hash;
end;

var
  I, J: Integer;
  T1, T2, F: Int64;
  ms: Single;
  Strings: array [0..2] of string;
const
  NUMBER = 5000000;
begin
  for I := 0 to 2 do
    for J := 0 to 255 do
      Strings[I] := Strings[I] + Char(Random(255));

  Randomize();


  writeln('Strarting 1st method');

  QueryPerformanceCounter(T1);

  for I := 0 to NUMBER do
    SuperFastHash( Strings[ ((I mod 5)*(I mod 8)+2) mod 3 ] );

  QueryPerformanceCounter(T2);
  QueryPerformanceFrequency(F);
  ms := ((T2 - T1) / F) * 1000;
  writeln('Finished 1st method');

  writeln(IntToStr(NUMBER)+' executions in: '+Format('%3.3n',[ms])+'ms');

//-----------------------------------------------------------------

  writeln('Strarting 2st method');

  QueryPerformanceCounter(T1);

  for I := 0 to NUMBER do
    SuperFastHash2( Strings[ ((I mod 5)*(I mod 8)+2) mod 3 ] );

  QueryPerformanceCounter(T2);
  QueryPerformanceFrequency(F);
  ms := ((T2 - T1) / F) * 1000;
  writeln('Finished 2st method');

  writeln(IntToStr(NUMBER)+' executions in: '+Format('%3.3n',[ms])+'ms');

  readln;
end.

First method uses the function you posted, the second method has some minor changes (just get rid of getWord function)

[chronozphere]

Hah great. Thanks for that one.

I was actually looking for a fast string hashing function, but I realize now that this is not really suitable. I'm talking about short < 32char strings.
Does anyone know a good/fast hash for those?

Thanks!