Guid和GetHashCode的唯一性问题

Question

给定以下密钥：

int key = Guid.NewGuid().GetHashCode();

这个键和Guid的唯一性一样吗？

- Ashraf Sayied-Ahmad

Answer 1

鸽巢原理说不行。GUID有16字节的信息-128位。一个int有32位的信息。(编辑：为了澄清由于评论，据我所知，.NET GUID将允许任意设置这128位；随机生成的GUID遵循更严格的模式，因此不会生成2¹²⁸个不同的值。尽管如此，仍然比2³²多。)

有2¹²⁸个可能的GUID和2³²个可能的哈希码，因此您不可能为每个GUID拥有不同的哈希码。

还有更多内容-GetHashCode()从来不意味着表示唯一性。如果它可以，则很好-但即使有足够的int值可用于此，它也不必这样做。 int.GetHashCode()返回（例如）除以二的值将完全有效...因此，-1、0和1都将获得哈希码0；3和4将获得哈希码2等。这不是好的（而且比只返回值要慢），但它是一个有效的实现。它将满足GetHashCode的所有约束-即，如果您在两个相等的值上调用它，它将返回相同的哈希码。

事实上，对于所有值返回常量是一种有效的实现方式——尽管这是一种相当无用的实现方式，因为它将哈希表通常快速查找转化为O(N)操作。

- Jon Skeet

---

@Joey：随机生成的可以，但我认为你可以将任何值放入16字节数组中，并将其传递给Guid构造函数。你有任何相反的证据吗？ - Jon Skeet

@Joey：好的，我们特别谈论的是.NET Guid类型，我仍然坚持认为该类型有2^128个可能的值。 - Jon Skeet

@Joey：当然，通常情况下你不会得到在Unicode中未分配值的字符串 - 但它们仍然是可以轻松创建的值。 - Jon Skeet

如果两个不同的实例可以具有相同的值，那么GetHashCode有什么用呢？ 它不能可靠地用于确认2个事物是相同的或者不同的！ - Jez

@Jez：它可以用来确认两个东西是否不同 - 如果它们有不同的哈希码，它们就不能相等（假设实现正确）。如果它们具有相同的哈希码，则可能相等。关键是，如果您在地图中有一百万个键，并且您正在尝试找到其中一个键，则可以非常快速地将其缩小为“仅具有正确哈希码的键”，然后您可以对所有这些候选项调用Equals以找出哪个键实际上是正确的。 - Jon Skeet

Answer 2

今天我注意到了 Guid.GetHashCode() 的另一个问题：在微软.NET实现中，Guid 的并非每个“字节”都被哈希处理：有6个字节的Guid没有被哈希，因此对其中任何一个字节的更改都不会改变哈希码。

我们可以在参考来源中看到此情况：

return _a ^ (((int)_b << 16) | (int)(ushort)_c) ^ (((int)_f << 24) | _k);

所以_d, _e, _g, _h, _i, _j字节不会被哈希。这对于"连续"的Guid有重要影响，例如：

c482fbe1-9f16-4ae9-a05c-383478ec9d13
c482fbe1-9f16-4ae9-a05c-383478ec9d14
c482fbe1-9f16-4ae9-a05c-383478ec9d15
...
c482fbe1-9f16-4ae9-a05c-383478ec9dff
c482fbe1-9f16-4ae9-a05c-383478ec9e00
c482fbe1-9f16-4ae9-a05c-383478ec9e01

像这样的 Guid，生成的不同哈希值数量非常小（256个不同的值），因为 3478ec9d/3478ec9e 不会被哈希。

- xanatos

---

哇，非常有趣的观察。不确定为什么微软不会对整个GUID进行哈希处理，但这是需要注意的事情... - Roger Hill

对于版本1 UUID，GetHashCode() 中包含的字段是60位时间戳和MAC地址的部分。对于版本4 UUID（从Guid.NewGuid()获得），GUID的几乎所有字节都是随机的。因此，在这些情况下，算法似乎是可以接受的。 - Martin Liversage

我在OracleDB生成的GUID上遇到了这个生产问题。有人能解释一下为什么它不会哈希所有的值吗？很难相信哈希额外的6个字节会成为性能问题。 - Philipp Aumayr

@PhilippAumayr 在 .NET Core 中已经发生了变化...现在所有的位都被哈希了（请参见 https://github.com/dotnet/runtime/blob/master/src/libraries/System.Private.CoreLib/src/System/Guid.cs#L795）。这个 commit 是从2016年的。 - xanatos

Answer 3

GetHashCode()返回一个整数 - 它不能像Guid那样唯一，因此不会保证唯一性并可能会发生碰撞。

散列码的关键是它应该在哈希范围内均匀分布，以便碰撞应该通常很少，但您始终有碰撞的机会，必须为此做出调整。

- BrokenGlass

---

需要注意的是，GUID并不能保证唯一性。 - Muad'Dib

据传说，于2012年12月21日可能会生成重复的GUID。 - Hans Passant

@HansPassant，很抱歉让你失望了。那个谣言是假的。 - Fabian Bigler

Answer 4

我在另一个答案中遇到了xanatos描述的问题。 我有一个类，其中使用两个Guid值来区分不同的对象，我发现我的Guids产生了可怕的碰撞（我的Guids不是随机生成的）。 这是我用来解决问题的代码。 Guid1和Guid2是用于区分对象的Guid类型属性。 该代码遵循Jon Skeet在此处描述的方法。

    public override int GetHashCode()
    {
        int hash = 173;
        foreach (Byte b in Guid1.ToByteArray().Concat(Guid2.ToByteArray()))
        {
            hash = hash * 983 + b;
        }
        return hash;
    }

- Tony Pulokas

---

这对我很有帮助。我正在寻找一个简单的“足够好”的算法，可以将GUID转换为整数，并具有较低的碰撞可能性。在我的情况下，该值的唯一性不需要全局——它在非常小的上下文/数据集中是唯一的。在这里找到了一个好东西，我已经用一些单元测试进行了验证。 - K. Akins

Answer 5

Guid是一个128位的数字。而int是32位的数字，所以它不能像Guid一样“唯一”。

此外，GetHashCode返回...哈希码，并不意味着它在任何方面都是唯一的。请参阅其他关于为什么存在GetHashCode()的SO讨论。

- Simon Mourier