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

Question

假设我有一个存储字节数组的对象,我希望能够为它有效地生成哈希码.我过去曾经使用过加密哈希函数,因为它们很容易实现,但是他们做的工作比他们应该加密的工作要多得多,而且我并不关心(我只是在用它)哈希码作为哈希表的密钥).

这就是我今天所拥有的:

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();

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

Answer 1

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

检查规则是:

• 哈希码是否相等？然后调用完整(慢)Equals方法.
• 哈希码不相等吗？那两个项目绝对不相等.

你想要的只是一个GetHashCode算法,它将你的集合分成大致均匀的组 - 它不应该形成密钥,因为HashTable或者Dictionary<>需要使用哈希来优化检索.

你期望数据有多长？怎么随机？如果长度变化很大(比如文件),那么只返回长度.如果长度可能相似,则查看变化的字节子集.

GetHashCode应该比Equals它快很多,但不一定是唯一的.

两个相同的东西绝不能有不同的哈希码.两个不同的对象不应该具有相同的哈希码,但是可以预期一些冲突(毕竟,存在比可能的32位整数更多的排列).

Answer 2

不要使用加密哈希作为哈希表,这是荒谬/过度的.

在这里你去...在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;

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

Answer 3

借用JetBrains软件生成的代码,我已经确定了这个功能:

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

仅仅XOring字节的问题是返回值的3/4(3字节)只有2个可能的值(全部打开或全部关闭).这会将比特分散一点.

在Equals中设置断点是一个很好的建议.将大约200,000个我的数据条目添加到字典中,可以看到大约10个等于呼叫(或1/20,000).

Answer 4

如果您正在寻找性能，我测试了一些哈希键，我推荐Bob Jenkin 的哈希函数。它的计算速度非常快，并且产生的冲突与您迄今为止使用的加密哈希一样少。

我根本不懂 C#，也不知道它是否可以与 C 链接，但这是它在 C 中的实现。