1

Bob Jenkins 哈希函数是否有不区分大小写的变体？

Generics.Defaults.BobJenkinsHash

提供快速哈希函数。不幸的是，它不能与这样的不区分大小写的比较函数结合使用

TCustomStringComparer = class (TEqualityComparer <String>)
  function Equals(const Left, Right: String): Boolean; override;
  function GetHashCode(const Value: String): Integer; override;
end;
function TCustomStringComparer.Equals (const Left, Right : String) : Boolean;
begin
  Result := CompareText (Left, Right) = 0;
end;
function TCustomStringComparer.GetHashCode (const Value : String) : Integer;
begin
  Result := Generics.Defaults.BobJenkinsHash (Value [1], Length (Value) * SizeOf (Char), 0);
end;

这是因为 TDictionary 首先比较哈希码，然后在检查相等性时使用提供的比较器。

当然我可以在我的GetHashCode函数中使用大写，但我想知道如果我能以某种方式修改散列函数本身是否会更快。

4

4 回答 4

8

不，哈希函数没有大小写不变的版本。将所有字符串小写或大写，然后再将它们传递给散列函数。

于 2009-10-30T11:48:45.577 回答
3

它会稍微快一点，但它会极大地损害您的可维护性。这种类型的微优化很少有充分的理由。只需在按照您的建议进行散列之前将您的字符串转换为小写或大写即可。

“我们应该忘记小的效率，比如说大约 97% 的时间：过早的优化是万恶之源。但我们不应该放弃关键的 3% 的机会。一个好的程序员不会被这样的推理，他将明智地仔细查看关键代码；但只有在识别出该代码之后” - Donald Knuth

于 2009-10-30T12:03:50.870 回答
3

IMO整个问题都是错误的。引用关于散列函数的维基百科文章：

散列函数是任何定义明确的过程或数学函数，它将大量的、可能大小可变的数据转换为一个小的数据，通常是一个可以用作数组索引的整数。

注意“数据量”——没有指定类型，而且 Bob Jenkins 散列函数确实有一个const Data指向要散列的数据的无类型参数。由于输入数据不一定是字符序列，因此无法计算“不区分大小写”的哈希值。即使它是一个字符序列 - 大写或小写也将取决于字符集和编码。因此，您需要对 ASCII 字符串、UTF-8 编码字符串、UTF-16 LE 编码字符串......（你明白了）有不同的哈希函数。

于 2009-10-30T12:30:50.967 回答
0

我在一个项目中也需要这样的功能。Bob Jenkins 的一次一个哈希：

function hash(const s: string): cardinal;
var
  p, last: PByte;
begin
  if s = '' then exit(1);
  p := pbyte(pointer(s));
  last := p + length(s);
  result := 0;
  while p < last do begin
    if {$ifdef asciionly}p^ < 128{$else}true{$endif}  then begin
      result := result + p^;
      if (p^ >= ord('a')) and (p^ <= ord('z')) then result := result - ord('a') + ord('A');
      result := result + (result shl 10);
      result := result xor (result shr 6);
    end;
    inc(p);
  end;

  result := result + (result shl 3);
  result := result xor (result shr 11);
  result := result + (result shl 15);
end;

如果设置了 asciionly，它还应该为 utf-8 和 latin1 字符串提供相同的哈希值。

不要忘记禁用溢出检查。

于 2016-10-22T18:52:43.987 回答