English 中文(简体)
我能确定给定字符串的内置哈希始终相同吗?
原标题:
  • 时间:2009-01-22 11:11:40
  •  标签:

我正在获取一个字符串哈希值,像这样:

string content = "a very long string";
int contentHash = content.GetHashCode();

然后我将哈希值存储到字典中作为映射到另一个ID的键。这很有用,因为我不必在默认字典哈希计算期间比较大字符串,而是可以通过键从字典中找到ID。

我是否可以确定给定字符串“a very long string”的哈希值始终相同?

我能确认两个不同的字符串不会有相同的哈希吗?

另外,如果可能的话,不同的字符串获得相同的哈希值的可能性有多大?

最佳回答

只是为了增加一些细节,以说明更改哈希码的想法可能来自哪里。

其他答案已经正确说了,特定字符串的哈希码在特定的运行时版本中始终相同。不能保证新的运行时因为性能原因可能使用不同的算法。

字符串类在对象中重写了默认的GetHashCode实现。

.NET 中引用类型的默认实现是分配一个连续的 ID(由 .NET 内部持有)并将其分配给对象(对象的堆存储有一个存储此哈希码的插槽,仅在该对象的第一次调用 GetHashCode 时分配)。

因此创建一个类的实例,给它分配一些值,然后检索哈希码,接着使用相同的一组值做完全相同的序列将产生不同的哈希码。这可能是为什么有些人认为哈希码可以改变的原因。实际上,分配哈希码的是类的实例,一旦分配了该哈希码,该实例的哈希码就不会改变。

编辑:我刚刚注意到,没有一个答案直接涉及你们的每一个问题(尽管我认为它们的答案是清楚的),但只是为了整理一下:

我可以确定给定字符串(“一个非常长的字符串”)的哈希值始终相同吗?

在您的使用中,是的。

我能确定两个不同的字符串不会有相同的哈希吗?

没有。两个不同的字符串可能具有相同的哈希值。

此外,如果可能的话,不同字符串是否可能得到相同的哈希值?

概率很低,从一个4G域名中得到的哈希值非常随机。

问题回答

是的,它将保持一致,因为字符串是不可变的。然而,我认为您正在误用字典。您应该通过使用字符串作为键让字典为您获取字符串的哈希值。哈希值不能保证唯一,因此您可能会将一个键覆盖另一个键。

是的,这就是哈希码的目的!但不能保证在不同版本的运行时中相同。更多信息请参考MSDN

正如其他人指出的那样,哈希值会随时间保持恒定。但是你为什么要将一个字符串进行哈希,然后将其作为字典的键呢?哈希值不保证唯一性,因此你的比较可能不正确。让字典来完成它的工作吧。我认为这种情况下最适合的集合是HashSet

正如许多人所说,实现取决于框架的版本,但它也取决于架构。即使它们具有相同的版本号,字符串.GetHashCode()的实现在框架的x86和x64版本中是不同的。

例如,如果您正在编写客户端/服务器或.NET远程调用类型的架构,并且希望使用字符串HashCode来防止下载大型资源,则仅当两者是相同版本和位数时才能实现此目的。否则,您应该使用不同的哈希-- MD5,SHA等将正确地工作。

Object.GetHashCode 的文档说明。

如果两个对象比较相等,则每个对象的GetHashCode方法都必须返回相同的值。

因此,您可以确保给定字符串的哈希码将是相同的。但是,您不能保证它是唯一的(可能会有其他具有相同哈希码的字符串)。

你不需要猜测运行时间或版本,只需要使用我在空闲时间里制作的 CaseInsensitiveStringComparer 类(你可以将其传递给字典的构造函数,或者如果你使用 .NET 3.5,则传递给 HashSet)。

/// <summary>
/// StringComparer that is basically the same as StringComparer.OrdinalIgnoreCase, except that the hash code function is improved and guaranteed not to change.
/// </summary>
public class CaseInsensitiveStringComparer : StringComparer
{
    /// <summary>
    /// Compares two strings, ignoring case
    /// </summary>
    /// <param name="x">First string</param>
    /// <param name="y">Second string</param>
    /// <returns>Compare result</returns>
    public override int Compare(string x, string y)
    {
        return StringComparer.OrdinalIgnoreCase.Compare(x, y);
    }

    /// <summary>
    /// Checks if two strings are equal, ignoring case
    /// </summary>
    /// <param name="x">First string</param>
    /// <param name="y">Second string</param>
    /// <returns>True if strings are equal, false if not</returns>
    public override bool Equals(string x, string y)
    {
        return Compare(x, y) == 0;
    }

    /// <summary>
    /// Gets a hash code for a string, ignoring case
    /// </summary>
    /// <param name="obj">String to get hash code for</param>
    /// <returns>Hash code</returns>
    public override int GetHashCode(string obj)
    {
        if (obj == null)
        {
            return 0;
        }
        int hashCode = 5381;
        char c;
        for (int i = 0; i < obj.Length; i++)
        {
            c = obj[i];
            if (char.IsLower(c))
            {
                c = char.ToUpperInvariant(c);
            }
            hashCode = ((hashCode << 5) + hashCode) + c;
        }
        return hashCode;
    }
}

Can I be sure that the hash for a given string ("a very long string") will be always the same?

是的

Can I be sure that two different strings won t have the same hash?

不。

字符串根据其内容进行哈希处理,因此,如果您使用默认的GetHashCode,则该哈希值的时间应该保持不变。

正如已经提到的,您可以确信特定字符串的哈希值将与内容基础上进行的哈希值相同。然而,您不能确定特定字符串将在后续版本的.NET框架中哈希相同,正如在这里提到的一样。

所以我认为如果它仅在应用程序内部使用,那么这种方法是可行的。如果要将值持久化到数据存储中,则最好自己编写一个函数,以确保它在各个版本中保持一致。

鉴于有无限数量的不同字符,不可能为每个字符分配一个不同的int(32位可以表示高达40亿)编号。

With just 8 characters tehre are 2^60 different strings. This is infinitely larger than 2^32. Naturally the hashcode of some of these strings must clash.

具有相同哈希码的两个对象不一定相等。要确定,请使用equals方法。这基本上是hashmap用来确定键是否相等的策略。

地图获取(字符串键)

  • Calculate hashcode of key
  • Use modulo to figure out which bucket key belongs too.
  • Loop thru all the entries from that bucket attempting to find a matching key.
  • When a key match is found return that entries value.

附带说明,随着地图增加更多元素,它将重新创建更多存储区,并将所有旧条目放入新存储区。这有助于避免桶条目列表变得非常长。地图需要许多桶和短列表。

Object.hashcode的Javadoc很有意思-我粘贴了一小段。

 The equals method implements an equivalence relation:

* It is reflexive: for any reference value x, x.equals(x) should return true.
* It is symmetric: for any reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
* It is transitive: for any reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
* It is consistent: for any reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the object is modified.
* For any non-null reference value x, x.equals(null) should return false. 

Object类的equals方法实现了最具有区分能力的对象等同关系;也就是说,对于任何引用值x和y,当且仅当x和y引用同一对象时(x==y的值为true),该方法返回true。

这是过早优化弊端的一个很好的例子。

你有分析器或基准测试的输出吗,告诉你在同一个哈希桶中的字符串比较实际上会导致性能问题?

没有想过。只需将字符串本身用作字典中的键。这就是您应该使用它的方式。

顺便提一下,字符串的种类比整数的种类要多得多,因此基本的逻辑告诉您每个不同的字符串都有一个不同的哈希码是不可能的。





相关问题
热门标签