首页 / 知识

关于哈希：如何从C＃中的字节数组生成哈希码？

2023-04-12 12:43:00

How do I generate a hashcode from a byte array in C#?

假设我有一个存储字节数组的对象，并且希望能够有效地为其生成哈希码。过去，我已经使用了加密哈希函数，因为它们易于实现，但是它们的工作量远远超过了以单向加密的方式，而且我对此并不在乎(我只是在使用哈希码作为哈希表的键)。

这是我今天所拥有的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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支票，我已经对其进行了更新。使用字节数组中的现有哈希码将导致引用相等(或至少将相同的概念转换为哈希码)。
例如：

1
2
3
4

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

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

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

检查规则为：

哈希码是否相等？然后调用完整(慢速)Equals方法。
哈希码不相等吗？那么，这两项绝对不相等。

您想要的只是一个GetHashCode算法，该算法将您的集合大致分为几类-它不应该构成键，因为HashTable或Dictionary<>将需要使用哈希来优化检索。

您希望数据多长时间？如何随机？如果长度变化很大(例如文件)，则只需返回长度即可。如果长度可能相似，则查看变化的字节子集。

GetHashCode应该比Equals快很多，但不必唯一。

两个相同的事物绝对不能具有不同的哈希码。两个不同的对象不应具有相同的哈希码，但是可能会发生一些冲突(毕竟，比可能的32位整数有更多的排列)。

不要将加密哈希用于哈希表，这太荒谬了。

你们去...在C＃中修改了FNV哈希

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;
}
}

借用JetBrains软件生成的代码，我决定使用此功能：

1
2
3
4
5
6
7
8
9
10

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个条目添加到Dictionary中，可以看到大约10个Equals调用(或1 / 20,000)。

我发现了有趣的结果：

我上课：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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类型的键的字典，以测试插入的速度以及我还知道有多少次碰撞。我做了以下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 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()方法中找到此处找到的几个答案，来判断哪种方法最有效。迄今为止，最快且冲突次数最少的方法是：

1
2
3
4
5

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

花了2秒钟来执行。方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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秒钟执行！

您是否将其与SHA1CryptoServiceProvider.ComputeHash方法进行了比较？它需要一个字节数组并返回SHA1哈希，我相信它已经很好地优化了。我在一个Identicon处理程序中使用它，该程序在负载下表现良好。

无论您是想要一个完美的哈希函数(每个对象的值都相等)还是一个不错的哈希函数，始终都是性能的折衷，通常需要时间来计算一个好的哈希函数，如果您的数据集很小，那么您最好快速功能。最重要的是正确性(正如您在第二篇文章中所指出的那样)，要实现这一目标，您需要返回数组的Length。根据您的数据集，可能还可以。如果不是(例如，所有数组都一样长)，则可以使用一些便宜的东西，例如查看第一个和最后一个值并对它们的值进行XOR，然后添加更多的复杂性(如认为适合您的数据)。

查看哈希函数如何对数据执行的一种快速方法是将所有数据添加到哈希表中，并计算调用Equals函数的次数，如果这种情况经常发生，则您需要对该函数进行更多的工作。如果执行此操作，请记住，哈希表的大小必须在开始时设置为大于数据集的大小，否则将重新哈希数据，这将触发重新插入和更多的Equals评估(尽管可能更现实吗？)

对于某些对象(不是这个对象)，可以通过ToString()。GetHashCode()生成快速的HashCode，这当然不是最佳方法，但是由于人们倾向于从ToString()返回与对象的身份相似的东西，因此很有用。 GetHashcode在寻找什么

Trivia：我见过的最糟糕的性能是有人错误地从GetHashCode返回了一个常量，尽管很容易通过调试器发现，特别是如果您在哈希表中进行大量查找时

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

我所学到的最简单的哈希是将所有字节异或。它比大多数复杂的哈希算法简单易行，而且比用于小型数据集的中途通用哈希算法要快。这实际上是Bubble Sort的哈希算法。由于简单的实现将使您剩下8位，因此只有256个散列...并不是那么热。您可以对块进行XOR运算，而不是单个字节，但随后算法变得更加复杂。

因此，可以肯定的是，密码算法可能正在做一些您不需要的事情……但是它们在通用哈希质量上也有了巨大的进步。您正在使用的MD5哈希具有128位，并且可能有数十亿个哈希。您可能会得到更好的改进的唯一方法是对您希望通过应用程序进行数据处理的一些代表性样本，并在其上尝试各种算法，以查看遇到了多少冲突。

因此，在我看到不使用固定哈希算法的某些理由(也许是性能？)之前，我将不得不建议您坚持使用现有的技术。

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

如果您正在寻找性能，我测试了一些哈希键，并且
我推荐鲍勃·詹金(Bob Jenkin)的哈希函数。都快疯了
进行计算，将产生与密码术一样少的碰撞
您到目前为止使用的哈希。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}

RuntimeHelpers.GetHashCode可能会帮助：