最快的哈希码生成器.NET

Question

我正在使用C#为System.Drawing.Point类实现自定义的GetHashCode。目前我的方法无法满足以下要求：

var hashA = MyGetHashCode(new Point(1, 0));
var hashB = MyGetHashCode(new Point(0, 1));
var hashC = MyGetHashCode(new Point(0, 0));
var hashD = MyGetHashCode(new Point(1, 1));
Assert.AreNotEqual(hashA ^ hashB, hashC ^ hashD);

为了通过这个测试，我相信使用new SHA256Managed().ComputeHash(currentHash)就可以了。但是还有其他更快的哈希算法吗？我知道SHA256是关于安全性的，而我不需要那么高的安全性。

- Jader Dias

---

你是怎么想到你的哈希函数应该通过那个测试的呢？ - mqp

@mquander 确实看起来很奇怪。但是其他一些类的Equals函数依赖于一个简单的GetHashCode实现，而这个实现又依赖于我的自定义Point.GetHashCode方法。 - Jader Dias

@mquander 这一切都关乎在Equals和GetHashCode中不重复代码，并使它们等效。 - Jader Dias

Answer 1

一个简单的哈希？那么可以考虑使用如下方式：

 (17 * point.X) + (23 * point.Y);

或者更明显的熵：

int hash = -1047578147;
hash = (hash * -1521134295) + point.X;
hash = (hash * -1521134295) + point.Y;

- Marc Gravell

---

Marc，这肯定会满足Assert但没有边界（大的X或Y会溢出）...如果允许溢出，那么它就没有良好的分布。 - Jorge Córdoba

它将进行包装（未选中）；据我所知，分发是正常的...这是C#编译器使用的方法 ;-p - Marc Gravell

这些数字只是（如所述）C#编译器将用于形式为：new {X = 123, Y = 456}的匿名类型的数字。 - Marc Gravell

Answer 2

• 你为什么要这样做？System.Drawing.Point已经有很好的哈希函数了吧？

• 你明白测试并不代表着严格的要求，对吧？哈希码不一定非得唯一。

• 如果你真的想要一个非常好的坐标哈希值，你可能需要从这个页面开始，它介绍了如何哈希多个整数。

- mqp

---

关于“精细哈希函数” - x ^ y... 这并不是很好的选择；因为它意味着对角线上的任何元素都是零，而对称的元素，例如(5,7)和(7,5) - 是相等的。 - Marc Gravell

这不是很好，但除非您有相当病态的点分布，否则还可以。我感觉OP没有根据任何具体的性能要求工作，如果他考虑使用SHA哈希，那么我怀疑是否需要更好的东西。 - mqp

我在问题的评论中回答了第一个问题。 - Jader Dias

Answer 3

一个简单的Elf哈希实现（它是用Delphi编写的，应该很容易翻译）。

function ElfHash(id : string; tableSize : integer) : integer;
var
  i : integer;
  h,x : longint;
begin
  h := 0;
  // Obtener el valor numérico
  for i := 1 to Length(id) do
  begin
    h := (h shl 4) + Ord(id[i]);

    x := h and $F0000000;
    if x <;>; 0 then
       h = h xor (x shr 24) xor x;
  end;
  // Ajustar al tamaño de la tabla
  result := h mod tableSize;
end;

- Jorge Córdoba

---

我以为我懂Delphi，但我不知道<;>;是什么意思。 - Jader Dias

与stackoverflow的代码消毒器交流...那显然是“<>”。 - Jorge Córdoba

在托管代码中进行左移、右移和异或操作时，很容易进行翻译。 - Hogan

Answer 4

我知道这不会回答你的问题，但是为了其他读者的利益，我必须提到您正在更改框架内置方法的默认行为。根据文档：
http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

GetHashCode方法的默认实现不能保证不同对象返回唯一的返回值。此外，.NET Framework不保证GetHashCode方法的默认实现，并且它返回的值将在不同版本的.NET Framework之间相同。因此，此方法的默认实现不能用作哈希目的的唯一对象标识符。

- Joel Martinez

---

请使用块引用而不是代码块（在引用前加上“>”而不是缩进）。这将使阅读更加容易。 - Samir Talwar

在这种情况下，这不是问题。他们的意思是您不应使用默认的GetHashCode作为唯一值，因为不同的对象可能返回相同的哈希值。当Jader将其实现为（实际上）唯一值（使用sha256或其他方式）时，它不会破坏任何东西。只是会变慢... - tanascius

公平地说，如果他实际上有一个大的点哈希表，那么速度会相当慢 - 慢到相当可笑的程度。 - mqp

当然可以 - 这并不是很聪明，他永远不应该为此目的使用sha256或类似的东西。但是，乔尔的陈述仍然是不正确的。 - tanascius

Answer 5

这是一篇关于哈希速度的有趣文章：

一个用于哈希表查找的哈希函数

- TWA

Answer 6

我不知道你的应用是什么，但你可能正在寻找 Zobrist 哈希。

http://en.wikipedia.org/wiki/Zobrist_hashing

它可以进行增量更新，因此非常快速。

- Fantius

Answer 7

如果您事先知道您的点值在0到N之间，您可以使用hashcode = X+Y*N; 这是一种相当明显的可能哈希方式。它根本不是随机的，有丑陋的重复，并且通常非常愚蠢。它相当于连接您两个点的位（假设N是2的幂次）。 它具有完美均匀的分布和无碰撞。

我过去曾经使用这种策略取得了很好的效果，但承认它确实有一些真正的（但显而易见的）限制。 最大的限制是当N足够大以至于N^2无法适合您的哈希值时会发生什么情况（即痛苦的碰撞）。

- Brian

---

我的当前实现是 ((x << 16) | (x >> 16)) ^ y（使用C#），它符合您的描述。 - Jader Dias