哈希碰撞定义解析及C# Dictionary链式存储失效问题咨询

一、哈希碰撞到底是什么？ #

• 哈希碰撞的核心定义是：两个不同的对象生成了完全相同的哈希码，这是哈希碰撞的本质。
• 至于“进入Dictionary的同一个桶”，这是哈希碰撞带来的结果——因为Dictionary会根据哈希码计算桶的索引，相同哈希码必然会被分配到同一个桶里。反过来，就算两个对象哈希码不同，也可能因为索引计算（比如取模）的巧合落到同一个桶，这种属于广义上的桶冲突，但通常我们说的哈希碰撞特指哈希码重复的情况。

二、你的C#代码为什么没触发链式存储？ #

先看你的代码逻辑：

static Dictionary<Number, string> dict = new Dictionary<Number, string>();

class Number
{
    private int X;

    public Number(int x)
    {
        X = x;
    }

    public override bool Equals(object obj)
    {
        Number other = obj as Number;
        return X.Equals(other.X);
    }

    public override int GetHashCode()
    {
        return X;
    }
}

public static void Main(string[] args)
{
    dict.Add(new Number(5), "Value5");
    dict.Add(new Number(2), "Value2");
    dict.Add(new Number(5), "Value52"); // 这里会直接报错
}

问题出在：你添加的两个new Number(5)对象，在Dictionary看来是同一个键——因为它们的Equals方法返回true，且哈希码相同。Dictionary不允许重复键，所以执行第三行Add的时候会直接抛出ArgumentException，根本到不了链式存储那一步。

链式存储是用来处理键不同但哈希码相同的情况。比如修改GetHashCode方法，让不同X值返回相同哈希码：

public override int GetHashCode()
{
    return X % 2; // 所有奇数返回1，偶数返回0
}

这时候添加new Number(1)和new Number(3)，它们是不同的键（Equals返回false）但哈希码相同，Dictionary才会把这两个元素放到同一个桶里，用链式存储保存，不会报错。

内容的提问来源于stack exchange，提问作者garnom