HashMap 底层源码解读（文字加图片篇）
HashMap 底层源码解读（文字加图片篇）
若有不对的地方请多多指教！
试图猜想一下HashMap (jdk1.8)采用的数据结构是什么？数组? 还是？
匪夷所思当然不会很low!
是否了解hash算法原理，作用与用途?
HashMap 是一种高效的键值对查找集合，高效到什么层度呢？又为什么这么说？
首先我们先来做一个简单比较了解：
1.比如数组中有十万个数值，你需要查找一个元素，你最坏的情况需要迭代遍历十万次!
有些同学也说可以使用二分法等查找算法，但当然随着数据的增大时间复杂度也在增高！
2.而hash值是单一的，是用来确定这一个对象的，就好比我们的身份证，你只要从十几亿人中输入身份证就可拿到那个人的信息，效率是不是一下子高的太多太多了!hash就是如此
在此之前，我们需要知道的是，在大数据上亿的数据量下，hash是否能做到不冲突？这肯定做不到，所以我们关注的问题应该是又如何解决冲突！
那么它又是如何在HashMap集合中有序的存储的呢？
我们先了解一下HashMap几个基本数据类型
1.HashMap中默认初始化大小，且值必须是2的幂，试着想2的幂的二进制有什么规律和基数再做下对比
2.HashMap中的负载因子,负载因子=当前长度/总长度,当数值越大hash冲突也高，数组利用率也高，反之，不懂得可以百度一下，在此不展开篇幅
暂且先了解这两个基本数据类型!
接下来我们来看HashMap的put方法
1.首先将key值进行hash得到hash值（比较简单大家自己翻阅源码），调用的是本类中的一个putVal方法，后面的两个boolean类型先不管他
重头戏开始了,别着急的往下看其他代码，一步一步的来，首先创建两个Node对象和两个基本数据类型变量
点击去查看Node泛型对象发现！诶！就是HashMap中的一个内部类，可以肯定他就是一个链表数组tab[]！put进去的数据就存放在这里！
现在有了一个初步的明白，HashMap用的是数组加单向链表的一种数据结构!
再来看putVal方法的下一句代码
Table是HashMap中封装的一个Node对象,并未被初始化，直接进入到if条件中
进入到resize()方法中
Table是一个未初始化Null对象，thershold是一个未初始化int型(0)，不满足上述条件，做的是集合的初始化，newCap = 16,newThr = 12
将threshold = newThr=12;new Node[16]并被table对象引用然后返回对象,
初始化完成,返回到putVal方法中,n=16:
下一句代码，作用是计算出下标位置，（n-1）&hash是减少冲突的方法，并把位置控制在0到15之间，如果当前位置为Null,表示当前位置是空闲的,则在当前位置i插入
这是比较理想hash不冲突的情况下
而事情总不是这么顺利,当hash冲突了怎么办，接下来看下面的代码
-
第一句条件语句作用是key值相同的时候替换v值
-
第二句条件语句作用是当key值不相同且当前结点是红黑树的结构，则进行红黑树的添加算法
-
第三句条件语句也很简单，试想一下如果当前结点下有很多个hash冲突的结点呢，是否就需要遍历到next = null为止，再在空位置下下添加一个结点
但是链表是访问查找效率很低，如果你hash一直这样冲突，那就拉胯了整个效率，那要怎么办呢？于是，当链表结点大于8个的时候，就要转红黑树的数据结构了！
这时候又可以总结HashMap是数组加单向链表加红黑树的一种数据结构（jdk1.8）
（当红黑树结点低于6个的话会重新转链表结构）
红黑树是一种平衡二叉树，数据量多的时候访问查找的效率要比链表高很多！（不了解请百度翻阅资料）
下一句就很简单了，作用同样是链表中存在key相同的时候替换v值，结束循环
- 最后一句是替换v值得实现代码，返回旧值
哈哈，真不容易，到这里已经了解了hashMap冲突的解决方法了,但是就只存16个数据吗？当然不是，接下来做好准备，来了解HashMap是怎样来进行扩容的:
重点了解if条件语句的作用含义，当size大于thresshold(12)的时候，就要进行扩容，同样调用的是resize()方法
HashMap为了保持平衡，为了减少冲突，负载因子为0.75，集合大小始终要大于实际容量，HashMap扩容的方式是加一倍的扩容，比如实际存放容量超过12的话，集合大小16扩容一倍变32，实际存放容量扩容一倍变24。以此类推，接下来我们来探讨一下主要的扩容代码,
这个条件句的意思是当超过临界点最大容量的时候才执行，代码很简单
比较重要的是下一句条件句
一一来通俗的讲解一下
(newCap =32= oldCap << 1)将16扩容成32
oldCap >=默认集合大小 16>=16
直接将newThr=24=oldThr<<1 将12扩容一倍
没毛病,再接着看
重新赋值
就算是扩容完成了！！
但是还没完，数值还没有重新分配，试着回想一下，当集合中空间变多了，是不是需要将链表中或红黑树中的结点放在空余的数组位置呢？这样才能更好的提高效率,我们称之为重新散列
是不是有种似曾相识的感觉呢？哈哈。没错，你只要知道每一个条件语句的作用即可
首先for循环遍历16个数值
大条件语句作用是当前结点不为空
第一句条件语句作用是当前不存在有冲突数值，重新散列
第二句条件语句作用是当前结点是红黑树结构进行重新散列
第三句条件语句作用是当前结点存在多个链结点进行重新散列
具体代码有兴趣可以自己调试细究
总结：hashMap采用的hash冲突的解决办法是链地址法，这是解决hash冲突其中的一种算法，优点在于不会出现堆积的情况，红黑树结构是在jdk1.8中引入的