》二哥，我在看《Effective Java》的时候，章程11条说重写equals的时候一定要重写hashCode方法，为什么是这个啊？”三妹直接问道。“三姐，这道题很好，因为也是面试中经常考到的知识点，今天就带你来梳理一下。”我说。Java是一种面向对象的编程语言。所有的类都会默认继承自Object类，Object在中文里就是“对象”的意思。Object类中有两个方法：publicnativeinthashCode()；publicbooleanequals(Objectobj){return(this==obj);}1)hashCode方法这是一个本地方法，用于返回对象的散列值（整数）。在Java程序执行过程中，对同一个对象多次调用该方法，必须返回相同的哈希值。2)当且仅当x和y引用同一对象时，equals方法对任何非空引用x和y返回true。“二哥，这两种方法好像没有什么联系？”三姐质问。“从这两段的解释来看，的确如此。”我解释说：“但是这两种方法的doc文档中还有两条信息。”首先，如果两个对象调用equals方法返回的结果为true，那么调用这两个对象的hashCode方法返回的结果一定是相同的——来自hashCode方法的doc文档。其次，每当覆盖equals方法时，hashCode方法也需要被覆盖，以保持之前的约定。“哦，这么说来，这两种方法确实有关联，但是为什么呢？”三姐问了最后一个问题。“hashCode方法的作用是获取哈希值，哈希值的作用是确定对象在哈希表中的索引位置。”我说。哈希表的典型代表是HashMap，它存储键值对，可以根据键快速检索出对应的值。publicVget(Objectkey){HashMap.Nodee;return(e=getNode(hash(key),key))==null?null:e.value;}这是HashMap的get方法，通过key方法获取value。它将调用getNode方法：finalHashMap.NodegetNode(inthash,Objectkey){HashMap.Node[]tab;HashMap.Nodefirst,e;intn;Kk;if((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){if(first.hash==hash&&//alwayscheckfirstnode((k=first.key)==key||(key!=null&&key.equals(k))))returnfirst;if((e=first.next)!=null){if(firstinstanceofHashMap.TreeNode)return((HashMap.TreeNode)first).getTreeNode(hash,key);do{if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))return;}while((e=e.next)!=null);}}returnnull;}正常情况下（无hash冲突），first=tab[(n-1)&hash]为key相应的值。就时间复杂度而言，可以表示为O(1)。如果发生hash冲突，也就是在if((e=first.next)!=null){}子句中，可以看到如果节点不是红黑树，do-while循环语句会用于判断key是否equals返回对应的值。就时间复杂度而言，可以表示为O(n)。HashMap使用zipper方式解决hash冲突，即如果发生hash冲突，会在同一个key的坑里放多个值，超过8个值后，就变成红黑树来提高查询效率。很明显，O(n)在时间复杂度上比O(1)差，这就是哈希表的价值所在。“什么是O(n)和O(1)？”三妹有些疑惑。》这是时间复杂度的一种表示，接下来二哥具体给大家讲一下，简单说一下n和1的含义，显然n和1都代表代码执行的次数，如果数据大小为n，n表示需要执行n次，1表示只需要执行一次。我解释道：“三姐，你想一想，如果没有哈希表，但是你需要这样一个数据结构，里面存储的数据不允许重复，你怎么办？”我问。想用equals的方法一个一个比较？”三妹有点不确定。体积非常大，性能会很差。最好的解决方案还是HashMap。”HashMap本质上是通过数组来实现的。当我们要从HashMap中取值的时候，其实是想获取数组中某个位置的元素，这个位置是由key决定的。publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}这是HashMap的put方法，会将键值对放入数组中。它将调用putVal方法：=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{//zipper}returnnull;}通常p=tab[i=(n-1)&hash])是对应的值钥匙。数组的索引(n-1)&hash是根据hashCode方法计算出来的。staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}“二哥你好像还没说为什么重写equals方法，要重写hashCode方法吗？”三妹没办法。“看看下面的代码，”我说。publicclassTest{publicstaticvoidmain(String[]args){Students1=newStudent(18,"张三");Mapscores=newHashMap<>();scores.put(s1,98);Students2=newStudent(18"张三");System.out.println(scores.get(s2));}}classStudent{privateintage;privateStringname;publicStudent(intage,Stringname){this.age=age;this.name=name;}@Overridepublicbooleanequals(Objecto){Studentstudent=(Student)o;returnage==student.age&&Objects.equals(name,student.name);}}我们重写Student类的equals方法，如果两个学生的年龄和姓名是一样的，我们就当是同一个学生，这很可笑，但我们就是这么草率。主法中，18岁的张三考了98分，这是一个非常不错的成绩。我们把张三和他的分数放到HashMap中，然后准备取出：null"二哥，为什么你输出的不是预期的null，而是其中的98呢？"三姐难以置信。“原因是重写equals方法的时候没有重写hashCode方法。”我回答说，“虽然equals方法假定相同的名字和年龄是同一个学生，但它们本质上是两个具有不同hashCode的对象。”“那hashCode方法怎么重写呢？”三妹问道。“可以直接调用Objects类的hash方法。”我回答。@OverridepublicinthashCode(){returnObjects.hash(age,name);}Objects类的hash方法可以为不同数量的参数生成新的哈希值。hash方法调用Arrays类的hashCode方法。该方法源码如下：publicstaticinthashCode(Objecta[]){if(a==null)return0;intresult=1;for(Objectelement:a)result=31*result+(element==null?0:element.hashCode();returnresult;}first第二个循环：result=31*1+Integer(18).hashCode();第二个循环：result=(31*1+Integer(18).hashCode())*31+String("张三")。哈希码();对于不同名称和年龄的对象，计算出的哈希值很难重复；对于具有相同名称和年龄的对象，哈希值保持一致。再次执行main方法，结果如下：98因为此时s1和s2对象的哈希值都是776408。“每当重写equals方法时，hashCode方法也需要重写。原因是为了保证如果两个对象调用equals方法并返回true，那么这两个对象调用hashCode方法并返回相同的结果。”我就是这样。“好，我知道了。”三姐开心的点点头，看得出来今天收获颇丰。本文转载自微信公众号“沉默王二”，可通过以下二维码关注。转载本文请联系沉默王二公众号。
