在前面几篇博客分别介绍了这样几种集合, 基于数组实现的 ArrayList 类, 基于链表实现的 LinkedList 类, 基于散列表实现的 HashMap 类, 本篇博客我们来介绍另一种数据类型, 基于树实现的 TreeSet 类.
1,TreeMap 定义
听名字就知道, 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 接口, 分别表示支持对象序列化以及对象克隆.
2, 字段定义
- 1,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 集合时, 需要对其按照年龄进行排序.
- package com.ys.test;
- /**
- * Create by YSOcean
- */
- public class Person {
- private String pname;
- private Integer page;
- public Person() {
- }
- public Person(String pname, Integer page) {
- this.pname = pname;
- this.page = page;
- }
- public String getPname() {
- return pname;
- }
- public void setPname(String pname) {
- this.pname = pname;
- }
- public Integer getPage() {
- return page;
- }
- public void setPage(Integer page) {
- this.page = page;
- }
- @Override
- public String toString() {
- return "Person{" +
- "pname='" + pname + '\'' +
- ", page=" + page +
- '}';
- }
- }
- View Code
排序代码:
- List<Person> personList = new ArrayList<>();
- personList.add(new Person("李四",20));
- personList.add(new Person("张三",10));
- personList.add(new Person("王五",30));
- System.out.println("原始顺序为:"+personList.toString());
- Collections.sort(personList, new Comparator<Person>() {
- @Override
- public int compare(Person o1, Person o2) {
- // 升序
- //return o1.getPage()-o2.getPage();
- // 降序
- return o2.getPage()-o1.getPage();
- // 不变
- //return 0
- }
- });
- System.out.println("排序后顺序为:"+personList.toString());
打印结果为:
- 2,Entry
- private transient Entry<K,V> root;
对于 Entry 详细源码如下:
- 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;
- /**
- * Make a new cell with given key, value, and parent, and with
- * {@code null} child links, and BLACK color.
- */
- Entry(K key, V value, Entry<K,V> parent) {
- this.key = key;
- this.value = value;
- this.parent = parent;
- }
- /**
- * Returns the key.
- *
- * @return the key
- */
- public K getKey() {
- return key;
- }
- /**
- * Returns the value associated with the key.
- *
- * @return the value associated with the key
- */
- public V getValue() {
- return value;
- }
- /**
- * Replaces the value currently associated with the key with the given
- * value.
- *
- * @return the value associated with the key before this method was
- * called
- */
- 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;
- }
- }
- View Code
这里主要看 Entry 类的几个字段:
- K key;
- V value;
- Entry<K,V> left;
- Entry<K,V> right;
- Entry<K,V> parent;
- boolean color = BLACK;
相信对红黑树这种数据结构了解的人, 一看这几个字段就明白了, 这也印证了前面所说的 TreeMap 底层有红黑树这种数据结构.
- 3,size
- /**
- * The number of entries in the tree
- */
- private transient int size = 0;
用来表示 entry 的个数, 也就是 key-value 的个数.
- 4,modCount
- /**
- * The number of structural modifications to the tree.
- */
- private transient int modCount = 0;
基本上前面讲的在 ArrayList,LinkedList,HashMap 等线程不安全的集合都有此字段, 用来实现 Fail-Fast 机制, 如果在迭代这些集合的过程中, 有其他线程修改了这些集合, 就会抛出 ConcurrentModificationException 异常.
5, 红黑树常量
- private static final boolean RED = false;
- private static final boolean BLACK = true;
3, 构造函数
1, 无参构造函数
- public TreeMap() {
- comparator = null;
- }
将比较器 comparator 置为 null, 表示按照 key 的自然顺序进行排序.
2, 带比较器的构造函数
- public TreeMap(Comparator<? super K> comparator) {
- this.comparator = comparator;
- }
需要自己实现 Comparator.
3, 构造包含指定 map 集合的元素
- public TreeMap(Map<? extends K, ? extends V> m) {
- comparator = null;
- putAll(m);
- }
使用该构造器创建的 TreeMap, 会默认插入 m 表示的集合元素, 并且 comparator 表示按照自然顺序进行插入.
4, 带 SortedMap 的构造函数
- public TreeMap(SortedMap<K, ? extends V> m) {
- comparator = m.comparator();
- try {
- buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
- } catch (java.io.IOException cannotHappen) {
- } catch (ClassNotFoundException cannotHappen) {
- }
- }
和上面带 Map 的构造函数不一样, map 是无序的, 而 SortedMap 是有序的, 使用 buildFromSorted() 方法将 SortedMap 集合中的元素插入到 TreeMap 中.
4, 添加元素
- // 添加元素
- public V put(K key, V value) {
- TreeMap.Entry<K,V> t = root;
- // 如果根节点为空, 即 TreeMap 中一个元素都没有, 那么设置新添加的元素为根节点
- // 并且设置集合大小 size=1, 以及 modCount+1, 这是用于快速失败
- if (t == null) {
- compare(key, key); // type (and possibly null) check
- root = new TreeMap.Entry<>(key, value, null);
- size = 1;
- modCount++;
- return null;
- }
- int cmp;
- TreeMap.Entry<K,V> parent;
- // split comparator and comparable paths
- Comparator<? super K> cpr = comparator;
- // 如果比较器不为空, 即初始化 TreeMap 构造函数时, 有传递 comparator 类
- // 那么插入新的元素时, 按照 comparator 实现的类进行排序
- if (cpr != null) {
- // 通过 do-while 循环不断遍历树, 调用比较器对 key 值进行比较
- do {
- parent = t;
- cmp = cpr.compare(key, t.key);
- if (cmp <0)
- t = t.left;
- else if (cmp> 0)
- t = t.right;
- else
- // 遇到 key 相等, 直接将新值覆盖到原值上
- return t.setValue(value);
- } while (t != null);
- }
- // 如果比较器为空, 即初始化 TreeMap 构造函数时, 没有传递 comparator 类
- // 那么插入新的元素时, 按照 key 的自然顺序
- else {
- // 如果 key==null, 直接抛出异常
- // 注意, 上面构造 TreeMap 传入了 Comparator, 是可以允许 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);
- }
- // 找到父亲节点, 根据父亲节点创建一个新节点
- TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
- if (cmp <0)
- parent.left = e;
- else
- parent.right = e;
- // 修正红黑树 (包括节点的左旋和右旋, 具体可以看我 Java 数据结构和算法中对红黑树的介绍)
- fixAfterInsertion(e);
- size++;
- modCount++;
- return null;
- }
添加元素, 如果初始化 TreeMap 构造函数时, 没有传递 comparator 类, 是不允许插入 key==null 的键值对的, 相反, 如果实现了 Comparator, 则可以传递 key=null 的键值对.
另外, 当插入一个新的元素后 (除了根节点), 会对 TreeMap 数据结构进行修正, 也就是对红黑树进行修正, 使其满足红黑树的几个特点, 具体修正方法包括改变节点颜色, 左旋, 右旋等操作, 这里我不做详细介绍了, 具体可以参考我的这篇博客: https://www.cnblogs.com/ysocean/p/8004211.html
5, 删除元素
1, 根据 key 删除
- public V remove(Object key) {
- // 根据 key 找到该节点
- TreeMap.Entry<K,V> p = getEntry(key);
- if (p == null)
- return null;
- // 获取该节点的 value, 并返回
- V oldValue = p.value;
- // 调用 deleteEntry() 方法删除节点
- deleteEntry(p);
- return oldValue;
- }
- private void deleteEntry(TreeMap.Entry<K,V> p) {
- modCount++;
- size--;
- // 如果删除节点的左右节点都不为空, 即有两个孩子
- if (p.left != null && p.right != null) {
- // 得到该节点的中序后继节点
- TreeMap.Entry<K,V> s = successor(p);
- p.key = s.key;
- p.value = s.value;
- p = s;
- } // p has 2 children
- // Start fixup at replacement node, if it exists.
- TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right);
- // 待删除节点只有一个子节点, 直接删除该节点, 并用该节点的唯一子节点顶替该节点
- if (replacement != null) {
- // Link replacement to parent
- replacement.parent = p.parent;
- if (p.parent == null)
- root = replacement;
- else if (p == p.parent.left)
- p.parent.left = replacement;
- else
- p.parent.right = replacement;
- // Null out links so they are OK to use by fixAfterDeletion.
- p.left = p.right = p.parent = null;
- // Fix replacement
- if (p.color == BLACK)
- fixAfterDeletion(replacement);
- //TreeMap 中只有待删除节点 P, 也就是只有一个节点, 直接返回 nul 即可
- } else if (p.parent == null) { // return if we are the only node.
- root = null;
- } else { // No children. Use self as phantom replacement and unlink.
- // 待删除节点没有子节点, 即为叶子节点, 直接删除即可
- if (p.color == BLACK)
- fixAfterDeletion(p);
- if (p.parent != null) {
- if (p == p.parent.left)
- p.parent.left = null;
- else if (p == p.parent.right)
- p.parent.right = null;
- p.parent = null;
- }
- }
- }
删除节点分为四种情况:
1, 根据 key 没有找到该节点: 也就是集合中不存在这一个节点, 直接返回 null 即可.
2, 根据 key 找到节点, 又分为三种情况:
1, 待删除节点没有子节点, 即为叶子节点: 直接删除该节点即可.
2, 待删除节点只有一个子节点: 那么首先找到待删除节点的子节点, 然后删除该节点, 用其唯一子节点顶替该节点.
3, 待删除节点有两个子节点: 首先找到该节点的中序后继节点, 然后把这个后继节点的内容复制给待删除节点, 然后删除该中序后继节点, 删除过程又转换成前面1,2两种情况了, 这里主要是找到中序后继节点, 相当于待删除节点的一个替身.
6, 查找元素
1, 根据 key 查找
- public V get(Object key) {
- TreeMap.Entry<K,V> p = getEntry(key);
- return (p==null ? null : p.value);
- }
- final TreeMap.Entry<K,V> getEntry(Object key) {
- // Offload comparator-based version for sake of performance
- if (comparator != null)
- return getEntryUsingComparator(key);
- if (key == null)
- throw new NullPointerException();
- @SuppressWarnings("unchecked")
- Comparable<? super K> k = (Comparable<? super K>) key;
- TreeMap.Entry<K,V> p = 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;
- }
- return null;
- }
7, 遍历元素
通常有下面两种方法, 第二种方法效率要快很多.
- TreeMap<String,Integer> map = new TreeMap<>();
- map.put("A",1);
- map.put("B",2);
- map.put("C",3);
- // 第一种方法
- // 首先利用 keySet() 方法得到 key 的集合, 然后利用 map.get() 方法根据 key 得到 value
- Iterator<String> iterator = map.keySet().iterator();
- while(iterator.hasNext()){
- String key = iterator.next();
- System.out.println(key+":"+map.get(key));
- }
- // 第二种方法
- Iterator<Map.Entry<String,Integer>> iterator1 = map.entrySet().iterator();
- while(iterator1.hasNext()){
- Map.Entry<String,Integer> entry = iterator1.next();
- System.out.println(entry.getKey()+":"+entry.getValue());
- }
来源: https://www.cnblogs.com/ysocean/p/10300976.html