第 26 节 Map集合

Collection每一次都只会保存一个对象，而Map主要是负责保存一对对象的信息。

如果说现在要保存一对关联数据（key=value）的时候，那么如果直接使用Collection就不能直接满足要求，可以使用Map接口实现此类数据的保存，并且Map接口还提供有根据key查找value的功能。

在开发之中，Collection集合保存数据的目的是为了输出，Map集合保存数据的目的是为了进行key的查找。

Map接口简介

Map接口是进行二元对象保存的最大父接口，该接口定义如下：

public interface Map<K, V>

该接口为一个独立的父接口，并且在进行接口对象实例化的时候需要设置Key与Value的类型，也就是说在整体操作的时候需要保存两个内容，在Map接口里面定义有如下的常用方法。

No.	方法名称	类型	描述
1	public V put(K key, V value)	普通	向集合中保存数据
2	public V get(Object key)	普通	根据key查找对应的value数据
3	public Set<Map.Entry<K, V>> entrySet()	普通	将Map集合转化为Set集合
4	public boolean containsKey(Object key)	普通	查询指定的key是否存在
5	public Set keySet()	普通	取出全部的key
6	public V remove(Object key)	普通	根据key删除内容

范例： 观察Map的特点

package com.alpha.demo;
import java.util.HashMap;
import java.util.Map;
public class TestDemo { 
	public static void main(String[] args) throws Exception {
		Map<String, Integer> map = Map.of("one", 1, "two", 2, "one", 101, null, 0);
        System.out.println(map);
	}
}

在Map集合之中数据的保存就是按照key = value的形式存储的，并且使用of()方法操作的时候里面是不允许重复的，如果出现重复则会出现IllegalArgumentException，如果设置的内容为null，则会出现NullPointerException。

对于现在使用的of()方法严格意义上来讲并不是Map集合的标准用法，因为正常的开发之中需要通过Map集合的子类来进行接口对象的实例化，常用的子类：HashMap，Hashtable，TreeMap，linkedHashMap，ConcurrentHashMap。

HashMap

HashMap是Map接口之中最为常见的一个子类，该类的主要特点是无序存储，HashMap类的定义如下：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {}

范例： 观察Map集合的使用

public class Application {
    public static void main(String[] args) throws Exception {
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("one", 101);
        map.put(null, 0);
        map.put("zero", null);
        System.out.println(map.get("one"));
        System.out.println(map.get(null));
        System.out.println(map.get("ten"));
    }
}

以上的操作形式为Map集合使用的标准形式，通过代码可以发现，通过HashMap实例化的Map接口可以针对与key或value保存null的数据，同时即使保存相同的key值也并不会报错，只是将value旧的内容使用新内容替换了。

但是对于put()方法本身是提供返回值的，这个返回值就是在key相同的情况下返回替换掉的旧的value。

范例： 观察put()方法

public class Application {
    public static void main(String[] args) throws Exception {
        Map<String, Integer> map = new HashMap<>();
        System.out.println(map.put("one", 1));
        System.out.println(map.put("one", 101));
    }
}

HashMap在今后的项目开发之中是一定会使用到的，为了深入理解HashMap的底层机制，下面对其源码进行解析：

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {

    /**
     * 默认初始容量 - 必须是2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大容量。如果具有参数的任一构造函数隐式指定较高值，则使用最大容量。
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 在构造函数中未指定时使用的加载因子。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 链表-树 转换阈值
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 在调整大小期间 树-链表 转换阈值
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 最小树容量
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 基础的内部维护节点，单向链表
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        // 全参构造、getter/setter、toString、hashCode、equals 略
    }

    /**
     * 内部维护的二元数组，其大小始终为 2 的幂数
     */
    transient Node<K,V>[] table;

    /**
     * 用作缓存的entrySet
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * key-value映射的数量
     */
    transient int size;

    /**
     * 此HashMap经过结构修改的次数结构修改是指更改HashMap中映射数或以其他方式修改其内部结构（例如，重新散列）的修改。
     */
    transient int modCount;

    /**
     * 下一个要调整大小的值（capacity * load factor）。
     */
    int threshold;

    /**
     * 加载因子
     *
     * @serial
     */
    final float loadFactor;

    /**
     * 使用指定的初始容量和加载因子构造一个空的HashMap。
     *
     * @param  initialCapacity 初始容量
     * @param  loadFactor      加载因子
     * @throws IllegalArgumentException 如果初始容量为负或加载因子为非正数
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 使用指定的初始容量和默认加载因子（0.75）构造一个空的HashMap。
     *
     * @param  initialCapacity 初始容量
     * @throws IllegalArgumentException 初始容量为负
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 使用默认初始容量（16）和默认加载因子（0.75）构造一个空的HashMap。
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * 调用putVal方法实现添加操作
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果在内部维护的tab[hash]为空时，直接将新节点存放到该位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 不为空则进行链表或树的拓展
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 如果容量大于转换阈值，将其转换为树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果容量大于下一个要调整大小的值，扩容至原大小的二倍并且重新散列
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 当链表长度过长时将节点转变为红黑树以提高效率
     * @param <K>
     * @param <V>
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K, V> parent; 
        TreeNode<K, V> left;
        TreeNode<K, V> right;
        TreeNode<K, V> prev;
        boolean red;
    }
}

LinkedHashMap

HashMap本身存储数据是无序的，如果希望添加的元素有序，则可以使用LinkedHashMap：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

由于LinkedHashMap是基于链表的存储，所以在进行操作时数据量不易过大，否则容易造成时间复杂度攀升。

范例： 使用LinkedHashMap

public class Application {
    public static void main(String[] args) throws Exception {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("one", 101);
        map.put(null, 0);
        map.put("zero", null);
        System.out.println(map);
    }
}

Hashtable

在Map接口下还有一个Hashtable的子类，此类是在JDK 1.0的时候提供的，属于最早的Map集合的实现操作，在JDK 1.2的时候让其多实现了一个Map接口，从而保存下来继续使用。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

范例： 使用Hashtable

public class Application { 
	public static void main(String[] args) throws Exception {
		Map<String, Integer> map = new Hashtable<String, Integer>();
		map.put("壹", 1);
		map.put("贰", 2);
		map.put("叁", 3);
		map.put(null, 0); // key的内容为null
		System.out.println(map);
	}
}

发现Hashtable里面对于key和value的数据都不允许设置为null。

程序抛出的异常代码如下：

Exception in thread "main" java.lang.NullPointerException
	at java.util.Hashtable.put(Hashtable.java:464)
	at com.alpha.demo.TestDemo.main(TestDemo.java:10)

查阅JDK源码：

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException();
    }
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

**面试题：**请解释HashMap与Hashtable的区别？

No.	区别	HashMap（90%）	Hashtable（10%）
1	推出时间	JDK 1.2时推出，属于新的类	JDK 1.0时推出，属于旧的类
2	性能	采用异步处理	采用同步处理
3	数据安全	非线程安全	线程安全
4	设置null	允许key或value内容为null	不允许设置null

TreeMap

TreeMap属于有序的Map集合类型，他可以按照key进行排除，所以在使用TreeMap时一定要配合Comparable接口使用。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

范例： 使用TreeMap实现排序

public class Application {
    public static void main(String[] args) throws Exception {
        Map<String, Integer> map = new TreeMap<>();
        map.put("C", 3);
        map.put("B", 2);
        map.put("A", 1);
        System.out.println(map);
    }
}

在使用TreeMap时可以根据key实现数据的排序操作，由于要调用Comparable接口的compareTo()方法进行排序，所以key是不允许为null的，value则允许为null。

Map.Entry接口

之前对HashMap进行源码分析是发现其内部是将键值对保存在了HashMap.Node之中，而HashMap.Node本身实现的是Map.Entry接口。

static class Node<K,V> implements Map.Entry<K,V>

所以可以得出：所有的key-value都被封装在Map.Entry接口之中，Map.Entry接口的定义如下：

public interface Map<K, V> {
    interface Entry<K, V> {}
}

在JDK1.9之后Map提供了一个静态方法可以直接构造Map.Entry：

• 创建Map.Entry对象：static <K,V> Map.Entry<K,V> entry​(K k, V v)；

范例： 创建Map.Entry对象

public class Application {
    public static void main(String[] args) throws Exception {
        Map.Entry<String, Integer> entry = Map.entry("one", 1);
        System.out.println("获取key：" + entry.getKey());
        System.out.println("获取value：" + entry.getValue());
        System.out.println(entry.getClass().getName());
    }
}

可以发现，Map.Entry的主要作用就是作为一个key和value的包装类型使用，而大部分情况下在进行数据存储的时候都会将key和value包装为一个Map.Entry对象进行使用。

使用Iterator输出Map集合

在之前强调过，只要是集合的输出一定要使用Iterator完成，但是在整个Map接口里面并没有定义任何的可以返回Iterator接口对象的方法，所以下面如果要想使用Iterator输出Map集合，首先必须要针对于Map集合与Collection集合保存数据的特点进行分析后才能实现。

每当用户使用put()方法向Map集合里面保存一对数据的时候，实际上所有的数据都会被自动的封装为Map.Entry接口对象。观察Map.Entry接口定义：

public static interface Map.Entry<K,V>

在这个接口里面定义了两个操作：

• 取得key：public K getKey()；

• 取得value：public V getValue()；

在Map接口里面定义有一个将Map集合转化为Set集合的方法：public Set<Map.Entry<K, V>> entrySet()。

Map集合利用Iterator接口输出的步骤：

• 利用Map接口的entrySet()方法将Map集合变为Set集合，里面的泛型是Map.Entry；

• 利用Set集合中的iterator()方法将Set集合进行Iterator输出；

• 每一次Iterator循环取出的都是Map.Entry接口对象，利用此对象进行key与value的取出。

范例： 利用Iterator实现Map接口的输出

public class Application {
	public static void main(String[] args) throws Exception {
		Map<String, Integer> map = new Hashtable<String, Integer>();
		map.put("壹", 1);
		map.put("贰", 2);
		map.put("叁", 3);
		// 将Map集合变为Set集合，目的是为了使用 iterator()方法
		Set<Map.Entry<String, Integer>> set = map.entrySet();
		Iterator<Map.Entry<String, Integer>> iter = set.iterator();
		while (iter.hasNext()) {
			Map.Entry<String, Integer> me = iter.next();
			System.out.println(me.getKey() + " = " + me.getValue());
		}
	}
}

以上的代码会不定期的出现，一定要掌握步骤。

关于Map集合中key的说明

在使用Map接口的时候可以发现，几乎可以使用任意的类型来作为key或value的存在，那么也就表示可以使用自定义的类型作为key。作为key的自定义的类必须要覆写Object类中的hashCode()与equals()两个方法。

在以后使用Map集合的时候，首选的key类型是String，尽量不要去使用其他类型。