Java 集合系列 08 Map架构

浏览数：46 / 时间：2015年06月08日

java 集合系列目录：

Java 集合系列 01 总体框架

Java 集合系列 02 Collection架构

Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例

Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例

Java 集合系列 05 Vector详细介绍(源码解析)和使用示例

Java 集合系列 06 Stack详细介绍(源码解析)和使用示例

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

Java 集合系列 08 Map架构

概要

前面，我们已经系统的对List进行了学习。接下来，我们先学习Map，然后再学习Set；因为Set的实现类都是基于Map来实现的(如，HashSet是通过HashMap实现的，TreeSet是通过TreeMap实现的)。

首先，我们看看Map架构。

如上图：
(01) Map 是映射接口，Map中存储的内容是键值对(key-value)。
(02) AbstractMap 是继承于Map的抽象类，它实现了Map中的大部分API。其它Map的实现类可以通过继承AbstractMap来减少重复编码。
(03) SortedMap 是继承于Map的接口。SortedMap中的内容是排序的键值对，排序的方法是通过比较器(Comparator)。
(04) NavigableMap 是继承于SortedMap的接口。相比于SortedMap，NavigableMap有一系列的导航方法；如"获取大于/等于某对象的键值对"、“获取小于/等于某对象的键值对”等等。
(05) TreeMap 继承于AbstractMap，且实现了NavigableMap接口；因此，TreeMap中的内容是“有序的键值对”！
(06) HashMap 继承于AbstractMap，但没实现NavigableMap接口；因此，HashMap的内容是“键值对，但不保证次序”！
(07) Hashtable 虽然不是继承于AbstractMap，但它继承于Dictionary(Dictionary也是键值对的接口)，而且也实现Map接口；因此，Hashtable的内容也是“键值对，也不保证次序”。但和HashMap相比，Hashtable是线程安全的，而且它支持通过Enumeration去遍历。
(08) WeakHashMap 继承于AbstractMap。它和HashMap的键类型不同，WeakHashMap的键是“弱键”。

主要内容如下：

1 Map

Map的定义如下：

public interface Map<K,V>

Map 是一个键值对(key-value)映射接口。Map映射中不能包含重复的键；每个键最多只能映射到一个值。
Map 接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。
Map 映射顺序。有些实现类，可以明确保证其顺序，如 TreeMap；另一些映射实现则不保证顺序，如 HashMap 类。
Map 的实现类应该提供2个“标准的”构造方法：第一个，void（无参数）构造方法，用于创建空映射；第二个，带有单个 Map 类型参数的构造方法，用于创建一个与其参数具有相同键-值映射关系的新映射。实际上，后一个构造方法允许用户复制任意映射，生成所需类的一个等价映射。尽管无法强制执行此建议（因为接口不能包含构造方法），但是 JDK 中所有通用的映射实现都遵从它。

Map的API

 void clear() 
          从此映射中移除所有映射关系（可选操作）。 
 boolean containsKey(Object key) 
          如果此映射包含指定键的映射关系，则返回 true。 
 boolean containsValue(Object value) 
          如果此映射将一个或多个键映射到指定值，则返回 true。 
 Set<Map.Entry<K,V>> entrySet() 
          返回此映射中包含的映射关系的 Set 视图。 
 boolean equals(Object o) 
          比较指定的对象与此映射是否相等。 
 V get(Object key) 
          返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 
 int hashCode() 
          返回此映射的哈希码值。 
 boolean isEmpty() 
          如果此映射未包含键-值映射关系，则返回 true。 
 Set<K> keySet() 
          返回此映射中包含的键的 Set 视图。 
 V put(K key, V value) 
          将指定的值与此映射中的指定键关联（可选操作）。 
 void putAll(Map<? extends K,? extends V> m) 
          从指定映射中将所有映射关系复制到此映射中（可选操作）。 
 V remove(Object key) 
          如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。 
 int size() 
          返回此映射中的键-值映射关系数。 
 Collection<V> values() 
          返回此映射中包含的值的 Collection 视图。

说明：
(01) Map提供接口分别用于返回键集、值集或键-值映射关系集。
entrySet()用于返回键-值集的Set集合
keySet()用于返回键集的Set集合
values()用户返回值集的Collection集合
因为Map中不能包含重复的键；每个键最多只能映射到一个值。所以，键-值集、键集都是Set，值集时Collection。

(02) Map提供了“键-值对”、“根据键获取值”、“删除键”、“获取容量大小”等方法。

2 Map.Entry

Map.Entry的定义如下：

Map.Entry的定义如下：

interface Entry<K,V> { }

Map.Entry是Map中内部的一个接口，Map.Entry是键值对，Map通过 entrySet() 获取Map.Entry的键值对集合，从而通过该集合实现对键值对的操作。

Map.Entry的API

boolean equals(Object o) 
          比较指定对象与此项的相等性。 
 K getKey() 
          返回与此项对应的键。 
 V getValue() 
          返回与此项对应的值。 
 int hashCode() 
          返回此映射项的哈希码值。 
 V setValue(V value) 
          用指定的值替换与此项对应的值（可选操作）。

3 AbstractMap

AbstractMap的定义如下：

public abstract class AbstractMap<K,V> implements Map<K,V> {}

AbstractMap类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作。
要实现不可修改的映射，编程人员只需扩展此类并提供 entrySet 方法的实现即可，该方法将返回映射的映射关系 set 视图。通常，返回的 set 将依次在 AbstractSet 上实现。此 set 不支持 add() 或 remove() 方法，其迭代器也不支持 remove() 方法。

要实现可修改的映射，编程人员必须另外重写此类的 put 方法（否则将抛出 UnsupportedOperationException），entrySet().iterator() 返回的迭代器也必须另外实现其 remove 方法。

/**
 * AbstractMap
 * @ClassName: map_test_1
 * @author Xingle
 * @date 2014-5-30 上午11:07:33
 */
public class map_test_1 extends AbstractMap<Object, Object>{
    public static void main(String[] args){
        
    }

    /**
     * 
     * @Description: 
     * @return
     * @author xingle
     * @data 2014-5-30 下午2:23:34
     */
    @Override
    public Set<java.util.Map.Entry<Object, Object>> entrySet() {
        return null;
    }

}

AbstractMap的API

 void clear() 
          从此映射中移除所有映射关系（可选操作）。 
protected  Object clone() 
          返回此 AbstractMap 实例的浅表副本：不复制键和值本身。 
 boolean containsKey(Object key) 
          如果此映射包含指定键的映射关系，则返回 true。 
 boolean containsValue(Object value) 
          如果此映射将一个或多个键映射到指定值，则返回 true。 
abstract  Set<Map.Entry<K,V>> entrySet() 
          返回此映射中包含的映射关系的 Set 视图。 
 boolean equals(Object o) 
          比较指定对象与此映射的相等性。 
 V get(Object key) 
          返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 
 int hashCode() 
          返回此映射的哈希码值。 
 boolean isEmpty() 
          如果此映射未包含键-值映射关系，则返回 true。 
 Set<K> keySet() 
          返回此映射中包含的键的 Set 视图。 
 V put(K key, V value) 
          将指定的值与此映射中的指定键关联（可选操作）。 
 void putAll(Map<? extends K,? extends V> m) 
          从指定映射中将所有映射关系复制到此映射中（可选操作）。 
 V remove(Object key) 
          如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。 
 int size() 
          返回此映射中的键-值映射关系数。 
 String toString() 
          返回此映射的字符串表示形式。 
 Collection<V> values() 
          返回此映射中包含的值的 Collection 视图。

4 SortedMap

SortedMap的定义如下：

public interface SortedMap<K,V> extends Map<K,V> { }

SortedMap是一个继承于Map接口的接口。它是一个有序的SortedMap键值映射。
SortedMap的排序方式有两种：自然排序 或者 用户指定比较器。插入有序 SortedMap 的所有元素都必须实现 Comparable 接口（或者被指定的比较器所接受）。

另外，所有SortedMap 实现类都应该提供 4 个“标准”构造方法：
(01) void（无参数）构造方法，它创建一个空的有序映射，按照键的自然顺序进行排序。
(02) 带有一个 Comparator 类型参数的构造方法，它创建一个空的有序映射，根据指定的比较器进行排序。
(03) 带有一个 Map 类型参数的构造方法，它创建一个新的有序映射，其键-值映射关系与参数相同，按照键的自然顺序进行排序。
(04) 带有一个 SortedMap 类型参数的构造方法，它创建一个新的有序映射，其键-值映射关系和排序方法与输入的有序映射相同。无法保证强制实施此建议，因为接口不能包含构造方法。

SortedMap的API

 Comparator<? super K> comparator() 
          返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。 
 Set<Map.Entry<K,V>> entrySet() 
          返回在此映射中包含的映射关系的 Set 视图。 
 K firstKey() 
          返回此映射中当前第一个（最低）键。 
 SortedMap<K,V> headMap(K toKey) 
          返回此映射的部分视图，其键值严格小于 toKey。 
 Set<K> keySet() 
          返回在此映射中所包含键的 Set 视图。 
 K lastKey() 
          返回映射中当前最后一个（最高）键。 
 SortedMap<K,V> subMap(K fromKey, K toKey) 
          返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。 
 SortedMap<K,V> tailMap(K fromKey) 
          返回此映射的部分视图，其键大于等于 fromKey。 
 Collection<V> values() 
          返回在此映射中所包含值的 Collection 视图。

从接口 java.util.Map 继承的方法 
clear, containsKey, containsValue, equals, get, hashCode, isEmpty, put, putAll, remove, size

5 NavigableMap

NavigableMap的定义如下：

public interface NavigableMap<K,V> extends SortedMap<K,V> { }

NavigableMap是继承于SortedMap的接口。它是一个可导航的键-值对集合，具有了为给定搜索目标报告最接近匹配项的导航方法。
NavigableMap分别提供了获取“键”、“键-值对”、“键集”、“键-值对集”的相关方法。

NavigableMap的API

 Map.Entry<K,V> ceilingEntry(K key) 
          返回一个键-值映射关系，它与大于等于给定键的最小键关联；如果不存在这样的键，则返回 null。 
 K ceilingKey(K key) 
          返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。 
 NavigableSet<K> descendingKeySet() 
          返回此映射中所包含键的逆序 NavigableSet 视图。 
 NavigableMap<K,V> descendingMap() 
          返回此映射中所包含映射关系的逆序视图。 
 Map.Entry<K,V> firstEntry() 
          返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。 
 Map.Entry<K,V> floorEntry(K key) 
          返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null。 
 K floorKey(K key) 
          返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。 
 SortedMap<K,V> headMap(K toKey) 
          返回此映射的部分视图，其键值严格小于 toKey。 
 NavigableMap<K,V> headMap(K toKey, boolean inclusive) 
          返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。 
 Map.Entry<K,V> higherEntry(K key) 
          返回一个键-值映射关系，它与严格大于给定键的最小键关联；如果不存在这样的键，则返回 null。 
 K higherKey(K key) 
          返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。 
 Map.Entry<K,V> lastEntry() 
          返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。 
 Map.Entry<K,V> lowerEntry(K key) 
          返回一个键-值映射关系，它与严格小于给定键的最大键关联；如果不存在这样的键，则返回 null。 
 K lowerKey(K key) 
          返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。 
 NavigableSet<K> navigableKeySet() 
          返回此映射中所包含键的 NavigableSet 视图。 
 Map.Entry<K,V> pollFirstEntry() 
          移除并返回与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。 
 Map.Entry<K,V> pollLastEntry() 
          移除并返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。 
 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 
          返回此映射的部分视图，其键的范围从 fromKey 到 toKey。 
 SortedMap<K,V> subMap(K fromKey, K toKey) 
          返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。 
 SortedMap<K,V> tailMap(K fromKey) 
          返回此映射的部分视图，其键大于等于 fromKey。 
 NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) 
          返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。

从接口 java.util.SortedMap 继承的方法 
comparator, entrySet, firstKey, keySet, lastKey, values

从接口 java.util.Map 继承的方法 
clear, containsKey, containsValue, equals, get, hashCode, isEmpty, put, putAll, remove, size

说明：

NavigableMap除了继承SortedMap的特性外，它的提供的功能可以分为4类：
第1类，提供操作键-值对的方法。
lowerEntry、floorEntry、ceilingEntry 和 higherEntry 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象。
firstEntry、pollFirstEntry、lastEntry 和 pollLastEntry 方法，它们返回和/或移除最小和最大的映射关系（如果存在），否则返回 null。
第2类，提供操作键的方法。这个和第1类比较类似
lowerKey、floorKey、ceilingKey 和 higherKey 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键。
第3类，获取键集。
navigableKeySet、descendingKeySet分别获取正序/反序的键集。
第4类，获取键-值对的子集。

6 Dictionary

Dictionary的定义如下：

public abstract class Dictionary<K,V> {}

NavigableMap是JDK 1.0定义的键值对的接口，它也包括了操作键值对的基本函数。

Dictionary的API

abstract  Enumeration<V> elements() 
          返回此 dictionary 中值的枚举。 
abstract  V get(Object key) 
          返回此 dictionary 中该键所映射到的值。 
abstract  boolean isEmpty() 
          测试此 dictionary 是否不存在从键到值的映射。 
abstract  Enumeration<K> keys() 
          返回此 dictionary 中的键的枚举。 
abstract  V put(K key, V value) 
          将指定 key 映射到此 dictionary 中指定 value。 
abstract  V remove(Object key) 
          从此 dictionary 中移除 key （及其相应的 value）。 
abstract  int size() 
          返回此 dictionary 中条目（不同键）的数量。