Java中的集合（七）双列集合顶层接口------Map接口
一、Map接口的简介
通过List接口，我们知道List接口下的集合是单列集合，数据存储是单列的结构。Map接口下是一个键值对（key-value）的映射接口，Map集合中，不能包含重复的键，每个键只能映射一个值（元素），值可以重复，因此可以根据key快速查找value的值。
（一）、Hash(散列/哈希)的概念
1、hash（哈希）
想要清楚Map的数据结构，哈希是基本概念，我们先来看看什么是哈希？
hash翻译为"散列"，也有直接音译为"哈希"，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。这是一种压缩机制，因为散列值所占用的空间远小于输入值所占的空间，不同的输入可能形成相同的散列值，所以不能通过散列值来确定唯一的输入值。简单来说，hash就是将任意长度消息压缩为固定长度消息摘要的函数。
2、散列表
散列表（hash table 也叫哈希表）是通过关键（key，value）key值直接访问的数据结构。它通过将关键key值映射到表中的位置来访问数据，来加快访问速度，这个映射函数叫做散列函数，存储散列值的数组叫做散列表。
3、拉链法解决冲突
既然我们知道，不同的输入值可能产生相同的散列值，那就产生了冲突问题，针对这个问题，可以使用拉链法解决。解决方式为：将不同输入值产生相同散列值的数据存储在一个单链表中。如果选定的散列表长度为n，也就是a[0，1，2…n-1] 的数组，如果产生的散列值为i，也就将所有输入值存储到以a[i]为头指针的链表中。
4、Map的存储方式
Map是（key,value）形式，每次插入数据时都会调用hashCode()和equals()方法对key进行比较，确保key是唯一的，hashCode()会返回int类型的值，以String为例：
二、Map接口的类图结构
通过结构图可以知道：
1、Map接口是双列集合的顶层接口，以键值对（key-value）的形式存储内容；
2、AbstractMap实现Map接口，实现了Map接口的大部分API，其实现类有TreeMap、HashMap和WeakHashMap；
3、SortedMap继承Map接口，主要用于键值对的排序，通过外部比较器（Comparator）排序；
4、NavigableMap继承SortedMap接口，NavigableMap定义一系列的导航方法；如"获取大于/等于某对象的键值对"、“获取小于/等于某对象的键值对”等等；
5、TreeMap是Map接口的实现类，且实现了NavigableMap接口，是有序的键值对；
6、HashMap是Map接口的实现类，在日常开发中最常用，是无序的键值对；
7、WeakHashMap是Map接口的实现类，其键的类型与其他实现类不同，WeakHashMap的键是“弱键”；
8、Hashtable实现了Map接口，且继承Dictionary抽象类，是无序的键值对，但是是线程安全的；
9、Dictionary抽象类封装了Enumeration接口，Hashtable可以通过numeration接口进行遍历。
三、Map接口的常用API
四、Map接口内部定义的Entry接口
Entry是Map接口内部定义的接口，Entry接口也是键值对，通过Map接口的entrySet（）方法获取Entry的键值对集合，从而实现该集合元素对键值对元素的操作。
五、Map接口下的SortedMap接口
SortedMap接口继承Map接口，提供了一个有序的键值对映射。其的排序有两种：自然排序和定制排序；
-
- 自然排序：插入SortedMap的自然排序的元素都必须实现Comparable接口；
- 定制排序：插入SortedMap的定制排序的元素都必须实现Comparator接口。
所以实现了SortedMap接口的自定义类，都应该提供四个构造方法，如TreeMap实现类：
SortedMap常用的API
六、Map接口下的NavigableMap接口
NavigableMap继承SortedMap接口，它是一个有序有导航的键值对映射，具有了为给定搜索目标报告最接近匹配项的导航方法。
NavigableMap分别提供了获取“键”、“键-值对”、“键集”、“键-值对集”的相关方法。
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、获取键-值对的子集。
七、Map接口下的AbstractMap抽象类
AbstractMap是Map接口主要的实现类，以最大限度地减少实现此接口所需的工作。定义为抽象类，程序的自定义类可以继承AbstractMap，可以减少重复的编码。
如果要实现不可修改的映射，只需继承此类并提供 entrySet 方法的实现即可，该方法将返回映射的映射关系 Set 视图。通常，返回的 Set 将依次在 AbstractSet 上实现。此 Set 不支持 add() 或 remove() 方法，其迭代器也不支持 remove() 方法。
如果要实现可修改的映射，必须另外重写此类的 put 方法（否则将抛出 UnsupportedOperationException），entrySet().iterator() 返回的迭代器也必须另外实现其 remove 方法。
八、Dictionary抽象类
注意：此类已过时。 新的实现应该实现Map接口，而不是扩展这个类。
此类中的API都是抽象方法，由子类实现
九、Enumeration接口
Enumeration（枚举）接口的作用和Iterator类似，只提供了遍历Vector和Hashtable类型集合元素的功能，不支持元素的移除操作。
Enumeration接口定义了从一个数据结构得到连续数据的手段。
Enumeration接口提供了一套标准的方法，由于Enumeration是一个接口，它的角色局限于为数据结构提供方法协议。
注意：该接口的功能由Iterator接口复制。 此外，Iterator还添加了一个可选的删除操作，并具有较短的方法名称。 新的实现应该考虑使用迭代器优先于枚举。
