logo标签列表

C# 4.0如何获取给定字符串的64位哈希码

c#.netstringhash64-bit
13

我想要获取给定字符串的64位哈希码。有什么最快的方法可以做到这一点吗？

虽然有一个现成的方法可以获取32位哈希码，但我需要64位。

我只需要整数哈希，不需要md5。

非常感谢。

C# 4.0

2
我将把爬取的URL存储在数据库中。为了最小化冲突并获得最大速度，我需要64位哈希码。 - Furkan Gözükara
1
如果“速度”是唯一的要求，您可以将32位哈希值直接赋值给64位变量。 - Codo
1
这不是唯一的要求。主要目的是减少可能的冲突。最多可能有1000万个URL。 - Furkan Gözükara
2
是的，但如果你使用数学计算，当有1000万个32位字符串时，会存在非常大的碰撞风险 :) 对我来说，64位是最好的解决方案。 - Furkan Gözükara
1
生日悖论表明，如果哈希函数具有完美的分布，则在1000万行中发生冲突的风险为368936分之一。公式为：1 - e ^ ( -10^7 * (10^7 - 1) / ( 2 * 2^64 ) )。 - Jonas Elfström
显示剩余7条评论
6个回答
13

简单解决方案：

public static long GetHashCodeInt64(string input)
{
    var s1 = input.Substring(0, input.Length / 2);
    var s2 = input.Substring(input.Length / 2);

    var x= ((long)s1.GetHashCode()) << 0x20 | s2.GetHashCode();

    return x;
}
2
@MonsterMMORPG，如果您正在存储这些哈希值，请优先选择MD5或任何其他哈希实现（例如@Pratik的解决方案），因为将来版本的“字符串”可能会使用不同的算法来计算对象的哈希码。 - Kirill Polishchuk
1
@KirillPolishchuk，这段代码在某些机器上存在错误（无法确定导致问题的规格）。如果第一半的哈希码为负数，请考虑在SHIFT和OR操作之前将两个哈希码都转换为UInt64。 - giladrv
1
从GetHashCode获得的值不应存储到永久存储（例如数据库）中。不能保证下次运行应用程序时会得到一致的值（特别是如果进行了更新）。 - Mike Fisher
这个方法有时会抛出这个异常：值对于 int64 来说太大或太小。 - Tim.Tang
@KirillPolishchuk OP 表示他们将在数据库中存储哈希值，而 GetHashCode() 不适合此用途。它可能会在不同的调用中返回相同数据的不同值。我最近就因为这个问题遇到了一个 bug... - Göran Roseen
显示剩余5条评论
7

既然问题是关于生成URL，我假设您总是需要相同的哈希值为64位整数。使用GetHashCode不可靠。为了生成具有较少冲突的哈希值，我使用以下方法。

public static ulong GetUInt64Hash(HashAlgorithm hasher, string text)
{
    using (hasher)
    {
        var bytes = hasher.ComputeHash(Encoding.Default.GetBytes(text));
        Array.Resize(ref bytes, bytes.Length + bytes.Length % 8); //make multiple of 8 if hash is not, for exampel SHA1 creates 20 bytes. 
        return Enumerable.Range(0, bytes.Length / 8) // create a counter for de number of 8 bytes in the bytearray
            .Select(i => BitConverter.ToUInt64(bytes, i * 8)) // combine 8 bytes at a time into a integer
            .Aggregate((x, y) =>x ^ y); //xor the bytes together so you end up with a ulong (64-bit int)
    }
}

要使用它，只需传递您喜欢的哈希算法即可。

ulong result = GetUInt64Hash(SHA256.Create(), "foodiloodiloo")
//result: 259973318283508806

或者

ulong result = GetUInt64Hash(SHA1.Create(), "foodiloodiloo")
//result: 6574081600879152103

这个答案与被接受的答案的区别在于，这个答案对所有位进行异或操作，并且您可以使用任何算法。
1
我认为这个答案被严重低估了。正如你所指出的，GetHashCode()不能保证在调用之间给出相同的值。这意味着如果您存储哈希并尝试稍后匹配它，您将会遇到有趣的错误。 此外，您使用字节数组中的所有字节（当前顶部答案存在一个错误）。 - Göran Roseen
似乎这种方法（主要是 bytes.Length / 8）无法与某些算法（如 SHA1）一起使用，因为它们会产生不可分割长度的哈希值（例如，SHA1 会产生一个20字节的哈希值）。 - Nick
@Nick，你说得对。之前代码中有一个错误，如果使用SHA1，它只使用了前16个字节。现在已经更新了代码，将数组大小调整为8的倍数。谢谢！ - Daniel Richter
@Daniel，你觉得对SHA哈希的字节块进行异或运算是否能避免碰撞，就像完整的SHA哈希一样？即使它们是不同的序列，[1,5]和[5,1]的异或结果是否相同。我只是想了解，如果对超过8个字节的哈希字节进行异或运算是否安全。 - Nick
5

我将介绍一个新的可能答案。xxHash非常快。在这里查看基准测试：

https://cyan4973.github.io/xxHash/

它有一个NuGet包： https://www.nuget.org/packages/System.Data.HashFunction.xxHash

或者开源代码： https://github.com/brandondahler/Data.HashFunction/blob/master/src/System.Data.HashFunction.xxHash/xxHash_Implementation.cs

这里的其他答案要么存在问题，无法真正防止冲突，要么只是现有HashAlgorithm实现的包装器。

xxHash不具备加密强度，但似乎更适合您所需的。它的：

  1. 全部使用64位，
  2. 比其他算法更快，
  3. 具有良好的分布以最大化避免碰撞。
5

此代码来自于Code Project文章 - 将字符串转换为64位整数

 static Int64 GetInt64HashCode(string strText)
{
    Int64 hashCode = 0;
    if (!string.IsNullOrEmpty(strText))
    {
        //Unicode Encode Covering all characterset
          byte[] byteContents = Encoding.Unicode.GetBytes(strText);
        System.Security.Cryptography.SHA256 hash = 
        new System.Security.Cryptography.SHA256CryptoServiceProvider();
        byte[] hashText = hash.ComputeHash(byteContents);
        //32Byte hashText separate
        //hashCodeStart = 0~7  8Byte
        //hashCodeMedium = 8~23  8Byte
        //hashCodeEnd = 24~31  8Byte
        //and Fold
        Int64 hashCodeStart = BitConverter.ToInt64(hashText, 0);
        Int64 hashCodeMedium = BitConverter.ToInt64(hashText, 8);
        Int64 hashCodeEnd = BitConverter.ToInt64(hashText, 24);
        hashCode = hashCodeStart ^ hashCodeMedium ^ hashCodeEnd;
    }
    return (hashCode);
}
1
Pratik是你的解决方案好还是Orentet的解决方案好？ - Furkan Gözükara
12
哇，这个程序使用了极高的CPU功率。我将其与strText.GetHashCode()方法进行了比较，发现它慢了376倍。 - Furkan Gözükara
@MonsterMMORPG，如果您想进行比较，那么您必须使用缓存，据我所知.NET会缓存字符串的哈希值。 - Sebastian
9
相当缓慢，端序相关且怪异。你为什么要从SHA-256哈希中读取3个64位整数并将它们异或？这不比仅读取单个64位整数并使用它更有优势。 - CodesInChaos
这个哈希对象应该使用 'using'。它是可丢弃的。 - DAG
显示剩余3条评论
3

我使用了@Kirill的解决方法。由于我有点古怪，不喜欢"var"（我猜这是因为我来自c++），所以我做了一个变体：

string s1 = text.Substring(0, text.Length / 2);
string s2 = text.Substring(text.Length / 2);

Byte[] MS4B = BitConverter.GetBytes(s1.GetHashCode());
Byte[] LS4B = BitConverter.GetBytes(s2.GetHashCode());
UInt64 hash = (UInt64)MS4B[0] << 56 | (UInt64)MS4B[1] << 48 | 
              (UInt64)MS4B[2] << 40 | (UInt64)MS4B[3] << 32 |
              (UInt64)LS4B[0] << 24 | (UInt64)LS4B[1] << 16 | 
              (UInt64)LS4B[2] << 8  | (UInt64)LS4B[3] ;

我对字节的顺序并不确定，这取决于机器（是小端序还是大端序），但是，谁在乎呢？它只是一个数字（哈希值）。非常感谢@Kirill，对我很有帮助！

如果你像我想的那样想要效率，也许你应该避免创建两个字节数组并直接移动整数本身？ - Djof
3
如果你不喜欢var，那么你可能也不喜欢C++的auto.... - Sebastian
GetHashCode方法返回的值不应该被存储到像数据库这样的永久性储存中。因为下一次运行应用程序时不能保证会得到相同的结果(尤其是假如你进行了更新)。 - Mike Fisher
3
我只需要整数哈希。 - Furkan Gözükara
2
@MonsterMMORPG你知道从byte [8] <===> Int64可以轻松转换吗？所以...只要你有8个字节的输出，你就拥有一个Int64. - Marc Gravell
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接