object.GetHashCode()能否为不同机器上的相同对象(字符串)产生不同的结果？

Question

是否有可能同一个对象,特别是一个string或任何原始或非常简单的类型(如a struct),.GetHashCode()在不同的机器上调用时产生不同的方法值？

例如,表达式是否可以"Hello World".GetHashCode()在不同的机器上生成不同的值.我主要是要求C#.NET,但我想这可能适用于Java甚至其他语言？

编辑:

从下面的答案和评论中.GetHashCode()可以看出,我知道可以覆盖,并且不能保证它在不同版本的框架之间产生的结果.因此,重要的是要澄清我有简单的类型(不能继承,因此GetHashCode()被覆盖),我在所有机器上使用相同版本的框架.

Answer 1

简短回答:是的.

但简短的答案并不好玩,是吗？

在实施时,GetHashCode()您必须做出以下保证:

当GetHashCode()在另一个应该被认为与此相等的对象上调用时,在此App Domain中,将返回相同的值.

而已.有一些事情你真的需要尝试做(尽可能多地使用不相等的对象扩散,但不要花太多时间,它首先超过散列的所有好处)和你的代码如果你不这样做会很糟糕,但它实际上不会破裂.如果你不走那么远就会破裂,因为那样:

dict[myObj] = 3;
int x = dict[myObj];//KeyNotFoundException

好的.如果我正在实施GetHashCode(),为什么我会更进一步,为什么不呢？

首先,为什么我不呢？

也许这是一个稍微不同的程序集版本,我在构建之间改进(或至少尝试过).

也许一个是32位,一个是64位,我为了效率而疯狂,并为每个选择不同的算法来使用不同的字大小(这不是闻所未闻的,尤其是在散列像集合或字符串这样的对象时) .

也许我决定在决定什么构成"平等"对象时要考虑的一些因素本身就是这种方式在不同系统之间变化的.

也许我实际上故意引入一个不同构建的不同种子来捕捉任何同事错误依赖我的哈希码的情况!(我听过MS这样做的实现string.GetHashCode(),但不记得我是否从可靠或轻信的来源中听到过).

主要是,这将是前两个原因之一.

现在,为什么我可以给出这样的保证？

如果我这么做的话,很可能是偶然的.如果可以仅基于单个整数id来比较元素的相等性,那么我将使用它作为我的哈希码.对于不太好的哈希,任何其他东西都会更有效.我不太可能改变这个,所以我可能会.

我可能的另一个原因是我自己想要保证.没有什么可说的,我不能提供它,只是我不需要.

好的,让我们做一些实用的事情.在某些情况下,您可能需要与机器无关的保证.有些情况下你可能会想要相反的情况,我会稍微谈谈.

首先,检查你的逻辑.你能处理碰撞吗？好的,那我们就开始吧.

如果它是你自己的类,那么实现以便提供这样的保证,记录它,你就完成了.

如果不是你的班级,那么IEqualityComparer<T>以提供它的方式实施.例如:

public class ConsistentGuaranteedComparer : IEqualityComparer<string>
{
  public bool Equals(string x, string y)
  {
    return x == y;
  }
  public int GetHashCode(string obj)
  {
    if(obj == null)
      return 0;
    int hash = obj.Length;
    for(int i = 0; i != obj.Length; ++i)
      hash = (hash << 5) - hash + obj[i];
    return hash;
  }
}

然后使用它而不是内置的哈希码.

有一个有趣的案例,我们可能想要相反的情况.如果我可以控制你正在散列的字符串集,那么我可以选择一堆具有相同哈希码的字符串.你的基于散列的集合的性能将会变得更糟,并且非常糟糕.我可以继续比你处理它更快地做到这一点,所以它可能是一种拒绝服务攻击.发生这种情况的情况并不多,但重要的是,如果您正在处理我发送的XML文档,您不能仅排除某些元素(许多格式允许其中的元素自由).然后NameTable你的解析器里面会受到伤害.在这种情况下,我们每次都创建一个新的哈希机制:

public class RandomComparer : IEqualityComparer<string>
{
  private int hashSeed = Environment.TickCount;
  public bool Equals(string x, string y)
  {
    return x == y;
  }
  public int GetHashCode(string obj)
  {
    if(obj == null)
      return 0;
    int hash = hashSeed + obj.Length;
    for(int i = 0; i != obj.Length; ++i)
      hash = hash << 5 - hash + obj[i];
    hash += (hash <<  15) ^ 0xffffcd7d;
    hash ^= (hash >>> 10);
    hash += (hash <<   3);
    hash ^= (hash >>>  6);
    hash += (hash <<   2) + (hash << 14);
    return hash ^ (hash >>> 16)
  }
}

这将在给定的使用中保持一致,但从使用到使用不一致,因此攻击者无法构造输入以强制它为DoSsed.顺便说一句,NameTable不使用an IEqualityComparer<T>因为它想要处理具有索引和长度的char数组而不构造字符串,除非必要,但它确实做了类似的事情.

顺便提一下,在Java中,哈希代码string被指定并且不会改变,但对于其他类可能不是这种情况.

编辑:ConsistentGuaranteedComparer我已经对上面采用的方法的整体质量进行了一些研究,我不再满足于在我的答案中使用这些算法; 虽然它用于描述这个概念,但它并没有像人们想象的那样好.当然,如果一个人已经实现了这样的事情,那么在不破坏保证的情况下就不能改变它,但如果我现在建议使用我的这个库,那么在研究之后写的如下:

public class ConsistentGuaranteedComparer : IEqualityComparer<string>
{
  public bool Equals(string x, string y)
  {
    return x == y;
  }
  public int GetHashCode(string obj)
  {
    return obj.SpookyHash32();
  }
}

对于RandomComparer上述情况并没有那么糟糕,但也可以改进:

public class RandomComparer : IEqualityComparer<string>
{
  private int hashSeed = Environment.TickCount;
  public bool Equals(string x, string y)
  {
    return x == y;
  }
  public int GetHashCode(string obj)
  {
    return obj.SpookyHash32(hashSeed);
  }
}

或者更难预测:

public class RandomComparer : IEqualityComparer<string>
{
  private long seed0 = Environment.TickCount;
  private long seed1 = DateTime.Now.Ticks;
  public bool Equals(string x, string y)
  {
    return x == y;
  }
  public int GetHashCode(string obj)
  {
    return obj.SpookyHash128(seed0, seed1).GetHashCode();
  }
}