共计 3297 个字符，预计需要花费 9 分钟才能阅读完成。
HashMap 的底层是 Hash 表构造，元素的排列是依据哈希算法和哈希函数排序的，且不可反复。
JDK8 以前，Hash 表的底层是【数组】+【链表】
JDK8及之后，变成了【数组】+【链表】+【红黑树】
存入新键值对时，如果呈现哈希抵触，会先判断键是否雷同，如果键雷同，会比拟值，值雷同则不放入，值不同则批改原值；如果键不雷同，则会以链表模式挂下来，并且 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 自身就是不平安的，多线程下，在增加元素时容易呈现数据笼罩状况而失落数据，也可能在扩容时，迁徙数据呈现数据笼罩状况而失落数据。
