1

我有一个在 [1, 1000] 和字符串中有 3 个整数的结构。

我需要用 32 位数字表示它，以便至少一个字段中不同的两个结构会产生不同的代码，而具有相同内容的结构会始终产生相同的代码。通常整数字段之一将以几个单位增加。这必然会产生不同的代码。

起初，我想将结构字段格式化为常量格式的字符串，然后使用 String 类的 GetHashCode 函数对其进行哈希处理。但是后来我在一些讨论中读到，在相同输入上运行的重复过程不一定会产生相同的哈希输出。首先，在 .NET 4 中这是真的吗？这对我很重要，因为哈希值应该被持久化并在进程运行中保持一致。我还在这里看到了使用素数对应用于每个结构字段的平台 GetHashCode 的结果执行按位运算的建议。但是在这里，显然我不能指望过程运行的一致结果。

如果我使用加密哈希函数，我会超过 32 位。

如果我没有字符串字段，我会将代码组合为来自数字字段的 32 位数组。可能值得用字符串字段 GetHashCode 结果对这样的位数组进行异或吗？我是否会增加在某些输入上重复运行会产生相同哈希输出的机会？

你会建议做什么？

4

3 回答 3

1

匿名类型具有自动生成的合理GetHashCode()实现。我会尝试使用：

struct MyStruct 
{
    int _intField1;
    int _intField2;
    int _intField3;
    string _stringField;

    public long GetHashCode() 
    {
        return new { _intField1, _intField2, _intField3, _stringField }.GetHashCode();
    }
}

由于ints 和strings 都是不可变类型，因此只要底层 .NET 框架版本相同，哈希码在应用程序运行之间应该保持相同。（这可能会或可能不会“足够持久”。）

也就是说，如果内部实施发生变化，它可能会GetHashCode()发生变化。在这种情况下，请使用加密哈希。它超过 32 位并不重要，因为加密哈希旨在为输入的微小变化产生截然不同的输出。这意味着对于两个不同的输入，任何给定的 32 位哈希码都不太可能相等。只需使用BitConverter.ToInt32()将您想要的散列的任何部分转换为int.

此外，显然，这只会使两种不同的结构不太可能产生不同的哈希码。（这可以使用生日悖论的近似公式来确定，如果我正确阅读 wiki，这意味着一旦您存储了~140,000 ~30,000 条记录，您就有 10% 的机会获得重复。假设加密哈希具有理想的属性。我不确定如果没有完美的哈希，你能做得更好。）

于 2013-03-04T22:39:38.517 回答
1

如果您有以下情况：

struct 
{
    int A;
    int B;
    int C;
}

假设 A、B、C 在范围内[1, 1000]。可以创建“完美哈希”（没有冲突），因为 A、B、C 可以有 1000 个不同的可能值。实际上，log2(1000^3) <= 32(1000^3是结构的可能值的数量，并且log2用于获得存储所有这些值而不会发生冲突所需的位数，并且32是整数的位数)。

int MyHashCode()
{
    return 1000 * (1000 * (A - 1) + (B - 1)) + (C - 1);  // There is no overflow or collision since A, B, C are in the range [1, 1000]
}

我们可以通过使用更弱的条件来简化它：A、B、C 在 [0, 1000] 范围内：

int MyHashCode()
{
    return 1001 * (1001 * A + B) + C;  // There is no overflow or collision since A, B, C are in the range [0, 1000]
}

更新

鉴于您的结构中包含一个字符串。你想要达到的目标是不可能的。因为字符串可以表示无限数量的值。

如果可以做到这一点，可以创建一个非常强大的压缩算法。这可以将任何文件存储到... 32 位数字中！从数学上讲，它来自于一个单射函数只能映射到更大空间的事实。

于 2013-03-04T22:33:04.493 回答
0
  1. 将您的类型序列化为 byte[]
  2. 对byte[]应用常用的hash算法，得到hash byte[]
  3. 例如，提取哈希字节 [] 的前 32 位并使用它
于 2013-03-04T22:48:44.410 回答