Map用来存储key-value键值对，是最常用的数据结构之一。

HashMap

• HashMap存储数据时将要存入key的数据进行hash运算，大多数情况下可以快速定位应当放到哪里，因此HashMap的访问速度是很快的，但是遍历顺序是不确定的，不能保证是放入时的顺序。
  在java7时的底层实现是数组+链表，如下图所示：

  
  
• 当出现hash碰撞时，会在同一个位置使用链表链接。因此当链表长度较长时，查询的时间复杂度是比较高的。HashMap在扩容时总是扩容至原来的两倍，有一个核心参数叫负载因子0.75，这个是衡量在何时扩容的参数。扩容的阈值=容量*负载因子。

• java8中底层实现上进行了优化，如下图所示：

  
  
  

  和之前相比最大的不同在于底层实现上使用了数组+链表+红黑树；红黑树的引入当链表长度超过8时，会自动转换为红黑树，这样时间复杂度由O(N)降低为O(logN)。