HashMap是java中非常常用的数据结构，但是我却很少看到有人去优化它，或者说是如何的正确的使用它，或者说是如何以最小的代价达到自己的目的，其实关于HashMap原理的博客我也有看过，不过都是泛泛而过，都不够清楚仔细。下面我带大家源码层面逐步分析一下。（基于jdk1.8进行源码分析）
1、HashMap的继承结构：
这里没什么好说的，就一带而过了。
2、HashMap的初始化：
HashMap提供了上面四种初始化的构造函数，下面我们逐一进行分析：
上面其实是使用了默认的数组长度和默认的负载因子。他是初始化HashMap最快的一个构造函数，但是缺点是如果要储存的数据很多那将触发多次扩容函数，影响效率。
此构造方法其实就是用已有的map当做入参去计算出初始化长度和使用默认负载因子去初始化一个HashMap，然后遍历出所有数据，添加到新的HashMap中去。
这个构造函数是我比较推荐使用的初始化HashMap的方式，它提供了初始化长度的设定，如果对自己的数据有个大概的估算的话，它将为你省去多次扩容函数的开销，具体为什么会在介绍完这几个构造函数进行讲解。请回上面的这个构造方法也是调用的下面的这个构造方法。
次构造函数是HashMap初始化的时候定制化最高的，我将详细的分析一下这两个入参，和他们的用处，还有应该怎么合理的定制这两个参数:
initialCapacity:为HashMap的初始化长度，HashMap为什么需要一个初始化长度呢，还有为什么要自己设置一个初始化长度更好呢，我就先从HashMap的整体结构先来看一下。
其实HashMap的主干是一个数组，数组的每个节点是一个链表，保存的数据如下：
看到这里HashMap初始化时的这两个参数的作用就很明朗了，通过日常的使用应该是可以猜测出来的。
我们从上面的那个构造函数可以看出来，它对initialCapacity和loadFactor做了一些范围和合法性的一些校验，然后通过tableSizeFor()方法计算出了一个值，此处这个方法设计很精妙，也为下边的一些东西作出伏笔。
从这里可以看出你的入参初始化的时候会通过这个方法计算出一个最小的大于入参的2的整数次幂的一个数值，最为初始化数组的长度。这又是为啥呢？还有构造函数已经完事了，但是也没有看见HashMap主要的结构进行初始化？为什么呢，按照使用者的角度继续往下看。
现在HashMap已经初始化完毕，我们试着放几条数据：
很明显第一次使用会触发resize()这个方法，让我们一探究竟，
我们可以看出来，resize()方法才是真正的初始化了HashMap，由于此方法太长了，上面截图是初始化得部分，还有扩容部分并没有截出来，此方法给我们返回了一个
Node[] newTab = (Node[])new Node[newCap];
这才是真正的初始化了HashMap的主干，细心地人可以看到threshold已经变成了96，由计算出来的数组长度乘负载因子计算而来。
这一步就解释了为什么那个数组的长度要是2的整数次幂的值，（以前看博客有很多人写着HashMap的构造函数入参必须是2的整数次幂，其实是胡扯，真正必须是2的整数次幂的值是里面的数组的长度，而这个长度是由前面的那个算法根据你的入参计算而来）
此处代码我个人觉得设计很精妙，（也许是因为我菜），首先数组长度为n，那么最大下标为n-1，因为n是2的整数次幂，所以二进制表示类似1000000这种，而n-1恰好是11111111这种，而且(n - 1) & hash恰好是取得我们存入的key的hash码的后几位(&是按位与操作，所以(n - 1) &只是起到了截取hash码的后几位的作用)，而这后几位转成十进制正好是0~(n - 1)之间的一个数字，而hash码重复的概率又不高，所以就保证了这些数据均匀的分布在这个数组上，但是如果hash码后几位真的有重复的怎么办，其实很简单，数组上每个节点都是一个链表，我们也看到链表节点里面有hash码，key, value,等值，如果重复就在链表上做一些操作就好了。
从上面代码可以看出，当hash码所指向的数组节点不为空的时候，有三种情况:
1、当链表头结点key值与要存的节点的key相同时，用新的value替换旧的value，并返回旧的value。
2、当节点为TreeNode类型的时候通过putTreeVal()方法添加（后面进行说明）。
3、遍历链表从第二个节点开始，如果找到了相同的key，操作同1、，如果到了第八个节点还没有找到，就会做一个惊人的步骤。
如果当前哈希数组为空，或者哈希数组中元素的个数小于进行树形化的阈值（默认为64），就进行前面说到的resize()方法，（初始化，或者是扩容），否则将进行树形化（就是将当前哈希数组节点的链表转成红黑树，让第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了，这样保证了在极端条件下，还没有达到扩容条件，而一个节点数据过多的情况，此处应该为此代码作者来一段掌声，厉害厉害！）然后通过hd.treeify()方法去塑造红黑树，代码我就不贴出来了，毕竟我不是来讲红黑树的，那玩意讲起来要画图的，我比较懒。
我前面提到的putTreeVal()方法现在可以说说了，其实就是往红黑树里面添加元素，细节大家自己用心去体会，代码我也就不贴了，类似的还有红黑树的查找getNode()，修剪split()，同样大家自己去体会了。
值得一提的是当触发删除，扩容时如果节点下结构为红黑树，同时树中元素过少，会进行树的修剪或者是直接还原成链表，具体细节同样大家自己去体会了。
好了扯得有点远，回到putVal()方法，这个方法最后几行会对当前数据数量进行判断，如果达到阈值将会触发扩容，看下面两段代码，
resize()的后半段代码，前半段再讲初始化的时候已经介绍了，这后半段用于扩容
这个threshold前面我也提到过，就是细心的人可以看到的那段，其实它是由数组乘负载因子得到的，前面初始化的时候数组长度为128，所以threshold为96，当超过这个阈值将进行扩容，目的是保证HashMap的速度，不管是查找还是插入，因为如果没有下标重复的元素，一下就可以找到了，但是如果重复的太多，还要遍历里面的链表或者是操作红黑树，这样效率就打折扣了，所以通过扩容，是得决定位置的hash码的有效位数增多，从而数组下标重复的就会越少。但是这样也会浪费很多空间，数组长度越多相对于来说空闲的节点就会越多，所以这个负载因子就是用来平衡时间和空间的一个关键参数，侧重于时间相应的调小，侧重于空间相应的调大。
扩容的时候虽然数组长度增大了一倍，但是节点上的数据要怎么方法新的数组里面呢，下面我们分析下上面的代码，因为数组长度是增加一倍的所以长度的二进制就相当于多了一位，也就是相当于决定位置的hash码的有效位又多了一位，那么新的位置的索引就好确定了，因为要不就是原位置，要么就是原位置+原数组长度，为什么呢，我带大家揭秘一下，因为新增的有效位要么是0，那么相对于来说数值是不变的，要么是1，如果为1，那么新增位后面的又没有变化，所以新的就是原数组长度+原位置了。源码中用此方法判断是原位置还是原位置+元长度，((e.hash & oldCap) == 0)，感觉作者位运算玩的真溜，（此处我为作者鼓掌。。。）原长度是2的整数次幂，那二进制形式类似于100000这种，hash码&原长度不就是判断新增的有效数位是0还是1吗，此处和上面的用长度-1&hash码求索引的方法实在是妙，厉害了我的哥，然后把相应的元素放到相应的位置，扩容就结束了。
从上面可以看出虽然扩容的实现很赞，但是也是个相当耗费时间的操作，我们应该尽量避免，所以说估算出自己的数据量，定制合理的初始化参数，能让我们的HashMap更好的为我们工作。
同样可以优化的点还有clear()方法:
大家可以看出来，这个方法要遍历数组，把每个节点都至为null，但是这个方法保留了数组长度（这是唯一的优点），如果你想继续使用这个HashMap，还想要清空里面的数据，不妨试试把HashMap的对象指向一个新的HashMap，把老的数据的长度通过.size()方法取出来作为新的HashMap的初始化参数就好了，在数据比较多的时候明显优于第一种方法。
收工，盒饭走起。。。。。。。。。
网友评论