logo标签列表

如何在C#中从字节数组生成哈希码？

c#hash
55

假设我有一个存储字节数组的对象，我想能够高效地为其生成哈希码。过去我用过加密哈希函数来实现这个目的，因为它们易于实现，但是它们执行了比必要的更多的工作以实现加密单向性，而我对此不关心（我只是将哈希码用作散列表中的键）。

以下是我目前拥有的：

struct SomeData : IEquatable<SomeData>
{
    private readonly byte[] data;
    public SomeData(byte[] data)
    {
        if (null == data || data.Length <= 0)
        {
            throw new ArgumentException("data");
        }
        this.data = new byte[data.Length];
        Array.Copy(data, this.data, data.Length);
    }

    public override bool Equals(object obj)
    {
        return obj is SomeData && Equals((SomeData)obj);
    }

    public bool Equals(SomeData other)
    {
        if (other.data.Length != data.Length)
        {
            return false;
        }
        for (int i = 0; i < data.Length; ++i)
        {
            if (data[i] != other.data[i])
            {
                return false;
            }
        }
        return true;
    }
    public override int GetHashCode()
    {
        return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0);
    }
}

有什么想法吗？

dp: 你说得对，我在Equals方法中漏掉了一个检查，已经进行了更新。使用字节数组的现有hashcode将导致引用相等性（或者至少是hashcode概念的相同转换）。例如：

byte[] b1 = new byte[] { 1 };
byte[] b2 = new byte[] { 1 };
int h1 = b1.GetHashCode();
int h2 = b2.GetHashCode();

尽管这段代码中的两个字节数组具有相同的值，但它们引用了内存中不同的部分，并且将生成（可能）不同的哈希码。我需要两个具有相同内容的字节数组的哈希码相等。

11个回答
70

对象的哈希码并不需要唯一。

检查规则如下：

  • 哈希码相等吗？然后调用完整（慢速）Equals方法。
  • 哈希码不相等吗？那么这两个项肯定不相等。

你所需要的是一个GetHashCode算法，将你的集合分成大致均匀的组 - 它不应该形成键，因为HashTable或Dictionary<>需要使用哈希来优化检索。

你期望数据有多长？有多随机？如果长度差异很大（比如文件），那么只需返回长度即可。如果长度可能相似，请查看变化的字节的子集。

GetHashCode应该比Equals快得多，但不需要唯一。

两个相同的东西绝不能有不同的哈希码。两个不同的对象不应该具有相同的哈希码，但是某些冲突是可以预期的（毕竟，比可能的32位整数更多的排列组合存在）。

12
+1 这是我听过的为什么覆盖 Equals 和 GetHashcode 有益的最清晰的解释之一。 - Andrew Hare
53

不要在哈希表中使用加密哈希，那太荒谬了/过度杀伤力了。

这里有一个... 在C#中修改的FNV哈希

http://bretm.home.comcast.net/hash/6.html

    public static int ComputeHash(params byte[] data)
    {
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < data.Length; i++)
                hash = (hash ^ data[i]) * p;

            return hash;
        }
    }
7
这将生成相当独特的哈希值，但对于GetHashCode并不会很有效。思路是哈希允许集合在使用较慢的Equals之前快速检查两个byte[]是否匹配。在此实现中，您正在循环整个数组，因此对于非常大的数组，平等性检查可能会更快。这是计算通用哈希的好方法，但对于.NET实际使用GetHashCode的方式，这实际上可能会减缓集合的速度。 - Keith
2
@tigrou - 我并不是说这不是一个有用的哈希机制，但你不应该将其用于 GetHashCode 实现，因为 .Net 哈希集合都假定 GetHashCode 比 Equals 快几个数量级。实际上，如果 GetHashCode 检查通过，它们将继续调用 Equals，因为预期会出现一定量的冲突。如果两种方法都循环整个集合，你将得到一个非常慢的 HashTable 或 Dictionary。 - Keith
14
@Keith - 你在这里是错误的。关键点是GetHashCode()只需要调用一次，而每次比较都需要调用Equals()。因此，哈希计算的运行时间比相等运算长完全没有问题。事实上，.NET内置的字符串哈希就是这样做的。 - kaalus
4
@Keith：kaalus是正确的。一个好的哈希码必须包含要哈希的整个对象的信息，包括所有属性和字段值。除非所涉及的对象是不可变的并且在创建时缓存哈希码，否则无法避免每次调用都要扫描这些信息。 - Frank Hileman
1
值得注意的是，链接的页面（缓存版本在此处 - http://archive.is/MnmRY）实际上使用了`uint`，因此会产生不同的哈希值。 - sclarke81
显示剩余7条评论
13
借鉴JetBrains软件生成的代码，我选择了这个函数：
    public override int GetHashCode()
    {
        unchecked
        {
            var result = 0;
            foreach (byte b in _key)
                result = (result*31) ^ b;
            return result;
        }
    }

仅对字节进行XOR运算的问题在于返回值的3/4（3字节）只有2种可能的值（全开或全关）。这会使位分布更加广泛。

在Equals中设置断点是一个好建议。将大约200,000个数据条目添加到Dictionary中，看到大约10次Equals调用（或1/20,000）。

对于 IList<byte>，一定要使用基于索引的 for 循环，而不是 foreach。对于 byte[] 来说，可能没有太大区别，因为 foreach 会在内部转换为 for。 - nawfal
当使用foreach循环遍历List时，有时会被编译成for循环。不确定在遍历IList时是否也会发生这种情况（始终应该稍微慢一些，对于大数组没有太大影响，但对于小数组来说 => foreach比for有更多的初始化）。 - Daniel Bişar
4

我发现了有趣的结果：

我有一个类：

public class MyHash : IEquatable<MyHash>
{        
    public byte[] Val { get; private set; }

    public MyHash(byte[] val)
    {
        Val = val;
    }

    /// <summary>
    /// Test if this Class is equal to another class
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool Equals(MyHash other)
    {
        if (other.Val.Length == this.Val.Length)
        {
            for (var i = 0; i < this.Val.Length; i++)
            {
                if (other.Val[i] != this.Val[i])
                {
                    return false;
                }
            }

            return true;
        }
        else
        {
            return false;
        }            
    }

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }
}

接下来我创建了一个键类型为MyHash的字典，以测试插入速度，并且可以知道有多少次碰撞。我按照以下步骤进行：

        // dictionary we use to check for collisions
        Dictionary<MyHash, bool> checkForDuplicatesDic = new Dictionary<MyHash, bool>();

        // used to generate random arrays
        Random rand = new Random();



        var now = DateTime.Now;

        for (var j = 0; j < 100; j++)
        {
            for (var i = 0; i < 5000; i++)
            {
                // create new array and populate it with random bytes
                byte[] randBytes = new byte[byte.MaxValue];
                rand.NextBytes(randBytes);

                MyHash h = new MyHash(randBytes);

                if (checkForDuplicatesDic.ContainsKey(h))
                {
                    Console.WriteLine("Duplicate");
                }
                else
                {
                    checkForDuplicatesDic[h] = true;
                }
            }
            Console.WriteLine(j);
            checkForDuplicatesDic.Clear(); // clear dictionary every 5000 iterations
        }

        var elapsed = DateTime.Now - now;

        Console.Read();

每次我向字典中插入新项时，字典都会计算该对象的哈希值。因此，您可以通过在方法public override int GetHashCode()中放置此处找到的几个答案来确定哪种方法最有效。迄今为止最快且碰撞最少的方法是：

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }

该方法执行时间为2秒。

    public override int GetHashCode()
    {
        // 7.1 seconds
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < Val.Length; i++)
                hash = (hash ^ Val[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }

没有发生碰撞，但执行时间需要7秒钟！
你能解释一下你的哈希算法吗？ - nicolas2008
4
4
如果您不担心安全问题，那么使用MD5即可。SHA1比MD5慢。 - Jonathan C Dickinson
谢谢Jon.. SHA1CryptoServiceProvider.ComputeHash方法对我很有用..!! - Deepak
2
如果你想要更好的性能，我测试了几个哈希函数，推荐使用Bob Jenkin's hash function。它既计算速度极快，又可以避免与你现在使用的加密哈希函数一样的碰撞问题。
我不会C#语言，也不知道它是否可以与C语言链接，但是这里有它的C语言实现代码。
你可以通过PInvoke从C#调用C函数。这会对性能产生一定的影响（例如固定和传递参数时的封送 - 具体取决于实际使用的类型），但是当不频繁调用它们时（即在循环中>数千次）可以忽略不计。甚至一些图形渲染框架（如OpenTK、SkiaSharp）也使用了大量的PInvoke调用，但性能仍然不错。 - Daniel Bişar
1

使用字节数组字段中现有的哈希码不够好吗？此外，请注意在Equals方法中，在进行比较之前应检查数组是否具有相同的大小。

1
生成一个好的哈希值比说起来容易得多。记住，你基本上是用m位信息表示n个字节的数据。你的数据集越大，m越小，就越有可能发生冲突...即两个数据片段解析为相同的哈希值。
我学过的最简单的哈希算法就是将所有字节简单地进行异或运算。它很容易，比大多数复杂的哈希算法更快，并且对于小数据集而言是一种相当不错的通用哈希算法。实际上，它就像是哈希算法中的冒泡排序。由于简单的实现只会留下8位，因此只有256个哈希值...并不太好。你可以对块进行异或运算而不是单独的字节，但这样算法就变得更加复杂了。
因此，当然，密码算法可能做了一些你不需要的事情...但它们也是通用哈希质量的巨大提升。你正在使用的MD5哈希具有128位，有数十亿个可能的哈希值。你要想得到更好的结果，唯一的方法就是取一些代表性的数据样本，看看在其中应用各种算法时会出现多少冲突。
因此，在我看来，除非有理由不使用预先定义的哈希算法（例如性能），否则我建议你继续使用现有的算法。
1
无论您想要一个完美的哈希函数（对于每个评估为相等的对象都有不同的值）还是只需要一个相当不错的哈希函数，这总是一种性能权衡。计算出一个好的哈希函数通常需要时间，如果您的数据集较小，则最好使用快速函数。最重要的是正确性（正如您的第二篇帖子所指出的），为了实现这一点，您只需要返回数组的长度。根据您的数据集，这甚至可能是可以接受的。如果不行（比如说所有的数组长度都相等），您可以采用一些简单的方法，例如查看第一个和最后一个值并异或它们的值，然后根据您的数据适当增加更多复杂度。
快速检查哈希函数在您的数据上的表现的方法是将所有数据添加到哈希表中，并计算Equals函数被调用的次数，如果太频繁，则需要在函数上进行更多的工作。如果您这样做，请记住，哈希表的大小需要在开始时设置得比您的数据集大，否则您将重新哈希数据，这将触发重新插入和更多的Equals评估（虽然可能更真实）。
对于某些对象（不包括此对象），可以通过ToString().GetHashCode()生成快速的HashCode，虽然不是最优的，但由于人们倾向于从ToString()返回接近对象标识的内容，因此这非常有用，而这正是GetHashcode正在寻找的。
趣闻：我曾经见过的最糟糕的性能是有人错误地从GetHashCode中返回了一个常量，使用调试器很容易发现，特别是如果您在哈希表中进行了大量查找。
0
private int? hashCode;

public override int GetHashCode()
{
    if (!hashCode.HasValue)
    {
        var hash = 0;
        for (var i = 0; i < bytes.Length; i++)
        {
            hash = (hash << 4) + bytes[i];
        }
        hashCode = hash;
    }
    return hashCode.Value;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接