热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

还要谈谈Equals和GetHashcode

这篇随笔和上篇随笔《从两个数组中查找相同的数字谈Hashtable》都是为了下面分析Dictionary的实现做的铺垫一.两个逻辑上相等的实例对象。两个对象相等,除了指两个不同变量引用了

这篇随笔和上篇随笔《从两个数组中查找相同的数字谈Hashtable》都是为了下面分析Dictionary的实现做的铺垫

 

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

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


二.Object的GetHashcode方法。

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

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

View Code
    [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也有可能相等。当对象不相等但是hashcode相等的时候,就叫做hash冲突。

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

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

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

View Code
        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方法来完成。总而言之,保持两者的一致性是最好的做法。
所以.NET中定义了一个比较相等性的接口IEqualityComparer,就包含了EqualsGetHashCode这两种方法。Dictionary 和 HashSet 类的构造函数都用到了 IEqualityComparer 接口。还有 ConcurrentDictionary、SortedSet、KeyedCollection、SynchronizedKeyedCollection 等也使用 IEqualityComparer 接口作为构造函数的参数。


下面是个例子

class BoxEqualityComparer : IEqualityComparer
{

    public bool Equals(Box b1, Box b2)
    {
        if (b1.Height == b2.Height & b1.Length == b2.Length
                            & b1.Width == b2.Width)
        {
            return true;
        }
        else
        {
            return false;
        }
    }


    public int GetHashCode(Box bx)
    {
        int hCode = bx.Height ^ bx.Length ^ bx.Width;
        return hCode.GetHashCode();
    }

}

 在构造Dictionarty时如果不传递实现了这个接口的对象,那么就会使用EqualityComparer.Default。具体使用的是哪个,还是要看我们用做key的那个对象实现了哪个接口。

比如

struct MyKey : IEquatable {
}


//这个方法会被调用
public bool Equals(MyKey that) { }


和下面这个,生成的就是不同的实例

struct MyKey  {
}
//这个方法会被调用
 public bool Equals(Object that) {
 }

 

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

可以想象,最烂的Hashcode的实现方法无疑就是返回一个写死的整数,这样Hashtable很容易就被迫转换成链表结构。这是查找的时间复杂度就变味O(n)

        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发生了改变,那么你也没办法找到先前存放的对象,因为你计算出来的数组下标是错误的。

在没有重写GetHashCode方法的情况下,这个方法继承自Object,而Object的实现就是每一个New出来的对象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 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 Dictionaryint>();

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

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

}
}

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

View Code
public struct Point {
public int x;
public int y;

//other methods

public override int GetHashCode() {
return x ^ y;
}
}

 

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

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


重写后的代码如下:

View Code
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 Dictionaryint>();

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

Console.WriteLine(dic.ContainsKey(new Staff("123", "langxue")));
}
}

 

四.一些推荐做法:

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

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

 

有了这两篇随笔做铺垫,就为下篇Dictionary源码分析提供了帮助。


推荐阅读
  • 本文详细介绍了 com.apollographql.apollo.api.internal.Optional 类中的 orNull() 方法,并提供了多个实际代码示例,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 如何使用 net.sf.extjwnl.data.Word 类及其代码示例详解 ... [详细]
  • 本文介绍了如何使用Python爬取妙笔阁小说网仙侠系列中所有小说的信息,并将其保存为TXT和CSV格式。主要内容包括如何构造请求头以避免被网站封禁,以及如何利用XPath解析HTML并提取所需信息。 ... [详细]
  • 本文介绍了如何在 Spring Boot 项目中使用 spring-boot-starter-quartz 组件实现定时任务,并将 cron 表达式存储在数据库中,以便动态调整任务执行频率。 ... [详细]
  • 一个建表一个执行crud操作建表代码importandroid.content.Context;importandroid.database.sqlite.SQLiteDat ... [详细]
  • Java中不同类型的常量池(字符串常量池、Class常量池和运行时常量池)的对比与关联分析
    在研究Java虚拟机的过程中,笔者发现存在多种类型的常量池,包括字符串常量池、Class常量池和运行时常量池。通过查阅CSDN、博客园等相关资料,对这些常量池的特性、用途及其相互关系进行了详细探讨。本文将深入分析这三种常量池的差异与联系,帮助读者更好地理解Java虚拟机的内部机制。 ... [详细]
  • 在处理大图片时,PHP 常常会遇到内存溢出的问题。为了避免这种情况,建议避免使用 `setImageBitmap`、`setImageResource` 或 `BitmapFactory.decodeResource` 等方法直接加载大图。这些函数在处理大图片时会消耗大量内存,导致应用崩溃。推荐采用分块处理、图像压缩和缓存机制等策略,以优化内存使用并提高处理效率。此外,可以考虑使用第三方库如 ImageMagick 或 GD 库来处理大图片,这些库提供了更高效的内存管理和图像处理功能。 ... [详细]
  • 本文作为“实现简易版Spring系列”的第五篇,继前文深入探讨了Spring框架的核心技术之一——控制反转(IoC)之后,将重点转向另一个关键技术——面向切面编程(AOP)。对于使用Spring框架进行开发的开发者来说,AOP是一个不可或缺的概念。了解AOP的背景及其基本原理,对于掌握这一技术至关重要。本文将通过具体示例,详细解析AOP的实现机制,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 本文深入探讨了 MXOTDLL.dll 在 C# 环境中的应用与优化策略。针对近期公司从某生物技术供应商采购的指纹识别设备,该设备提供的 DLL 文件是用 C 语言编写的。为了更好地集成到现有的 C# 系统中,我们对原生的 C 语言 DLL 进行了封装,并利用 C# 的互操作性功能实现了高效调用。此外,文章还详细分析了在实际应用中可能遇到的性能瓶颈,并提出了一系列优化措施,以确保系统的稳定性和高效运行。 ... [详细]
  • 在Spring与Ibatis集成的环境中,通过Spring AOP配置事务管理至服务层。当在一个服务方法中引入自定义多线程时,发现事务管理功能失效。若不使用多线程,事务管理则能正常工作。本文深入分析了这一现象背后的潜在风险,并探讨了可能的解决方案,以确保事务一致性和线程安全。 ... [详细]
  • 在稀疏直接法视觉里程计中,通过优化特征点并采用基于光度误差最小化的灰度图像线性插值技术,提高了定位精度。该方法通过对空间点的非齐次和齐次表示进行处理,利用RGB-D传感器获取的3D坐标信息,在两帧图像之间实现精确匹配,有效减少了光度误差,提升了系统的鲁棒性和稳定性。 ... [详细]
  • 本文将深入探讨Java编程语言中顶级类`Object`的源码实现,旨在为Java新手提供进阶指导。`Object`类是所有Java类的基类,了解其内部机制对于提升编程技能至关重要。文章首先介绍了API文档的使用方法,这对于有开发经验的Java程序员来说是不可或缺的工具。通过详细解析`Object`类的关键方法和属性,读者可以更好地理解Java的核心原理和设计思想。此外,文章还提供了实际代码示例,帮助读者在实践中掌握这些知识。 ... [详细]
  • 本文介绍了如何在 Spring 3.0.5 中使用 JdbcTemplate 插入数据并获取 MySQL 表中的自增主键。 ... [详细]
  • 大类|电阻器_使用Requests、Etree、BeautifulSoup、Pandas和Path库进行数据抓取与处理 | 将指定区域内容保存为HTML和Excel格式
    大类|电阻器_使用Requests、Etree、BeautifulSoup、Pandas和Path库进行数据抓取与处理 | 将指定区域内容保存为HTML和Excel格式 ... [详细]
author-avatar
sunci99_652
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有