一、为什么需要hashmap？
在我们写程序的时候经常会遇到数据检索等操作，对于几百个数据的小程序而言，数据的存储方式或是检索策略没有太大影响，但对于大数据，效率就会差很远。
1、线性检索：
线性检索是最为直白的方法，把所有数据都遍历一遍，然后找到你所需要的数据。其对应的数据结构就是数组，链表等线性结构，这种方式对于大数据而言效率极低，其时间复杂度为O(n)。
2、二分搜索：
二分搜索算是对线性搜索的一个改进，比如说对于[1，2，3，4，5，6，7，8]，我要搜索一个数（假设是2），我先将这个数与4（这个数一般选中位数比较好）比较，小于4则在4的左边[1，2，3]中查找，再与2比较，相等，就成功找到了，这种检索方式好处在于可以省去很多不必要的检索，每次只用查找集合中一半的元素。其时间复杂度为O(logn)。但其也有限制，数排列本身就需要是有序的。
3、Hash表中的查找：
好了，重点来了，Hash表闪亮登场，这是一种时间复杂度为O(1)的检索，就是说不管你数据有多少只需要查一次就可以找到目标数据。大家请看下图。
大家可以看到这个数组中的值就等于其下标，比如说我要存11，我就把它存在a[11]里面，这样我要找某个数字的时候就直接对应其下标就可以了。这其实是一种牺牲空间换时间的方法，这样会对内存占用比较大，但检索速度极快，只需要搜索一次就能查到目标数据。
看了上面的Hash表你肯定想问，如果我只存一个数10000，那我不是要存在a[10000]，这样其他空间不是白白浪废了吗，好吧，不存在的。Hash表已经有了其应对方法，那就是Hash函数。Hash表的本质在于可以通过value本身的特征定位到查找集合的元素下标，从而快速查找。一般的Hash函数为：要存入的数 mod（求余） Hash数组长度。比如说对于上面那个长度为9的数组，12的位置为12 mod 9=3，即存在a3，通过这种方式就可以安放比较大的数据了。
4、Hash冲突解决策略
看了上面的讲解，有出现了一个问题，通过求余数得到的地址可能是一样的。这种我们称为Hash冲突，如果数据量比较大而Hash桶比较小，这种冲突就很严重。我们采取如下方式解决冲突问题。
我们可以看到12和0的位置冲突了，然后我们把该数组的每一个元素变成了一个链表头，冲突的元素放在了链表中，这样在找到对应的链表头之后会顺着链表找下去，至于为什么采用链表，是为了节省空间，链表在内存中并不是连续存储，所以我们可以更充分地使用内存。
上面讲了那么多，那跟我们今天的主题HashMap有什么关系呢？进入正题。我们知道HashMap中的值都是key，value，这里的存储与上面的很像，key会被映射成数据所在的地址，而value就在以这个地址为头的链表中，这种数据结构在获取的时候就很快。
但是又出现了一个问题：如果hash桶较小，数据量较大，就会导致链表非常的长。所以就出现了红黑树。
二、红黑树的出现
在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。在jdk1.8版本后，java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。
JDK1.8HashMap的红黑树是这样解决的：
如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。
它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。
三、实现原理
HashMap可以看成是一个大的数组，然后每个数组元素的类型是Node类。当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。
HashMap存取put/get
取值：get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可。
HashMap put与resize的实例图
四、为什么是红黑树？为什么不直接采用红黑树还要用链表？
1、因为红黑树需要进行左旋，右旋操作， 而单链表不需要，
如果元素小于8个，查询成本高，新增成本低
如果元素大于8个，查询成本低，新增成本高
五、区别
01. jdk 1.7 用的是头插法，而jdk1.8以后使用的是尾插法？为什么这样做呢？因为 JDK 1.7 是用单链表进行纵向延伸，采用头插法时会出现逆序循环链表死循环的问题，在 jdk 1.8 之后是
因为加入了红黑树，使用尾插法，能够避免出现逆序且链表死循环的问题。
02.扩容后数据存储位置的计算方式也不一样，在 jdk1.7 的时候是直接用 hash 值和需要扩容的二进制数进行，（）
03.jdk1.8 的时候直接使用了 jdk1.7 的时候计算的规律，也就是扩容前的原始位置+扩容的大小值 = jdk1.8 的计算方式，而不再是 jdk1.7 的那种异或方式。
但这种方式就相当于只需要判断 hash 值的新增参与运算的位置是0 还是1 就直接迅速计算出扩容后的存储方式。
在计算 hash 值的时候， jdk1.7 用了9次扰动处理 = 4次位运算+5次异或，而jdk1.8 只用了2次扰动处理 = 1次位运算+1 次异或
扩容流程对比：
JDK1.7 的时候使用的是数组+单链表的数据结构。但是在 jdK1.8 之后时，使用的是数组+链表+红黑树的数据结构，当链表深度达8的时候，也就是默认伐值，就会自动扩容把链表转换成红黑树的
数据结构把时间复杂度从O（n） 变成 O（logN），提高效率。
补充：
01.为什么在 JDK1.7 的时候是先进行扩容后进行插入，而在 jdk1.8 的时候是先插入再进行扩容呢？
//其实就是当这个Map中实际插入的键值对的值的大小如果大于这个默认的阈值的时候（初始是16*0.75=12）的时候才会触发扩容，
//这个是在JDK1.8中的先插入后扩容
if (++size > threshold)
resize();其实这个问题也是 jdk8 对 hashMap 中，主要是因为对链表转化为红黑树进行的优化，因为插入这个节点的时候有可能是普通链表节点，也有可能是红黑树节点，但是为社么1.8之后HashMap 变为先插入后扩容的原因？，，
但是在 jdK1.7中的话是先扩容后进行插入的，就是当你发现你插入的桶是不是为空，如果不为空说明存在的值发生了hash 冲突，那么必须得扩容，但是如果不发生 hash 冲突的话，说明当前桶是空的，那就等到下次hash
冲突的时候扩容。
为社么 jdk 1.8 在进行对 HashMap 优化的时候，把链表转换为红黑树的阈值是8，而不是7 或者20等等？
六、哈希表如何解决 Hash 冲突？
七、为什么 HashMap 具备如下特点：键值都运行为空，线程不安全，不保证有序，存储位置随时间变化。
八、为什么 Hashmap 中 String 、Integer 这样的包装类适合作为 key 键
参考：
https://blog.csdn.net/qq_40645822/article/details/91139215
https://blog.csdn.net/qq_36520235/article/details/82417949
https://www.jianshu.com/p/8324a34577a0?utm_source=oschina-app
