理解HashMap的原理

HashMap是java面试中常被问到的一个数据类型，因为这个问题可以追问的很深，而且常用的HashSet底层也是HashMap实现的，所以作为java程序员有必要了解多一点，而且有时候面试官和你聊到HashMap时，可能因为自己没有系统的了解过，有些观点逻辑自己是对的，可能也会没有太多的底气坚持自己的观点，比如put操作的逻辑有些博客写的不全，所以这边推荐一篇比较专业的文章给大家，之前在ImportNew看过一篇介绍的文章有点细节有问题，所以建议好好看和理解美团点评发布的这篇文章，介绍的比较全。

美团的博客：Java 8系列之重新认识HashMap

简单总结：

• Jdk7和Jdk8的区别：
  1.Jdk8引入了红黑树的结构（当链表元素达到八个的时候，链表结构转红黑树结构）
  2.扩容的时候也进行了优化
• 存储结构：数组+链表+红黑树（Jdk8引入）
• HashMap可以存储null，根据源码可知：key为null会放在数组的最前面，hash的结果为0。

• put的流程：

  
  流程图

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。