Java
Java集合

Java集合13 - TreeMap详细介绍(1)

简介:集合是Java中非常重要而且基础的内容,因为任何数据必不可少的就是该数据是如何存储的,集合的作用就是以一定的方式组织、存储数据。

1. TreeMap简介

  • TreeMap是一个有序的key-value集合,它是通过红黑树实现的。
  • TreeMap继承于AbstractMap,所以它是一个Map,即一个key-value集合。
  • TreeMap实现了NavigableMap接口,意味着它支持一系列的导航方法,比如返回有序的key集合。
  • TreeMap实现了Cloneable接口,意味着它能被克隆。
  • TreeMap实现了java.io.Serializable接口,意味着它支持序列化。

TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的Comparator进行排序,具体取决于使用的构造方法。

TreeMap的基本操作containsKey、get、put和remove的时间复杂度是log(n)。另外,TreeMap是非同步的。它的iterator方法返回的迭代器是fail-fast的。

1.1. TreeMap的构造函数

  • // 默认构造函数。使用该构造函数,TreeMap中的元素按照自然排序进行排列。
  • TreeMap()
  • // 创建的TreeMap包含Map
  • TreeMap(Map<? extends K, ? extends V> copyFrom)
  • // 指定Tree的比较器
  • TreeMap(Comparator<? super K> comparator)
  • // 创建的TreeSet包含copyFrom
  • TreeMap(SortedMap<K, ? extends V> copyFrom)

1.2. TreeMap的API

  • Entry<K, V> ceilingEntry(K key)
  • K ceilingKey(K key)
  • void clear()
  • Object clone()
  • Comparator<? super K> comparator()
  • boolean containsKey(Object key)
  • NavigableSet<K> descendingKeySet()
  • NavigableMap<K, V> descendingMap()
  • Set<Entry<K, V>> entrySet()
  • Entry<K, V> firstEntry()
  • K firstKey()
  • Entry<K, V> floorEntry(K key)
  • K floorKey(K key)
  • V get(Object key)
  • NavigableMap<K, V> headMap(K to, boolean inclusive)
  • SortedMap<K, V> headMap(K toExclusive)
  • Entry<K, V> higherEntry(K key)
  • K higherKey(K key)
  • boolean isEmpty()
  • Set<K> keySet()
  • Entry<K, V> lastEntry()
  • K lastKey()
  • Entry<K, V> lowerEntry(K key)
  • K lowerKey(K key)
  • NavigableSet<K> navigableKeySet()
  • Entry<K, V> pollFirstEntry()
  • Entry<K, V> pollLastEntry()
  • V put(K key, V value)
  • V remove(Object key)
  • int size()
  • SortedMap<K, V> subMap(K fromInclusive, K toExclusive)
  • NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
  • NavigableMap<K, V> tailMap(K from, boolean inclusive)
  • SortedMap<K, V> tailMap(K fromInclusive)

1.3. TreeMap的数据结构

  • java.lang.Object
  • java.util.AbstractMap<K, V>
  • java.util.TreeMap<K, V>
  • public class TreeMap<K,V>
  • extends AbstractMap<K,V>
  • implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}

TreeMap与Map关系如下图:

1.TreeMap与Map关系图.png

从图中可以看出:

  1. TreeMap实现继承于AbstractMap,并且实现了NavigableMap接口。
  2. TreeMap的本质是R-B Tree(红黑树),它包含几个重要的成员变量:rootsizecomparator
    • root是红黑数的根节点。它是Entry类型,Entry是红黑数的节点,它包含了红黑数的6个基本组成成分:key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序,Entry节点包含的内容为value
    • 红黑数排序时,根据Entry中的key进行排序;Entry中的key比较大小是根据比较器comparator来进行判断的。
    • size是红黑数中节点的个数。

关于红黑数的具体算法,请参考数据结构——红黑树原理和算法详细介绍

2. TreeMap源码解析(基于JDK1.6.0#_45)

为了更了解TreeMap的原理,下面对TreeMap源码代码作出分析,源码内容中包含了详细的代码注释。

TreeMap源码,点击菜单展开
  • package java.util;
  • public class TreeMap<K, V>
  • extends AbstractMap<K, V>
  • implements NavigableMap<K, V>, Cloneable, java.io.Serializable {
  • // 比较器,用来给TreeMap排序
  • private final Comparator<? super K> comparator;
  • // TreeMap是红黑树实现的,root是红黑书的根节点
  • private transient Entry<K, V> root = null;
  • // 红黑树的节点总数
  • private transient int size = 0;
  • // 记录红黑树的修改次数
  • private transient int modCount = 0;
  • // 默认构造函数
  • public TreeMap() {
  • comparator = null;
  • }
  • // 带比较器的构造函数
  • public TreeMap(Comparator<? super K> comparator) {
  • this.comparator = comparator;
  • }
  • // 带Map的构造函数,Map会成为TreeMap的子集
  • public TreeMap(Map<? extends K, ? extends V> m) {
  • comparator = null;
  • putAll(m);
  • }
  • // 带SortedMap的构造函数,SortedMap会成为TreeMap的子集
  • 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) {
  • }
  • }
  • public int size() {
  • return size;
  • }
  • // 返回TreeMap中是否保护键(key)
  • public boolean containsKey(Object key) {
  • return getEntry(key) != null;
  • }
  • <