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

  • 时间:
  • 浏览:0
  • 来源:亦辰娱乐网 - 专注共享黑色天空博客活动

     我在面试 Java初级开发的后来,老是 会问:你有没法 重写过hashcode土法律法子?不少候选人直接说没写过。我你可不还都能否想,或许真的没写过,于是就再通过有俩个 哪此的问题图片确认:你在用HashMap的后来,键(Key)每种,有没法 放过自定义对象?而你这人 后来,候选人说放过,于是有俩个 哪此的问题图片的回答就自相矛盾了。

    最近问下来,你这人 哪此的问题图片普遍回答不大好,于是在本文里,就干脆从hash表讲起,讲述HashMap的存数据规则,由此村里人 歌词 都都 就自然清楚上述哪此的问题图片的答案了。

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

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

村里人 歌词 都都 再来观察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对象的内存地址(假设是4000)。

    

    将会村里人 歌词 都都 后来是调用hm.get(k1),没法 村里人 歌词 都都 会再次调用hashCode土法律法子(还是返回k1的地址4000),后来根据得到的hash值,能没法快地找到k1。

    但村里人 歌词 都都 这里的代码是hm.get(k2),村里人 歌词 歌词 都都 调用Object类的hashCode土法律法子(将会Key里没定义)计算k2的hash值时,实在得到的是k2的内存地址(假设是4000)。将会k1和k2是有俩个 不同的对象,好多好多 它们的内存地址一定不不相同,也好多好多 说它们的hash值一定不同,这好多好多 村里人 歌词 都都 无法用k2的hash值去拿k1的意味着。

    村里人 歌词 歌词 都都 把第16和17行的hashCode土法律法子的注释添加后,会发现它是返回id属性的hashCode值,这里k1和k2的id全部都是1,好多好多 它们的hash值是相等的。

    村里人 歌词 都都 再来更正一下存k1和取k2的动作。存k1时,是根据它id的hash值,假设这里是400,把k1对象插进到对应的位置。而取k2时,是先计算它的hash值(将会k2的id也是1,你这人 值也是400),后来到你这人 位置去找。

    但结果会出乎村里人 歌词 都都 意料:明明400号位置将会有k1,但第26行的输出结果依然是null。其意味着好多好多 没法 重写Key对象的equals土法律法子。

    HashMap是用链地址法来出理 冲突,也好多好多 说,在400号位置上,有将会位于着多个用链表形式存储的对象。它们通过hashCode土法律法子返回的hash值全部都是400。

     村里人 歌词 歌词 都都 通过k2的hashCode到400号位置查找时,实在会得到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核心技术及面试指南这本书中相关内容改编而来。