读HashSet与HashMap源代码

假设有一个Person类型是这样定义的：

public class Person{

       private String name;

       public Person(String name){

           this.name = name

       }

}

测试类：

public class Test{

   public static void main(String[] args){

       HashSet set = new HashSet();

       set.add(new Person("zhangsan"));

       set.add(new Person("lisi"));

       set.add(new Person("zhangsan");

       System.out.println(set.size());    //结果为：3

   }

       Person p = new Person("zhangsan");

       set.add(p);

       System.out.println(set.size());    //结果为：1

相信，运行结果对大家来说并不难，但是究其原因，绝对会让很多人大吃一惊。

闲话少叙。。。

咱们一起去探个究竟

首先，看HashSet

<a target="_blank" href="http://blog.51cto.com/attachment/201312/193303483.png"></a>

HashSet竟然是用HashMap来实现的。

再看看add()方法

<a target="_blank" href="http://blog.51cto.com/attachment/201312/193719225.png"></a>

就是说，向HashSet对象中添加一个元素实际上是向HashMap中添加一个键值对元素，其中key为这个元素，值为一个Object对象。

也就是说HashSet中所维护的这个HashMap中所有元素的value值都相同。

其它方法就不一一看了，都是通过操作这个HashMap对象完成。

为了搞清楚什么时候才会向HashSet中增加元素，我们得再看HashMap的源代码。

我们重点看HashMap中put和get方法是怎样实现

<a target="_blank" href="http://blog.51cto.com/attachment/201312/194644708.png"></a>

我们看到，HashMap底层是通过一个Entry类型的数组来实现的

那么Entry又是怎样一个类呢?

<a target="_blank" href="http://blog.51cto.com/attachment/201312/194901353.png"></a>

这里，Entry是HashMap的一个内部类。它有四个属性，key,value,hash，next。

值得注意的是next是Entry&lt;K,V&gt;类型的，它指向当前元素的下一个元素，就像一个单向链表。

回来再看put方法

<a target="_blank" href="http://blog.51cto.com/attachment/201312/195736277.png"></a>

如果，key==null就调用putForNullKey(value)并返回，这不是重点，我们看看key不为null的情况。

<a target="_blank" href="http://blog.51cto.com/attachment/201312/195614920.png"></a>

调用hash()方法传入key.hashCode()方法返回值，计算出一个hash值。

<a target="_blank" href="http://blog.51cto.com/attachment/201312/200018915.png"></a>

然后调用indexFor方法返回一个整型值，并以此返回值为数组下标，获取table数组中指定下标的元素。

如果指定下标的元素不为null,则继续判断。

如果table数组中已经存在的那个Entry对象的hash属性的值和传入的key的hash值相等并且

Entry对象的key属性值与传入的key相等，则返回旧值，也就是不进行添加操作。

稍微总结一下，先判断已经存储在HashMap中的Key与添加的对象的hash code进行比较，

如果二者的hash code不同，直接添加到HashMap中，否则在进行equals方法比较，

equals方法比较返回true就不添加，返回false就添加。

有人可能会会这句

for (Entry&lt;K,V&gt; e = table[i]; e != null; e = e.next)

有些疑惑，table[i]不就是取数组中下标为i的元素吗？怎么还会有e.next呢？难不成数组中元素又是集合？

我们回头看看Entry类的定义就会恍然大悟

Entry中有个属性Entry&lt;K,V&gt; next;表示下一个元素，前面我们说它类似于链表，那究竟是不是呢？

我们看看addEntry(hash, key, value, i);方法。这个方法是真正执行添加操作的方法。

<a target="_blank" href="http://blog.51cto.com/attachment/201312/203037782.png"></a>

其实就是首先取出指定下标处的元素，然后为其赋值，赋的什么值呢？是一个新的Entry对象

回想一个，有这么几种情况会导致addEntry方法被调用执行

1. 通过key.hashCode计算出的下标处的元素为null时，addEntry

2. 通过key.hashCode计算出的数字下标处的元素不为null,遍历完这个位置的Entry对象后发现，不存在这样一个元素，addEntry

有人说，为什么hashCode()返回值相同，equals()却返回false呢？

我记得，在Object对象的hashCode()方法中有这样一段说明，

<a target="_blank" href="http://blog.51cto.com/attachment/201312/204809358.png"></a>

大意是这样的：

1.如果通过equals方法判断两个对象相等，那么它们分别调用hashCode()方法也应该返回相同的整数

2.如果通过equals方法比较两个对象不相等，不要求它们分别调用hashCode()方法必须返回不同的整数。

然而程序员应该意识到在这种情况下让它们返回不同的整数值可以提高哈希表的性能。

言归正传，继续看上面说的2种情况

第1种情况是，在指定下标处不存在元素，就直接进行添加操作。构造一个Entry对象，注意此时这个Entry对象的next属性为null

第2种情况是说，在指定下标处存在元素，但是它们和添加的对象的调用equals方法不相等，这时执行添加操作。

同样是构造一个新的Entry对象，注意，此时这个新的Entry对象的next属性指向之前已经存在的那个Entry元素。

也就是先添加的元素放在旧的元素的位置上，然后新添加的元素指向旧的元素

画个图说明一下：

<a target="_blank" href="http://blog.51cto.com/attachment/201312/211647126.png"></a>

所有，我们看到HashMap底层是用数组和链表混合来实现的。

在Entry类型的数组的每个位置上都是一个链表

至此，文章开始的那两个测试程序指向结果的原因我们也就清楚了。

先说第一个测试例子

new了三个Person对象，我们知道Person类是继承自Object的，它没有重写hashCode()方法，

说明它沿用的是Object类的hashCode()方法，而Object类的hashCode()方法返回的是

对象的内存地址的表示形式，自然不同的对象的hashCode()方法返回值是不同的。

由此计算出的HashMap中的数组下标也不相同，故而三个对象都加进行了。、

再看第二个测试例子

同一个对象，加了两次，第二次执行添加操作时由于它们是同一个对象，

且继承Object类，所有二者hashCode()相同，equals()方法比较相等，

内存地址也相同，故而只是返回已经存在的这个对象的值，而不再进行添加操作。

既然都说到这里了，我们索性再看看get方法

<a target="_blank" href="http://blog.51cto.com/attachment/201312/213228553.png"></a>

相信，看完了put方法的实现，get方法的实现，我们就一点不陌生了。

同样是通过key的hashCode方法获取指定数组下标的元素，如果该元素不为null，

遍历此位置上的链表，如果找到则返回元素的value,否则返回null。

这里顺便插一句,

如果我们重新了equals()方法，而没有重写hashCoe()方法，

就有可能造成通过equals()方法进行比较，两个对象相同，

而调用它们的hashCode()方法返回的整数值却不同。

这样，就造成理解上的不便，而且也降低了hashtable的性能。

假设，我们把这样的对象添加到HashMap中，当你想要取出来时，

就有可能不是我们期望的那个值。比如：明明HashMap中有一个

元素和这个Key相同，但是由于它们的hashCode返回值不同，导致

查找的数组元素不同，那么返回的结果就有可能不同，

这显然不是我们期望的。

当然，并不强制说重写equals方法时一定要重写hashCode，但是为了

避免不必要的麻烦，建议最好重写equals方法时也重写hashCode方法，

以维护hashCode方法的常规协定。

以上是我个人的一些见解，由于水平有限，有说得不对的地方，还请指正。

本文转自    手不要乱摸      51CTO博客，原文链接:http://blog.51cto.com/5880861/1334468