一、Map 整体结构
1.1 类继承结构
1.2 实现类简介
Map是一种把键对象和值对象映射的集合，是一个顶层接口，定义了Map的基本操作。它的每一个元素都包含一对键对象和值对象。 Map没有继承Collection接口。
- AbstractMap：实现了Map接口的抽象类。Map的基本实现，其他Map的实现类可以通过继承AbstractMap来减少编码量。
- SortedMap：继承Map。保证按照键的升序排列的映射，对entrySet、keySet和values方法返回的结果进行迭代时，顺序就会反映出来。
- NavigableMap：继承SortedMap，含有返回特定条件最近匹配的导航方法。
- HashMap：Map接口基于哈希表的实现，是使用频率最高的用于键值对处理的数据类型。它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，特点是访问速度快，遍历顺序不确定，线程不安全，最多允许一个key为null，允许多个value为null。可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap类。
- HashTable：Hashtable和HashMap从存储结构和实现来讲有很多相似之处，不同的是它继承自Dictionary类，而且是线程安全的，另外Hashtable不允许key和value为null。并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以使用HashMap，需要线程安全的场合可以使用ConcurrentHashMap。
- LinkedHashMap： LinkedHashMap继承了HashMap，是Map接口的哈希表和链表实现。它维护着一个双重链表。此链表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
- WeakedHashMap： 以弱键实现的基于哈希表的Map。在WeakHashMap中，当某个键不再正常使用时，将自动移除其条目。
- TreeMap ： Map接口基于红黑树的实现。
二、源码分析
2.1 注释
Map是一种以键值对形式存储的对象。Map中不能包含重复的keys，每个key最多只能对应一个value。
此接口代替了Dictionary类，此类是一个完全的抽象类。
Map接口提供了三种集合视图，分别是键集，值集，键值集。Map的顺序定义在map集合视图的迭代器中。一些实现如TreeMap，保证了特定的顺序；其他实现如HashMap，则不保证。
注意：当使用可变对象作为map的keys的时候，要注意重写equals和hashCode方法。
所有的通用map实现类都应该提供2种标准的构造函数：一个void(无参数)的构造函数，此构造函数创建一个空map；和一个参数类型为Map的单参数的构造函数，允许以与参数相同的键值对创建一个新的map。实际上，后一种构造方法允许用户复制任何一种map。
一些map可能会对它的kyes和values更加严格，比如对于Null值。
2.2 定义
public interface Map<K,V>
此接口为顶层接口。
2.3 域
Map接口并没有自己的域变量。
查询操作（Query Operations）
/**
* 返回map中键值对的数量
* 如果map中包含的元素大于Integer.MAX_VALUE，那么返回Integer.MAX_VALUE
*
* @return the number of key-value mappings in this map
*/
int size();
/**
* map中有键值对则返回true，没有则返回false
*/
boolean isEmpty();
/**
* 有指定的key则返回true
*/
boolean containsKey(Object key);
/**
* 有一个或以上的keys对应指定的value则返回true
*/
boolean containsValue(Object value);
/**
* 有该key则返回对应的value，没有则返回null
*/
V get(Object key);
2.5 修改操作（Modification Operations）
/**
* 在map中添加新的键值对，如果指定key已经存在，则新的value将取代旧value
*/
V put(K key, V value);
/**
* 删除map中的以指定的key组成的键值对，并返回对应的value
* 如果没有该key，则返回null
*/
V remove(Object key);
2.6 块操作（Bulk Operations）
/**
* 将指定的map全部拷贝到调用该函数的map中
* 如果在这个过程中，指定的map发生修改，那么最后拷贝的结果将是不确定的；
* 即不确定拷贝的是修改前还是修改后的。
*/
void putAll(Map<? extends K, ? extends V> m);
/**
* 删除此map中所有的键值对，结束后map为空
*/
void clear();
2.7 视图
/**
* 返回该map中所有keys的一个视图（属性为Set）。此Set被该map支持，因此改变map也会改变此Set，反之亦然。
* 如果在迭代器使用此set时,map被修改，那么迭代器的结果是不能预料的（迭代器通过自己的remove方法是安全的）。
* 此set支持元素删除，通过<tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>完成
* 此set不支持<tt>add</tt> or <tt>addAll</tt>操作
*/
Set<K> keySet();
/**
* 返回该map所有values的一个视图（属性为Collection，表明可重复）此Collection被该map支持，因此改变map也会改变此Set，反之亦然。
* 如果在迭代器使用此Collection时,map被修改，那么迭代器的结果是不能预料的（迭代器通过自己的remove方法是安全的）。
* 支持元素删除，通过<tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>完成
* 不支持<tt>add</tt> or <tt>addAll</tt>操作
*/
Collection<V> values();
/**
* 返回该map中所有键值对的一个视图（属性为Set）。此Set被该map支持，因此改变map也会改变此Set，反之亦然。
* 如果在迭代器使用此set时,map被修改，那么迭代器的结果是不能预料的（迭代器通过自己的remove方法是安全的）。
* 此set支持元素删除，通过<tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>完成
* 此set不支持<tt>add</tt> or <tt>addAll</tt>操作
*/
Set<Map.Entry<K, V>> entrySet();
2.8 Comparison and hashing
// Comparison and hashing
boolean equals(Object o);
int hashCode();
2.9 默认方法(实际中大部分方法很少用到)
// Defaultable methods
/**
* map中有指定的key时返回对应的value,否则返回默认值defaultValue
* @since 1.8
*/
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
/**
* 对此映射中的每个条目执行给定的操作，直到所有条目都被处理或操作引发异常。
* action和BiConsumer是什么？
* forEach的使用场景是什么？
* @since 1.8
*/
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) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
/**
* 将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都被处理或该函数抛出异常。
* BiFunction是啥，使用场景是啥？
* @since 1.8
*/
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) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
/**
* 仅当指定的密钥当前映射到指定的值时删除该条目
* @since 1.8
*/
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;
}
/**
* 仅当当前映射到指定的值时，才能替换指定键的条目
* @since 1.8
*/
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;
}
/**
* 只有当目标映射到某个值时，才能替换指定键的条目。
* @since 1.8
*/
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
/**
* 如果指定的键尚未与值相关联（或映射到 null ），则尝试使用给定的映射函数计算其值，
* 并将其输入到此映射中，除非 null 。
* @since 1.8
*/
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;
}
}
/**
* 尝试计算指定键的映射及其当前映射的值（如果没有当前映射， null ）。
* @since 1.8
*/
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) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
/**
* 如果指定的键尚未与值相关联或与null相关联，则将其与给定的非空值相关联。
* @since 1.8
*/
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;
}
2.10 内部接口
Interface Entry<K, V>{}
/**
* map的entry(entry可翻译为条目)，Map.entrySet()方法返回的就是一个map的集合视图，其元素就是这个entry
* 集合视图的迭代器是获得一个map的entry引用的唯一方式。
* 只有在迭代器中，这些Map.Entry对象是可用的
*
* @see Map#entrySet()
* @since 1.2
*/
interface Entry<K,V> {
/**
* Returns the key corresponding to this entry.
*
*/
K getKey();
/**
* 返回此entry的value。如果键值对已经被remove了，那么此调用的结果undefined（未定义）
*/
V getValue();
/**
* Replaces the value corresponding to this entry with the specified
* value (optional operation). (Writes through to the map.) The
* behavior of this call is undefined if the mapping has already been
* removed from the map (by the iterator's <tt>remove</tt> operation).
*/
V setValue(V value);
/**
* 判断两个键值对是否相等
*/
boolean equals(Object o);
/**
* Returns the hash code value for this map entry. The hash code
* of a map entry <tt>e</tt> is defined to be: <pre>
* (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
* (e.getValue()==null ? 0 : e.getValue().hashCode())
*/
int hashCode();
/**
* 按key排列
* @since 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());
}
/**
* 按value排列
* @since 1.8
*/
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());
}
/**
* 根据key用指定的比较器排序
* @since 1.8
*/
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());
}
/**
* 根据value用指定的比较器排序
* @since 1.8
*/
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());
}
}
三、AbstractMap
3.1 注释
/**
- 1、此类提供了Map接口的基本实现，使得实现Map接口变得更简单
- 2、为了实现一个不可修改的map，开发者只需要去继承这个类，并提供entrySet的实现
- Typically, the returned set will, in turn, be implemented atop AbstractSet.
- This set should not support the add or remove methods, and its iterator
- should not support the remove method.
- 3、为了实现一个可修改的map, 开发者必须另外覆盖此类的put方法
- 并且，entrySet().iterator()返回的iterator必须额外实现它的remove方法
- 4、此类的中非抽象方法必要时可以被覆盖
- @since 1.2
*/
3.2 核心方法
AbstrctMap的源码就是提供了Map接口的一些简单实现。主要是利用Map中三种视图：
Set<Entry<K,V>> entrySet()
Set<K> keySet;
Collection<V> values;
再结合“Set”或者“Collection”本身的迭代器或一些域变量（size）进行实现。如果有疑问，可以简单对照看一看即可。
四、SortedMap
SortedMap也是一个接口，继承自Map接口，Sorted表示它是一个有序的键值映射。
SortedMap的排序方式有两种：自然排序和指定比较器排序。插入有序的SortedMap的所有元素都必须实现Comparable接口（或被指定的比较器所接受）。
4.1 核心方法
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();