旅游兼职网站建设,有网站前台,网站开发工程师swot分析,网页设计师面试TreeMap 是一个基于 key 有序的 key value 散列表。
map 根据其键的自然顺序排序#xff0c;或者根据 map 创建时提供的 Comparator 排序不是线程安全的key 不可以存入null底层是基于红黑树实现的
TreeMap 的类结构图#xff1a;
实现了 NavigableMap 接口#xff0c;Na…TreeMap 是一个基于 key 有序的 key value 散列表。
map 根据其键的自然顺序排序或者根据 map 创建时提供的 Comparator 排序不是线程安全的key 不可以存入null底层是基于红黑树实现的
TreeMap 的类结构图
实现了 NavigableMap 接口NavigableMap 又实现了Map接口提供了导航相关的方法。继承了 AbstractMap该方法实现 Map 操作的骨干逻辑。实现了 Cloneable 接口标记该类支持 clone 方法复制实现了 Serializable 接口标记该类支持序列化
构造方法
TreeMap() // 使用键的自然排序构造一个新的空树映射。
TreeMap(Comparator? super K comparator) // 构造一个新的空树映射根据给定的比较器排序。
TreeMap(Map? extends K,? extends V m) // 构造一个新的树映射包含与给定映射相同的映射按照键的自然顺序排序。
TreeMap(SortedMapK,? extends V m) // 构造一个新的树映射包含相同的映射并使用与指定排序映射相同的顺序。关键方法
SortedMap 接口
Comparator? super K comparator() // 返回用于排序此映射中的键的比较器如果此映射使用其键的自然排序则返回 null。
SetMap.EntryK,V entrySet() // 返回此映射中包含的映射的 Set 视图。
K firstKey() // 返回当前映射中的第一个(最低)键。
K lastKey() // 返回当前映射中的最后(最高)键。NavigableMap 接口
Map.EntryK,V ceilingEntry(K key) 返回与大于或等于给定键的最小键相关联的键值映射如果没有这样的键则返回 null。
K ceilingKey(K key) 返回大于或等于给定键的最小键如果没有这样的键则返回 null。
NavigableMapK,V descendingMap() 返回此映射中包含的映射的倒序视图。
Map.EntryK,V firstEntry() 返回与该映射中最小的键关联的键值映射如果映射为空则返回 null。
Map.EntryK,V floorEntry(K key) 返回与小于或等于给定键的最大键相关联的键值映射如果没有这样的键则返回 null。
SortedMapK,V headMap(K toKey) 返回该映射中键严格小于 toKey 的部分的视图。
Map.EntryK,V higherEntry(K key) 返回与严格大于给定键的最小键关联的键值映射如果没有这样的键则返回 null。
Map.EntryK,V lastEntry() 返回与此映射中最大键关联的键值映射如果映射为空则返回 null。
Map.EntryK,V lowerEntry(K key) 返回与严格小于给定键的最大键关联的键值映射如果没有这样的键则返回 null。
Map.EntryK,V pollFirstEntry() 删除并返回与该映射中最小的键关联的键值映射如果映射为空则返回 null。
Map.EntryK,V pollLastEntry() 删除并返回与此映射中最大键关联的键值映射如果映射为空则返回 null。
SortedMapK,V subMap(K fromKey, K toKey) 返回该映射中键范围从 fromKey(包含)到 toKey(独占)的部分的视图。
SortedMapK,V tailMap(K fromKey) 返回该映射中键大于或等于 fromKey 的部分的视图。验证顺序性
Testpublic void test1() {MapInteger, String treeMap new TreeMap();treeMap.put(16, a);treeMap.put(1, b);treeMap.put(4, c);treeMap.put(3, d);treeMap.put(8, e);// 遍历System.out.println(默认排序);treeMap.forEach((key, value) - {System.out.println(key: key , value: value);});// 构造方法传入比较器MapInteger, String tree2Map new TreeMap((o1, o2) - o2 - o1);tree2Map.put(16, a);tree2Map.put(1, b);tree2Map.put(4, c);tree2Map.put(3, d);tree2Map.put(8, e);// 遍历System.out.println(倒序排序);tree2Map.forEach((key, value) - {System.out.println(key: key , value: value);});}验证不能存储 null
Testpublic void test2() {MapInteger, String treeMap new TreeMap();treeMap.put(null, a);}验证 NavigableMap 相关方法
Testpublic void test3() {NavigableMapInteger, String treeMap new TreeMap();treeMap.put(16, a);treeMap.put(1, b);treeMap.put(4, c);treeMap.put(3, d);treeMap.put(8, e);// 获取大于等于 5 的 keyInteger ceilingKey treeMap.ceilingKey(5);System.out.println(ceilingKey 5 is ceilingKey);// 获取最大的 keyInteger lastKey treeMap.lastKey();System.out.println(lastKey is lastKey);}核心机制
实现原理 TreeMap 的底层是如何维护 key 的顺序呢答案就是基于红黑树实现的。
红黑树是一颗 自平衡 的 排序二叉树。 二叉树 很容易理解就是一棵树分俩叉。 上面这颗就是一颗最普通的二叉树。但是你会发现看起来不那么美观因为你以 H 为根节点发现左右两边高低不平衡高度相差达到了 2。于是出现了平衡二叉树使得左右两边高低差不多。
平衡二叉树 不管是从任何一个字母为根节点左右两边的深度差不了 2最多是 1。这就是平衡二叉树。把字母变成数字还要保持这种特性怎么办呢于是又出现了平衡二叉排序树。
平衡二叉排序树
不管是从长相平衡还是从规律排序感觉这棵树超级完美。但是有一个问题那就是在增加删除节点的时候你要时刻去让这棵树保持平衡需要做太多的工作了旋转的次数超级多于是乎出现了红黑树。
红黑树 这就是传说中的红黑树和平衡二叉排序树的区别就是每个节点涂上了颜色他有下列五条性质
每个节点都只能是红色或者黑色 根节点是黑色 每个叶节点NIL节点空节点是黑色的。 如果一个结点是红的则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这些性质有什么优点呢就是插入效率超级高。因为在插入一个元素的时候最多只需三次旋转O(1)的复杂度但是有一点需要说明他的查询效率略微逊色于平衡二叉树因为他比平衡二叉树会稍微不平衡最多一层也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较。如何去旋转呢如下图所示。
首先是左旋 然后是右旋
红黑树更详细的内容可以参考这篇文章segmentfault.com/a/119000001…
源码解析 成员变量
//这是一个比较器方便插入查找元素等操作
private final Comparator? super K comparator;
//红黑树的根节点每个节点是一个Entry
private transient EntryK,V root;
//集合元素数量
private transient int size 0;
//集合修改的记录
private transient int modCount 0;
comparator是一个排序器作为key的排序规则
root是红黑树的根节点说明的确底层用的红黑树作为数据结构。
static final class EntryK,V implements Map.EntryK,V {K key;V value;//左子树EntryK,V left;//右子树EntryK,V right;//父节点EntryK,V parent;//每个节点的颜色红黑树属性。boolean color BLACK;Entry(K key, V value, EntryK,V parent) {this.key key;this.value value;this.parent parent;}public K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {V oldValue this.value;this.value value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry?,? e (Map.Entry?,?)o;return valEquals(key,e.getKey()) valEquals(value,e.getValue());}public int hashCode() {int keyHash (keynull ? 0 : key.hashCode());int valueHash (valuenull ? 0 : value.hashCode());return keyHash ^ valueHash;}public String toString() {return key value;}}查找get方法 TreeMap基于红黑树实现而红黑树是一种自平衡二叉查找树所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的先将目标值和根节点的值进行比较如果目标值小于根节点的值则再和根节点的左孩子进行比较。如果目标值大于根节点的值则继续和根节点的右孩子比较。在查找过程中如果目标值和二叉树中的某个节点值相等则返回 true否则返回 false。TreeMap 查找和此类似只不过在 TreeMap 中节点Entry存储的是键值对k,v。在查找过程中比较的是键的大小返回的是值如果没找到则返回null。TreeMap 中的查找方法是get。
public V get(Object key) {//调用 getEntry方法查找EntryK,V p getEntry(key);return (pnull ? null : p. value);
}final EntryK,V getEntry(Object key) {/ 如果比较器为空只是用key作为比较器查询if (comparator ! null) return getEntryUsingComparator(key);if (key null)throw new NullPointerException();Comparable? super K k (Comparable? super K) key;// 取得root节点EntryK,V p root;//核心来了从root节点开始查找根据比较器判断是在左子树还是右子树while (p ! null) {int cmp k.compareTo(p.key );if (cmp 0)p p. left;else if (cmp 0)p p. right;elsereturn p;}插入put方法 我们来看下关键的插入方法在插入时候是如何维护key的。
public V put(K key, V value) {EntryK,V t root;// 1.如果根节点为 null将新节点设为根节点if (t null) {compare(key, key); // type (and possibly null) checkroot new Entry(key, value, null);size 1;modCount;return null;}//如果root不为null说明已存在元素 int cmp;EntryK,V parent;// split comparator and comparable pathsComparator? super K cpr comparator;//如果比较器不为null 则使用比较器if (cpr ! null) {//找到元素的插入位置do {parent t;cmp cpr.compare(key, t.key);//当前key小于节点key 向左子树查找if (cmp 0)t t.left;//当前key大于节点key 向右子树查找else if (cmp 0)t t.right;else//相等的情况下 直接更新节点值return t.setValue(value);} while (t ! null);}//如果比较器为null 则使用默认比较器else {//如果key为null 则抛出异常if (key null)throw new NullPointerException();SuppressWarnings(unchecked)Comparable? super K k (Comparable? super K) key;//找到元素的插入位置do {parent t;cmp k.compareTo(t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);} while (t ! null);}EntryK,V e new Entry(key, value, parent);//根据比较结果决定插入到左子树还是右子树if (cmp 0)parent.left e;elseparent.right e;//保持红黑树性质进行红黑树的旋转等操作fixAfterInsertion(e);size;modCount;return null;}比较关键的就是fixAfterInsertion方法 看懂这个方法需要你对红黑树的机制比较了解。
private void fixAfterInsertion(EntryK,V x) {// 将新插入节点的颜色设置为红色x. color RED;// while循环保证新插入节点x不是根节点或者新插入节点x的父节点不是红色这两种情况不需要调整while (x ! null x ! root x. parent.color RED) {// 如果新插入节点x的父节点是祖父节点的左孩子if (parentOf(x) leftOf(parentOf (parentOf(x)))) {// 取得新插入节点x的叔叔节点EntryK,V y rightOf(parentOf (parentOf(x)));// 如果新插入x的父节点是红色if (colorOf(y) RED) {// 将x的父节点设置为黑色setColor(parentOf (x), BLACK);// 将x的叔叔节点设置为黑色setColor(y, BLACK);// 将x的祖父节点设置为红色setColor(parentOf (parentOf(x)), RED);// 将x指向祖父节点如果x的祖父节点的父节点是红色按照上面的步奏继续循环x parentOf(parentOf (x));} else {// 如果新插入x的叔叔节点是黑色或缺少且x的父节点是祖父节点的右孩子if (x rightOf( parentOf(x))) {// 左旋父节点x parentOf(x);rotateLeft(x);}// 如果新插入x的叔叔节点是黑色或缺少且x的父节点是祖父节点的左孩子// 将x的父节点设置为黑色setColor(parentOf (x), BLACK);// 将x的祖父节点设置为红色setColor(parentOf (parentOf(x)), RED);// 右旋x的祖父节点rotateRight( parentOf(parentOf (x)));}} else { // 如果新插入节点x的父节点是祖父节点的右孩子和上面的相似EntryK,V y leftOf(parentOf (parentOf(x)));if (colorOf(y) RED) {setColor(parentOf (x), BLACK);setColor(y, BLACK);setColor(parentOf (parentOf(x)), RED);x parentOf(parentOf (x));} else {if (x leftOf( parentOf(x))) {x parentOf(x);rotateRight(x);}setColor(parentOf (x), BLACK);setColor(parentOf (parentOf(x)), RED);rotateLeft( parentOf(parentOf (x)));}}}// 最后将根节点设置为黑色root.color BLACK;
}删除remove方法 删除remove是最复杂的方法。
public V remove(Object key) {// 根据key查找到对应的节点对象EntryK,V p getEntry(key);if (p null)return null;// 记录key对应的value供返回使用V oldValue p. value;// 删除节点deleteEntry(p);return oldValue;
}
private void deleteEntry(EntryK,V p) {modCount;//元素个数减一size--;// 如果被删除的节点p的左孩子和右孩子都不为空则查找其替代节if (p.left ! null p. right ! null) {// 查找p的替代节点EntryK,V s successor (p);p. key s.key ;p. value s.value ;p s;}EntryK,V replacement (p. left ! null ? p.left : p. right);if (replacement ! null) { // 将p的父节点拷贝给替代节点replacement. parent p.parent ;// 如果替代节点p的父节点为空也就是p为跟节点则将replacement设置为根节点if (p.parent null)root replacement;// 如果替代节点p是其父节点的左孩子则将replacement设置为其父节点的左孩子else if (p p.parent. left)p. parent.left replacement;// 如果替代节点p是其父节点的左孩子则将replacement设置为其父节点的右孩子elsep. parent.right replacement;// 将替代节点p的left、right、parent的指针都指向空p. left p.right p.parent null;// 如果替代节点p的颜色是黑色则需要调整红黑树以保持其平衡if (p.color BLACK)fixAfterDeletion(replacement);} else if (p.parent null) { // return if we are the only node.// 如果要替代节点p没有父节点代表p为根节点直接删除即可root null;} else {// 如果p的颜色是黑色则调整红黑树if (p.color BLACK)fixAfterDeletion(p);// 下面删除替代节点pif (p.parent ! null) {// 解除p的父节点对p的引用if (p p.parent .left)p. parent.left null;else if (p p.parent. right)p. parent.right null;// 解除p对p父节点的引用p. parent null;}}}最终还是落到了对红黑树节点的删除上需要维持红黑树的特性做一系列的工作。
