文章导读
【Map接口同Set接口和List接口有所不同，Map接口是通过键值对来存储元素的，存储元素时需要提供一个键值（Key），键值不能重复，查询元素时也需要提供键值（Key），类似于地址中的街道门牌号，通过门牌号确定唯一的地址。Map接口有多个实现类，分别是HashMap、LinkedHashMap、TreeMap、Propeties。本文重点介绍HashMap、LinkedHashMap、TreeMap三个类。】
文章分成三个小节。第一小节讲述Map接口及HashMap类；第二小节讲述LinkedHashMap，LinkedHashMap和HashMap的主要区别在于元素的有序性；第三小节讲述树结构TreeMap。
第一小节 Map接口及HashMap类
HashMap是最常用的Map接口实现类，HashMap根据键的Hash值计算元素的存储位置，并将Hash值和元素同时存储起来，程序访问该存储元素时，只需要提供Hash值就可以，其访问速速非常高效。
HashMap同HashSet类似，也是根据元素的哈希码（Hash值）进行存储的，HashMap根据每个存储对象的哈希码，用固定的算法算出它的存储索引，把存储元素存放在一个叫做散列表的相应位置中。当后加入元素的哈希码与已经加入的元素哈希码相同时，HashMap就会创建一个链表，将相同哈希码的元素存入一个链表，并将该链表的头指针存储到哈希码对应的数组元素中。HashMap存储结构如下图所示：
图1 HashMap存储结构
哈希码（Hash值）计算方式通过Object类的hashcode获取，代码如下:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}代码通过hashcode的高16位实现，能保证散列表的长度比较小的时候，保证高低bit都参与到hash计算中，不会有大的开销。
需要注意的是，虽然HashMap和HashSet实现的接口规范不同，但是它们底层的 Hash 存储机制完全相同。实际上，HashSet 本身就是在 HashMap 的基础上实现的。
HashMap在实际编程中，应用非常广泛。例如，在员工管理信息系统中，需要按照员工号来存储大量的员工信息，并且要考虑查询速度。这时就可以使用HashMap作为员工信息的存储结构，将员工号作为键值，员工对象作为值来存储到HashMap中。
下面给出一个具体应用实例，说明HashMap的用法。
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
System.out.println("请输入一句英语，单词间用空格隔开：");
String sentence = sc.nextLine();
String[] arr = sentence.split(" ");
// 键代表着单词，值代表着次数
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < arr.length; i++) {
if (!map.containsKey(arr[i])) {
map.put(arr[i], 1);
} else {
// 说明map中，存在该元素
int num = map.get(arr[i]);
map.put(arr[i], ++num);
}
}
System.out.println("统计单词出现的个数，结果如下：");
Set<String> set = map.keySet();
for (Iterator<String> iterator = set.iterator(); iterator.hasNext();) {
String key = iterator.next();
Integer value = map.get(key);
System.out.println(key + "=" + value);
}
}
}该程序用于简单统计各个单词出现的次数。因为HashMap存储的是键值对，因此不能用迭代器、foreach等方法遍历HashMap。如果需要遍历HashMap，可以通过HashMap的keySet方法返回HashMap中key值的集合，通过遍历Key值集合读取HashMap中的元素。程序输出结果如下图所示：
图2 HashMapTest输出结果
第二小节 认识LinkedHashMap类
前面介绍了HashMap集合类，了解了HashMap的存储结构，HashMap所存储的元素是无序的，遍历HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。在实际编程应用中一些场景可能需要有序存储，因此需要用到一个可以保持插入顺序的Map类。这个类就是LinkedHashMap类，LinkedHashMap类是HashMap的子类，它可以依照插入的顺序来存储元素，LinkedHashMap的存储结构采用了双重链表，因此元素的增加、修改和删除效率都比较高。
1、LinkedHashMap 的存储结构
LinkedHashMap的存储结构如下图所示：
图3 LinkedHashMap存储结构图
从上图可以看出，LinkedHashMap和HashMap的存储结构基本相同，都是数组加链表。唯一不同的是，链表结点有两个指针，分别是before和after，指向该结点的直接后继和直接前驱，再通过双向链表表头结点，就可以实现从双向链表中的任意一个结点开始，很方便地访问它的前驱结点和后继结点。
LinkedHashMap采用的hash算法和HashMap相同，但它扩展了Entry（结点，用于存储key和value）。LinkedHashMap中的Entry增加了 before 和 after两个指针，用于维护双向链表。图中的next指针用于维护Map中各个Entry的连接顺序，before、after用于维护Entry插入的先后顺序的。
2、LinkedHashMap 的构造函数
LinkedHashMap 提供了五个构造函数，它们都是在HashMap的构造函数的基础上实现的，分别如下：
● LinkedHashMap()
用于构造默认存储元素容量为16、负载因子为0.75的LinkedHashMap对象。其中容量为可存储元素的初始长度，负载因子表示散列表空间的使用程度，负载因子越大则散列表就能容纳更多的元素，存储的元素过多，索引效率就会降低。
● LinkedHashMap(int initialCapacity, float loadFactor)
用于构造指定初始容量和负载因子的LinkedHashMap对象。
● LinkedHashMap(int initialCapacity)
用于构造指定初始容量，负载因子默认为0.75的LinkedHashMap对象。
● LinkedHashMap(Map<? extends K, ? extends V> m)
用于构造指定具有相同Map具有相同映射的LinkedHashMap对象，该对象初始容量依赖于传入Map的容量，负载因子默认为0.75。
● LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
用于构造指定容量、负载因子、迭代顺序的LinkedHashMap对象。
注意：初始容量 和负载因子是影响LinkedHashMap性能的两个重要参数。
3、LinkedHashMap 的存储与修改
同HashMap一样，LinkedHashMap提供了put方法用于元素的存储与修改。
● put(K key, V value)
该方法用于添加一个Entry（结点，包括key和value）到LinkedHashMap对象，key为与指定值将要关联的键，value为使用指定键关联的值。如果key对应的值已经存在，则将key对应的值修改为value。
存储与修改示例代码如下：
package com.milihua.linkedhashdemo;
import java.util.LinkedHashMap;
public class LinkedHashMapAddDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedHashMap<Integer, String> newmap = new LinkedHashMap();
// 添加元素
newmap.put(1, "tutorials");
newmap.put(2, "point");
newmap.put(3, "is best");
System.out.println("Map value before change: " + newmap);
// 修改key为3的元素
String prevvalue = (String) newmap.put(3, "is great");
// 输出key为3修改前的元素
System.out.println("Returned previous value: " + prevvalue);
System.out.println("Map value after change: " + newmap);
}
}该程序声明了LinkedHashMap对象，其中key为整型，值为String类型。程序首先用put方法添加了key分别为1、2、3，值分别为tutorials、
point、is best的三个Entry，然后再用put方法修改key为3的值。程序输出结果如下图所示：
图4 LinkedHashMapAddDemo输出结果
4、LinkedHashMap 的访问
同HashMap一样，LinkedHashMap提供了get方法用于元素的获取。
● V get(Object key)
该方法用于获取指定key的value，key为与value相关联的键。
访问示例代码如下：
package com.milihua.linkedgetdemo;
import java.util.LinkedHashMap;
public class LinkedHashMapGetDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
// create a new linked hash map
LinkedHashMap<String, String> map = new LinkedHashMap();
//添加结点
map.put("001", "李明");
map.put("002", "赵飞");
map.put("003", "王义");
// 打印map
System.out.println("Map:" + map);
// get key "001"
System.out.println("" + map.get("001"));
// get key "003"
System.out.println("" + map.get("003"));
}
}该程序声明了LinkedHashMap对象，其中key、value均为字符串类型。首先用put方法添加了key分别为001、002、003，值分别为李明、赵飞、王义的三个Entry，然后用get方法获取指定key的值。程序输出结果如下图所示：
图5 LinkedHashMapGetDemo输出结果
5、LinkedHashMap 的遍历
同HashMap相同，LinkedHashMap也不能用迭代器、foreach等方法遍历。如果需要遍历LinkedHashMap，可以通过LinkedHashMap的keySet方法返回HashMap中key值的集合进行遍历。
LinkedHashMap遍历代码如下：
package com.milihua.linkedhashdemo;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LinkedHashMapDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
//创建Map对象
LinkedHashMap<String, String> map = new LinkedHashMap<String,String>();
//给map中添加元素
map.put("邓超", "孙俪");
map.put("李晨", "范冰冰");
map.put("刘德华", "柳岩");
//获取Map中的所有key与value的对应关系
Set<Map.Entry<String,String>> entrySet =map.entrySet();
//遍历Set集合
Iterator<Map.Entry<String,String>> it=entrySet.iterator();
while(it.hasNext()){
//得到每一对对应关系
Map.Entry<String,String> entry = it.next();
//通过每一对对应关系获取对应的key
String key = entry.getKey();
//通过每一对对应关系获取对应的value
String value = entry.getValue();
System.out.println(key+"="+value);
}
}
}程序获取Map集合中，所有的键值对(Entry)对象，并以Set集合形式返回。然后，通过遍历包含键值对(Entry)对象的Set集合，得到每一个键值对(Entry)对象。程序输出结果如下图所示：
图6 LinkedHashMapDemo输出结果
第三小节 认识TreeMap类
LinkedHashMap存储的元素是有序的，可以保持元素的插入顺序，但不能对元素进行自动排序。在一些编程应用场景中，如果在数据的存储过程中，能够自动对数据进行排序，将会极大提高编程效率，程序员无需再为数据排序编写必要的代码。例如，一般大量的数据都被存储在大型数据库中，程序员需要能够按照多个键对索引排序以提供搜索效率。
Map接口有一个重要的实现类TreeMap，TreeMap可以实现存储元素的自动排序。在TreeMap中，键值对之间按键有序，TreeMap的实现基础是平衡二叉树。
1、TreeMap 的存储结构
TreeMap使用的存储结构是平衡二叉树，也称为红黑树。它首先是一棵二叉树，具有二叉树所有的特性，即树中的任何节点的值大于它的左子节点，且小于它的右子节点，如果是一棵左右完全均衡的二叉树，元素的查找效率将获得极大提高。最坏的情况就是一边倒，只有左子树或只有右子树，这样势必会导致二叉树的检索效率大大降低。为了维持二叉树的平衡，程序员们提出了各种实现的算法，其中平衡二叉树就是其中的一种算法。平衡二叉树的数据结构如下图所示：
图7 TreeMap存储结构
2、TreeMap 的构造函数
TreeMap 提供了三个常用的构造函数，说明如下：
● TreeMap()
使用该构造函数，TreeMap中的key按照自然排序进行排列。
● TreeMap(Map<? extends K, ? extends V> copyFrom)
使用该构造函数，用指定的Map填充TreeMap，TreeMap中的key按照自然排序进行排列。
● TreeMap(Comparator<? super K> comparator)
使用该构造函数，指定元素排序所用的比较器，key排列顺序由比较器指定。
2、TreeMap 元素的存取
同HashMap一样，TreeMap提供了get和put方法用于元素的存取。
● put(K key, V value)
该方法用于添加一个Entry（结点，包括key和value）到TreeMap对象，key为与指定值将要关联的键，value为使用指定键关联的值。如果key对应的值已经存在，则将key对应的值修改为value。
● V get(Object key)
该方法用于获取指定key的value，key为与value相关联的键。
TreeMap 元素存取示例代码如下：
package com.milihua.treemapdemo;
import java.util.TreeMap;
public class TreeMapDemo1 {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<Integer, String>();
// 添加元素
map.put(8, "eight");
map.put(6, "six");
map.put(3, "three");
map.put(12, "twelve");
map.put(9, "nine");
map.put(11, "eleven");
System.out.println("输出map:" + map);
// 获取key为3的元素
String value = (String) map.get(3);
System.out.println("key为3的value为: " + value);
// 修改key为3前的元素
map.put(3, "sixteen");
System.out.println("输出修改后的map: " + map);
}
}该程序声明了TreeMap对象。首先用put方法添加了6个Entry结点，然后用get方法获取指定key的值，再用put方法修改指定key的值。程序输出结果如下图所示：
图8 TreeMapDemo1输出结果
从图中输出结果可以看出，TreeMap按照传入的key进行自动排序。
3、TreeMap 的遍历
同HashMap、LinkedHashMap相同，TreeMap也不能用迭代器、foreach等方法遍历。如果需要遍历TreeMap，可以通过TreeMap的keySet方法返回TreeMap中key值的集合进行遍历。
TreeMap遍历代码如下：
package com.milihua.treemapdemo;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapDemo1 {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<Integer, String>();
// 添加元素
map.put(8, "eight");
map.put(6, "six");
map.put(3, "three");
map.put(12, "twelve");
map.put(9, "nine");
map.put(11, "eleven");
System.out.println("输出map:" + map);
// 获取key为3的元素
String value = (String) map.get(3);
System.out.println("key为3的value为: " + value);
// 修改key为3前的元素
map.put(3, "sixteen");
System.out.println("输出修改后的map: " + map);
//获取Map中的所有key与value的对应关系
Set<Entry<Integer, String>> entrySet =map.entrySet();
//遍历Set集合
Iterator<Map.Entry<Integer, String>> it=entrySet.iterator();
while(it.hasNext()){
//得到每一对对应关系
Map.Entry<Integer, String> entry = it.next();
//通过每一对对应关系获取对应的key
Integer key = entry.getKey();
//通过每一对对应关系获取对应的value
String strValue = entry.getValue();
System.out.println(key+"="+value);
}
}
}程序获取TreeMap所有的键值对(Entry)对象，并以Set集合形式返回。然后，通过遍历包含键值对(Entry)对象的Set集合，得到每一个键值对。程序输出结果如下图所示：
图9 遍历TreeMap输出结果
文章小结
1、前面学习过数组，数组是通过下标对其存储的元素进行索引的，因此可以通过下标直接访问数组元素。在Map集合中，存储的元素是通过Key来进行索引的，Key是一个字符串，通过Key可以直接访问Map存储的元素。在Map集合中，索引是Key，存储的元素可以称之为value，key — value就称为键值对。
2、LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序，因此在遍历的时候效率比HashMap要低。不过也有例外情况，当HashMap容量很大，实际存储的数据较少时，遍历起来可能会比LinkedHashMap要慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
一般情况下，在Map 中插入、删除和定位元素，HashMap 是最好的选择。如果需要元素输出的顺序和输入的相同，就需要选择LinkedHashMap了。
3、HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap。HashMap通常比TreeMap效率要高一些，一个是哈希表，一个是二叉树，建议多使用HashMap，在需要排序的Map时才用TreeMap。
思考与练习
1、创建Book和BookTest类，Book类的属性为id（编号），title（书名），并重写toString方法，返回title的值。要求使用HashMap存储多个Book对象，键为Book对象的编号，值为Book对象，遍历HashMap，通过编号获取Book对象，并输出该书的书名。
2、输入英文句子，用TreeMap对英文句子的单词进行排序存储，并遍历TreeMap输出英文单词。