代码之家 › 专栏 › 技术社区 › jpfollenius Rob Kennedy

不区分大小写的Bob Jenkins哈希?

delphi-2010 hash delphi

jpfollenius Rob Kennedy · 技术社区 · 16 年前

是否存在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 回复 | 直到 16 年前

Niels Castle 16 年前

不,没有哈希函数的大小写不变版本。在将所有字符串传递给哈希函数之前,请使用小写或大写。

Thorarin 16 年前

它会稍微快一点,但会对您的可维护性造成很大伤害。这种类型的微观优化很少有好的理由。在按照您的建议散列之前,只需将字符串转换为小写或大写。

“我们应该忘记小效率,比如97%的时间:过早的优化是万恶之源。但是我们不应该放弃我们的机会临界3%。一个好的程序员会不要被这样的人哄得自满。推理,他将是明智的看仔细阅读关键代码;但是只有在该代码识别“—Donald Knuth

mghie 16 年前

我觉得整个问题都错了。引述 Wikipedia article on hash functions :

一 哈希函数 是一个定义良好的过程或数学函数,它将大量的、可能是可变大小的数据转换成一个小的数据,通常是一个整数,可以作为数组的索引。

注意“数据量”-没有指定类型,实际上Bob Jenkins哈希函数有一个非类型化参数 const Data 指向要散列的数据。由于输入数据不一定是字符序列,因此无法计算“不区分大小写”的哈希值。即使它是一个字符序列——上下换行将取决于字符集和编码。因此,对于ASCII字符串、UTF-8编码字符串、UTF-16LE编码字符串等,您需要具有不同的哈希函数。(你明白了)。

BeniBela 9 年前

我在一个项目中也需要这样的功能。鲍勃·詹金的一次一个的杂烩:

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字符串提供相同的哈希。

不要忘记禁用溢出检查。