Java 集合 (9) -- TreeMap 类

1. 简介

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

TreeMap 使用红黑树存储元素，可以保证元素按 key 值的大小进行遍历。

TreeMap 继承自 AbstractMap 抽象类，并实现了 NavigableMap 接口，而 NavigableMap 继承了 SortedMap 接口，因此 TreeMap 支持遍历时按元素的大小有序遍历，另外 TreeMap 还实现了 Cloneable 接口和 Serializable 接口，支持使用 clone() 进行克隆 、 支持序列化与反序列化。

TreeMap 的存储结构只有一颗红黑树，性能上比 HashMap 要差一些，因为 HashMap 前面还做了一层桶，寻找元素要快很多，TreeMap 没有扩容的概念，遍历也不是采用传统的递归式遍历，可以按范围查找元素，查找最近的元素。

2. 继承体系

3. NavigableMap 接口 & SortedMap 接口

1. SortedMap 规定了元素可以按 key 的大小来遍历，它定义了一些返回部分 map 的方法。

   public interface SortedMap<K,V> extends Map<K,V> {
         // key的比较器Comparator<? super K> comparator();// 返回fromKey（包含）到toKey（不包含）之间的元素组成的子mapSortedMap<K,V> subMap(K fromKey, K toKey);// 返回小于toKey（不包含）的子mapSortedMap<K,V> headMap(K toKey);// 返回大于等于fromKey（包含）的子mapSortedMap<K,V> tailMap(K fromKey);// 返回最小的keyK firstKey();// 返回最大的keyK lastKey();// 返回key集合Set<K> keySet();// 返回value集合Collection<V> values();// 返回节点集合Set<Map.Entry<K, V>> entrySet();
   }
   

2. NavigableMap 是对 SortedMap 的增强，定义了一些返回离目标 key 最近的元素的方法。

   public interface NavigableMap<K,V> extends SortedMap<K,V> {
         // 小于给定key的最大节点Map.Entry<K,V> lowerEntry(K key);// 小于给定key的最大keyK lowerKey(K key);// 小于等于给定key的最大节点Map.Entry<K,V> floorEntry(K key);// 小于等于给定key的最大keyK floorKey(K key);// 大于等于给定key的最小节点Map.Entry<K,V> ceilingEntry(K key);// 大于等于给定key的最小keyK ceilingKey(K key);// 大于给定key的最小节点Map.Entry<K,V> higherEntry(K key);// 大于给定key的最小keyK higherKey(K key);// 最小的节点Map.Entry<K,V> firstEntry();// 最大的节点Map.Entry<K,V> lastEntry();// 弹出最小的节点Map.Entry<K,V> pollFirstEntry();// 弹出最大的节点Map.Entry<K,V> pollLastEntry();// 返回倒序的mapNavigableMap<K,V> descendingMap();// 返回有序的key集合NavigableSet<K> navigableKeySet();// 返回倒序的key集合NavigableSet<K> descendingKeySet();// 返回从fromKey到toKey的子map，是否包含起止元素可以自己决定NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,K toKey,   boolean toInclusive);// 返回小于toKey的子map，是否包含toKey自己决定NavigableMap<K,V> headMap(K toKey, boolean inclusive);// 返回大于fromKey的子map，是否包含fromKey自己决定NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);// 等价于subMap(fromKey, true, toKey, false)SortedMap<K,V> subMap(K fromKey, K toKey);// 等价于headMap(toKey, false)SortedMap<K,V> headMap(K toKey);// 等价于tailMap(fromKey, true)SortedMap<K,V> tailMap(K fromKey);
   }
   

4. 内部类

1. 存储节点，典型的红黑树结构。

   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;
   }
   

5. 字段

/*** 比较器，如果没传则key要实现Comparable接口，以上就是按key的大小排序的两种方式*/
private final Comparator<? super K> comparator;/*** 根节点，TreeMap没有桶的概念，所有的元素都存储在一颗树中。*/
private transient Entry<K,V> root;/*** 元素个数*/
private transient int size = 0;/*** 修改次数*/
private transient int modCount = 0;

6. 构造器

1. TreeMap()：默认构造方法，key必须实现Comparable接口

   public TreeMap() {
         comparator = null;
   }
   

2. TreeMap(Comparator<? super K> comparator)：使用传入的comparator比较两个key的大小

   public TreeMap(Comparator<? super K> comparator) {
         this.comparator = comparator;
   }
   

3. TreeMap(Map<? extends K, ? extends V> m)： key必须实现Comparable接口，把传入map中的所有元素保存到新的TreeMap中

   public TreeMap(Map<? extends K, ? extends V> m) {
         comparator = null;putAll(m);
   }
   

4. TreeMap(SortedMap<K, ? extends V> m)：使用传入map的比较器，并把传入map中的所有元素保存到新的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) {
         }
   }
   

7. 常用方法

1. public V get(Object key)：获取元素，典型的二叉查找树的查找方法。
2. public V put(K key, V value)：插入元素，如果元素在树中存在，则替换value；如果元素不存在，则插入到对应的位置，再平衡树。
3. public V remove(Object key)：删除元素本身比较简单，就是采用二叉树的删除规则。