HashMap的底层原理是什么

????????面试必问究极重点之HashMap的底层原理

????????HashMap首先说一下它的底层数据结构，首先呢，在JDK1.7的时候，HashMap是数组+链表的形式。而在JDK1.8的时候，HashMap是数组+链表+红黑树的形式。这里呢，虽然它在JDK1.8的时候加入了红黑树，但其实，红黑树只是起到了一个保底的作用。这里要讲一个HashMap中的树化：红黑树用来避免 DoS 攻击，防止链表超长时性能下降。而树化呢也会有一个阈值，如果链表长度超过了这个阈值（>8），并且数组长度（>=64）那么链表就会树化，转换为红黑树的结构。当然，有树化也有退化，在HashMap正常的扩容过程中，如果已经有红黑树的结构且小于等于<=6时，结构就会从红黑树转换为原来的链表。退化呢，还有另一种情况，就是当remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表（在移除之前检查）默认的树化阈值为>8，默认的退化阈值为<=6。

????????然后就是正常的一个添加数据的过程：当put数据时，首先会计算它的一个Hash码，然后进行二次Hash，接着对当前Hash表数组长度取模得到，这个数据在Hash表中的位置也就是索引下标。当数据越来越多的情况下，可能会遇到多个数据需要存放在同一个位置上，这个我们叫做Hash冲突，解决这种冲突的办法就是，采用了链表的形式挂在这个位置上。JDK1.7的时候采用的是头插法，也就是后一个元素插入到前一个元素的上方，而JDK1.8的时候，采用的是尾插法，后一个元素接在前一个元素的下方。

????????当插入的元素越来越多，出现Hash冲突的情况也会变多，也就会导致链表越来越长，这样对于查找数据来讲，性能是降低的。所以要想办法，缩短链表长度。有两种形式，一种呢就是咱们前面讲到的树化，转化为红黑树，另一种形式就是扩容。所以HashMap中也有自动扩容机制。它采用的是，定义了一个负载因子，在源码中它是定义了一个float类型的static final float DEFAULT_LOAD_FACTOR = 0.75f;

????????而扩容的条件就是，当HashMap中的元素个数超过当前数组长度与负载因子的乘积，也就是当前数组长度的四分之三时，就会进行扩容。数组的容量是符合2的n次幂，每次扩容为原来的两倍。扩容过程为创建一个新的数组，新的数组为原来数组容量的两倍，然后将原来的元素从新计算加入到新的HashMap中。

????????在扩容方面JDK1.7时是大于等于阈值并且数组中没有空位时才进行扩容，而JDK1.8是大于阈值就扩容。

????????在多线程情况下，HashMap会出现问题。在JDK1.7时，会出现一个扩容死链的问题。出现这个问题的主要原因是，在多线程情况下，扩容时，需要把元素重新放入新数组中，那么在同一位置上的元素会顺序放入新数组中，1.7采用的是头插法从而导致了扩容死链问题。另一个是JDK7/8都会出现的问题，数据错乱。多个线程同时操作HashMap会出现，数据丢失的情况，是因为在添加元素时，可能在同一位置需要添加多个元素，但是会出现覆盖情况。