数据结构-HashMap解析
带着问题去学习一个知识点的时候往往会更加记忆深刻，所以本篇文章主要来解答以下几个问题：
1.HashMap的工作原理是什么
2.HashMap的get()方法工作原理是什么
3.当两个对象的hashcode相同会发生什么
4.如果两个键的hashcode相同，如何取键的值
5.如果HashMap的大小超过了负载因子(load Factory)定义的容量，怎么解决
6.重新调整HashMap大小存在什么问题
7.为什么String，Interger这样的wrapper类适合作为键
8.可以使用自定义的对象作为键吗
在开始讲解HashMap之前我们还需要了解其他几种数据结构：
数组：一片物理上连续的大小确定的储存空间
由于数组的大小是确定的，当数据量不确定时不好进行操作，因此就出现了顺序表，你也许会疑惑什么是顺序表，没错，就是我们经常用的ArrayList 。
ArrayList：物理上连续，逻辑上连续，大小可以动态增加
通过查看源码可知在插入，添加，删除时需要对整个空间进行移位，因此这种操作是很耗费性能的
数组移位操作
但在获取元素时由于可以通过数组下标，因此速度较快
通过数组下标获取指定元素
为了解决插入，删除这种耗费性能的操作，就出现了链表(LinkedList)这种数据结构
LinkedList：物理上不连续，逻辑上连续，可以动态地添加，删除，节点
以下是LinkedList的示意图：
LinkedList数据结构示意图
其中每一个节点都由两部分组成，一部分是保存的当前数据的数据单元，另一部分是指向下一节点的数据单元（类似于指针）因此当拿到了next节点就可以知道下一节点的数据。
回到添加，删除，这两种操作上面来，通过 这种链表这种数据结构只需要对next节点改变指向操作就可以了，无需对整个数据结构进行移位。
而对于查找的操作则需要进行轮询，类似于for循环，因此性能不高。
以下是对顺序表以及链表的优缺点对比总结：
顺序表以及链表
那这时候就有个问题，能不能把这两种数据的优点都结合起来，让查找，添加，删除都很快呢，这个时候HashMap就出现了。
讲完这两种数据结构就要进入我们的HashMap了。
HashMap：在1.7以前是由数组+链表组成的，以下是HashMap的数据结构示意图：
HashMap数据结构
下面通过HashMap的源码查看HashMap保存数据的是通过数组实现的：
通过数组保存数据
查看Node源码可以看出，Node是一个链表的数据结构：
链表的数据结构
put操作：
put操作
从源码中可以看到，在进行put操作时，会对传入的key进行hash操作，接下来查看hash方法做了什么：
hash方法
从源码可以看出，每个key都有与之一个对应的hashode值，通过这个hashcode，然后对这个hashcode值进行位运算，这个位运算后的值就是这个key的hash值。使用位运算的原因：速度更快，效率更高（CPU->芯片构成->二极管构成->只包含0/1->只能通过位运算->在内存里面通过位运算效率更高，速度更快）因此计算hash值时使用了位运算。 此时计算完key的hash值之后再通过indexFor方法找出数组对应的下标（类似于映射)，以下是indexFor方法
indexFor方法
这一步就是把计算出来的hash值映射到数组上面对应的下标位置。得到下标之后就可以把对应的数据存放到相应的数组位置上去。
由于数组中每个位置存放的是一个链表，因此当计算出来的下标位置相同时，则在数组相同下标位置的链表后面添加数据
get()操作
对于get操作来说，也是先计算出key值对应的hash值，然后计算出映射到数组里的下标，当有相同下标时则在链表中进行遍历，得到对应的key值对应的数据
get获取数据
从源码可以看出通过遍历链表，找到对应的key然后返回对应的节点数据。
LoadFactory加载因子（DEFAULT_LOAD_FACTOR=0.75f）：
查看HashMap源码可以看到里面存在一个LoadFactory的参数，这个有什么用呢？
在解决这个问题之前我们要回到刚才那个计算出来后数组下标相同的问题上来。
在计算（映射）出数组对应下标的时候，是通过刚才的indexFor方法，在该方法里是通过数组的长度（length）计算出来的。
当数组长度较小时，出现相同的index下标的概率较高，此时增加数组的长度(length)则可以有效避免冲突的产生。
那什么时候才应该增加数组的长度呢？
这个时候就需要用到了加载因子（LoadFactory），所谓加载因子，就是：
加载因子
有了加载因子之后HashMap里还有一个阈值的概念，所谓阈值就是：
阈值
当存储的数量超过了阈值之后就会进行扩容。数组扩容之后有什么影响？
由于数组扩容后长度发生了变化，因此会影响计算出来的下标值，因此需要重新计算每一个元素的hash值，以下是源码中遍历数组中每一个元素，重新计算每个元素的hash值
重新计算hash值
以上就是相对JDK1.7时，HashMap的解析，而对于JDK1.8时，则将链表替换成了红黑树，目的是提高遍历轮询时的效率，不再是采用遍历轮询。
效率对比：
链表：O(N)
红黑树：O(logN)
从时间复杂度方面可以看出红黑树的效率更高。
回到开头的问题，我们一 一来回答一下：
1.HashMap的工作原理是什么
JDK1.7：通过数组+链表的方式存储遍历数据
JDK1.8：通过数组+红黑树方式存储获取获取数据
2.HashMap的get()方法工作原理是什么
通过计算出对应的hash值，映射到对应的数组下标，再遍历下标下对应的链表得到相同key的数据
3.当两个对象的hashcode相同会发生什么
当两个对象的hashcode相同时，在映射到数组里时，会得到相同的下标，也就是所谓的hash碰撞
4.如果两个键的hashcode相同，如何取键的值
JDK1.7：通过遍历数组中对应下标下的链表得到键的值
JDK1.8：通过遍历数组中对应下标下的红黑树得到键的值
5.如果HashMap的大小超过了负载因子(load Factory)定义的容量，怎么解决
通过扩容的方式进行解决。
6.重新调整HashMap大小存在什么问题
需要遍历数组中每一个元素，重新计算hash值。
7.为什么String，Interger这样的wrapper类适合作为键
因为String，Interger这样的wrapper类里面实现了hashCode方法，通过hashCode可以得到数组的下标，因此适合作为键。同时String 定义为final，对于一个不经常改变的类hashCode 发生碰撞的几率也会相对较低
8.可以使用自定义的对象作为键吗
可以，但要实现 hashCode 以及 equals 方法。
您的一丝帮助是对他的无限动力~
后浪~
