12

这个问题来自关于tuples的讨论。

我开始考虑元组应该具有的哈希码。如果我们接受 KeyValuePair 类作为元组呢？它不会覆盖 GetHashCode() 方法，所以它可能不会知道它的“孩子”的哈希码......所以，运行时将调用 Object.GetHashCode()，它不知道实物结构。

然后我们可以创建一些引用类型的两个实例，它们实际上是 Equal，因为重载了 GetHashCode() 和 Equals()。并将它们用作元组中的“孩子”来“欺骗”字典。

但它不起作用！运行时以某种方式计算出我们的元组的结构并调用我们类的重载 GetHashCode！

它是如何工作的？Object.GetHashCode() 做了什么分析？

当我们使用一些复杂的键时，它会在一些糟糕的情况下影响性能吗？（可能，不可能的情况......但仍然）

以这段代码为例：

namespace csharp_tricks
{
    class Program
    {
        class MyClass
        {
            int keyValue;
            int someInfo;

            public MyClass(int key, int info)
            {
                keyValue = key;
                someInfo = info;
            }

            public override bool Equals(object obj)
            {
                MyClass other = obj as MyClass;
                if (other == null) return false;

                return keyValue.Equals(other.keyValue);
            }

            public override int GetHashCode()
            {
                return keyValue.GetHashCode();
            }
        }

        static void Main(string[] args)
        {
            Dictionary<object, object> dict = new Dictionary<object, object>();

            dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 1), 1), 1);

            //here we get the exception -- an item with the same key was already added
            //but how did it figure out the hash code?
            dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 2), 1), 1); 

            return;
        }
    }
}

更新我想我已经找到了对此的解释，如下所述。它的主要成果是：

  • 小心你的密钥和它们的哈希码:-)
  • 对于复杂的字典键，您必须正确覆盖 Equals() 和 GetHashCode()。
4

6 回答 6

13

不要在可变类上覆盖 GetHashcode() 和 Equals()，只在不可变类或结构上覆盖它，否则如果您修改用作键的对象，哈希表将不再正常工作（您将无法在修改键对象后检索与键关联的值）

此外，哈希表不使用哈希码来标识对象，它们使用键对象本身作为标识符，并不要求用于在哈希表中添加条目的所有键都返回不同的哈希码，但建议它们这样做，否则性能深受其害。

于 2008-09-19T15:26:38.323 回答
3

这是 Quad 元组（内部包含 4 个元组组件）的正确哈希和相等实现。此代码确保在 HashSets 和字典中正确使用此特定元组。

更多关于这个主题（包括源代码）在这里。

注意unchecked关键字的使用（以避免溢出），如果 obj 为 null 则抛出 NullReferenceException（根据基本方法的要求）

public override bool Equals(object obj)
{
    if (ReferenceEquals(null, obj))
        throw new NullReferenceException("obj is null");
    if (ReferenceEquals(this, obj)) return true;
    if (obj.GetType() != typeof (Quad<T1, T2, T3, T4>)) return false;
    return Equals((Quad<T1, T2, T3, T4>) obj);
}

public bool Equals(Quad<T1, T2, T3, T4> obj)
{
    if (ReferenceEquals(null, obj)) return false;
    if (ReferenceEquals(this, obj)) return true;
    return Equals(obj.Item1, Item1)
        && Equals(obj.Item2, Item2)
            && Equals(obj.Item3, Item3)
                && Equals(obj.Item4, Item4);
}

public override int GetHashCode()
{
    unchecked
    {
        int result = Item1.GetHashCode();
        result = (result*397) ^ Item2.GetHashCode();
        result = (result*397) ^ Item3.GetHashCode();
        result = (result*397) ^ Item4.GetHashCode();
        return result;
    }
}
public static bool operator ==(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right)
{
    return Equals(left, right);
}


public static bool operator !=(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right)
{
    return !Equals(left, right);
}
于 2008-09-30T17:23:11.063 回答
2

查看 Brad Abrams 的这篇文章以及 Brian Grunkemeyer 的评论，了解有关 object.GetHashCode 如何工作的更多信息。另外，请查看 Ayande 博客文章的第一条评论。我不知道框架的当前版本是否仍然遵循这些规则，或者他们是否真的像 Brad 暗示的那样改变了它。

于 2008-09-19T15:36:32.623 回答
1

看来我现在有了线索。

我认为 KeyValuePair 是一个引用类型，但它不是，它是一个结构。因此它使用 ValueType.GetHashCode() 方法。MSDN 说：“派生类型的一个或多个字段用于计算返回值”。

如果您将真正的引用类型作为“元组提供者”，那么您将欺骗字典（或您自己......）。

using System.Collections.Generic;

namespace csharp_tricks
{
    class Program
    {
        class MyClass
        {
            int keyValue;
            int someInfo;

            public MyClass(int key, int info)
            {
                keyValue = key;
                someInfo = info;
            }

            public override bool Equals(object obj)
            {
                MyClass other = obj as MyClass;
                if (other == null) return false;

                return keyValue.Equals(other.keyValue);
            }

            public override int GetHashCode()
            {
                return keyValue.GetHashCode();
            }
        }

        class Pair<T, R>
        {
            public T First { get; set; }
            public R Second { get; set; }
        }

        static void Main(string[] args)
        {
            var dict = new Dictionary<Pair<int, MyClass>, object>();

            dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 2) }, 1);

            //this is a pair of the same values as previous! but... no exception this time...
            dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 3) }, 1);

            return;
        }
    }
}
于 2008-09-19T16:44:28.497 回答
0

我不再有这本书的参考资料，我必须找到它来确认一下，但我认为默认的基本哈希只是将你对象的所有成员散列在一起。由于 CLR 的工作方式，它可以访问它们，所以它不是你可以像他们那样编写的东西。

这完全来自我简要阅读的内容的记忆，因此请随心所欲。

编辑：这本书是来自 MS Press的Inside C# 。盖子上有锯片的那个。作者花了很多时间解释 CLR 是如何实现的，语言如何翻译成 MSIL 等等。等等。如果你能找到这本书，那读起来还不错。

编辑：形成链接提供它看起来像

Object.GetHashCode() 使用 System.Object 类中的内部字段来生成哈希值。创建的每个对象都被分配一个唯一的对象键，在创建时存储为整数。这些键从 1 开始，并在每次创建任何类型的新对象时递增。

嗯，如果我希望将对象用作散列键，我想我需要编写一些自己的散列码。

于 2008-09-19T15:21:47.477 回答
-1

所以它可能不会知道它的“孩子”的哈希码。

您的示例似乎证明并非如此 :-) 键MyClass和值的哈希码对于1两者都是相同KeyValuePair的。KeyValuePair 实现必须同时使用Key它Value自己的哈希码

向上移动，字典类需要唯一的键。它使用每个键提供的哈希码来解决问题。请记住，运行时不是在调用Object.GetHashCode()，而是在调用您给它的实例提供的 GetHashCode() 实现。

考虑一个更复杂的情况：

public class HappyClass
{

    enum TheUnit
    {
        Points,
        Picas,
        Inches
    }

    class MyDistanceClass
    {
        int distance;
        TheUnit units;

        public MyDistanceClass(int theDistance, TheUnit unit)
        {
            distance = theDistance;

            units = unit;
        }
        public static int ConvertDistance(int oldDistance, TheUnit oldUnit, TheUnit newUnit)
        {
            // insert real unit conversion code here :-)
            return oldDistance * 100;
        }

        /// <summary>
        /// Figure out if we are equal distance, converting into the same units of measurement if we have to
        /// </summary>
        /// <param name="obj">the other guy</param>
        /// <returns>true if we are the same distance</returns>
        public override bool Equals(object obj)
        {
            MyDistanceClass other = obj as MyDistanceClass;
            if (other == null) return false;

            if (other.units != this.units)
            {
                int newDistance = MyDistanceClass.ConvertDistance(other.distance, other.units, this.units);
                return distance.Equals(newDistance);
            }
            else
            {
                return distance.Equals(other.distance);
            }


        }

        public override int GetHashCode()
        {
            // even if the distance is equal in spite of the different units, the objects are not
            return distance.GetHashCode() * units.GetHashCode();
        }
    }
    static void Main(string[] args)
    {

        // these are the same distance... 72 points = 1 inch
        MyDistanceClass distPoint = new MyDistanceClass(72, TheUnit.Points);
        MyDistanceClass distInch = new MyDistanceClass(1, TheUnit.Inch);

        Debug.Assert(distPoint.Equals(distInch), "these should be true!");
        Debug.Assert(distPoint.GetHashCode() != distInch.GetHashCode(), "But yet they are fundimentally different values");

        Dictionary<object, object> dict = new Dictionary<object, object>();

        dict.Add(new KeyValuePair<MyDistanceClass, object>(distPoint, 1), 1);

        //this should not barf
        dict.Add(new KeyValuePair<MyDistanceClass, object>(distInch, 1), 1);

        return;
    }

}

基本上......在我的示例中，您希望两个距离相同的对象为 Equals 返回“true”，但返回不同的哈希码。

于 2008-09-19T15:48:19.240 回答