HashMap数据结构面试

• JDK7 数组+链表
• JDK8 数组+链表+红黑树 链表长度大于等于8 红黑树 小于等于6 链表
• new HashMap() 时初始容量是0
• put()的时候 开辟空间

HashMap在jdk1.8之后引入了红黑树的概念，表示若桶中链表元素超过8时，会自动转化成红黑树；

若桶中元素小于等于6时，树结构还原成链表形式。

原因：

• 链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的
• 红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，
• 链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，
• 其实在大于5时，红黑树已经优于链表的 平均查找长度
• 树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。
• 也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

选择6和8的原因是：

• 中间有个差值7可以防止链表和树之间频繁的转换。
• 假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。