TreeMap
TreeSet使用适配器模式包装了TreeMap,所以只需要理解TreeMap就够了
概述
TreeMap实现了SortedMap接口,也就是说会按照顺序对Map中的元素进行排序,可以是自然顺序,也可以使用自定义比较器
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Apple");
treeMap.put(1, "Banana");
treeMap.put(4, "Cherry");
treeMap.put(2, "Date");
//打印顺序
1 => Banana
2 => Date
3 => Apple
4 => Cherry
TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> o2.compareTo(o1));
treeMap.put(3, "Apple");
treeMap.put(1, "Banana");
treeMap.put(4, "Cherry");
treeMap.put(2, "Date");
//打印顺序
4 => Cherry
3 => Apple
2 => Date
1 => Banana
底层原理
TreeMap底层通过红黑树(Red-Black tree)实现,也就意味着containsKey()
, get()
, put()
, remove()
都有着log(n)
的时间复杂度。
红黑树是一种近似平衡的二叉查找树,左子树的所有节点比根节点小,右子树的所有节点比根节点大
红黑树只能做到近似平衡,确保左右子树的高度差不会超过二者中较低那个的一倍,结构改变时需要调整树
调整过程中包括两个基本操作:
左旋和右旋
由于红黑树是一棵增强版的二叉查找树,红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似,唯一的区别是红黑树在节点删除之后可能需要进行调整。
快速失败
TreeMap是一个快速失败的集合,使用modCount记录结构性修改tag
标签:Cherry,treeMap,TreeMap,Date,红黑树,put,解析,TreeSet From: https://www.cnblogs.com/lilizzyy/p/18377454