在Java语言规范中，Map作为Java集合框架中的一员，提供了对同类型数据进行存储、插入、删除和查找等需求的实现过程。其实现机制和特点使得Map是一个无序的（部分实现可以保证顺序），不可存储相同key的数据结构。本文演示代码段的执行环境基于JDK版本1.7。
概述
Map是Java集合框架体系中的成员之一，和Collection相互独立且两者地位平等。Map本身只是一个接口定义，其定义了对Map进行操作的方法API，且所有的map实现类都会实现Map接口定义的方法。
Map是一个保存键值对映射的数据结构，map不允许维护重复的key，且每个key最多只能映射一个value。Map接口完全取代了抽象类Dictionary类。Map提供了三种浏览集合内数据的方式：键集合、值集合和键值对集合。像TreeMap这样的实现类可以保证元素遍历的顺序，而像HashMap这样的实现类则无法保证元素遍历的顺序，也就是说其是一个无序结构。需要注意的是，Map的key如果存储的是可变的对象，那么由于equals()方法的影响无法保证根据可变对象可以正确的存储和获取Map集合中的元素。除此之外，也不允许map集合以其自身作为key存储到map集合中（equals()和hashCode()方法无法保证）。
通用的map实现需要提供两种标准的构造器：一个是无参构造器，用来构建一个空map集合。另一个是只含有一个以map作为参数的构造器，这个构造方法允许用户实现map复制。
有些实现类对维护的key和value值会有一些限制。例如，有的实现禁止null类型的key和value值，有的实现则限制了key的类型。尝试加入key-value映射会抛出NullPointerException或者ClassCastException异常。尝试查找违反规则的key或者value会抛出异常或者直接返回false。
Map接口的常见实现有AbstractMap、HashMap、ConcurrentHashMap、LinkedHashMap、Hashtable、TreeMap，而TreeMap则实现了NavigableMap和SortedMap声明的一系列方法。其结构如图1所示：
关于上述几个具体实现类之间，分别有其适应的应用场景和特点：
- HashMap：
- HashMap是一个key不可重复的集合结构；
- 遍历HashMap时，从底层数组首部依次向后遍历；
- 底层实现依赖于数组，查找元素可以保证常量时间的性能，插入和删除需要的时间和集合存储的键值对数量成比例；
- HashMap需要考虑扩容情况，扩容规则是按照当前容量的两倍进行扩容；
- HashMap不是一个线程安全的集合实现；
- HashMap可以允许key、value为null，如果key为null，那么该键值对会存储在内部数组的第一个下标位置上；
- 加入到HashMap的元素只需要保证hashcode()和equals()方法被实现即可（默认实现或者自定义实现）。不需要实现Comparable或者Comparator接口；
- LinkedHashMap：
- LinkedHashMap是一个有序的，key不可重复的集合结构。其顺序默认为元素插入顺序，但是也具有访问顺序的特性（最近被访问的元素位于集合的尾部位置，即LRU）；
- 底层依赖于链表，查找元素时需要逐个遍历，时间开销和链表长度成比例，元素插入和移除可以保证常量时间内完成；
- LinkedHashMap同样存在扩容过程；
- LinkedHashMap同样也不是一个线程安全的集合实现；
- LinkedHashMap允许key、value为null；
- 加入到LinkedHashMap的元素只需要保证hashcode()和equals()方法被实现即可（默认实现或者自定义实现）。不需要实现Comparable或者Comparator接口；
- Hashtable：
- Hashtable是一个key不可重复的集合；
- 遍历Hashtable时，从底层数组尾部依次向前遍历；
- 底层实现依赖于数组，具体实现和HashMap类似；
- Hashtable需要考虑扩容情况，扩容规则是按照当前容量的两倍与1的和进行扩容；
- Hashtable是HashMap的线程安全版本；
- Hashtable的key和value均不允许为null；
- 加入到Hashtable的元素只需要保证hashcode()和equals()方法被实现即可（默认实现或者自定义实现）。不需要实现Comparable或者Comparator接口；
- TreeMap：
- TreeMap是一个key不可重复的集合；
- 遍历TreeMap的元素时，要么按照自然排序进行遍历（集合内元素实现的Comparable接口），要么按照特定的规则进行遍历（集合内元素实现的Comparator接口）；
- 底层实现依赖于红黑树结构，查找、插入和删除性能都可以达到O($ \lg n $)；
- TreeMap不需要考虑扩容。但是在元素插入后需要重新调整树结构以保持红黑树的性质；
- TreeMap也不是一个线程安全的集合实现；
- TreeMap不允许key为null，但是value可以为null；
- 加入到TreeMap的元素需要实现Comparable或者Comparator接口，否则元素无法正常加入到集合中；
- ConcurrentHashMap：
- ConcurrentHashMap是一个key不可重复的集合；
- 遍历ConcurrentHashMap时，从底层数组尾部依次向前遍历;
- 底层实现依赖于数组，数组元素是Segment实例，每个Segment实例内部又维护了一个HashEntry数组。类似于书本分页设计，一个Segment实例类似于一本书的一页，而Segment实例内部的HashEntry数组类似于每页中的每一行；
- ConcurrentHashMap需要考虑扩容，在扩容时针对的是某个具体的segment实例内部的HashEntry数组进行扩容；
- ConcurrentHashMap是HashMap的另一个线程安全的实现版本；
- ConcurrentHashMap可以允许多个线程同时对集合内的不同元素进行锁定和处理，如果是对同一个键值对实体或者同一个Segment实例内部的键值对实体进行处理，那么依旧存在锁抢占，即同一时刻只有线程可以访问一个键值对实体或者一个特定的segment内部的HashEntry数组；
- 加入到ConcurrentHashMap的元素只需要保证hashcode()和equals()方法被实现即可（默认实现或者自定义实现）。不需要实现Comparable或者Comparator接口；
部分方法
| 方法声明 | 备注 |
|---|---|
| Map.Entry<K,V> lowerEntry(K key) | 返回严格小于key的最大key的键值对映射 |
| K lowerKey(K key) | 返回严格小于key的最大key |
| Map.Entry<K,V> floorEntry(K key) | 返回小于等于key的最大key的键值对映射 |
| K floorKey(K key) | 返回小于等于key的最大key |
| Map.Entry<K,V> ceilingEntry(K key) | 返回大于等于key的最小key的键值对映射 |
| K ceilingKey(K key) | 返回大于等于key的最小key |
| Map.Entry<K,V> higherEntry(K key) | 返回严格大于key的最小key的键值对映射 |
| K higherKey(K key) | 返回严格大于key的最小key |
| Map.Entry<K,V> firstEntry() | 返回当前map集合中key最小的键值对映射 |
| Map.Entry<K,V> lastEntry() | 返回当前map集合中key最大的键值对映射 |
| Map.Entry<K,V> pollFirstEntry() | 取出并返回当前map集合中key最小的键值对映射 |
| Map.Entry<K,V> pollLastEntry() | 取出并返回当前map集合中key最大的键值对映射 |
| NavigableMap<K,V> descendingMap() | 返回当前map集合的一个逆序集合 |
| NavigableMap<K,V> navigableKeySet() | 返回当前map集合的key值集合 |
| NavigableMap<K,V> descendingKeySet() | 返回当前map集合的key值一个逆序集合 |
| NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) | 返回当前map集合中自fromKey到toKey的子集合，由fromInclusive和toInclusive指定是否包含fronKey和toKey |
| NavigableMap<K,V> headMap(K toKey, boolean inclusive) | 返回小于等于toKey的集合，由inclusive指定是否等于toKey |
| NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) | 返回大于等于fromKey的集合，由inclusive指定是否等于fromKey |
| SortedMap<K,V> subMap(K fromKey, K toKey) | 返回当前map集合中自fromKey（包含）到toKey（不包含）的子集合。 |
| SortedMap<K,V> headMap(K toKey) | 返回小于toKey的集合 |
| SortedMap<K,V> tailMap(K fromKey) | 返回大于fromKey的集合 |
涉及基础知识点
- NIL
参考文献
- RUNOOB.COM. Java 集合框架 [E]
- J Steven Perry. 第 10 单元：Java 集合 [E]
- ORACLE. Collections Framework Overview [E]