几种常用的字符串Hash

明天就NOIP了..

今天找到一堆常用的字符串Hash算法.贴出来分享+以后自己找也方便..

RS Hash:

function RSHash(S: string): Cardinal;
var
  a, b: Cardinal;
  I: Integer;
begin
  Result := 0;
  a := 63689;
  b := 378551;
  for I := 1 to Length(S) do
  begin
    Result := Result * a + Ord(S[I]);
    a := a * b;
  end;
  Result := Result and $7FFFFFFF;
end;

JS Hash

function JSHash(S: string): Cardinal;
var
  I: Integer;
begin
  Result := 1315423911;
  for I := 1 to Length(S) do
  begin
    Result := ((Result shl 5) + Ord(S[I]) + (Result shr 2)) xor Result;
  end;
  Result := Result and $7FFFFFFF;
end;

P.J.Weinberger Hash

function PJWHash(S: string): Cardinal;
var
  OneEighth,
  ThreeQuarters,
  BitsInUnignedInt,
  HighBits,
  test: Cardinal;
  I: Integer;
begin
  Result := 0;
  test   := 0;
  BitsInUnignedInt := SizeOf(Cardinal) * 8;
  ThreeQuarters    := BitsInUnignedInt * 3 div 4;
  OneEighth        := BitsInUnignedInt div 8;
  HighBits         := $FFFFFFFF shl (BitsInUnignedInt - OneEighth);
  for I := 1 to Length(S) do
  begin
    Result := (Result shl OneEighth) + Ord(S[I]);
    test   := Result and HighBits;
    if test <> 0 then Result := ((Result xor (test shr ThreeQuarters)) and not HighBits);
  end;
  Result := Result and $7FFFFFFF;
end;

最普遍的 ELF Hash:

function ELFHash(S: string): Cardinal;
var
  X: Cardinal;
  I: Integer;
begin
  Result := 0;
  X := 0;
  for I := 1 to Length(S) do
  begin
    Result := (Result shl 4) + Ord(S[I]);
    X := Result and $F0000000;
    if X <> 0 then
    begin
      Result := Result xor (X shr 24);
      Result := Result and not X;
    end;
  end;
  Result := Result and $7FFFFFFF;
end;

简单的BKDR Hash

function BKDRHash(S: string): Cardinal;
var
  seed: Cardinal;
  I: Integer;
begin
  Result := 0;
  seed   := 131;  // 31 131 1313 13131 131313 etc..
  for I := 1 to Length(S) do
  begin
    Result := Result * seed + Ord(S[I]);
  end;
  Result := Result and $7FFFFFFF;
end;

SDBM Hash

function SDBMHash(S: string): Cardinal;
var
  I: Integer;
begin
  Result := 0;
  for I := 1 to Length(S) do
  begin
    Result := Ord(S[I]) + (Result shl 6) + (Result shl 16) - Result;
  end;
  Result := Result and $7FFFFFFF;
end;

DJB Hash

function DJBHash(S: string): Cardinal;
var
  I: Integer;
begin
  Result := 5381;
  for I := 1 to Length(S) do
  begin
    Result := Result + (Result shl 5) + Ord(S[I]);
  end;
  Result := Result and $7FFFFFFF;
end;

AP Hash:

function APHash(S: string): Cardinal;
var
  I: Integer;
begin
  Result := 0;
  for I := 1 to Length(S) do
  begin
    if (i and 1) <> 0 then
      Result := Result xor ((Result shl 7) xor Ord(S[I]) xor (Result shr 3))
    else
      Result := Result xor (not (Result shl 11)  xor Ord(S[I]) xor (Result shr 5));
  end;
  Result := Result and $7FFFFFFF;
end;

, ,

现在只有1个回复

  1. EvilSound Says @ 08-11-14 7:06 下午

    mr要参加NOIP啊。。真羡慕哦
    祝NO.1

看完了要说点啥么?