TreeMap是Map家族中的一员,也是用来存放key-value键值对的。平时在工作中使用的可能并不多,它最大的特点是遍历时是有顺序的,根据key的排序规则来,那么它具体是如何使用,又是怎么实现的呢?本文基于jdk8做一个讲解。
TreeMap是一个基于key有序的key value散列表。
以上是TreeMap的类结构图:
TreeMap()
说明:使用键的自然排序构造一个新的空树映射。
TreeMap(Comparator<? super K> comparator)
说明:构造一个新的空树映射,根据给定的比较器排序。
TreeMap(Map<? extends K,? extends V> m)
说明:构造一个新的树映射,包含与给定映射相同的映射,按照键的自然顺序排序。
TreeMap(SortedMap<K,? extends V> m)
说明:构造一个新的树映射,包含相同的映射,并使用与指定排序映射相同的顺序。
这边主要讲解下NavigableMap和SortedMap提供的一些方法,Map相关的方法大家应该都很熟悉了。
SortedMap接口:
Comparator<? super K> comparator()
返回用于排序此映射中的键的比较器,如果此映射使用其键的自然排序,则返回null。
Set<Map.Entry<K,V>> entrySet()
返回此映射中包含的映射的Set视图。
K firstKey()
返回当前映射中的第一个(最低)键。
K lastKey()
返回当前映射中的最后(最高)键。
NavigableMap接口:
Map.Entry<K,V> ceilingEntry(K key)
返回与大于或等于给定键的最小键相关联的键值映射,如果没有这样的键则返回null。
K ceilingKey(K key)
返回大于或等于给定键的最小键,如果没有这样的键,则返回null。
NavigableMap<K,V> descendingMap()
返回此映射中包含的映射的倒序视图。
Map.Entry<K,V> firstEntry()
返回与该映射中最小的键关联的键值映射,如果映射为空,则返回null。
Map.Entry<K,V> floorEntry(K key)
返回与小于或等于给定键的最大键相关联的键值映射,如果没有这样的键则返回null。
SortedMap<K,V> headMap(K toKey)
返回该映射中键严格小于toKey的部分的视图。
Map.Entry<K,V> higherEntry(K key)
返回与严格大于给定键的最小键关联的键值映射,如果没有这样的键,则返回null。
Map.Entry<K,V> lastEntry()
返回与此映射中最大键关联的键值映射,如果映射为空,则返回null。
Map.Entry<K,V> lowerEntry(K key)
返回与严格小于给定键的最大键关联的键值映射,如果没有这样的键,则返回null。
Map.Entry<K,V> pollFirstEntry()
删除并返回与该映射中最小的键关联的键值映射,如果映射为空,则返回null。
Map.Entry<K,V> pollLastEntry()
删除并返回与此映射中最大键关联的键值映射,如果映射为空,则返回null。
SortedMap<K,V> subMap(K fromKey, K toKey)
返回该映射中键范围从fromKey(包含)到toKey(独占)的部分的视图。
SortedMap<K,V> tailMap(K fromKey)
返回该映射中键大于或等于fromKey的部分的视图。
验证顺序性
@Test public void test1() { Map<Integer, 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); }); // 构造方法传入比较器 Map<Integer, 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
@Test public void test2() { Map<Integer, String> treeMap = new TreeMap<>(); treeMap.put(null, "a"); }
运行结果:
验证NavigableMap相关方法
@Test public void test3() { NavigableMap<Integer, 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的key Integer ceilingKey = treeMap.ceilingKey(5); System.out.println("ceilingKey 5 is " + ceilingKey); // 获取最大的key Integer lastKey = treeMap.lastKey(); System.out.println("lastKey is " + lastKey); }
运行结果:
大家有想过TreeMap的底层是怎么实现的吗,是如何维护key的顺序呢?答案就是基于红黑树实现的。
那什么是红黑树呢?我们在这里简单的认识一下,了解一下红黑树的特点:红黑树是一颗自平衡的排序二叉树。我们就先从二叉树开始说起。
二叉树
二叉树很容易理解,就是一棵树分俩叉。
上面这颗就是一颗最普通的二叉树。但是你会发现看起来不那么美观,因为你以H为根节点,发现左右两边高低不平衡,高度相差达到了2。于是出现了平衡二叉树,使得左右两边高低差不多。
平衡二叉树
这下子应该能看到,不管是从任何一个字母为根节点,左右两边的深度差不了2,最多是1。这就是平衡二叉树。不过好景不长,有一天,突然要把字母变成数字,还要保持这种特性怎么办呢?于是又出现了平衡二叉排序树。
平衡二叉排序树
不管是从长相(平衡),还是从规律(排序)感觉这棵树超级完美。但是有一个问题,那就是在增加删除节点的时候,你要时刻去让这棵树保持平衡,需要做太多的工作了,旋转的次数超级多,于是乎出现了红黑树。
红黑树
这就是传说中的红黑树,和平衡二叉排序树的区别就是每个节点涂上了颜色,他有下列五条性质:
这些性质有什么优点呢?就是插入效率超级高。因为在插入一个元素的时候,最多只需三次旋转,O(1)的复杂度,但是有一点需要说明他的查询效率略微逊色于平衡二叉树,因为他比平衡二叉树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较。如何去旋转呢?如下图所示。
首先是左旋:
然后是右旋:
红黑树更详细的内容可以参考文章:Java红黑树的数据结构与算法解析
//这是一个比较器,方便插入查找元素等操作 private final Comparator<? super K> comparator; //红黑树的根节点:每个节点是一个Entry private transient Entry<K,V> root; //集合元素数量 private transient int size = 0; //集合修改的记录 private transient int modCount = 0;
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; //左子树 Entry<K,V> left; //右子树 Entry<K,V> right; //父节点 Entry<K,V> parent; //每个节点的颜色:红黑树属性。 boolean color = BLACK; Entry(K key, V value, Entry<K,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 = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } }
TreeMap基于红黑树实现,而红黑树是一种自平衡二叉查找树,所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的,先将目标值和根节点的值进行比较,如果目标值小于根节点的值,则再和根节点的左孩子进行比较。如果目标值大于根节点的值,则继续和根节点的右孩子比较。在查找过程中,如果目标值和二叉树中的某个节点值相等,则返回 true,否则返回 false。TreeMap 查找和此类似,只不过在 TreeMap 中,节点(Entry)存储的是键值对<k,v>。在查找过程中,比较的是键的大小,返回的是值,如果没找到,则返回null。TreeMap 中的查找方法是get。
public V get(Object key) { //调用 getEntry方法查找 Entry<K,V> p = getEntry(key); return (p==null ? null : p. value); } final Entry<K,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节点 Entry<K,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; else return p; }
我们来看下关键的插入方法,在插入时候是如何维护key的。
public V put(K key, V value) { Entry<K,V> t = root; // 1.如果根节点为 null,将新节点设为根节点 if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } //如果root不为null,说明已存在元素 int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? 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; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); //根据比较结果决定插入到左子树还是右子树 if (cmp < 0) parent.left = e; else parent.right = e; //保持红黑树性质,进行红黑树的旋转等操作 fixAfterInsertion(e); size++; modCount++; return null; }
比较关键的就是fixAfterInsertion方法, 看懂这个方法需要你对红黑树的机制比较了解。
private void fixAfterInsertion(Entry<K,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的叔叔节点 Entry<K,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的父节点是祖父节点的右孩子和上面的相似 Entry<K,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是最复杂的方法。
public V remove(Object key) { // 根据key查找到对应的节点对象 Entry<K,V> p = getEntry(key); if (p == null) return null; // 记录key对应的value,供返回使用 V oldValue = p. value; // 删除节点 deleteEntry(p); return oldValue; }
private void deleteEntry(Entry<K,V> p) { modCount++; //元素个数减一 size--; // 如果被删除的节点p的左孩子和右孩子都不为空,则查找其替代节 if (p.left != null && p. right != null) { // 查找p的替代节点 Entry<K,V> s = successor (p); p. key = s.key ; p. value = s.value ; p = s; } Entry<K,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设置为其父节点的右孩子 else p. 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); // 下面删除替代节点p if (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; } } }
最终还是落到了对红黑树节点的删除上,需要维持红黑树的特性,做一系列的工作。