HashMap 的底层数据结构是什么？
在JDK1.7 中，由“数组+链表”组成：数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中，由“数组+链表+红黑树”组成：当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
● 当链表长度 > 8 && 数组长度 >= 64 才会转红黑树; 其实这种情况，发生的概率很低。
● 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。因为，数组扩容在一定程度上也可以减少哈希冲突如的发生。