昨天模拟面试,面试官问到了 哈希map 和 treeMap 我说都是使用了 红黑树 问我有什么区别 还有复杂度 稍微一深入讨论 我就废掉了 先亡羊补牢一下
1.8之前数组+链表,1.8加入红黑树
实现了SotredMap接口,它是有序的集合。 而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。 如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序
1、每个节点要么是红色,要么是黑色; 2、根节点永远是黑色的; 3、所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点); 4、每个红色节点的两个子节点一定都是黑色; 5、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;
右旋——自己变为左孩子的右孩子;
左旋——自己变为右孩子的左孩子。
容器名称 | 存储形式 | 复杂度 | |||
---|---|---|---|---|---|
查询 | 插入 | ||||
Map | HashMap | 哈希表 | O(1) | O(1) | |
NavigableMap | TreeMap | 红黑树 | O(log n) | O(log n) | |
Collection | List | ArrayList | 静态数组 | O(1) | O(n) |
LinkedList | 双向链表 | O(n) | O(n) | ||
Set | HashSet | HashMap | O(1) | O(1) | |
TreeSet | TreeMap | O(log n) | O(log n) |