引子
Map是各类开发中使用频率很高的数据结构，它提供了一种我们在描述事物关系时非常重要的工具----映射。从接口的描述上来看，截止到Java8, JDK为我们提供了三种功能依次进阶的Map，即 Map, SortedMap 和 NavigableMap；考虑到对并发的支持，又有 ConcurrentMap 和 ConcurrentNavigableMap 这两种。其中，Map接口中主要声明支持基于键和值的增删改查方法，以及整体状态函数（长度，是否为空等），基本符合经典数据结构中Map的特性；SortedMap要求所存入的键之间是可以比较大小的，并基于此支持寻找数据结构中的首尾元素，以及所给两键之间的submap等较高级的方法；NavigableMap 则在SortedMap基础上进一步支持了基于键的模糊查找。
在进一步讨论之前，先进一段广告将类图展示如下。
MapFamily.jpg
JDK中最早的Map实现是Dictionary和Hashtable（左下角所示），从1.0版本开始就已经存在。JDK1.2之后，Josh Bloch引入了集合框架，在抽象类AbstractMap的基础上提供了HashMap这一实现方法，后续在1.4及1.5中又加入EnumMap, IdentityHashMap, LinkedHashMap等实现作为补充。
如果将新老两代Map族的扛把子Hashtable和HashMap进行对比，首先可以发现一些细节上的不同：
- Hashtable初始大小为11，扩容时增长为 2 * old + 1，HashMap初始16，保证为2的幂
- HashMap支持null的键或值，Hashtable不支持
- Hashtable直接使用插入元素的hashcode()作为键，HashMap则自己实现了hash方法
此外，一个比较大的区别是JDK1.8在HashMap的节点组织方式中新引入了“数组 + 链表 / 红黑树”的结构，提高了性能（亲儿子既视感）。另一个明显区别是Hashtable是线程安全的，HashMap本身则不支持。为此，集合框架的解决方案是，在java.util.Collections中定义了一些私有类：Synchronized*Map（上图蓝框），并暴露出了工厂方法；这些方法接受Map对象作为入参，将其“包装”升级成一个线程安全的Map对象并返回。如果粗略观察下Hashtable和SynchronizedMap的实现，可以看到他们都是在读写等方法上用synchronized关键字做了修饰，性能较差。因此，JDK1.5在java.util.concurrent包中，提供了ConcurrentMap 和 ConcurrentNavigableMap这样更好的解决方案（绿框）。
源码分析
（concurrent包打算以后再看，目前只分析java.util中的几个接口）
java.util.Map
public interface Map<K,V> {
// 整体状态及属性
int size();
boolean isEmpty();
boolean equals(Object o);
int hashCode();
// 基本读写方法
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
// 批量操作方法
void putAll(Map<? extends K, ? extends V> m);
void clear();
// 三种集合视图（键，值，键值对）
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
// 键值对的基本方法
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
// 对于lambda表达式的支持，讲真这里没太看懂
// 返回值是一个Comparator类对象，可以看作一个函数
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());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// default作为修饰函数的关键字在java8中引入，允许在接口中定义方法的具体实现
// 下面这几个方法将Map的一些基本读写操作组合起来，在一些常见的使用场景中为开发者提供了方便
// 比如在按键查找Map时，经常要判断如果找不到要如何取值，此时直接调用getOrDefault就可以了
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
// 下面这几个方法提供了函数式风格的接口，入参都包含函数对象
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
throw new ConcurrentModificationException(ise);
}
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// 遍历时出现键错误，一般是由于有非同步的并发，因此抛出这个异常
throw new ConcurrentModificationException(ise);
}
}
}
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
if (oldValue != null || containsKey(key)) {
remove(key);
return null;
} else {
return null;
}
} else {
put(key, newValue);
return newValue;
}
}
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}
java.util.SortedMap
// SortedMap适用于键与键之间可以比较大小的情况，并在此基础上提供了一些类似于线性容器的特性
public interface SortedMap<K,V> extends Map<K,V> {
Comparator<? super K> comparator(); // 需要支持基于键的比较函数
// 支持按键获取部分map
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
// 支持对键的边界查询
K firstKey();
K lastKey();
// 这几个方法从返回值，名字，参数列表来看与其父接口Map中的是完全一样的
// 然而作为SortedMap的视图，额外要求所返回的集合都是按键有序的
// 所以从逻辑角度上看，这些方法跟父接口中的又是不一样的
// （不知道我的理解对不对，我觉得这里没必要重新声明）
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
}
java.util.NavigableMap
public interface NavigableMap<K,V> extends SortedMap<K,V> {
// 返回比传入键严格小且最接近的键/键值对
Map.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();
// 返回一个当前map的逆序
// 要求keyset, entryset, valueset都随之逆序
NavigableMap<K,V> descendingMap();
// 支持navigable视图
NavigableSet<K> navigableKeySet();
NavigableSet<K> descendingKeySet();
// 支持查询navigable子图
// 对边界情况的讨论，类似于上面的lower和floor的区别
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);
}
总结
Map所提供的功能：
- 基于键的get, remove; 基于键值对的put
- 基于键和值的查找 containsKey & containsValue
- 基础批量操作 putAll, clear
- 基于键，值，键值对的视图 keySet, values, entrySet
- 常用的复合方法 getOrDefault, putIfAbsent等
- 函数式风格接口，接受Function或子类对象
SortedMap & NavigableMap 额外提供了基于有序键的线性集合方法
