求高手解惑HashCode的问题

Question

下面是摘抄的一段求HashCode的函数，向高手请教一下这种算法的原理与优点
function HashValue_Str(const Key :String):Cardinal; // 区分大小写
var
  i,Len    : integer;
  pStrChar : PChar;
begin
  result:=0;
  pStrChar:=pChar(Key);
  Len:= length(Key);
  for i:=1 to Len do
  begin
    result:=result*5;
    inc(result,Cardinal(pStrChar^)*37);
    inc(pStrChar);
  end;
end;

Answer 1

HashCode及Hash查找的原理
是用待查字符串本身内容特点产生一个整形数，作为其存到散列表的下标，这个整形数，在不同的字符串尽量不一样。产生速度要快。不同字符串的HashCode可能一样，但是没有关系，它们放到同一个下标不同的空间里(一般的下标上放一个TStringList对象来存不同的字符串)。我们在查一个字符串时，首先按一定规则算出HashCode转化出下标，再在下标的TStringList中遍历查找。
你可以看一下数据结构吧。不难的

Answer 2

我知道你的那些代码是从Delphi中Copy出来的，不过Delphi的那个字符串的HashCode函数有点问题，对于不同的字符串很容易产生一样的结果（也散列的平衡性不好！）

Answer 3

这个是从DGL的HashFunctions.pas单元里面Copy出来的，里面还有支持其他数据类型的HashCode函数，算法大同小异，以为这个算法一定有什么特别的优点，好像《编程玑珠》里面有一个算法与这个很像

Answer 4

优点是简单,速度快.
还有更简略的,直接把每个字节加和.
通常简单的处理Hash函数冲突的机会也大,而要减少冲突的话,算法可能也不会太简单,或者要针对性算法.

Answer 5

呵呵,我搜索了下HashCode,发现有不少:DBTables.pas
    
    function GetHashCode(Str: PChar): Integer;
    var
      Off, Len, Skip, I: Integer;
    begin
      Result := 0;
      Off := 1;
      Len := StrLen(Str);
      if Len < 16 then
        for I := (Len - 1) downto 0 do
        begin
          Result := (Result * 37) + Ord(Str[Off]);
          Inc(Off);
        end
      else
      begin
        { Only sample some characters }
        Skip := Len div 8;
        I := Len - 1;
        while I >= 0 do
        begin
          Result := (Result * 39) + Ord(Str[Off]);
          Dec(I, Skip);
          Inc(Off, Skip);
        end;
      end;
    end;
Graphics.pas
 
function GetHashCode(const Buffer; Count: Integer): Word; assembler;
asm
        MOV     ECX,EDX
        MOV     EDX,EAX
        XOR     EAX,EAX
@@1:    ROL     AX,5
        XOR     AL,[EDX]
        INC     EDX
        DEC     ECX
        JNE     @@1
end;
SysUtils.pas
 
function HashName(Name: PChar): Cardinal;
asm
  PUSH  ESI
  PUSH  EBX
  MOV   ESI, Name
  XOR   EAX, EAX@@loop:
  ROL   EAX, 5
  MOV   BL, [ESI]
  CMP   BL, 0
  JE    @@done
  CMP   BL, 'A'
  JL    @@LowerCased
  CMP   BL, 'Z'
  JG    @@LowerCased
  OR    BL, 20H // make lower case
@@LowerCased:
  XOR   AL, BL
  INC   ESI
  JMP   @@loop
@@done:
  POP   EBX
  POP   ESI
  RET
end;
HTTPParse.pas
 
function GetHashCode(Ident: PChar; Length: Integer): Word;
asm
      PUSH ESI
{$IFNDEF PIC}
PUSH EBX
XOR EBX,EBX
{$ENDIF}
      MOV  ESI, EAX
      XOR  EAX, EAX
      XOR  ECX, ECX
@@1:  MOV   AL,[ESI]
      ROL CX,5
      XOR CL,CharValue.Byte[EBX + EAX]
      INC ESI
      DEC EDX
JNE @@1
      MOV EAX,ECX
{$IFNDEF PIC}
POP EBX
{$ENDIF}
      POP   ESI
end;

Answer 6

java里面也有类似算法，但初值不同，我想明白的是为什么要乘37而不是别的数，初值为什么是17或乘5而不是别的数，最后结果为什么还要加上一个值
public int hashCode()  
{  
  if (this.hashValue == 0)  
  {  
    int result = 17;  
    int idValue = this.getId() == null ? 0 : this.getId().hashCode();  
    result = result * 37 + idValue;  
    this.hashValue = result;  
  }  
  return this.hashValue;  
}  

Answer 7

谢谢zwjchina兄提供这么多的代码
谢谢blazingfire兄的解释，不过还有一点不是很明白
37这个经验是怎么得来的呢，为什么好多数人都用这个值

Answer 8

 for i:=1 to Len do 
  begin 
    result:=result*5; 
    inc(result,Cardinal(pStrChar^)*37); 
    inc(pStrChar); 
  end; 适用于指针和文件操作。