logo标签列表

简单的字符串哈希函数

stringdelphihash
13

我想将字符串哈希成整数以便将其放入数组中。然而，我对哈希函数并不太了解，因此我的当前方法只是将所有字符的ASCII码值相加，并将其除以数组大小取余。

是否有更简单、更快速、更好的方法？

你在尝试制作哈希表吗？ - Steven Sudit
1
重复的内容 一半在这里。 - Dummy00001
我目前正在使用Delphi。 - Hal
Hal，正如您所看到的，哈希函数常常被误解并且经常成为码农争论的借口。 - Steven Sudit
3
有没有关于哈希函数的社区百科？如果没有，或许有意义创建一个，按照输入类型、性能和语言实现来组织信息。 - Dummy00001
6个回答
13
3
比较FNV-1、FNV-1a、DJB2、DJB2a、SDBM和CRC32哈希算法。其中，FNV-1a是最好的选择。 - Ian Boyd
@StevenSudit 很巧，你提到这个。我已经看了一个小时了。我已经把它翻译成Delphi了，但是没有测试向量，所以我无法确定我是否正确（它非常敏感于字节序，谁知道原始的C++正在做什么顺序）。 - Ian Boyd
@StevenSudit 自2009年以来，项目主页上一直存在一个开放问题，要求提供测试向量。 - Ian Boyd
Austin在smhasher上回复道：“SMHasher使用VerificationTest函数来检查哈希函数是否正确实现——它不依赖于'The quick brown fox...'的正确大小写或标点符号，并且可以捕获比单个测试向量更多的实现错误。我会在首页上做个注释来指出这一点。” - Steven Sudit
我猜你测试了一个pascal版本的crc32，它比较慢。 如果使用8KB的查找表和汇编语言，crc32可以变得非常快，甚至在CPU具有SSE4.2硬件指令的情况下，比其他替代方案更快。请参见http://blog.synopse.info/post/2014/05/25/New-crc32c%28%29-function-using-optimized-asm-and-SSE-4.2-instruction 关于哈希分布，crc32非常好 - 请参见https://www.delphitools.info/2014/08/25/string-hashing-shootout/ 你可以纠正你关于crc32的答案。 - Arnaud Bouchez
显示剩余12条评论
4
请参考http://www.strchr.com/hash_functions，了解一些很好的哈希函数。
在Delphi实现中，以下是几个版本：
首先想到的是官方IniFiles.pas单元中TStringHash.HashOf方法使用的版本。其中包括一个更快的汇编版本：
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程序设计语言》第三版的经典 Kernighan & Ritchie 哈希算法 - 不是最好的，但是代码简单高效。

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;

在zlib中实现的快速“Adler”循环冗余校验 - 优化的汇编版本在这里:

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进行读取 - 以及一个更快的汇编版本在这里：

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版本 - 您可以在此处找到一个非常 优化的汇编版本（使用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;
2
Delphi 2009及以上版本还提供了Jenkins Hash（用于哈希字典条目）在Generics.Defaults.BobJenkinsHash中。 - mjn
关于哈希函数的比较，请查看http://www.delphitools.info/2014/08/25/string-hashing-shootout/简而言之：crc32在性能和冲突之间取得了最佳平衡，kr32存在很多冲突，而BobJenkinsHash则非常慢。 - Arnaud Bouchez
3
正如Dummy00001指出的那样，这个问题之前已经有人问过并得到了答案。请参考最佳哈希数字值算法？，特别是建议使用MurmurHash。
我推荐MurmurHash，因为：

  1. 它非常快。

  2. 它的分布和雪崩特性对于非加密哈希来说非常好。

  3. 即使在最坏情况下，它的表现仍然相当不错。

我用过它，感觉还不错。
编辑
关于如何最好地将其移植到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实现的自我测试。

1
我在其他地方已经回答过这个问题，但我会在这里重复一遍：http://sites.google.com/site/murmurhash/avalanche - Steven Sudit
@Steven：关于链接的问题 - 在尝试查看链接中的图表时出现404错误。您也没有提供任何广告算法示例实现的链接。另外，第二个链接（~bretm）显示了Jenkins的不同雪崩图，并且结论也很好：“Bob Jenkins的这个哈希函数应该适用于一般用途，无论是用于哈希表查找、基本文件指纹识别还是其他非加密用途。” 您是非常值得信赖的信息来源 ;) - Dummy00001
更全面的哈希函数调查，重点关注冲突避免和速度，可在http://www.strchr.com/hash_functions找到。 - Steven Sudit
除了http://programmers.stackexchange.com/questions/49550/what-hashing-algorithm-is-good-for-uniqueness-and-speed/145633#145633之外，我想提一下Murmur3。 - Steven Sudit
一旦我找到了一些测试向量 :) - Ian Boyd
显示剩余7条评论
2

Jenkins哈希函数可以帮助您入门。

我的当前方法只是将所有字符的ASCII码相加，然后取模数组大小。

这样做会丢失重要的信息，即字符在字符串中的位置。这是一个不好的想法，因为字符串“AB”和“BA”将具有相同的哈希值。

与简单的加法相比，保持它的原始性，可以使用表达式hash = hash*P1 + str[i]*P2 + P3;，其中Pi是一些质数。如果我需要快速哈希函数，我就是这么做的。我经常使用7、5和3作为质数，但数字应该明显调整（以及hash的初始值），以便哈希函数的结果可用于您的任务。

有关更多信息，请阅读对应的（而且相当信息丰富的）维基百科文章。

当然，可以从那里开始，但是要继续前进。正如你提供的文章所示，它具有相当糟糕的雪崩特性。只需看看所有的黄色像素即可。 - Steven Sudit
我并不否认它比加法更好——我甚至在一个被删除的答案的评论中指出了AB/BA问题。然而，没有任何理由应该有任何黄色像素。像memcachedb这样的项目之所以使用Murmur是有充分理由的！ - Steven Sudit
别傻了，总会有黄色像素的——因为仍然需要对哈希函数的结果应用模运算，这将丢弃更多有用的信息位。而且Murmur似乎并不比Jenkins或FNV好多少。或者你甚至都没费心去检查Murmur是如何工作的？我认为你在这里过于追求完美了。 - Dummy00001
哦，我绝对是个追求严谨的人，但我也是完全正确的。它并不是根本不同，但它的设计是为了避免这个特定的缺陷。如果想要进行良好的视觉比较，请查看http://sites.google.com/site/murmurhash/avalanche - Steven Sudit
附注：Delphi 2009及以上版本使用此函数来哈希字典条目 - Generics.Defaults.BobJenkinsHash。 - mjn
显示剩余3条评论
2

我尝试了许多快速哈希函数，最终选择了这个：

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函数一样快（实际上甚至更快），但它可以产生更好（更均匀）的分布。
-3
一个非常简单的方法是将所有值进行异或运算。据我所知，这是最简单的方法。
2
哦，a异或a等于0。因此，任何具有偶数个相同字母的字符串...变位词吗？ - Guy Gordon
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接