集合中的Hash码，要尽量避免重复!

在一个列表中查找某值是非常耗费资源的，随机存取的列表是遍历查找，顺序存储的列表是链表查找，或者是Collections的二分法查找，但这都不够快，毕竟都是遍历嘛，最快的还要数以Hash开头的集合(如HashMap、HashSet等类)查找，我们以HashMap为例，看看是如何查找key值的，代码如下：

两个不同的集合容器，一个是ArrayList，一个是HashMap，都是插入10000个元素，然后判断是否包含最后一个加入的元素。逻辑相同，但是执行时间差别却非常大，结果如下：

HahsMap比ArrayList快了两个数量级！两者的contains方法都是判断是否包含指定值，为何差距如此巨大呢？而且如果数据量增大，差距也会非线性增长。

我们先来看看ArrayList，它的contains方法是一个遍历对比，这很easy，不多说。我们看看HashMap的ContainsKey方法是如何实现的，代码如下：

getEntry方法会根据key值查找它的键值对（也就是Entry对象）,如果没有找到，则返回null。我们再看看该方法又是如何实现的，代码如下：

注意看上面代码中红色字体部分，通过indexFor方法定位Entry在数组table中的位置，这是HashMap实现的一个关键点，怎么能根据hashCode定位它在数组中的位置呢？

要解释此问题，还需要从HashMap的table数组是如何存储元素的说起，首先要说明三点：

• table数组的长度永远是2的N次幂。

• table数组的元素是Entry类型

• table数组中的元素位置是不连续的

table数组为何如此设计呢？下面逐步来说明，先来看HashMap是如何插入元素的，代码如下：

注意看，HashMap每次增加元素时都会先计算其哈希码值，然后使用hash方法再次对hashCode进行抽取和统计，同时兼顾哈希码的高位和低位信息产生一个唯一值，也就是说hashCode不同，hash方法返回的值也不同，之后再通过indexFor方法与数组长度做一次与运算，即可计算出其在数组中的位置，简单的说，hash方法和indexFor方法就是把哈希码转变成数组的下标，源代码如下：

顺便说一下，null值也是可以作为key值的，它的位置永远是在Entry数组中的第一位。

现在有一个很重要的问题摆在前面了：哈希运算存在着哈希冲突问题，即对于一个固定的哈希算法f(k)，允许出现f(k1)=f(k2)，但k1≠k2的情况，也就是说两个不同的Entry，可能产生相同的哈希码，HashMap是如何处理这种冲突问题的呢？答案是通过链表，每个键值对都是一个Entry，其中每个Entry都有一个next变量，也就是说它会指向一个键值对---很明显，这应该是一个单向链表，该链表是由addEntity方法完成的，其代码如下：　

这段程序涵盖了两个业务逻辑，如果新加入的元素的键值对的hashCode是唯一的，那直接插入到数组中，它Entry的next值则为null；如果新加入的键值对的hashCode与其它元素冲突，则替换掉数组中的当前值，并把新加入的Entry的next变量指向被替换的元素，于是一个链表就产生了，如下图所示：

HashMap的存储主线还是数组，遇到哈希码冲突的时候则使用链表解决。了解了HashMap是如何存储的，查找也就一目了然了：使用hashCode定位元素，若有哈希冲突，则遍历对比，换句话说，如果没有哈希冲突的情况下，HashMap的查找则是依赖hashCode定位的，因为是直接定位，那效率当然就高了。

知道HashMap的查找原理，我们就应该很清楚：如果哈希码相同，它的查找效率就与ArrayList没什么两样了，遍历对比，性能会大打折扣。特别是哪些进度紧张的项目中，虽重写了hashCode方法但返回值却是固定的，此时如果把哪些对象插入到HashMap中，查找就相当耗时了。

　注意：HashMap中的hashCode应避免冲突。