决定在讲解TreeMap的源码之前,先讲解这两个接口
SortedMap和SortedSet接口两个接口jdk1.2就已经提供,扩展的NavigableMap与NavigableSet接口jdk1.6才开始支持。
SortedMap:顾名思义,此接口应该与排序有关,以下是它的一些方法:
Comparator<? super K> comparator(); //可以自定义排序比较器
//按key升序排列,返回子映射,fromKey到toKey,包括fromKey,不包括toKey
SortedMap<K,V> subMap(K fromKey, K toKey);
//按key升序排列,返回子映射,开头到toKey,不包括toKey
SortedMap<K,V> headMap(K toKey);
//按key升序排列,返回子映射,fromKey到末尾,包括fromKey
SortedMap<K,V> tailMap(K fromKey);
//按key升序排列,返回第一个key
K firstKey();
//按key升序排列,返回最后一个key
K lastKey();
//返回key的集合,升序排列
Set<K> keySet();
//返回value的集合,按key升序排列,
Collection<V> values();
//返回Entry的集合,按key升序排列
Set<Map.Entry<K, V>> entrySet();
再看NavigableMap,它继承了SortedMap:
public interface NavigableMap<K,V> extends SortedMap<K,V>
它自己又定义了一些导航方法:
//返回第一个key小于参数的Entry
Map.Entry<K,V> lowerEntry(K key);
//返回第一个key小于参数的key
K lowerKey(K key);
//返回第一个key小于等于参数的Entry
Map.Entry<K,V> floorEntry(K key);
//返回第一个key小于等于参数的key
K floorKey(K key);
//返回第一个key大于等于参数的Entry
Map.Entry<K,V> ceilingEntry(K key);
//返回第一个key大于等于参数的key
K ceilingKey(K key);
//返回第一个key大于参数的Entry
Map.Entry<K,V> higherEntry(K key);
//返回第一个key大于参数的key
K higherKey(K key);
//返回key最小的Entry
Map.Entry<K,V> firstEntry();
//返回key最大的Entry
Map.Entry<K,V> lastEntry();
//删除并返回key最小的Entry
Map.Entry<K,V> pollFirstEntry();
//删除并返回key最大的Entry
Map.Entry<K,V> pollLastEntry();
//返回key降序排列的NavigableMap(视图) 注意是视图,所以对它进行一个remove操作,也会影响到原来的Map的 是同一个引用
NavigableMap<K,V> descendingMap();
//返回key升序排列的NavigableSet
NavigableSet<K> navigableKeySet();
//返回key降序排列的NavigableSet
NavigableSet<K> descendingKeySet();
//返回key升序排列的子映射,设置包含标志
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
//按key升序排列,返回子映射,开头到toKey,设置包含标志
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
//按key升序排列,返回子映射,fromKey到末尾,设置包含标志
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
//同时也继承了SortedMap的【不带包含标志】的子映射方法
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
NavigableMap所有已知实现类:ConcurrentSkipListMap(后面博文会有讲解), TreeMap
NavigableMap扩展了 SortedMap,具有了针对给定搜索目标返回最接近匹配项的导航方法。 方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象,如果不存在这样的键,则返回 null。 类似地,方法 lowerKey、floorKey、ceilingKey 和 higherKey 只返回关联的键。所有这些方法是为查找条目而不是遍历条目而设计的。
descendingMap 方法返回映射的一个视图,该视图表示的所有关系方法和方向方法都是逆向的。升序操作和视图的性能很可能比降序操作和视图的性能要好。
此接口还定义了 firstEntry、pollFirstEntry、lastEntry 和 pollLastEntry 方法,它们返回和/或移除最小和最大的映射关系(如果存在),否则返回 null。
public static void main(String[] args) {
// NavigableMap多态接收TreeMap的实例
NavigableMap<String, Integer> navigatorTreeMap = new TreeMap<String, Integer>() {{
put("aa", 11);
put("bb", 22);
put("cc", 33);
put("dd", 44);
put("ee", 55);
put("ff", 55);
put("gg", 55);
}};
System.out.println(navigatorTreeMap.size());// 7个元素:7
System.out.println(navigatorTreeMap.ceilingKey("cc"));// 返回大于等于cc的最小键:cc
System.out.println(navigatorTreeMap.ceilingEntry("c"));// 返回一个键-值映射关系,它与大于等于cc的最小键关联:cc=33
System.out.println(navigatorTreeMap.firstKey());// 最小键:aa
System.out.println(navigatorTreeMap.firstEntry());// 最小键对应的k-v键值对:aa=11
System.out.println(navigatorTreeMap.floorEntry("c"));// 返回一个键-值映射关系,它与小于等于给定键的最大键关联:bb=22
System.out.println(navigatorTreeMap.floorKey("cc"));// 返回小于等于cc的最大键:cc
System.out.println(navigatorTreeMap.headMap("bb"));// 返回此映射的部分视图,其键值严格小于bb:{aa=11}
System.out.println(navigatorTreeMap.headMap("bb", true));// 同上小于等于(true):{aa=11, bb=22}
System.out.println(navigatorTreeMap.higherEntry("c"));// 返回一个键-值映射关系,它与小于等于给定键的最大键关联:cc=33
System.out.println(navigatorTreeMap.higherKey("cc"));// 返回小于等于cc的最大键:dd
System.out.println(navigatorTreeMap.lastEntry());// 返回一个键-值映射关系,它与小于等于给定键的最大键关联:gg=55
System.out.println(navigatorTreeMap.lastKey());// 返回小于等于cc的最大键:gg
System.out.println(navigatorTreeMap.lowerEntry("c"));// 返回一个键-值映射关系,它与小于等于给定键的最大键关联:bb=22
System.out.println(navigatorTreeMap.lowerKey("cc"));// 返回严格小于cc的最大键:bb
System.out.println(navigatorTreeMap.pollFirstEntry());// 移除并返回与此映射中的最小键关联的键-值映射关系:aa=11
System.out.println(navigatorTreeMap.pollLastEntry());// 移除并返回与此映射中的最大键关联的键-值映射关系:gg=55
System.out.println(navigatorTreeMap.navigableKeySet());// 返回此映射中所包含键的
// NavigableSet 视图。:[bb, cc, dd, ee, ff]
System.out.println(navigatorTreeMap.subMap("aa", true, "dd", true));// 返回部分视图,true表示包括当前元素键值对:{bb=22, cc=33, dd=44}
System.out.println(navigatorTreeMap.subMap("bb", "dd"));// 返回部分视图包括前面的元素,不包括后面的:{bb=22, cc=33}
System.out.println(navigatorTreeMap.tailMap("cc"));// 返回元素大于cc的元素映射视图,包括cc://{cc=33, dd=44, ee=55, ff=55}
System.out.println(navigatorTreeMap.tailMap("cc", false));// 返回元素大于等于cc的元素映射视图:{dd=44, ee=55, ff=55}
//逆序视图
NavigableMap<String, Integer> descendingMap = navigatorTreeMap.descendingMap();
System.out.println(navigatorTreeMap); //原来的Map:
System.out.println(descendingMap);// 返回逆序视图:{gg=55, ff=55, ee=55, dd=44, cc=33, bb=22, aa=11}
//执行一个移除操作后 再看看会不会影响到原来的Map
descendingMap.remove("gg");
System.out.println(navigatorTreeMap); //原来的Map:{aa=11, bb=22, cc=33, dd=44, ee=55, ff=55}
System.out.println(descendingMap);// 返回逆序视图:{ff=55, ee=55, dd=44, cc=33, bb=22, aa=11}
}
之所以可以去到第一个最后一个元素,或者某个元素的前一个,后一个,是因为集合内部的元素是有序的。
TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。
// Red-black mechanics
private static final boolean RED = false;
private static final boolean BLACK = true;
// 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;
}
从上面源码变量的命名中,很容易看出内部实现原理:红黑树。
TreeMap实现了NavigableMap、SortedMap接口(这另个接口下面会有详细介绍) 意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。 另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
(01) TreeMap实现继承于AbstractMap,并且实现了NavigableMap接口。 (02) TreeMap的本质是R-B Tree(红黑树),它包含几个重要的成员变量: root, size, comparator。
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
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);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
每次插入一个数据都会利用比较函数进行key的比较,重新对数据进行排序,保存的数据是有序的,按序取数据也就不足为奇了。