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