HashMap底层数据结构（数组+链表+红黑树）

HashMap底层实现JDK=1.8数组+链表+红黑树；HashMap这一个类型底层涉及到3中数据类型，数组、链表、红黑树，其中查询速度最快的是数组，时间复杂度是O(1),链表数据量少的时候还行，数据量过大性能就一般了，它的时间复杂度是O(N)，红黑树在数据量打的时候性能会比链表要好，他的时间复杂度是O(logn),这里在链表和红黑树这里性能对比其实在HashMap的扩容时，已经体现出来了，Hash值产生碰撞后，链表长度>8时会由链表转换为红黑树，而当红黑树的节点17–>25–>27这条链路不会比13–>8–>1、13–>8–>11、13–>8–>1–>6、13–>17–>15、13–>17–>25–>22这些链路的路径长出两倍，因为他会自动平衡，也就是当任何一条链路的路径高出其他链路2倍是，这条链路就会自动平衡，但是如果put比较频繁，且会经常打破平衡的话，那么这条链路就会自动平衡，这时的性能就会很低，低于链表；这里平衡有两种方式，左旋、右旋 左旋： 以这个为模拟数据，现在我们来添加一个数据来打破平衡(红黑树确保没有任何一条路径会比其他路径长出两倍)，现在最短的链路是50–>60,最长的是50–>40–>45–>47,现在这条最长的刚好是最短的两倍，那么这时要是再来一个49，这里49比50小，比40大，比45大，比47大，那么会挂在50–>40–>45–>47这条链路上，刚挂上去的结构是这样的，

嘿嘿，这个平衡就打破了，那么就会自动平衡，那么这种数据模型位移叫做左旋，左旋后的红黑树结构！ 右旋则刚好相反！！！ 这是一个可视化HashMap操作的工具

红黑 树有6个性质；