秒秒pk10下载_为什么要重写hashcode和equals方法?初级程序员在面试中很少能说清楚。

  • 时间:
  • 浏览:1

     我在面试 Java初级开发的事先,时不时会问:你有如此重写过hashcode最好的妙招?不少候选人直接说没写过。让他想,或许真的没写过,于是就再通过二个 现象确认:你在用HashMap的事先,键(Key)部分,有如此放过自定义对象?而这名事先,候选人说放过,于是二个 现象的回答就自相矛盾了。

    最近问下来,这名现象普遍回答不大好,于是在本文里,就干脆从hash表讲起,讲述HashMap的存数据规则,由此我门歌词 歌词 我门歌词 歌词 就自然清楚上述现象的答案了。

1 通过Hash算法来了解HashMap对象的高效性

    我门歌词 歌词 我门歌词 歌词 先复习数据型态里的二个 知识点:在二个 长度为n(假设是111500)的线性表(假设是ArrayList)里,存放着无序的数字;将会我门歌词 歌词 我门歌词 歌词 要找二个 指定的数字,就不得不通过从头到尾依次遍历来查找,从前的平均查找次数是n除以2(这里是11500)。

我门歌词 歌词 我门歌词 歌词 再来观察Hash表(这里的Hash表纯粹是数据型态上的概念,和Java无关)。它的平均查找次数接近于1,代价相当小,关键是在Hash表里,存装进 其中的数据和它的存储位置是用Hash函数关联的。

    我门歌词 歌词 我门歌词 歌词 假设二个 Hash函数是x*x%5。当然实际情况里不将会用如此简单的Hash函数,我门歌词 歌词 我门歌词 歌词 这里纯粹为了说明方便,而Hash表是二个 长度是11的线性表。将会我门歌词 歌词 我门歌词 歌词 要把6装进 其中,如此我门歌词 歌词 我门歌词 歌词 首先会对6用Hash函数计算一下,结果是1,所以我门歌词 歌词 我门歌词 歌词 就把6装进 到索引号是1这名位置。同样将会我门歌词 歌词 我门歌词 歌词 要放数字7,经过Hash函数计算,7的结果是4,如此它将被装进 索引是4的这名位置。这名效果如下图所示。

    从前做的好处非常明显。比如我门歌词 歌词 我门歌词 歌词 要从中找6这名元素,我门歌词 歌词 我门歌词 歌词 还需要先通过Hash函数计算6的索引位置,却说 直接从1号索引里找到它了。

不过我门歌词 歌词 我门歌词 歌词 会遇到“Hash值冲突”这名现象。比如经过Hash函数计算后,7和8会有相同的Hash值,对此Java的HashMap对象采用的是”链地址法“的处里方案。效果如下图所示。

 

    具体的做法是,为所有Hash值是i的对象建立二个 同义词链表。假设我门歌词 歌词 我门歌词 歌词 在装进 8的事先,发现4号位置将会被占,如此就会新建二个 链表结点装进 8。同样,将会我门歌词 歌词 我门歌词 歌词 要找8,如此发现4号索引里也有8,那会沿着链表依次查找。

    虽然我门歌词 歌词 我门歌词 歌词 还是无法彻底处里Hash值冲突的现象,却说 Hash函数设计合理,仍能保证同义词链表的长度被控制在二个 合理的范围里。这里讲的理论知识不不无的放矢,我门歌词 歌词 我门歌词 歌词 能在后文里清晰地了解到重写hashCode最好的妙招的重要性。

2 为那些要重写equals和hashCode最好的妙招

    我门歌词 歌词 歌词 我门歌词 歌词 用HashMap存入自定义的类时,将会不重写这名自定义类的equals和hashCode最好的妙招,得到的结果会和我门歌词 歌词 我门歌词 歌词 预期的不一样。我门歌词 歌词 我门歌词 歌词 来看WithoutHashCode.java这名例子。

在其中的第2到第18行,我门歌词 歌词 我门歌词 歌词 定义了二个 Key类;在其中的第3行定义了唯一的二个 属性id。当前我门歌词 歌词 我门歌词 歌词 先注释掉第9行的equals最好的妙招和第16行的hashCode最好的妙招。    

1	import java.util.HashMap;
2	class Key {
3		private Integer id;
4		public Integer getId() 
5	{return id; }
6		public Key(Integer id) 
7	{this.id = id;	}
8	//故意先注释掉equals和hashCode最好的妙招
9	//	public boolean equals(Object o) {
10	//		if (o == null || !(o instanceof Key)) 
11	//		{ return false;	} 
12	//		else 
13	//		{ return this.getId().equals(((Key) o).getId());}
14	//	}
15		
16	//	public int hashCode() 
17	//	{ return id.hashCode();	}
18	}
19	
20	public class WithoutHashCode {
21		public static void main(String[] args) {
22			Key k1 = new Key(1);
23			Key k2 = new Key(1);
24			HashMap<Key,String> hm = new HashMap<Key,String>(); 
25			hm.put(k1, "Key with id is 1");		
26			System.out.println(hm.get(k2));		
27		}
28	}

    在main函数里的第22和23行,我门歌词 歌词 我门歌词 歌词 定义了二个 Key对象,它们的id也有1,就好比它们是两把相同的都能打开同一扇门的钥匙。

    在第24行里,我门歌词 歌词 我门歌词 歌词 通过泛型创建了二个 HashMap对象。它的键部分还需要存放Key类型的对象,值部分还需要存储String类型的对象。

    在第25行里,我门歌词 歌词 我门歌词 歌词 通过put最好的妙招把k1和一串字符装进 到hm里; 而在第26行,我门歌词 歌词 我门歌词 歌词 想用k2去从HashMap里得到值;这就好比我门歌词 歌词 我门歌词 歌词 想用k1这把钥匙来锁门,用k2来开门。这是符合逻辑的,但从当前结果看,26行的返回结果也有我门歌词 歌词 我门歌词 歌词 想象中的那个字符串,所以null。

    由于 有二个 —如此重写。第一是如此重写hashCode最好的妙招,第二是如此重写equals最好的妙招。

   我门歌词 歌词 歌词 我门歌词 歌词 往HashMap里放k1时,首先会调用Key这名类的hashCode最好的妙招计算它的hash值,却说把k1装进 hash值所指引的内存位置。

    关键是我门歌词 歌词 我门歌词 歌词 如此在Key里定义hashCode最好的妙招。这里调用的仍是Object类的hashCode最好的妙招(所有的类也有Object的子类),而Object类的hashCode最好的妙招返回的hash值虽然是k1对象的内存地址(假设是11150)。

    

    将会我门歌词 歌词 我门歌词 歌词 却说是调用hm.get(k1),如此我门歌词 歌词 我门歌词 歌词 会再次调用hashCode最好的妙招(还是返回k1的地址11150),却说根据得到的hash值,能太快地找到k1。

    但我门歌词 歌词 我门歌词 歌词 这里的代码是hm.get(k2),我门歌词 歌词 歌词 我门歌词 歌词 调用Object类的hashCode最好的妙招(将会Key里没定义)计算k2的hash值时,虽然得到的是k2的内存地址(假设是1150)。将会k1和k2是二个 不同的对象,所以它们的内存地址一定不不相同,也所以说它们的hash值一定不同,这所以我门歌词 歌词 我门歌词 歌词 无法用k2的hash值去拿k1的由于 。

    我门歌词 歌词 歌词 我门歌词 歌词 把第16和17行的hashCode最好的妙招的注释加带后,会发现它是返回id属性的hashCode值,这里k1和k2的id也有1,所以它们的hash值是相等的。

    我门歌词 歌词 我门歌词 歌词 再来更正一下存k1和取k2的动作。存k1时,是根据它id的hash值,假设这里是1150,把k1对象装进 到对应的位置。而取k2时,是先计算它的hash值(将会k2的id也是1,这名值也是1150),却说到这名位置去找。

    但结果会出乎我门歌词 歌词 我门歌词 歌词 意料:明明1150号位置将会有k1,但第26行的输出结果依然是null。其由于 所以如此重写Key对象的equals最好的妙招。

    HashMap是用链地址法来处里冲突,也所以说,在1150号位置上,有将会占据 着多个用链表形式存储的对象。它们通过hashCode最好的妙招返回的hash值也有1150。

     我门歌词 歌词 歌词 我门歌词 歌词 通过k2的hashCode到1150号位置查找时,虽然会得到k1。但k1有将会仅仅是和k2具有相同的hash值,但不不和k2相等(k1和k2两把钥匙能够够开同一扇门),这名事先,就需要调用Key对象的equals最好的妙招来判断两者有无相等了。

    将会我门歌词 歌词 我门歌词 歌词 在Key对象里如此定义equals最好的妙招,系统就不得不调用Object类的equals最好的妙招。将会Object的固有最好的妙招是根据二个 对象的内存地址来判断,所以k1和k2一定不不相等,这所以为那些依然在26行通过hm.get(k2)依然得到null的由于 。

    为了处里这名现象,我门歌词 歌词 我门歌词 歌词 需要打开第9到14行equals最好的妙招的注释。在这名最好的妙招里,却说我二个 对象也有Key类型,却说 它们的id相等,它们就相等。

3 对面试现象的说明

    将会在项目里时不时会用到HashMap,所以我在面试的事先一定会问这名现象∶你有如此重写过hashCode最好的妙招?你在使用HashMap时有如此重写hashCode和equals最好的妙招?你是为什么么么在写的?

    根据问下来的结果,我发现初级守护程序员对这名知识点普遍没掌握好。重申一下,将会我门歌词 歌词 我门歌词 歌词 要在HashMap的“键”部分存放自定义的对象,一定要在这名对象里用此人 的equals和hashCode最好的妙招来覆盖Object里的同名最好的妙招。 

     本文是从Java核心技术及面试指南这本书中相关内容改编而来。