HashMap的基本概念

        HashMap是工作中经常会用到的数据结构，简单来说HashMap是一种基于Map接口的一种键值对结构的实现。HashMap的Key和Value都允许为null，但最多只允许一条Key为null，HashMap是无序的，非同步的，也就是说它是线程不安全的。HashMap的底层是由数组+链表+红黑树（JDK1.8新增）实现的，在HashMap存储和查找时，首先会通过Key的hashCode通过扰动函数（JDK1.8）/取模运算（JDK1.7）计算出存储位置。HashMap的基本操作效率非常不错，put和get在不考虑哈希冲突的情况下时间复杂度是O(1),如果出现了哈希冲突其时间复杂度为O(n)。是Arraylist 和linkedList的折中实现。

        HashMap通过链地址法解决哈希冲突，当发现冲突元素后，会将该元素插入到链表最后一位，形成单链表，当链表长度大于等于8时，HashMap会将链表转化为红黑树，来提高查找效率。当节点数量小于等于6时，HashMap会从红黑树转化为单链表。