学习目标：掌握Map接口及其实现类HashMap、LinkedHashMap、TreeMap类。

Map接口

Set接口存放的元素是无序的且不包含重复的元素，在编程应用中，可以应用Set接口存储不允许重复的元素。List接口存放的元素有序且允许重复，在编程应用中，可以应用List接口存储需要有序排列且允许重复的元素。本课学习Java集合框架的Map接口，Map接口同Set接口和List接口有所不同，Map接口是通过键值对来存储元素的，存储元素时需要提供一个键值（Key），键值不能重复，查询元素时也需要提供键值（Key），类似于地址中的街道门牌号，通过门牌号确定唯一的地址。

Map接口除了继承Collection的接口方法外，还提供了添加键值对、获取键值对等操作。下面分类列出予以说明。

 （1）Map集合添加键值对方法

● V  put(K key, V value)

向当前集合中添加key-value键值对，返回value。如果当前集合已存在key，则会覆盖key对应的value。

（2）判断键和值是否在Map集合

● boolean  containsValue(Object value)

如果在当前集合中有一个或多个key映射到value，则返回true。

● boolean  containsKey (Object key)

如果在当前集合中有key的映射，则返回true。

（3）通过键获取值

● V  get(Object key)

如果当前集合存在指定的key对象，则返回key对应的value。

● Set<K>  keySet()

返回当前集合所有key形成的Set集合。

● Collection<V>  values()

返回当前集合所有value形成的Collection集合。

根据内部数据结构的不同，Map接口有多个实现类，分别是HashMap、LinkedHashMap、TreeMap、Propeties。

HashMap类

HashMap是最常用的Map接口实现类，HashMap根据键的Hash值计算元素的存储位置，并将Hash值和元素同时存储起来，程序访问该存储元素时，只需要提供Hash值就可以，其访问速速非常高效。

HashMap同HashSet类似，也是根据元素的哈希码（Hash值）进行存储的，HashMap根据每个存储对象的哈希码，用固定的算法算出它的存储索引，把存储元素存放在一个叫做散列表的相应位置中。当后加入元素的哈希码与已经加入的元素哈希码相同时，HashMap就会创建一个链表，将相同哈希码的元素存入一个链表，并将该链表的头指针存储到哈希码对应的数组元素中。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中。

案例19：编写一个程序，用于简单统计各个单词出现的次数，key为单词，value为次数，使用HashMap存储。

在PUnit10项目新建map包，在map包下新建HashMapTest1类。代码如下：

package map;
 
import java.util.*;
 
public class HashMapTest1 {
    public static void main(String[] args) {
        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++) {
            // 判断单词（key）是否在Map内
            if (!map.containsKey(arr[i])) {
                // 添加key-value键值对到map
                map.put(arr[i], 1);
            } else {
                // 单词（key）已在Map内
                int num = map.get(arr[i]);
                // 覆盖key对应的value
                map.put(arr[i], ++num);
            }
        }
        System.out.println("统计单词出现的个数，结果如下：");
        // 从map获取所有key
        Set<String> set = map.keySet();
        // 遍历key所在的set集合
        for (Iterator<String> iterator = set.iterator(); iterator.hasNext();) {
            String key = iterator.next();
            // 获取指定key的value
            Integer value = map.get(key);
            System.out.println(key + "=" + value);
        }
 
    }
}

该程序用于简单统计各个单词出现的次数。因为HashMap存储的是键值对，因此不能用迭代器、foreach等方法遍历HashMap。如果需要遍历HashMap，可以通过HashMap的keySet方法返回HashMap中key值的集合，通过遍历Key值集合读取HashMap中的元素。程序输出结果如下图所示：

程序执行结果如下图所示：

在Map集合中，存储的元素是通过Key来进行访问的，Key是一个字符串，通过Key可以直接访问Map存储的元素。在Map集合中，Key和value是映射关系，key—value也称为键值对。

LinkedHashMap类

HashMap所存储的元素是无序的，遍历HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。在实际编程应用中一些场景可能需要有序存储，因此需要用到一个可以保持插入顺序的Map类。这个类就是LinkedHashMap类，LinkedHashMap类是HashMap的子类，它可以依照插入的顺序来存储元素，LinkedHashMap的存储结构采用了双重链表，因此元素的增加、修改和删除效率都比较高。

（1）LinkedHashMap 的存储结构

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。

案例20：建立LinkedHashMapTest1类，实例化LinkedHashMap对象，进行对象元素的添加和修改操作。

在map包下新建LinkedHashMapTest1类。代码如下：

package map;
 
import java.util.LinkedHashMap;
 
public class LinkedHashMapTest1 {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> newmap = new LinkedHashMap<Integer, String>();
        // 添加元素
        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）LinkedHashMap 的访问

同HashMap一样，LinkedHashMap提供了get方法用于元素的获取。

●   V  get(Object key)

该方法用于获取指定key的value，key为与value相关联的键。

案例21：建立LinkedHashMapTest2类，实例化LinkedHashMap对象，进行对象元素的访问操作。

在map包下新建LinkedHashMapTest2类。代码如下：

package map;
 
import java.util.LinkedHashMap;
 
public class LinkedHashMapTest2 {
    public static void main(String[] args) {
        // 实例化LinkedHashMap对象
        LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
        // 添加结点
        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的值。

程序执行结果如下图所示：

LinkedHashMap 的遍历

同HashMap相同，LinkedHashMap也不能用迭代器、foreach等方法遍历。如果需要遍历LinkedHashMap，可以通过LinkedHashMap的keySet方法返回HashMap中key值的集合进行遍历。

案例22：建立LinkedHashMapTest3类，实例化LinkedHashMap对象，进行集合的遍历操作。

在map包下新建LinkedHashMapTest3类。代码如下：

package map;
 
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
 
public class LinkedHashMapTest3 {
    public static void main(String[] args) {
        //实例化LinkedHashMap对象
        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)对象。

程序执行结果如下图所示：

LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序，因此在遍历的时候会比HashMap效率要低。不过也有例外情况，当HashMap容量很大，实际存储的数据较少时，遍历起来可能会比LinkedHashMap要慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

一般情况下，在Map 中插入、删除和定位元素，HashMap 是最好的选择。如果需要元素输出的顺序和输入的相同，就需要选择LinkedHashMap了。

TreeMap类

LinkedHashMap存储的元素是有序的，可以保持元素的插入顺序，但不能对元素进行自动排序。在一些编程应用场景中，如果在数据的存储过程中，能够自动对数据进行排序，将会极大提高编程效率，程序员无需再为数据排序编写必要的代码。例如，一般大量的数据都被存储在大型数据库中，程序员需要能够按照多个键对索引排序以提供搜索效率。

Map接口有一个重要的实现类TreeMap，TreeMap可以实现存储元素的自动排序。在TreeMap中，键值对之间按键有序，TreeMap的实现基础是平衡二叉树。

（1）TreeMap 的存储结构

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相关联的键。

案例23：建立TreeMapTest1类，实例化TreeMap对象，进行对象元素的添加和修改操作。

在map包下新建TreeMapTest1类。代码如下：

package map;
 
import java.util.TreeMap;
 
public class TreeMapTest1 {
    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的值。

程序执行结果如下图所示：

从图中输出结果可以看出，TreeMap按照传入的key进行自动排序。

（3）TreeMap 的遍历

同HashMap、LinkedHashMap相同，TreeMap也不能用迭代器、foreach等方法遍历。如果需要遍历TreeMap，可以通过TreeMap的keySet方法返回TreeMap中key值的集合进行遍历。

案例24：建立TreeMapTest2类，实例化TreeMap对象，进行集合的遍历操作。

在map包下新建TreeMapTest2测试类。代码如下：

package map;
 
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
 
public class TreeMapTest2 {
    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<Map.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集合，得到每一个键值对。

程序执行结果如下图所示：

HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap。HashMap通常比TreeMap效率要高一些，一个是哈希表，一个是二叉树，建议多使用HashMap，在需要排序的Map时候才用TreeMap。