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

  • 时间:
  • 浏览:1

     我在面试 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核心技术及面试指南这本书中相关内容改编而来。