[Java]-Map源码分析-SortedMap-NavigableMap

发表于 | 分类于 | 阅读次数

List特点：元素有放入顺序，元素可重复，用来处理序列

Map特点：元素按键值对存储，无放入顺序. key-value

Set特点：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的），用来处理集

Map接口有三个实现类：HashMap，HashTable，LinkeHashMap，SortedMap有一个实现类：TreeMap。

Map UML:

Map接口

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
41
42
public interface Map<K,V> {
	// 返回当前数据个数
	int size();
	
	// 是否为空
	boolean isEmpty();
	
	// 判断是否包含key，这里用到了key的equals方法，所以key必须实现它
	boolean containsKey(Object key);
	
	// 判断是否有key保存的值是value，这也基于equals方法
	boolean containsValue(Object value);
	
	// 通过key获取对应的value值
	V get(Object key);
	
	// 存入key-value
	V put(K key, V value);
	
	// 移除一个key-value对
	V remove(Object key);
	
	// 从其他Map添加
	void putAll(Map<? extends K, ? extends V> m);
	
	// 清空
	void clear();
	
	// 返回所有的key至Set集合中，因为key是不可重的，Set也是不可重的
	Set<K> keySet();
	
	// 返回所有的values
	Collection<V> values();
	
	// 返回key-value对到Set中
	Set<Map.Entry<K, V>> entrySet();
	
	// 希望我们实现equals和hashCode
	boolean equals(Object o);
	int hashCode();

}

接口entry,用于元素的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
interface Entry<K,V> {
	// 获取对应的key
	K getKey();
	
	// 获取对应的value
	V getValue();
	
	// 替换原有的value
	V setValue(V value);
	
	// 希望我们实现equals和hashCode
	boolean equals(Object o);
	int hashCode();
	
	// 从1.8起，还提供了比较的方法，类似的方法共四个
	public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
	        return (Comparator<Map.Entry<K, V>> & Serializable)
	            (c1, c2) -> c1.getKey().compareTo(c2.getKey());
	}
}

SortedMap 接口

SortedMap储存key有序的数据，要求key支持Comparable,或者可以被指定的Comparator接受.

SortedMap 提供了一些获取子集的方法：

subMap(K fromKey, K toKey) 可以获取某个范围的key的子集，

headMap(K toKey) 获取某个key之前的所有键值对（类型为Map.Entry）

tailMap(K fromKey) 获取某个key之后的所有键值对

firstKey() ，lastKey() 获取第一个或最后一个key（最大或最小）。

values() 方法返回所有value的collection，

keySet() 方法返回所有key的set（不可重复）

entrySet（） 方法返回所有键值对的set

SortedMap提供了获取最大值与最小值的方法，但对于一个已经排序的数据集，除了最大值与最小值之外，我们可以对任何一个元素，找到比它小的值和比它大的值，还可以按照按照原有的顺序倒序排序等。NavigableMap就为我们提供了这些功能。

NavigableMap是SortedMap的子接口，是扩展了的sortedMap，方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象，如果不存在这样的键，则返回 null。

类似地，方法 lowerKey、floorKey、ceilingKey 和 higherKey 只返回关联的键。所有这些方法是为查找条目而不是遍历条目而设计的。