Guid和GetHashCode的唯一性

Question

鉴于以下关键:

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

这个钥匙作为Guid的独特之处是独一无二的吗？

Answer 1

该鸽巢原理说,没有.GUID有16个字节的信息 - 128位.一个int有32位的信息.(编辑:为了澄清由于注释,.NET GUID将允许这些128位任意设置,据我所知;随机生成的GUID遵循更严格的模式,因此没有2 ^128个不同的值,这将是随机的但仍然超过2 ^32.)

有2 ^128个可能的GUID和2 ^32个可能的哈希码 - 因此您不可能为每个GUID使用不同的哈希码.

还有更重要的是,虽然- GetHashCode()从未意思表示的独特性.如果它可以,那就太好了 - 但它没有必要,即使有足够的int值可用.

返回(比方说)除以2的值是完全有效的int.GetHashCode()...所以-1,0和1都将得到哈希码0; 3和4将得到2的哈希码等.它不会好(并且它会比返回值慢) - 但它将是一个有效的实现.它将满足所有约束GetHashCode- 即如果你在两个相等的值上调用它,它将返回相同的哈希码.

事实上,为所有值返回一个常量是一个有效的实现 - 尽管它是一个相当无用的实现,因为它将哈希表的正常快速查找呈现为O(N)操作.

Answer 2

就在今天,我注意到了另一个问题Guid.GetHashCode():在Microsoft .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不会被散列.

Answer 3

GetHashCode()返回一个整数 - 它不能像a一样唯一Guid,所以不 - 可能存在冲突,并且不保证唯一性.

哈希码的要点是它应该在哈希范围内均匀分布,以便碰撞通常很少见,但是你总是有碰撞的机会并且必须适应它.

Answer 4

我遇到的问题正是xanatos在另一个答案中描述的问题。我有一个类，其中Guid使用两个值来区分不同的对象，我发现我遇到了可怕的碰撞次数（我的指导不是随机生成的）。这是我用来解决问题的代码。 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;
    }