TreeMap
Page content
简介
TreeMap 是由红黑树实现的有序的 key-value 集合。
- 想要学懂TreeMap的实现原理，红黑树的了解是必不可少的！
1public class TreeMap<K,V>
2 extends AbstractMap<K,V>
3 implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}
TreeMap 首先继承了 AbstractMap 抽象类，表示它具有散列表的性质，也就是由 key-value 组成。
其次 TreeMap 实现了 NavigableMap 接口，该接口支持一系列获取指定集合的导航方法，比如获取小于指定key的集合。
最后分别实现 Serializable 接口以及 Cloneable 接口，分别表示支持对象序列化以及对象克隆。
字段定义
Comparator
1/**
2 * The comparator used to maintain order in this tree map, or
3 * null if it uses the natural ordering of its keys.
4 * @serial
5 */
6private final Comparator<? super K> comparator;
可以看上面的英文注释，Comparator 是用来维护 treemap 集合中的顺序，如果为null，则按照 key 的自然顺序。
Comparator 是一个接口，排序时需要实现其 compare 方法，该方法返回正数、零、负数分别代表大于、等于、小于。那么怎么使用呢？这里举个例子：
这里有一个Person类，里面有两个属性name，age，将该person对象放入ArrayList集合时，需要对其按照年龄进行排序。
1package testTreeMap;
2
3/**
4 * @AUTHER Hory
5 * @TYPE Class
6 * @DATE 2021/3/19
7 */
8public class Person {
9 private String name;
10 private Integer age;
11
12 public Person() {}
13
14 public Person(String name, Integer age) {
15 this.name = name;
16 this.age = age;
17 }
18
19 public String getName() {
20 return name;
21 }
22
23 public void setName(String name) {
24 this.name = name;
25 }
26
27 public Integer getAge() {
28 return age;
29 }
30
31 public void setAge(Integer Age) {
32 this.age = age;
33 }
34
35 @Override
36 public String toString() {
37 return "Person{" +
38 "name='" + name + '\'' +
39 ", age=" + age +
40 '}';
41 }
42}
排序代码：
1List<Person> personList = new ArrayList<>();
2personList.add(new Person("李四",20));
3personList.add(new Person("张三",10));
4personList.add(new Person("王五",30));
5
6System.out.println("原始顺序为："+personList.toString());
7
8Collections.sort(personList, new Comparator<Person>() {
9 @Override
10 public int compare(Person o1, Person o2) {
11 //return o1.getPage()-o2.getPage(); // 升序
12 return o2.getAge()-o1.getAge(); // 降序
13 //return 0; // 不变
14 }
15});
16System.out.println("排序后顺序为：" + personList.toString());
打印结果为：
1原始顺序为：[Person{name='李四', age=20}, Person{name='张三', age=10}, Person{name='王五', age=30}]
2排序后顺序为：[Person{name='王五', age=30}, Person{name='李四', age=20}, Person{name='张三', age=10}]
Entry
1private transient Entry<K,V> root;
Entry详细源码如下：
1static final class Entry<K,V> implements Map.Entry<K,V> {
2 K key;
3 V value;
4 Entry<K,V> left;
5 Entry<K,V> right;
6 Entry<K,V> parent;
7 boolean color = BLACK;
8
9 /**
10 * Make a new cell with given key, value, and parent, and with
11 * {@code null} child links, and BLACK color.
12 */
13 Entry(K key, V value, Entry<K,V> parent) {
14 this.key = key;
15 this.value = value;
16 this.parent = parent;
17 }
18
19 /**
20 * Returns the key.
21 *
22 * @return the key
23 */
24 public K getKey() {
25 return key;
26 }
27
28 /**
29 * Returns the value associated with the key.
30 *
31 * @return the value associated with the key
32 */
33 public V getValue() {
34 return value;
35 }
36
37 /**
38 * Replaces the value currently associated with the key with the given
39 * value.
40 *
41 * @return the value associated with the key before this method was
42 * called
43 */
44 public V setValue(V value) {
45 V oldValue = this.value;
46 this.value = value;
47 return oldValue;
48 }
49
50 public boolean equals(Object o) {
51 if (!(o instanceof Map.Entry))
52 return false;
53 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
54
55 return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
56 }
57
58 public int hashCode() {
59 int keyHash = (key==null ? 0 : key.hashCode());
60 int valueHash = (value==null ? 0 : value.hashCode());
61 return keyHash ^ valueHash;
62 }
63
64 public String toString() {
65 return key + "=" + value;
66 }
67}
这里主要看 Entry 类的几个字段：
1K key;
2V value;
3Entry<K,V> left;
4Entry<K,V> right;
5Entry<K,V> parent;
6boolean color = BLACK;
相信对红黑树这种数据结构了解的人，一看这几个字段就明白了，这也印证了前面所说的 TreeMap 底层有红黑树这种数据结构。
size
1/**
2 * The number of entries in the tree
3 */
4private transient int size = 0;
用来表示 entry 的个数，也就是 key-value 的个数。
modCount
1/**
2 * The number of structural modifications to the tree.
3 */
4private transient int modCount = 0;
基本上前面讲的在 ArrayList、LinkedList、HashMap 等线程不安全的集合都有此字段，用来实现 Fail-Fast 机制，如果在迭代这些集合的过程中，有其他线程修改了这些集合，就会抛出 ConcurrentModificationException 异常。
红黑树常量
1private static final boolean RED = false;
2private static final boolean BLACK = true;
构造函数
无参构造函数
1public TreeMap() {
2 comparator = null;
3}
将比较器 comparator 置为 null，表示按照 key 的自然顺序进行排序。
带比较器的构造函数
1public TreeMap(Comparator<? super K> comparator) {
2 this.comparator = comparator;
3}
需要自己实现Comparator。
构造包含指定map集合的元素
1public TreeMap(Map<? extends K, ? extends V> m) {
2 comparator = null;
3 putAll(m);
4}
使用该构造器创建的 TreeMap，会默认插入m表示的集合元素，并且comparator表示按照自然顺序进行插入。
带 SortedMap 的构造函数
1public TreeMap(SortedMap<K, ? extends V> m) {
2 comparator = m.comparator();
3 try {
4 buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
5 } catch (java.io.IOException cannotHappen) {
6 } catch (ClassNotFoundException cannotHappen) {
7 }
8}
和上面带 Map 的构造函数不一样，map 是无序的，而 SortedMap 是有序的，使用 buildFromSorted() 方法将SortedMap 集合中的元素插入到 TreeMap 中。
添加元素
1public V put(K key, V value) {
2 TreeMap.Entry<K,V> t = root;
3 // 如果根节点为空，即TreeMap中一个元素都没有，那么设置新添加的元素为根节点
4 // 并且设置集合大小size=1,以及modCount+1，这是用于快速失败
5 if (t == null) {
6 compare(key, key); // type (and possibly null) check
7
8 root = new TreeMap.Entry<>(key, value, null);
9 size = 1;
10 modCount++;
11 return null;
12 }
13 int cmp;
14 TreeMap.Entry<K,V> parent;
15 // split comparator and comparable paths
16 Comparator<? super K> cpr = comparator;
17 // 如果比较器不为空，即初始化TreeMap构造函数时，有传递comparator类
18 // 那么插入新的元素时，按照comparator实现的类进行排序
19 if (cpr != null) {
20 // 通过do-while循环不断遍历树，调用比较器对key值进行比较
21 do {
22 parent = t;
23 cmp = cpr.compare(key, t.key);
24 if (cmp < 0)
25 t = t.left;
26 else if (cmp > 0)
27 t = t.right;
28 else
29 // 遇到key相等，直接将新值覆盖到原值上
30 return t.setValue(value);
31 } while (t != null);
32 }
33 // 如果比较器为空，即初始化TreeMap构造函数时，没有传递comparator类
34 // 那么插入新的元素时，按照key的自然顺序
35 else {
36 // 如果key==null，直接抛出异常
37 // 注意，上面构造TreeMap传入了Comparator，是可以允许key==null
38 if (key == null)
39 throw new NullPointerException();
40 @SuppressWarnings("unchecked")
41 Comparable<? super K> k = (Comparable<? super K>) key;
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 // 找到父亲节点，根据父亲节点创建一个新节点
54 TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
55 if (cmp < 0)
56 parent.left = e;
57 else
58 parent.right = e;
59 // 修正红黑树（包括节点的左旋和右旋，具体可以看我Java数据结构和算法中对红黑树的介绍）
60 fixAfterInsertion(e);
61 size++;
62 modCount++;
63 return null;
64}
添加元素，如果初始化 TreeMap 构造函数时，没有传递comparator类，是不允许插入 key==null 的键值对的，相反，如果实现了Comparator，则可以传递 key=null 的键值对。
另外，当插入一个新的元素后（除了根节点），会对 TreeMap 数据结构进行修正，也就是对红黑树进行修正，使其满足红黑树的几个特点，具体修正方法包括改变节点颜色、左旋、右旋等操作，这里我不做详细介绍了，具体可以参考这篇博客：https://www.cnblogs.com/ysocean/p/8004211.html
删除元素
根据 key 删除
1 public V get(Object key) {
2 TreeMap.Entry<K,V> p = getEntry(key);
3 return (p==null ? null : p.value);
4 }
5
6 final TreeMap.Entry<K,V> getEntry(Object key) {
7 // Offload comparator-based version for sake of performance
8 if (comparator != null)
9 return getEntryUsingComparator(key);
10 if (key == null)
11 throw new NullPointerException();
12 @SuppressWarnings("unchecked")
13 Comparable<? super K> k = (Comparable<? super K>) key;
14 TreeMap.Entry<K,V> p = root;
15 while (p != null) {
16 int cmp = k.compareTo(p.key);
17 if (cmp < 0)
18 p = p.left;
19 else if (cmp > 0)
20 p = p.right;
21 else
22 return p;
23 }
24 return null;
25 }
删除节点分为四种情况：
-
根据 key 没有找到该节点：也就是集合中不存在这一个节点，直接返回null即可。
-
根据key找到节点，又分为三种情况：
- ① 待删除节点没有子节点，即为叶子节点：直接删除该节点即可。
- ② 待删除节点只有一个子节点：那么首先找到待删除节点的子节点，然后删除该节点，用其唯一子节点顶替该节点。
- ③ 待删除节点有两个子节点：首先找到该节点的中序后继节点，然后把这个后继节点的内容复制给待删除节点，然后删除该中序后继节点，删除过程又转换成前面①、②两种情况了，这里主要是找到中序后继节点，相当于待删除节点的一个替身。
查找元素
根据 key 查找
1public V get(Object key) {
2 TreeMap.Entry<K,V> p = getEntry(key);
3 return (p==null ? null : p.value);
4}
5
6final TreeMap.Entry<K,V> getEntry(Object key) {
7 // Offload comparator-based version for sake of performance
8 if (comparator != null)
9 return getEntryUsingComparator(key);
10 if (key == null)
11 throw new NullPointerException();
12 @SuppressWarnings("unchecked")
13 Comparable<? super K> k = (Comparable<? super K>) key;
14 TreeMap.Entry<K,V> p = root;
15 while (p != null) {
16 int cmp = k.compareTo(p.key);
17 if (cmp < 0)
18 p = p.left;
19 else if (cmp > 0)
20 p = p.right;
21 else
22 return p;
23 }
24 return null;
25}
遍历元素
通常有下面两种方法，第二种方法效率要快很多。
1TreeMap<String,Integer> map = new TreeMap<>();
2map.put("A",1);
3map.put("B",2);
4map.put("C",3);
5
6// 第一种方法
7// 首先利用 keySet() 方法得到key的集合，然后利用map.get()方法根据key得到value
8Iterator<String> iterator = map.keySet().iterator();
9while(iterator.hasNext()){
10 String key = iterator.next();
11 System.out.println(key+":"+map.get(key));
12}
13
14//第二种方法
15Iterator<Map.Entry<String,Integer>> iterator1 = map.entrySet().iterator();
16while(iterator1.hasNext()){
17 Map.Entry<String,Integer> entry = iterator1.next();
18 System.out.println(entry.getKey()+":"+entry.getValue());
19}
