第九十四章 Java标准库－映射(Map)

1 概述

映射(Mapping)，有时又被称为字典(Dictionary)，建立了一种从键域(Key Domain)映射到值域(Value Domain)的数据结构。Java标准库中的java.util.Map接口提供了类似的功能。在一个Map对象中，键对象的值不能重复，并且一个键对象只能映射到一个值对象。

除了键值对映射以外，Map还提供了键集合(Key Collection)、值集合(Value Collection)和键值对集合(Key/Value Pair Collection)，允许开发人员独立的查阅键和值元素。

我们将在下面的内容中一一介绍Map接口提供的功能。Java标准库中包含的、与Map接口相关的类的结构如下图所示。

图一 Map接口的结构图

2 java.util.Map接口

2.1 添加和删除元素

Map接口提供了put()方法，向Map对象提供新的键值队。put()方法接收一对键和值。当键不存在于Map对象时，put()向Map添加新的键值对。如果键已存在于Map对象时，则使用新值对象替换旧值对象。如果不希望发生替换的话，开发人员可以考虑使用putIfAbsent()。putIfAbsent()方法只会添加新元素，不会替换元素。putAll()则是将给定Map对象中的键值对全部添加进当前的Map对象中。

如果只希望替换元素，而不希望添加新元素，则可以使用replace()方法。

Map接口提供了两种remove()方法。当remove()方法只接收一个键对象时，则从Map对象中删除该键值对。当remove()方法接收一对键值时，只有当Map中保存的键值和给定的键值相同时，才删除给定的键值对。

我们可以按照如下方式添加和删除元素。

Map<String, Integer> nameToAgeMap = new HashMap<String, Integer>();
nameToAgeMap.put("James", 18);
nameToAgeMap.put("Amy", 21);

nameToAgeMap.remove("James");

2.2 查阅元素

get()方法能够根据键对象来查询对应的值对象。当键对象不存在时，返回null。keySet()方法返回一个包含所有键对象的集合(Set);values()方法返回一个包含了全部值对象的容器。集合和容器的区别是，开发人员能够快速的查看一个键对象是否在键集合中。这两个方法不一定能保证键或者值的排列顺序。

containsKey()和containsValue()方法能够检查键对象或者值对象是否存在于Map对象中。我们可以按照如下的方式查看或者遍历键对象和值对象。

Map<String, Integer> nameToAgeMap = ...;

// 打印Amy的年龄
if (nameToAgeMap.containsKey("Amy")) {
    System.out.println("Amy is " + nameToAgeMap.get("Amy") + " years old.");
}

// 遍历打印所有的键对象
for (String name: nameToAgeMap.keySet()) {
    System.out.println(name);
}

// 遍历打印所有的年龄
for (Ingeter age: nameToAgeMap.values()) {
    System.out.println(age);
}

// 同时遍历键值对
for (var entry: entrySet()) {
    System.out.println(entry.key() + " is " + entry.value() + " years old.");
}

在使用entrySet()方法获取和遍历键值对时，我们使用了Map.Entry接口。这个接口表示的是一对键对象和值对象。它的常用方法是getKey()和getValue()，用于获取它所包含的键对象和值对象。

2.3 键值对个数

isEmpty()方法检查Map对象中是否包含了键值对。size()方法则返回Map对象中键值对的个数。

Map<String, Integer> nameToAgeMap = ...;

if (!nameToAgeMap.isEmpty()) {
    // 如果不为空，则打印键值对个数
    System.out.println("This map has " + nameToAgeMap.size() + " key/value entries.");
}

2.4 创建不可变更的Map对象

Map接口提供了一系列of()方法，帮助开发人员快速的创建不可变更Map对象(Unmodifiable Map)。ofEntries()方法也有着类似的功能。

Map<String, Integer> nameToAgeMap1 = Map.of("Amy", 21);
Map<String, Integer> nameToAgeMap2 = Map.of("James", 18, "Amy", 21);

3 java.util.SortedMap接口

SortedMap接口在Map接口的基础上，在键对象上提供了排序功能。在SortedMap内部，键对象按照从低到高的顺序排列。SortedMap接口继承自Map接口；SortedMap允许开发人员提供一个Comparator对象，对键对象进行排序；或者使用键对象的自然顺序。当使用Comparator对象比较键对象时，键对象之间的大小关系需保持一致(Consistent Ordering)。

因为SortedMap内部保持了键对象的顺序，所以在使用keySet()、values()和entrySet()方法获取键对象集合、值对象集合和键值对集合时，它们都能够按照键对象的顺序排列，并且按照键对象的升序遍历所有元素。

firstKey()方法和lastKey()方法能够获取最小键对象和最大键对象。headMap()、tailMap()和subMap()能够按照键对象的大小获取包含在指定取值范围内的所有键对象的Map对象。

下面是一段使用SortedMap的代码示例。

SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
sortedMap.add(1, "a value of key 1");
sortedMap.add(2, "a value of key 2");
sortedMap.add(3, "a value of key 3");

System.out.println("The smallest key is " + sortedMap.firstKey());
System.our.println("The greatest key is " + sortedMap.lastKey());

// 按照从小到大的顺序遍历每一个键值对
for (var entry: sortedMap) {
    System.out.println("The key in the key/value pair is " + entry.getKey());
}

4 java.util.Hashtable

Java标准库中java.util.Hashtable类实现了哈希表的功能。Hashtable实现了Map接口，所以，它是使用哈系表来实现Map接口的。Hashtable继承自Dictionary类，但是，Dictionary类已经不被推荐使用了(Obsolete)。Java标准库建议当设计新的Map类时，建议直接实现Map接口，不建议从Dictionary类继承。所以，我们在本章中直接介绍Hashtable类。

Hashtable类内部实现了一个哈希表。这个哈系表保存在成员变量table中。在创建Hashtable时，Hashtable对象保存了两个非常重要的信息：capacity和loadFactor。capacity表示的是哈希表的大小，或者bucket的个数。loadFactor则表示的是哈希表的使用率。根据这两个值，我们可以很容易的计算出一个阈值threshold。这个threshold的意思是当哈希表中元素的个数超过这个阈值时，哈希表需要更大的空间来保存这些元素，以降低哈希冲突发生的概率。

// OpenJDK 15
package java.util;

public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    private transient Entry<?,?>[] table;

    private transient int count; // 元素的个数(the number of entries)
    private float loadFactor; // Hashtable的使用率
    private int threshold; // threshold = capacity x loadFactor
    ...
}

图二 Hashtable内部结构图

成员变量table表示的是一个哈希表。与此同时，table也是一个数组，类型是Entry<?,?>。这个Entry保存的是开发人员传入的键值对。在哈希表中，这个Entry有被称为Bucket。它在数组中的位置被称为哈希值。每个Bucket维护这一个单向链表。当发生哈希冲突时，具有相同哈希值的键值对会保存在这个链表之中。所以，Entry对象有一个成员变量next，用于遍历这个单向链表。

当新增一个元素时，Hashtable使用hashCode()方法计算键对象的哈希值。当找到对应的Bucket之后，会沿着Entry对象组建成的链表依次查询是否存在相同的键对象。如果能找到相同的(equals()方法返回true)，则更新对应的值对象。如果未能找到，则调用addEntry()方法新增一个Entry对象。

在增加一个新Entry对象时，如果Entry对象的个数超过阈值的话，需要增加Hashtable的大小，并重新计算哈希值。这些是在rehash()方法中完成的。在完成了这些检查之后，Hashtable会计算新元素的哈希值，并将其插入到对应的Bucket中。

// OpenJDK 15
package java.util;

public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    ...
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        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;
    }
    ...
    private void addEntry(int hash, K key, V value, int index) {
        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
    }
    ...
}

在了解了Hashtable的内部实现之后，查询一个键对象就变得自然了。get()方法首先计算键对象的哈希值，然后再沿着Bucket对应的Entry链表中查询键对象。

// OpenJDK 15
package java.util;

public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    ...
    public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }
    ...
}

删除元素remove()实际上是添加元素put()的逆过程。我们在这里省略了remove()方法的介绍。感兴趣的读者可自行阅读remove()方法的代码。我们最后再介绍一下Entry单向链表的实现。Entry是Hashtable的内部类。Entry类包含了四个成员变量。key和value分别表示的是开发人员传入的键值对。hash表示的是key对象的哈希值。next则指向单向链表中的下一个节点。所以，可以看出，Entry链表是一个非常简洁的单向链表。

// OpenJDK 15
package java.util;

public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    ...
    private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
        ...
    }
    ...
}

4 java.util.HashMap

HashMap是另一种哈希表的实现。与Hashtable不同的是，HashMap优化了哈希冲突的情况。当有许多元素发生了哈希冲突时，HashMap会使用一棵红黑树来保存冲突的对象，而不再使用链表。HashMap提供的方法与Map接口非常相似，所以，我们省略了HashMap方法的介绍。

HashMap也有三个重要的成员变量。table是一个数组，用于表示哈希表；threshold和loadFactor的工作方式与上述的Hashtable一致。loadFactor用于表示使用率；当HashMap中的元素个数超过threshold时，HashMap需要使用更大的空间。

// OpenJDK 15
package java.util;

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ...
    transient Node<K,V>[] table;

    int threshold;

    final float loadFactor;
    ...
}

图三 HashMap内部结构图

当元素发生哈希冲突时，这些元素会保存在由Node组建的链表或者红黑树中。Node是HashMap类的一个内部类；它由四个成员变量。key和value分别表示开发人员插入的键对象和值对象；hash表示的是键对象的哈希值；next则指向下一个Node对象，连接成一个单向链表。

当这个链表较长时，HashMap会将这条链表转换成一棵红黑树。该红黑树的节点为TreeNode类型。TreeNode也是HashMap中的一个内部类。它的成员parent、left和right分别指向父节点和左右孩子节点。

// OpenJDK 15
package java.util;

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ...
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
    }
    ...
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        ...
    }
    ...
}

在了解了HashMap的内部结构之后，我们就能够理解添加元素和删除元素的操作了。在putVal()方法中，首先计算当前键值对的哈希值。然后再找到对应的索引位置(n-1) & hash。如果对应的Bucket为空，表示尚未有元素使用过这个Bucket，则直接将新元素放置在这个位置。如果已有元素在这个位置，则需要判断当前Bucket使用的是链表还是红黑树。

如果是红黑树，则调用putTreeVal()继续在树中查找并更新键值对。如果是链表，则在链表中查找。在更新之后，如果链表的长度达到了TREEIFY_THRESHOLD，则调用treeifyBin()方法，将链表转换为红黑树。我们在下面的代码的重要分支出给出了注释，读者可以仔细阅读这段代码，理解其实现细节。我们在此省略了putTreeVal()和treeifyBin()方法的实现，因为它们的实现不影响理解HashMap的工作原理。有兴趣的读者可自行阅读HashMap的源代码。

// OpenJDK 15
package java.util;

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ...
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    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;
        if ((p = tab[i = (n - 1) & hash]) == null)　// 当Bucket为空时
            tab[i] = newNode(hash, key, value, null);
        else { // 当Bucket不为空时
            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;
    }
    ...
}

那么，当查找一个键值对时，也时按照上述的思路进行的。我们将其实现展示如下。

// OpenJDK 15
package java.util;

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ...
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { // 如果对应的Bucket不为空
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first; // 检查第一个节点是不是要查找的对象
            if ((e = first.next) != null) { // 如果不是则继续查找
                if (first instanceof TreeNode)　// 如果当前Bucket使用了红黑树
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do { // 如果当前Bucket使用了链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    ...
}

5 java.util.TreeMap

TreeMap是一个有序映射(SortedMap)的实现。TreeMap内部实现了一棵红黑树，用以保存元素之间的有序性。从TreeMap的内部结构来看，它使用了一个成员变量root来表示这棵红黑树。树中的节点为Entry类型；它是TreeMap的一个内部类。成员变量key和value用于保存开发人员传入的键值对。left、right和parent用于指向父节点和左右孩子节点，构建一个红黑树。color是节点的颜色。

// OpenJDK 15
package java.util;

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;
    ...
    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
        ...
    }
    ...
}

图四 TreeMap内部结构图

在本文章中，我们并不想深入讲解红黑树的实现原理，其实现细节可参考我们数据结构部分的红黑树章节。在此，我们仅介绍一下TreeMap的查询元素的操作。从下面的代码可以看出，在查找的过程中，TreeMap是按照键的值的大小逐级比较树中的节点的。

// OpenJDK 15
package java.util;

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    ...
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null) // 如果提供了Comparator对象
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0) // 走左分支
                p = p.left;
            else if (cmp > 0) // 走右分支
                p = p.right;
            else
                return p; // 当前节点为目标节点
        }
        return null;
    }

    final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0) // 走左分支
                    p = p.left;
                else if (cmp > 0) // 走右分支
                    p = p.right;
                else
                    return p; // 当前节点为目标节点
            }
        }
        return null;
    }
    ...
}

添加元素和删除元素也是按照红黑树的结构和逻辑进行的。只不过在插入或者删除后，需要重新调节一下树中的节点，已保持树的平衡性。

6 java.util.EnumMap

EnumMap是一个特殊的映射实现，专门用于将枚举作为键对象使用的场景。从实现来看，成员变量keyUniverse保存着枚举的所有可能取值；vals则保存着所有键值对中的值对象。当给定一对键值对<k,v>时，如果k的值存放在keyType中的第i位时，即keyType[i] == k，那么，v会被存放在vals的第i位，即vals[i]=v。

// OpenJDK 15
package java.util;


public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
    implements java.io.Serializable, Cloneable
{
    ...
    private final Class<K> keyType;

    private transient K[] keyUniverse;

    private transient Object[] vals;
    ...
}

在初始化时，EnumMap会加载枚举中所有的可能值，并将keyUniverse和vals保持相同的长度。

// OpenJDK 15
package java.util;


public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
    implements java.io.Serializable, Cloneable
{
    ...
    public EnumMap(Class<K> keyType) {
        this.keyType = keyType;
        keyUniverse = getKeyUniverse(keyType);
        vals = new Object[keyUniverse.length];
    }
    ...
}

在添加和查找键值对时，直接按照键的值找到vals中对应的位置，并获取值对象。

// OpenJDK 15
package java.util;


public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
    implements java.io.Serializable, Cloneable
{
    ...
    public V get(Object key) {
        return (isValidKey(key) ?
                unmaskNull(vals[((Enum<?>)key).ordinal()]) : null);
    }

    public V put(K key, V value) {
        typeCheck(key);

        int index = key.ordinal();
        Object oldValue = vals[index];
        vals[index] = maskNull(value);
        if (oldValue == null)
            size++;
        return unmaskNull(oldValue);
    }
    ...
}

7 小结

本章介绍了Java标准库中提供的映射Map的实现。Map接口提供了根据键对象查找值对象的功能。SortedMap还能保持键对象的顺序。Hashtable和HashMap内部都实现了一个哈希表，提供快速的查找功能。当元素发生哈希冲突时，Hashtable将这些元素存放在一条单向链表之中。HashMap在此基础之上，做了进一步的优化。当冲突的元素较多时，HashMap会将链表转化为一棵红黑树。TreeMap使用了红黑树保存键值对，并且保存了键对象之间的顺序。EnumMap则用于键对象是枚举对象的情况，提供了更加有效的实现。