HashMap(无序, 线程不安全)
Jdk1.7 数据存储结构(采用数组 + 链表)
Jdk1.8 数据存储结构(采用数组 + 链表 + 红黑树)
注意: 在链表长度大于 8 后, 查询复杂度由 O(n)变为 O(logn), 将链表存储转换成红黑树存储(也就是 TreeMap)
红黑树 R-B Tree 简介(本质其实是 2-3-4 树):
二叉树特性:
(1)左字数上所有的节点的值都小于或等于他的根节点上的值
(2)右子树上所有节点的值均大于或等于他的根节点的值
(3)左, 右子树也分别为二叉树
红黑树特点(一种平衡二叉树):
(1)每个结点要么是红的要么是黑的.
(2)根结点是黑的.
(3)每个叶结点 (叶结点即指树尾端 NIL 指针或 NULL 结点) 都是黑的.
(4)如果一个结点是红的, 那么它的两个儿子都是黑的.
(5)对于任意结点而言, 其到叶结点树尾端 NIL 指针的每条路径都包含相同数目的黑结点
节点操作:
(1)左旋
(2)右旋
(3)变色
来源: https://www.2cto.com/kf/201904/803764.html