深圳幻海软件技术有限公司 欢迎您！
更多

一文带你全面深入了解TreeMap

2023-04-05

节点 null key
概述TreeMap是Map家族中的一员，也是用来存放key-value键值对的。平时在工作中使用的可能并不多，它最大的特点是遍历时是有顺序的，根据key的排序规则来，那么它具体是如何使用，又是怎么实现的呢？本文基于jdk8做一个讲解。TreeMap介绍TreeMap是一个基于key有序的keyval

概述

TreeMap是Map家族中的一员，也是用来存放key-value键值对的。平时在工作中使用的可能并不多，它最大的特点是遍历时是有顺序的，根据key的排序规则来，那么它具体是如何使用，又是怎么实现的呢？本文基于jdk8做一个讲解。

TreeMap介绍

TreeMap是一个基于key有序的key value散列表。

  • map根据其键的自然顺序排序，或者根据map创建时提供的Comparator排序
  • 不是线程安全的
  • key 不可以存入null
  • 底层是基于红黑树实现的

以上是TreeMap的类结构图：

  1. 实现了NavigableMap接口，NavigableMap又实现了Map接口，提供了导航相关的方法。
  2. 继承了AbstractMap，该方法实现Map操作的骨干逻辑。
  3. 实现了Cloneable接口，标记该类支持clone方法复制
  4. 实现了Serializable接口，标记该类支持序列化

构造方法

  • 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的部分的视图。

使用案例

  • 验证顺序性
  1. @Test
  2.     public void test1() {
  3.         Map<Integer, String> treeMap = new TreeMap<>();
  4.         treeMap.put(16, "a");
  5.         treeMap.put(1, "b");
  6.         treeMap.put(4, "c");
  7.         treeMap.put(3, "d");
  8.         treeMap.put(8, "e");
  9.         // 遍历
  10.         System.out.println("默认排序：");
  11.         treeMap.forEach((key, value) -> {
  12.             System.out.println("key: " + key + ", value: " + value);
  13.         });
  14.  
  15.         // 构造方法传入比较器
  16.         Map<Integer, String> tree2Map = new TreeMap<>((o1, o2) -> o2 - o1);
  17.         tree2Map.put(16, "a");
  18.         tree2Map.put(1, "b");
  19.         tree2Map.put(4, "c");
  20.         tree2Map.put(3, "d");
  21.         tree2Map.put(8, "e");
  22.         // 遍历
  23.         System.out.println("倒序排序：");
  24.         tree2Map.forEach((key, value) -> {
  25.             System.out.println("key: " + key + ", value: " + value);
  26.         });
  27.     }

运行结果：

  • 验证不能存储null
  1. @Test
  2.     public void test2() {
  3.         Map<Integer, String> treeMap = new TreeMap<>();
  4.         treeMap.put(null, "a");
  5.     }

运行结果：

  • 验证NavigableMap相关方法
  1. @Test
  2.     public void test3() {
  3.         NavigableMap<Integer, String> treeMap = new TreeMap<>();
  4.         treeMap.put(16, "a");
  5.         treeMap.put(1, "b");
  6.         treeMap.put(4, "c");
  7.         treeMap.put(3, "d");
  8.         treeMap.put(8, "e");
  9.  
  10.         // 获取大于等于5的key
  11.         Integer ceilingKey = treeMap.ceilingKey(5);
  12.         System.out.println("ceilingKey 5 is " + ceilingKey);
  13.  
  14.         // 获取最大的key
  15.         Integer lastKey = treeMap.lastKey();
  16.         System.out.println("lastKey is " + lastKey);
  17.     }

运行结果：

核心机制

实现原理

大家有想过TreeMap的底层是怎么实现的吗，是如何维护key的顺序呢？答案就是基于红黑树实现的。

那什么是红黑树呢？我们在这里简单的认识一下，了解一下红黑树的特点：红黑树是一颗自平衡的排序二叉树。我们就先从二叉树开始说起。

  • 二叉树

二叉树很容易理解，就是一棵树分俩叉。

上面这颗就是一颗最普通的二叉树。但是你会发现看起来不那么美观，因为你以H为根节点，发现左右两边高低不平衡，高度相差达到了2。于是出现了平衡二叉树，使得左右两边高低差不多。

  • 平衡二叉树

这下子应该能看到，不管是从任何一个字母为根节点，左右两边的深度差不了2，最多是1。这就是平衡二叉树。不过好景不长，有一天，突然要把字母变成数字，还要保持这种特性怎么办呢？于是又出现了平衡二叉排序树。

  • 平衡二叉排序树

不管是从长相（平衡），还是从规律（排序）感觉这棵树超级完美。但是有一个问题，那就是在增加删除节点的时候，你要时刻去让这棵树保持平衡，需要做太多的工作了，旋转的次数超级多，于是乎出现了红黑树。

  • 红黑树

这就是传说中的红黑树，和平衡二叉排序树的区别就是每个节点涂上了颜色，他有下列五条性质：

  1. 每个节点都只能是红色或者黑色
  2. 根节点是黑色
  3. 每个叶节点（NIL节点，空节点）是黑色的。
  4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质有什么优点呢？就是插入效率超级高。因为在插入一个元素的时候，最多只需三次旋转，O(1)的复杂度，但是有一点需要说明他的查询效率略微逊色于平衡二叉树，因为他比平衡二叉树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较。如何去旋转呢？如下图所示。

首先是左旋：

然后是右旋：

红黑树更详细的内容可以参考这篇文章：segmentfault.com/a/119000001…

源码解析

成员变量

  1. //这是一个比较器，方便插入查找元素等操作
  2. private final Comparator<? super K> comparator;
  3. //红黑树的根节点：每个节点是一个Entry
  4. private transient Entry<K,V> root;
  5. //集合元素数量
  6. private transient int size = 0;
  7. //集合修改的记录
  8. private transient int modCount = 0;
  • comparator是一个排序器，作为key的排序规则
  • root是红黑树的根节点，说明的确底层用的红黑树作为数据结构。
  1. static final class Entry<K,V> implements Map.Entry<K,V> {
  2.         K key;
  3.         V value;
  4.      //左子树
  5.         Entry<K,V> left;
  6.      //右子树
  7.         Entry<K,V> right;
  8.      //父节点
  9.         Entry<K,V> parent;
  10.      //每个节点的颜色：红黑树属性。
  11.         boolean color = BLACK;
  12.         Entry(K key, V value, Entry<K,V> parent) {
  13.             this.key = key;
  14.             this.value = value;
  15.             this.parent = parent;
  16.         }
  17.         public K getKey() {
  18.             return key;
  19.         }
  20.         public V getValue() {
  21.             return value;
  22.         }
  23.         public V setValue(V value) {
  24.             V oldValue = this.value;
  25.             this.value = value;
  26.             return oldValue;
  27.         }
  28.  
  29.         public boolean equals(Object o) {
  30.             if (!(o instanceof Map.Entry))
  31.                 return false;
  32.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  33.  
  34.             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
  35.         }
  36.  
  37.         public int hashCode() {
  38.             int keyHash = (key==null ? 0 : key.hashCode());
  39.             int valueHash = (value==null ? 0 : value.hashCode());
  40.             return keyHash ^ valueHash;
  41.         }
  42.  
  43.         public String toString() {
  44.             return key + "=" + value;
  45.         }
  46.     }

查找get方法

TreeMap基于红黑树实现，而红黑树是一种自平衡二叉查找树，所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的，先将目标值和根节点的值进行比较，如果目标值小于根节点的值，则再和根节点的左孩子进行比较。如果目标值大于根节点的值，则继续和根节点的右孩子比较。在查找过程中，如果目标值和二叉树中的某个节点值相等，则返回 true，否则返回 false。TreeMap 查找和此类似，只不过在 TreeMap 中，节点（Entry）存储的是键值对<k,v>。在查找过程中，比较的是键的大小，返回的是值，如果没找到，则返回null。TreeMap 中的查找方法是get。

  1. public V get(Object key) {
  2.         //调用 getEntry方法查找
  3.         Entry<K,V> p = getEntry(key);
  4.         return (p==null ? null : p. value);
  5. }
  6.  
  7. final Entry<K,V> getEntry(Object key) {
  8.     / 如果比较器为空，只是用key作为比较器查询
  9.     if (comparator != null) 
  10.         return getEntryUsingComparator(key);
  11.     if (key == null)
  12.         throw new NullPointerException();
  13.     Comparable<? super K> k = (Comparable<? super K>) key;
  14.     // 取得root节点
  15.     Entry<K,V> p = root;
  16.    //核心来了：从root节点开始查找，根据比较器判断是在左子树还是右子树
  17.     while (p != null) {
  18.         int cmp = k.compareTo(p.key );
  19.         if (cmp < 0)
  20.             p = p. left;
  21.         else if (cmp > 0)
  22.             p = p. right;
  23.         else
  24.            return p;
  25.     }
  26.

插入put方法

我们来看下关键的插入方法，在插入时候是如何维护key的。

  1. public V put(K key, V value) {
  2.         Entry<K,V> t = root;
  3.        // 1.如果根节点为 null，将新节点设为根节点
  4.         if (t == null) {
  5.             compare(key, key); // type (and possibly null) check
  6.  
  7.             root = new Entry<>(key, value, null);
  8.             size = 1;
  9.             modCount++;
  10.             return null;
  11.         }
  12.       //如果root不为null，说明已存在元素 
  13.         int cmp;
  14.         Entry<K,V> parent;
  15.         // split comparator and comparable paths
  16.         Comparator<? super K> cpr = comparator;
  17.     //如果比较器不为null 则使用比较器
  18.         if (cpr != null) {
  19.             //找到元素的插入位置
  20.             do {
  21.                 parent = t;
  22.                 cmp = cpr.compare(key, t.key);
  23.                  //当前key小于节点key 向左子树查找
  24.                 if (cmp < 0)
  25.                     t = t.left;
  26.                     //当前key大于节点key 向右子树查找
  27.                 else if (cmp > 0)
  28.                     t = t.right;
  29.                 else
  30.                     //相等的情况下 直接更新节点值
  31.                     return t.setValue(value);
  32.             } while (t != null);
  33.         }
  34.             //如果比较器为null 则使用默认比较器
  35.         else {
  36.             //如果key为null  则抛出异常
  37.             if (key == null)
  38.                 throw new NullPointerException();
  39.             @SuppressWarnings("unchecked")
  40.                 Comparable<? super K> k = (Comparable<? super K>) key;
  41.              //找到元素的插入位置
  42.             do {
  43.                 parent = t;
  44.                 cmp = k.compareTo(t.key);
  45.                 if (cmp < 0)
  46.                     t = t.left;
  47.                 else if (cmp > 0)
  48.                     t = t.right;
  49.                 else
  50.                     return t.setValue(value);
  51.             } while (t != null);
  52.         }
  53.         Entry<K,V> e = new Entry<>(key, value, parent);
  54.       //根据比较结果决定插入到左子树还是右子树
  55.         if (cmp < 0)
  56.             parent.left = e;
  57.         else
  58.             parent.right = e;
  59.     //保持红黑树性质，进行红黑树的旋转等操作
  60.         fixAfterInsertion(e);
  61.         size++;
  62.         modCount++;
  63.         return null;
  64.     }

比较关键的就是fixAfterInsertion方法， 看懂这个方法需要你对红黑树的机制比较了解。

  1. private void fixAfterInsertion(Entry<K,V> x) {
  2.     // 将新插入节点的颜色设置为红色
  3.     x. color = RED;
  4.     // while循环，保证新插入节点x不是根节点或者新插入节点x的父节点不是红色（这两种情况不需要调整）
  5.     while (x != null && x != root && x. parent.color == RED) {
  6.         // 如果新插入节点x的父节点是祖父节点的左孩子
  7.         if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
  8.             // 取得新插入节点x的叔叔节点
  9.             Entry<K,V> y = rightOf(parentOf (parentOf(x)));
  10.             // 如果新插入x的父节点是红色
  11.             if (colorOf(y) == RED) {
  12.                 // 将x的父节点设置为黑色
  13.                 setColor(parentOf (x), BLACK);
  14.                 // 将x的叔叔节点设置为黑色
  15.                 setColor(y, BLACK);
  16.                 // 将x的祖父节点设置为红色
  17.                 setColor(parentOf (parentOf(x)), RED);
  18.                 // 将x指向祖父节点，如果x的祖父节点的父节点是红色，按照上面的步奏继续循环
  19.                 x = parentOf(parentOf (x));
  20.             } else {
  21.                 // 如果新插入x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的右孩子
  22.                 if (x == rightOf( parentOf(x))) {
  23.                     // 左旋父节点
  24.                     x = parentOf(x);
  25.                     rotateLeft(x);
  26.                 }
  27.                 // 如果新插入x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的左孩子
  28.                 // 将x的父节点设置为黑色
  29.                 setColor(parentOf (x), BLACK);
  30.                 // 将x的祖父节点设置为红色
  31.                 setColor(parentOf (parentOf(x)), RED);
  32.                 // 右旋x的祖父节点
  33.                 rotateRight( parentOf(parentOf (x)));
  34.             }
  35.         } else { // 如果新插入节点x的父节点是祖父节点的右孩子和上面的相似
  36.             Entry<K,V> y = leftOf(parentOf (parentOf(x)));
  37.             if (colorOf(y) == RED) {
  38.                 setColor(parentOf (x), BLACK);
  39.                 setColor(y, BLACK);
  40.                 setColor(parentOf (parentOf(x)), RED);
  41.                 x = parentOf(parentOf (x));
  42.             } else {
  43.                 if (x == leftOf( parentOf(x))) {
  44.                     x = parentOf(x);
  45.                     rotateRight(x);
  46.                 }
  47.                 setColor(parentOf (x), BLACK);
  48.                 setColor(parentOf (parentOf(x)), RED);
  49.                 rotateLeft( parentOf(parentOf (x)));
  50.             }
  51.         }
  52.     }
  53.     // 最后将根节点设置为黑色
  54.     root.color = BLACK;
  55. }

删除remove方法

删除remove是最复杂的方法。

  1. public V remove(Object key) {
  2.         // 根据key查找到对应的节点对象
  3.         Entry<K,V> p = getEntry(key);
  4.         if (p == null)
  5.             return null;
  6.  
  7.         // 记录key对应的value，供返回使用
  8.         V oldValue = p. value;
  9.         // 删除节点
  10.         deleteEntry(p);
  11.         return oldValue;
  12. }
  1. private void deleteEntry(Entry<K,V> p) {
  2.         modCount++;
  3.         //元素个数减一
  4.         size--;
  5.         // 如果被删除的节点p的左孩子和右孩子都不为空，则查找其替代节
  6.         if (p.left != null && p. right != null) {
  7.             // 查找p的替代节点
  8.             Entry<K,V> s = successor (p);
  9.             p. key = s.key ;
  10.             p. value = s.value ;
  11.             p = s;
  12.         }
  13.         Entry<K,V> replacement = (p. left != null ? p.left : p. right);
  14.         if (replacement != null) { 
  15.             // 将p的父节点拷贝给替代节点
  16.             replacement. parent = p.parent ;
  17.             // 如果替代节点p的父节点为空，也就是p为跟节点，则将replacement设置为根节点
  18.             if (p.parent == null)
  19.                 root = replacement;
  20.             // 如果替代节点p是其父节点的左孩子，则将replacement设置为其父节点的左孩子
  21.             else if (p == p.parent. left)
  22.                 p. parent.left   = replacement;
  23.             // 如果替代节点p是其父节点的左孩子，则将replacement设置为其父节点的右孩子
  24.             else
  25.                 p. parent.right = replacement;
  26.             // 将替代节点p的left、right、parent的指针都指向空
  27.             p. left = p.right = p.parent = null;
  28.             // 如果替代节点p的颜色是黑色，则需要调整红黑树以保持其平衡
  29.             if (p.color == BLACK)
  30.                 fixAfterDeletion(replacement);
  31.         } else if (p.parent == null) { // return if we are the only node.
  32.             // 如果要替代节点p没有父节点，代表p为根节点，直接删除即可
  33.             root = null;
  34.         } else {
  35.             // 如果p的颜色是黑色，则调整红黑树
  36.             if (p.color == BLACK)
  37.                 fixAfterDeletion(p);
  38.             // 下面删除替代节点p
  39.             if (p.parent != null) {
  40.                 // 解除p的父节点对p的引用
  41.                 if (p == p.parent .left)
  42.                     p. parent.left = null;
  43.                 else if (p == p.parent. right)
  44.                     p. parent.right = null;
  45.                 // 解除p对p父节点的引用
  46.                 p. parent = null;
  47.             }
  48.         }
  49.     }

最终还是落到了对红黑树节点的删除上，需要维持红黑树的特性，做一系列的工作。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览43110 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪