首页 > 代码库 > Equals和GetHashcode

Equals和GetHashcode

一.两个逻辑上相等的实例对象。

两个对象相等,除了指两个不同变量引用了同一个对象外,更多的是指逻辑上的相等。什么是逻辑上相等呢?就是在一定的前提上,这两个对象是相等的。比如说某男生叫刘益红,然后也有另外一个女生叫刘益红,虽然这两个人身高,爱好,甚至性别上都不相同,但是从名字上来说,两者是相同的。Equals方法通常指的就是逻辑上相等。

二.Object的GetHashcode方法。

计算Hashcode的算法中,应该至少包含一个实例字段。Object中由于没有有意义的实例字段,也对其派生类型的字段一无所知,因此就没有逻辑相等这一概念。所以默认情况下Object的GetHashcode方法的返回值,应该都是独一无二的。利用Object的GetHashcode方法的返回值,可以在AppDomain中唯一性的标识对象。

下面是.Net中Object代码的实现:


    [Serializable]
    public class Object
    {
        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
        public Object()
        {
        }
        public virtual string ToString()
        {
            return this.GetType().ToString();
        }
        [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        public virtual bool Equals(object obj)
        {
            return RuntimeHelpers.Equals(this, obj);
        }
        [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        public static bool Equals(object objA, object objB)
        {
            return objA == objB || (objA != null && objB != null && objA.Equals(objB));
        }
        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success), TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        public static bool ReferenceEquals(object objA, object objB)
        {
            return objA == objB;
        }
        [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        public virtual int GetHashCode()
        {
            return RuntimeHelpers.GetHashCode(this);
        }
        [SecuritySafeCritical]
        [MethodImpl(MethodImplOptions.InternalCall)]
        public extern Type GetType();
        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
        protected virtual void Finalize()
        {
        }
        [SecuritySafeCritical]
        [MethodImpl(MethodImplOptions.InternalCall)]
        protected extern object MemberwiseClone();
        [SecurityCritical]
        private void FieldSetter(string typeName, string fieldName, object val)
        {
            FieldInfo fieldInfo = this.GetFieldInfo(typeName, fieldName);
            if (fieldInfo.IsInitOnly)
            {
                throw new FieldAccessException(Environment.GetResourceString("FieldAccess_InitOnly"));
            }
            Message.CoerceArg(val, fieldInfo.FieldType);
            fieldInfo.SetValue(this, val);
        }
        private void FieldGetter(string typeName, string fieldName, ref object val)
        {
            FieldInfo fieldInfo = this.GetFieldInfo(typeName, fieldName);
            val = fieldInfo.GetValue(this);
        }
        private FieldInfo GetFieldInfo(string typeName, string fieldName)
        {
            Type type = this.GetType();
            while (null != type && !type.FullName.Equals(typeName))
            {
                type = type.BaseType;
            }
            if (null == type)
            {
                throw new RemotingException(string.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("Remoting_BadType"), new object[]
                {
                    typeName
                }));
            }
            FieldInfo field = type.GetField(fieldName, BindingFlags.IgnoreCase | BindingFlags.Instance | BindingFlags.Public);
            if (null == field)
            {
                throw new RemotingException(string.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("Remoting_BadField"), new object[]
                {
                    fieldName, 
                    typeName
                }));
            }
            return field;
        }
    }

 

 为什么会有Hashcode?

Hashcode是为了帮助计算出该对象在hashtable中所处的位置。而能够把一个对象放入hashtable中无疑是有好处的。

这是Hashcode的作用,但是我们为什么需要他?

因为一个类型在定义了Equals方法后,在System.Collections.Hashtable类型,System.Collections.Generic.Dictionary类型以及其他一些集合的实现中,要求如果两个对象相等,不能单单只看Equals方法返回true,还必须要有相同的Hashcode.

这相当于一种前提条件的假设,而上述这些类型就是基于这种假设的基础上实现的。如果不遵守这些条件,那么在使用这些集合的时候就会出问题。

下面是摘自MSDN的一段描述

Hashcode是一个用于在相等测试过程中标识对象的数值。它还可以作为一个集合中的对象的索引。 GetHashCode方法适用于哈希算法和诸如哈希表之类的数据结构。 GetHashCode 方法的默认实现不保证针对不同的对象返回唯一值。而且,.NET Framework 不保证 GetHashCode 方法的默认实现以及它所返回的值在不同版本的 .NET Framework 中是相同的。因此,在进行哈希运算时,该方法的默认实现不得用作唯一对象标识符。

上面这段话想说明的就是:两个对象相等,hashcode也应该相等。但是两个对象不等,hashcode也有可能相等。

下面这两个不同的string对象就产生了相同的hashcode:

            string str1 = "NB0903100006";
string str2 = "NB0904140001";
Console.WriteLine(str1.GetHashCode());
Console.WriteLine(str2.GetHashCode());

这是因为string类型重写了Object的GetHashcode方法,如下:


        public override int GetHashCode() {
            unsafe { 
                fixed (char *src = this) {
                    Contract.Assert(src[this.Length] == ‘\0‘, "src[this.Length] == ‘\\0‘");
                    Contract.Assert( ((int)src)%4 == 0, "Managed string should start at 4 bytes boundary");
 
#if WIN32
                    int hash1 = (5381<<16) + 5381; 
#else 
                    int hash1 = 5381;
#endif 
                    int hash2 = hash1;

#if WIN32
                    // 32bit machines. 
                    int* pint = (int *)src;
                    int len = this.Length; 
                    while(len > 0) { 
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                        if( len <= 2) { 
                            break;
                        }
                        hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                        pint += 2; 
                        len  -= 4;
                    } 
#else 
                    int     c;
                    char *s = src; 
                    while ((c = s[0]) != 0) {
                        hash1 = ((hash1 << 5) + hash1) ^ c;
                        c = s[1];
                        if (c == 0) 
                            break;
                        hash2 = ((hash2 << 5) + hash2) ^ c; 
                        s += 2; 
                    }
#endif 
#if DEBUG
                    // We want to ensure we can change our hash function daily.
                    // This is perfectly fine as long as you don‘t persist the
                    // value from GetHashCode to disk or count on String A 
                    // hashing before string B.  Those are bugs in your code.
                    hash1 ^= ThisAssembly.DailyBuildNumber; 
#endif 
                    return hash1 + (hash2 * 1566083941);
                } 
            }
        }

 

归根结底,因为hashcode本来就是为了方便我们计算位置用的,本意并不是用来判断两个对象是否相等,这工作还是要交给Equals方法来完成。

两个拥有相同Hashcode的对象,只能说是有可能是相等的。而可能性就取决你的Hash函数是怎么实现的了。实现得越好,相等的可能性越大,相应的Hashtable性能就越好。这是因为放置在同一个Hash桶上的元素可能性就越小,越少可能发生碰撞。

可以想象,最烂的Hashcode的实现方法无疑就是返回一个写死的整数,这样Hashtable很容易就被迫转换成链表结构。

        public override int GetHashCode()
{
return 31;
}

一个好的hash函数通常意味着尽量做到“为不相等的对象产生不相等的hashcode",但是不要忘记”相同的对象必须有相同的hashcode"。一个是尽量做到,一个是必须的。

不相等的对象有相同的hashcode只是影响性能,而相同的对象(Equals返回true)没有相同的hashcode就会破坏整个前提条件

因此,计算hashcode的时候要避免使用在实现Equals方法中没有使用的字段,否则也可能出现Equals为true,但是hashcode却不相等的情况。

 

 三.逻辑上相等但是完全不同的实例

正如同1中所举的例子一样,两人同名,但是两人并不是同一个人。如上所述一般情况下我们判断两个对象是否相等使用的是Equals方法,但是在一些数据结构里面,判断两个对象是否相同,却采用的是hashcode。比如说Dictionnary,这时候如果没有重写GetHashcode方法,就会产生问题。

简单的描述一下整个过程:

1.在一个基于hashtable这种数据结构的集合中,添加一个key/value pair的时候,首先会获取key对象的hashcode,而这个hashcode指出这个key/value pair应该放在数组的那个位置上。

2.当我们在集合中查找一个对象是否存在时,会获取指定对象的hashcode,而这个hashcode就是当初用来计算出存放对象的位置的。因此如果hashcode发生了改变,那么你也没办法找到先前存放的对象。因为你计算出来的数组下标是错误的。

举例:

   public class Staff
    {
        private readonly string ID;
        private readonly string name;

        public Staff(string ID, string name)
        {
            this.ID = ID;
            this.name = name;
        }

        public override bool Equals(object obj)
        {
            if (obj == this)
                return true;
            if (!(obj is Staff))
                return false;

            var staff = (Staff)obj;

            return name == staff.name && ID == staff.ID;
        }
    }

    public class HashtableTest
    {
        public static void Main(){       
       Staff a = new Staff("123", "langxue");             Staff b = new Staff("123", "langxue");              Console.WriteLine(a.Equals(b));  //返回true

            var dic = new Dictionary<Staff, int>();

            dic.Add(new Staff("123", "langxue"), 0213);

            Console.WriteLine(dic.ContainsKey(new Staff("123", "langxue"))); //返回false

        }
    }

这时,我们就要重写hashcode方法,常见的就是XOR方式(先“或”然后取反):

 

当然,我们在这里可以直接使用.NET框架中帮string类型重写的GetHashcode方法:

        public override int GetHashCode()
{
return (ID + name).GetHashCode();
}


重写后的代码如下: 


public class Staff
    {
        private readonly string ID;
        private readonly string name;
 
        public Staff(string ID, string name)
        {
            this.ID = ID;
            this.name = name;
        }
 
        public override bool Equals(object obj)
        {
            if (obj == this)
                return true;
            if (!(obj is Staff))
                return false;
 
            var staff = (Staff)obj;
 
            return name == staff.name && ID == staff.ID;
        }
 
        public override int GetHashCode()
        {
            return (ID + name).GetHashCode();
        }
    }
 
    public class HashtableTest
    {
        public static void Main(){
 
            Staff a = new Staff("123", "langxue");
            Staff b = new Staff("123", "langxue");
 
            Console.WriteLine(a.Equals(b));
 
            var dic = new Dictionary<Staff, int>();
 
            dic.Add(new Staff("123", "langxue"), 0213);
 
            Console.WriteLine(dic.ContainsKey(new Staff("123", "langxue")));
        }
    }

 

四.一些推荐做法:

1.如果你觉得这种类型的大多数对象会被用作hash keys,那么就应该在创建实例的时候计算hash code。否则,可以选择采用”延迟初始化“的方法,在hashcode被第一次使用的时候再初始化。

2.不要试图从hash code中排除一个对象的某些关键字段来提高性能。

这就相当于把限制条件放宽,使得对象间的区别不那么明显,最终导致hash函数计算出来的hashcode相等,使得放入hashtable时发生碰撞,导致性能低下。

转自:http://www.cnblogs.com/colder/archive/2012/11/29/2795523.html

Equals和GetHashcode