如何从 C 中的字节数组生成哈希码

假设我有一个存储字节数组的对象,我希望能够有效地为其生成哈希码。我过去曾为此使用过加密哈希函数,因为它们易于实现,但它们所做的工作比单向加密要多得多,我不在乎(我只是使用哈希码作为哈希表的键)。

这是我今天所拥有的:

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 的检查,我已经更新了。使用字节数组中的现有哈希码将导致引用相等(或至少将相同的概念转换为哈希码)。 例如:

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

使用该代码,尽管两个字节数组在其中具有相同的值,但它们指的是内存的不同部分,并会导致(可能)不同的哈希码。我需要具有相同内容的两个字节数组的哈希码相等。

请先 登录 后评论

5 个回答

Keith

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

检查规则是:

  • 哈希码是否相等?然后调用完整的(慢)Equals 方法。
  • 哈希码不相等吗?那么这两个项目肯定不相等。

您只需要一个 GetHashCode 算法,将您的集合分成大致均匀的组 - 它不应该像 HashTable4< 那样形成密钥/code> 将需要使用哈希来优化检索。

您预计数据会持续多久?有多随机?如果长度变化很大(比如文件),那么只需返回长度。如果长度可能相似,请查看变化的字节子集。

GetHashCode 应该比 Equals 快很多,但不需要唯一。

两个相同的事物绝不能具有不同的哈希码。两个不同的对象不应该具有相同的哈希码,但是可以预料到一些冲突(毕竟,排列比可能的 32 位整数更多)。

请先 登录 后评论
Community

不要对哈希表使用加密哈希,这太荒谬/矫枉过正了。

给你...在C中修改的FNV哈希

请先 登录 后评论
Lee

生成一个好的散列说起来容易做起来难。请记住,您基本上是用 m 位信息表示 n 个字节的数据。您的数据集越大,m 越小,发生冲突的可能性就越大……解析为相同散列的两条数据。

我所学过的最简单的哈希就是将所有字节异或在一起。它比大多数复杂的散列算法和用于小数据集的半体面的通用散列算法更容易、更快。这确实是一种冒泡算法。因为简单的实现会给你留下 8 位,所以只有 256 个哈希......不是那么热。您可以异或块而不是单个字节,但算法会变得更加复杂。

当然,加密算法可能正在做一些您不需要的事情……但它们在通用哈希质量方面也是一个巨大的进步。您使用的 MD5 散列有 128 位,有数十亿个可能的散列。您可能会得到更好的东西的唯一方法是获取一些您希望通过应用程序的数据的代表性样本,并在其上尝试各种算法以查看您遇到的碰撞次数。

因此,除非我有理由不使用固定哈希算法(也许是性能?),否则我将不得不建议您坚持使用现有的算法。

请先 登录 后评论
Community

借用JetBrains软件生成的代码,定下了这个功能:

    public override int GetHashCode()
    {
        unchecked
        {
            var result = 0;
            foreach (byte b in _key)
                result = (result*31) ^ b;
            return result;
        }
    }

仅对字节进行异或运算的问题在于,返回值的 3/4(3 个字节)只有 2 个可能的值(全开或全关)。这将更多地传播这些位。

在 Equals 中设置断点是一个很好的建议。将我的数据的大约 200,000 个条目添加到字典中,会看到大约 10 个 Equals 调用(或 1/20,000)。

请先 登录 后评论
Oskar

无论您想要一个完美的散列函数(每个评估为相等的对象的不同值)还是只是一个相当好的散列函数总是一个性能权衡,通常需要时间来计算一个好的散列函数,如果您的数据集很小,你最好有一个快速的功能。最重要的(正如你的第二篇文章指出的)是正确性,要实现这一点,你需要返回数组的长度。取决于您的数据集,这甚至可能没问题。如果不是(假设您的所有数组都一样长),您可以使用一些便宜的方法,例如查看第一个和最后一个值并对它们的值进行异或,然后在您认为适合您的数据时增加更多的复杂性。

查看哈希函数对数据的执行情况的一种快速方法是将所有数据添加到哈希表中并计算调用 Equals 函数的次数,如果调用次数过多,则您需要对该函数执行更多工作.如果您这样做,请记住,开始时哈希表的大小需要设置为大于数据集,否则您将重新哈希数据,这将触发重新插入和更多的 Equals 评估(尽管可能更现实?)

对于某些对象(不是这个),可以通过 ToString().GetHashCode() 生成快速的 HashCode,这当然不是最佳的,但很有用,因为人们倾向于从 ToString() 和这正是 GetHashcode 正在寻找的

琐事:我见过的最糟糕的表现是有人错误地从 GetHashCode 返回了一个常量,但使用调试器很容易发现,尤其是当你在哈希表中进行大量查找时

请先 登录 后评论