equals和hashCode源码解析

equals和hashcode网上也有很多的资料。这里只是记录下我目前的理解与认识。

大家会经常听到这样的话，当你重写equals方法时，尽量要重写hashcode方法，有些人却并不知道为什么要这样，待会就会给出源码说明这个原因。

首先来介绍下object的equals和hashcode方法。如下：

<code>public</code> <code>native</code> <code>int</code> <code>hashcode();</code>

<code>public</code> <code>boolean</code> <code>equals(object obj) {</code>

<code> </code><code>return</code> <code>(</code><code>this</code> <code>== obj);</code>

这里挺简单的，equals(obj)默认比较的是内存地址，hashcode()方法默认是native方法，看下它的文档说明：

<code> </code><code>* returns a hash code value for the object. this method is</code>

<code> </code><code>* supported for the benefit of hash tables such as those provided by</code>

<code> </code><code>* {@link java.util.hashmap}.</code>

<code> </code><code>* the general contract of {@code hashcode} is:</code>

<code> </code><code>* <li>whenever it is invoked on the same object more than once during</code>

<code> </code><code>* an execution of a java application, the {@code hashcode} method</code>

<code> </code><code>* must consistently return the same integer, provided no information</code>

<code> </code><code>* used in {@code equals} comparisons on the object is modified.</code>

<code> </code><code>* this integer need not remain consistent from one execution of an</code>

<code> </code><code>* application to another execution of the same application.</code>

<code> </code><code>* <li>if two objects are equal according to the {@code equals(object)}</code>

<code> </code><code>* method, then calling the {@code hashcode} method on each of</code>

<code> </code><code>* the two objects must produce the same integer result.</code>

<code> </code><code>* <li>it is not required that if two objects are unequal</code>

<code> </code><code>* according to the {@link java.lang.object#equals(java.lang.object)}</code>

<code> </code><code>* method, then calling the {@code hashcode} method on each of the</code>

<code> </code><code>* two objects must produce distinct integer results. however, the</code>

<code> </code><code>* programmer should be aware that producing distinct integer results</code>

<code> </code><code>* for unequal objects may improve the performance of hash tables.</code>

<code> </code><code>* as much as is reasonably practical, the hashcode method defined by</code>

<code> </code><code>* class {@code object} does return distinct integers for distinct</code>

<code> </code><code>* objects. (this is typically implemented by converting the internal</code>

<code> </code><code>* address of the object into an integer, but this implementation</code>

<code> </code><code>* technique is not required by the</code>

<code> </code><code>* javatm programming language.)</code>

<code> </code><code>* @return a hash code value for this object.</code>

<code> </code><code>* @see java.lang.object#equals(java.lang.object)</code>

<code> </code><code>* @see java.lang.system#identityhashcode</code>

<code> </code><code>public</code> <code>native</code> <code>int</code> <code>hashcode();</code>

这里有三个关注点。

关注点1：主要是说这个hashcode方法对哪些类是有用的，并不是任何情况下都要使用这个方法（此时是根本没有必要来复写此方法），而是当你涉及到像hashmap、hashset(他们的内部实现中使用到了hashcode方法)等与hash有关的一些类时，才会使用到hashcode方法。

关注点2：推荐按照这样的原则来设计，即当equals(object)相同时，hashcode（）的返回值也要尽量相同，当equals(object)不相同时，hashcode（）的返回没有特别的要求，但是也是尽量不相同以获取好的性能。

关注点3：默认的hashcode实现一般是内存地址对应的数字，所以不同的对象，hashcode（）的返回值是不一样的。

java世界里的相同：

如person类，含有name和age属性：

<code>public</code> <code>class</code> <code>person {</code>

<code> </code><code>private</code> <code>string name;</code>

<code> </code><code>private</code> <code>int</code> <code>age;</code>

<code> </code><code>public</code> <code>string getname() {</code>

<code> </code><code>return</code> <code>name;</code>

<code> </code><code>public</code> <code>void</code> <code>setname(string name) {</code>

<code> </code><code>public</code> <code>int</code> <code>getage() {</code>

<code> </code><code>return</code> <code>age;</code>

<code> </code><code>public</code> <code>void</code> <code>setage(</code><code>int</code> <code>age) {</code>

<code> </code><code>@override</code>

<code> </code><code>public</code> <code>boolean</code> <code>equals(object obj) {</code>

<code> </code><code>if</code><code>(!(obj</code><code>instanceof</code> <code>person)){</code>

<code> </code><code>return</code> <code>false</code><code>;</code>

<code> </code><code>person tmp=(person)obj;</code>

<code> </code><code>return</code> <code>name.equals(tmp.getname()) && age==tmp.getage();</code>

我们认为当name和age值都相同时就是一个相同的person，所以我们可以重写equals方法如上所述，这样我们就可以调用perosn1.equals(person2)来判断他们是否相同。然而这样就完了吗？如果你不涉及其他有关hash方面的内容，这样的确可以满足你的需求了，也就是说这样做仅仅是针对部分情况是可以的，并没有针对全部情况，如若使用hashmap、hashset等还想实现person1和person2相同，仅仅重写equals方法肯定是不够的，必须要重写hashcode方法。

为什么会有hash类型的map？

简单理解：map本身是存放key和value信息的地方，若想获取某个key1对应的value，即map.get(key1)，常规思维就是拿key1和所有的key一个一个去比较，若相同，则返回对应的value。假如有10000个key，要比较10000次吗？这样的效率难道不是很低下的吗？所以要改进，假如我们对key1进行某种运算直接能得到对应value的存储位置，来直接获取到value，这样不是最爽的吗？不再和其他key进行比较了，而是得到位置，直接获取对应的value。这就是hashmap等的基本原理，同时hashcode方法在得到位置信息上发挥着巨大的作用。

接下来hashmap的源码分析这一具体过程：

<code>static</code> <code>final</code> <code>entry<?,?>[] empty_table = {};</code>

<code> </code><code>transient</code> <code>entry<k,v>[] table = (entry<k,v>[]) empty_table;</code>

hashmap内部是由entry<k,v>类型的数组table来存储数据的。来看下entry<k,v>的代码：

<code>static</code> <code>class</code> <code>entry<k,v></code><code>implements</code> <code>map.entry<k,v> {</code>

<code> </code><code>final</code> <code>k key;</code>

<code> </code><code>v value;</code>

<code> </code><code>entry<k,v> next;</code>

<code> </code><code>* creates new entry.</code>

<code> </code><code>entry(</code><code>int</code> <code>h, k k, v v, entry<k,v> n) {</code>

<code> </code><code>value = v;</code>

entry<k,v>有四个重要的属性，是一对key和value的结合，同时包含下一个entry<k,v>，就像链表一样，最后一个就是哈希值h（这个哈希值就是key的hashcode方法的返回值经过hash运算得到的值）。

所以我们可以画出hashmap的存储结构：

图中的每一个方格就表示一个entry<k,v>对象，其中的横向则构成一个entry<k,v>[] table数组，而竖向则是由entry<k,v>的next属性形成的链表。

假入我们想找编号为2的value，如果我们能直接找到它所在数组中的索引便可以快速找到它，假如我们想找编号为73的value，如果我们能直接找到编号7然后再继续沿着链表寻找，便可以快速找到它。

首先看下它hashmap是如何来添加的，即 put(k key, v value)方法：

<code>public</code> <code>v put(k key, v value) {</code>

<code> </code><code>if</code> <code>(table == empty_table) {</code>

<code> </code><code>inflatetable(threshold);</code>

<code> </code><code>return</code> <code>putfornullkey(value);</code>

<code> </code><code>int</code> <code>i = indexfor(hash, table.length);</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[i]; e !=</code><code>null</code><code>; e = e.next) {</code>

<code> </code><code>object k;</code>

<code> </code><code>if</code> <code>(e.hash == hash && ((k = e.key) == key || key.equals(k))) {</code>

<code> </code><code>v oldvalue = e.value;</code>

<code> </code><code>e.value = value;</code>

<code> </code><code>e.recordaccess(</code><code>this</code><code>);</code>

<code> </code><code>return</code> <code>oldvalue;</code>

<code> </code><code>modcount++;</code>

<code> </code><code>addentry(hash, key, value, i);</code>

<code> </code><code>return</code> <code>null</code><code>;</code>

现在先不管hashmap扩容的事情，我们重点关注它的存的过程，首先就是计算key的hash值，这个hash计算的过程便用到了key对象的hashcode方法，如下：

<code>final</code> <code>int</code> <code>hash(object k) {</code>

<code> </code><code>int</code> <code>h = hashseed;</code>

<code> </code><code>if</code> <code>(</code><code>0</code> <code>!= h && k</code><code>instanceof</code> <code>string) {</code>

<code> </code><code>return</code> <code>sun.misc.hashing.stringhash32((string) k);</code>

<code> </code><code>h ^= k.hashcode();</code>

<code> </code><code>// this function ensures that hashcodes that differ only by</code>

<code> </code><code>// constant multiples at each bit position have a bounded</code>

<code> </code><code>// number of collisions (approximately 8 at default load factor).</code>

<code> </code><code>return</code> <code>h ^ (h >>></code><code>7</code><code>) ^ (h >>></code><code>4</code><code>);</code>

先不用看懂这个方法是怎么计算的，它的内容就是对key的hashcode方法返回值进行一系列的运算得到一个最终的值，这个值就是hash值，就是上文所说的entry<k,v>中的h属性的值。

得到这个hash值后，紧接着执行了int i = indexfor(hash, table.length)；就是找到这个hash值在table数组中的索引值，具体方法indexfor(hash, table.length)为：

<code>static</code> <code>int</code> <code>indexfor(</code><code>int</code> <code>h,</code><code>int</code> <code>length) {</code>

<code> </code><code>return</code> <code>h & (length-</code><code>1</code><code>);</code>

就是拿刚才生成的hash值和（table数组的长度减一）进行了相&操作，可以看到我们得到的hash值是一个很大很大的数字，和length-1相&之后的值，必然是在0到length-1之内，即在table数组的范围之内。得到的这个索引之后，接下来针对这个索引值对应的链表便进行放入或者替换操作。遍历这个链表，拿要放进来的key和这个链表上的每一对象的key进行下对比，看是否一致，若一致则进行替换操作，若都不一致则进行新的插入操作。

判断是否一致的条件是：e.hash == hash && ((k = e.key) == key || key.equals(k))，一定要牢牢记住这个条件。

必须满足的条件1：hash值一样，hash值的来历就是根据key的hashcode再进行一个复杂的运算，当两个key的hashcode一致的时候，计算出来的hash也是必然一样的。

必须满足的条件2：两个key的引用一样或者equals相同。

综上所述，hashmap对于key的重复性判断是基于两个内容的判断，一个就是hash值是否一样（会演变成key的hashcode是否一样），另一个就是equals方法是否一样（引用一样则肯定一样）。它依据的是两个条件，所以对于上文的person类，若想在hashmap中以person对象作为key，要满足person1对象和person2对象一样,则我们必须要重写equals方法和hashcode方法。若没有重写hashcode方法，则使用系统默认的本地hashcode方法，不同的对象的hashcode是不一样的，所以hashmap在判断时就会认为person1和person2是不一样，造成了我们事与愿违的结果。

hashmap为什么要多引入key的hash是否一致的判断条件呢？为什么不仅仅判断equals方法是否一样？

我认为原因如下

好处1：当这个table数组特别大的时候，如长度为10000，根据hash&length-1这个计算的索引值，便很快的定位某一个链表下，过滤了很大一批数据，不需要一个一个遍历。仅仅依靠equals是无法实现这样的快速过滤的。

好处2：不同的hash值得出的索引位置很可能是一样的，所以在这个链表下仍要进一步判断，此时就需要一个一个进行遍历。entry<k,v>对象中hash值是已经保存的数据，新的key的hash也已经计算出来，所以在遍历对比的过程中判断hash值是否一致是相当快的，如果不一致，则认为不相同继续下一个判断，就不会调用费时的equals方法。假如这个链表的数据也特别多，判断过程也是相当快的。也就是说，判断hash是否一致加快了在链表上的遍历的速度，减少了相对费时的equals调用次数。

综上所述，为了实现hashmap的上述高效的存储操作，引入了hash这个重要的东西。同时带给我们的附加操作就是要满足key一致除了equals返回true外，还必须让hashcode一样。所以我们重写equals方法的时候尽量的重写hashcode方法，当用到hashmap或者hashset等时必须要重写hashcode方法。

hashcode的重写的原则：当equals方法返回true，则两个对象的hashcode必须一样。

如string、integer等类都重写了equals方法和hashcode方法，都是遵循上述原则。所以我们在重写hashcode时也要遵循上述原则。

接下来看下get(object key)源代码的具体寻找过程：

<code>public</code> <code>v get(object key) {</code>

<code> </code><code>return</code> <code>getfornullkey();</code>

<code> </code><code>entry<k,v> entry = getentry(key);</code>

<code> </code><code>return</code> <code>null</code> <code>== entry ?</code><code>null</code> <code>: entry.getvalue();</code>

就是找到对应key的entry<k,v>对象，有了这个对象我们便可以获取到value。继续看下是如何来找到key对应的entry<k,v>对象的：

<code>final</code> <code>entry<k,v> getentry(object key) {</code>

<code> </code><code>return</code> <code>null</code><code>;</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[indexfor(hash, table.length)];</code>

<code> </code><code>((k = e.key) == key || (key !=</code><code>null</code> <code>&& key.equals(k))))</code>

<code> </code><code>return</code> <code>e;</code>

看到这里就会明白了这个过程，和上面put的过程类似的。

hash&length-1结果相同我们称为冲突

同时要思考什么样的情况下，get（key）过程是最快的？当然是hash&length-1的结果所在的数组索引下只有一个对象，还没有其他对象插入进来。也就是当所有的数据均匀分布在table上，而不是集中在table某个索引对应的连表上的时候此时get操作的效率是相当高的，为了达到这一个操作，就是要满足hash&length-1要尽可能的不同，减少冲突。

首先看length-1：它的原因是因为要限制在table数组内，同时还有一个重要的作用就是减少冲突。首先要知道length的长度是2的幂级数，这个是hashmap来保证的，下一篇文章再说hashmap的大小及扩容。假如length为7,3&(7-1) 即二进制的11&110等于10,2&(7-1),即二进制的10&110即10，这就是说2和3这两个值不一样，却造成了一样的索引值，即产生了冲突，当length=8时，11&111为11,10&111为10所以避免了冲突。所以当length-1的二进制为全1时，会起到避免冲突的作用。

接着看hash值，hash值是由key的hashcode经过hash运算得到的，为了让hash&length-1的结果尽量不产生冲突，hash的值也要尽量均匀，这就对hash算法提出了很高的要求，一个好的hash算法，会让不同的hashcode计算出来的hash值更加均匀分布。hash算法不在本文的范围之内，感兴趣的可以去研究。

接下来顺便看看hashset的原理：

set与list相比是无序的，不允许元素重复。元素重复的依据和hashmap对key的要求是一样的。即所存元素的hash值一样并且equals相同才是一样的元素。看下代码：

<code>private</code> <code>transient</code> <code>hashmap<e,object> map;</code>

<code> </code><code>private</code> <code>static</code> <code>final</code> <code>object present =</code><code>new</code> <code>object();</code>

看到了没有，hashset内部是有一个hashmap的，这个key就是hashset的元素，而value始终是一个固定的值present。

看下hashset的add方法：

<code>public</code> <code>boolean</code> <code>add(e e) {</code>

<code> </code><code>return</code> <code>map.put(e, present)==</code><code>null</code><code>;</code>

看到没有，hashset就是依托hashmap中的key不能重复来实现hashset中自身的元素不能重复的。

下一篇文章就要讲讲hashmap的扩容。

equals和hashCode源码解析

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希