TreeMap
使用红黑树存储元素,可以保证元素按照key值的大小进行遍历。
其继承关系如下:
![](/Java集合/TreeMap/treeMap.png)
TreeMap
实现了Map
、SortedMap
、NavigableMap
、Cloneable
、Serializable
等接口SortedMap
规定了元素可以按key大小来遍历,定义了获取部分map的方法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//key的比较器
Comparator<? super K> comparator();
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
K firstKey();
K lastKey();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();NavigableMap
是对SortedMap
的增强,定义了获取离目标key最近的元素的方法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41Map.Entry<K,V> lowerEntry(K key);
K lowerKey(K key);
Map.Entry<K,V> floorEntry(K key);
K floorKey(K key);
Map.Entry<K,V> ceilingEntry(K key);
K ceilingKey(K key);
Map.Entry<K,V> higherEntry(K key);
K higherKey(K key);
Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();
Map.Entry<K,V> pollFirstEntry();
Map.Entry<K,V> pollLastEntry();
NavigableMap<K,V> descendingMap();
NavigableSet<K> navigableKeySet();
NavigableSet<K> descendingKeySet();
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
TreeMap
只使用到了红黑树,故它的时间复杂度为O(logn) 回顾下红黑树的特性:
- 每个节点 红色或者黑色
- 根节点是黑色
- 每个叶子节点是黑色(这里的叶子节点是空节点)
- 若一个节点是红色 则它的叶子节点必须是黑色
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
主要属性
1 | public class TreeMap<K,V> |
comparator可以通过构造器传入 或者key实现comparable接口
内部类
1 | static final class Entry<K,V> implements Map.Entry<K,V> { |
构造器
1 | public TreeMap() { |
getObject(Object key)
1 | public V get(Object key) { |
左旋
1 | /** From CLR */ |
右旋
1 | /** From CLR */ |
插入元素
1 | public V put(K key, V value) { |
插入再平衡
1 | private void fixAfterInsertion(Entry<K,V> x) { |
删除元素
1 | public V remove(Object key) { |
删除再平衡
1 | private void fixAfterDeletion(Entry<K,V> x) { |