HashMap的底层是Hash表构造，元素的排列是依据哈希算法和哈希函数排序的，且不可反复。
JDK8以前，Hash表的底层是【数组】+【链表】
JDK８及之后，变成了【数组】+【链表】+【红黑树】
存入新键值对时，如果呈现哈希抵触，会先判断键是否雷同，如果键雷同，会比拟值，值雷同则不放入，值不同则批改原值；如果键不雷同，则会以链表模式挂下来，并且1.7版本中是头插法，1.8版本是尾插法。
5.1、什么是哈希抵触？
哈希抵触就是两个元素在通过哈希函数后，失去的角标是雷同的，在同一个哈希槽中。哈希抵触的四种解决思路别离是：重哈希法，凋谢地址法，建设公共溢出，链地址法。
5.2、HashMap的扩容机制是怎么样的？它什么时候会转化为红黑树？
Hash表中数组的离别手动初始化，和主动初始化，主动初初始会在第一次插入元素时开拓空间，默认长度为16，扩容因子为0.75，每次扩容量为本身的2倍长度，扩容之后存入数组的新索引地位就会扭转。手动初始化的话，能够在创建对象时自定义初始数组长度，但HashMap不肯定会自主设置的数值初始化数组，而按2的n次方创立。
HashMap1.7版本的的扩容机会是先判断是否达到阈值，达到先扩容，再增加元素，并且采纳的是头插法，也就是旧元素挂在新元素下。
而HashMap1.8的扩容机会是先增加元素是否达到阈值，达到间接扩容，且应用的是尾插法，即新元素挂在旧元素上面。
初始化后，当存入新的键值对时，会先判断数组长度是否大于64，再判断链表元素是否大于等于8时，如果两者都成立，链表会主动转换成红黑树，如果数组小于64，会从第9个开始先扩容，直到数组大于等于64时，链表长度再减少，就会转为红黑树。
细节：
在增加第一个元素的时候是间接增加进数组的，而不会进入到红黑树转化的判断的，所以外面的binCount并没有创立。增加第二元素并产生了哈希抵触时，才进入红黑树转化的判断，同时初始化binCount=0，它判断的是binCount>=7，也就是0至7，有8个元素时，再加上没有进行判断的1个元素，即第9个元素时，才会转化为红黑树。
5.2.1、为什么要转为红黑树呢？
链表取一个数须要遍历链表，而红黑树相对效率要高。
5.2.2、为什么不间接应用红黑树呢？
HashMap源码中有相干形容： “因为树节点的大小是链表节点大小的两倍，所以只有在容器中蕴含足够的节点保障应用才用它”，显然只管转为树使得查找的速度更快，然而在节点数比拟小的时候，此时对于红黑树来说内存上的劣势会超过查找等操作的劣势，天然应用链表更加好，然而在节点数比拟多的时候，综合思考，红黑树比链表要好。
5.2.3、为什么转为红黑树的条件是8而不是第9第10个呢？
源码中有对这个进行计算，失常的随机哈希码下，哈希抵触多到超过8个的概率不到千万分之一，简直能够忽略不计了，再往后调整并没有很大意义。
如果哈希抵触有那么多，阐明极大可能是人为设置，成心制作哈希抵触导致，这时候就转为化红黑树，来保障查问效率。
5.2.3.1、那什么时候退出红黑树呢？
当哈希抵触个数从第8个变到第6个时，红黑树转化为链表。
5.2.3.1、6与8之间的第7个抵触时，会是什么状态？
分状况看。8退6，是红黑树转链表，6进8，是链表转红黑树，两头的7是避免频繁变动做的一个预留位，如果是8退6，两头的7就是红黑树；如果是6进8，两头的7就是链表。
5.2.4、为什么1.7是头插法，1.8是尾插法？
1.7版本应用头插法是因为头插法是操作速度最快的，找到数组地位就间接找到插入地位了，但这样插入方法在并发场景下会因为多个线程同时扩容呈现循环列表，也就是Hashmap的死锁问题。
1.8版本退出了红黑树来优化哈希桶中的遍历效率，相比头插法而言，尾插法在操作额定的遍历耗费（指遍历哈希桶）曾经小很多，也能够防止之前的循环列表问题，同时如果曾经变成红黑树了，也不能再用头插法了，而是按红黑树本人的规定排列了。
5.2.4.1、如果是头插法，怎么能力获取之前的旧元素呢？
因为1.7版本的头插法，是新元素在下面，旧元素挂新元素前面，所以新元素始终是在数组上的，能够通过在对象上重写toString办法，加上对象的HashCode值，这样只有打印进去雷同的HashCode阐明产生了哈希抵触，这时候只须要遍历即可，要取哪个就指定那个HashCode，雷同就取出，而上一个老元素就是第二个获取的元素。
5.2.4.2、什么是HashMap双链循环/死锁？
双链循环是JDK1.7及更早的版本之前才有的问题。在多线程扩容的状况下，一个线程执行到一半，还未扩容，而另一个线程却抢走后行扩容了，这时候可能呈现第一个线程的元素与第二个线程中的元素互相援用的状况，互相援用就会造成死锁。
比方一个数线长度为4，有两个数，一个为2，一个为10，那么这两个数都会在索引2上造成哈希桶构造，此时进行扩容，原本在新数组中是2指向10的，后果但之前那个前程正好断在10指向新数组的两头，这就会导至10又从新指向2，最终导while判断中的e永远不会等于null，造成死循环。
JDK1.8版本防止了双链循环，但不是完全避免，看过一些测试文章，红黑树之间也可能呈现死循环，只是比拟1.7版本，几率升高。
5.2.5、为什么1.7是先扩容再增加，1.8却改成先增加再扩容？
因为1.7版本中的扩容机制有两个条件：
1、 寄存新值的时候以后已有元素的个数必须大于等于阈值（数组长度*0.75）。
2、 寄存新值的时候以后存放数据产生hash碰撞（以后key计算的hash值换算进去的数组下标地位曾经存在值）
要满足以上两个条件，很可能呈现数组16个元素都填满的状况（正好无碰撞填满数组），如果是先增加再扩容，就会导致第17个元素必然产生哈希抵触，这不是咱们要的后果，咱们要的是尽量减少哈希抵触，所以须要先扩容，再放入元素。
而在1.8版本中，扩容的条件改成了理论数量大于等于阈值就扩容，所以容许了先增加再扩容这种状况，也可能是作者认为没有1.7那么强制性须要先扩容了，为了更合乎思考逻辑，改成了先增加，再扩容。
5.2.6、1.8版本是否完全避免死循环问题？
不能。1.8版本中引进了红黑树，能够升高死循环呈现的机率，但不能完全避免，红黑树之间也可能呈现死循环。
5.3、HashMap为什么数组长度始终是2的n次方？
在HashMap的底层对于数组的操作其实是（n-1）&hash，当数组的长度为2的n次时，减1转为二进制后，他被任何数字&上都不会超过这个数字，比方数组长度为8，减1后为7，那么它的数组长度就是0-7，共8个，即元素能够在这个数组上全副排满，而如果是奇数，或者不是2的n次的偶数，肯定会有一个二进制为0，也就是无论另一个数是什么，都不会被存入数组，会节约掉的地位。
5.4、HashMap的扩容为每次是原来的2倍？
首先，HashMap的初始化的数组长度肯定是2的n次的，每次扩容仍是原来的2倍的话，就不会毁坏这个法则，每次扩容后，原数据都会进行数据迁徙，依据二进制的计算，扩容后数据要么在原来地位，要么在【原来地位+扩容长度】，这样就不须要从新hash，效率上更高。
5.4、HashMap是怎么让存取效率最高的？
如果元素都是平均存储在数据的角标位而不产生抵触，就是最好的。
1、尽可能少的产生hash抵触
hash函数计算出来的角标尽可能做到平均。
2、的确产生了hash抵触——数据结构来解决
数组+链表+红黑树
3、HashMap的底层通过扰动函数（即高下位运算）来让数组更平均的被调配。
(h = key.hashCode()) ^ (h >>> 16)
扰动函数将本人的前即低16位与高16位运算，能够让数组在65535（int）范畴内更平均的调配。高下位运算：16刚好在32位的两头，前16位和本人的后16位比照，而后再把对比值和数组的比照。
5.5、多线程下的HashMap线程平安吗？为什么？
HashMap自身就是不平安的，多线程下，在增加元素时容易呈现数据笼罩状况而失落数据，也可能在扩容时，迁徙数据呈现数据笼罩状况而失落数据。