Java集合(四)：Map映射

浅浅的花香味﹌ 2022-07-28 09:48 297阅读 0赞

集是一个集合，它可以快速的查找现有的元素。但是，要查看一个元素，需要有要查找元素的精确副本。这不是一个非常通用的查找方式。通常，我们知道某些键的信息，并想要查找与之对应的元素。映射表（map）就是为此设计的。映射表用来存储键值对。如果提供了键，就可以查找对应的值。例如，有一张关于员工信息的记录表，键为员工ID，值为Employee。

Java类库为映射表提供了两个通用的实现：HashMap和TreeMap，这两个类都实现了Map接口。

散列映射表对键进行散列，树映射表用键的整体顺序对元素进行排序，并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

应该选择散列映射表还是树映射表呢？散列稍微快一些，如果不需要按照排列顺序访问键，就最好选择散列。

本文主要介绍HashMap类的底层实现，并简单介绍TreeMap但不做过多分析，因为TreeMap使用红黑树实现的，比较复杂，等以后再看。

### 1 Map接口 ###

Map接口提供了一些映射表的基本操作，下面是这些方法的总结：

（1）查询操作

int size();
    boolean isEmpty();
    boolean containsKey(Object);
    boolean containsValue(Object);
    V get(Object);

这些方法的含义都很明确。需要注意的是，containsKey方法、containsValue方法和get方法的参数类型都是Object。

（2）修改方法

V put(K,V);
    V remove(Object);
    void putAll(Map<? extends K,? extends V>);
    void clear();

put方法用于添加一个键值对，如果键已经存在就更新值并返回旧值。remove方法删除给定键的键值对并返回值。putAll方法将一个Map中的所有键值对添加到映射表中。clear方法删除所有元素。

（3）视图方法

Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K,V>> entrySet();

这三个方法返回三个视图：键集、值集合（不是集）和键值对集。对于视图会在后续的文章中作介绍。

在Map接口中还定义了一个子接口：Entry，用来操作键值对。

这个接口主要有一下几个方法：

K getKey();
    V getValue();
    V setValue(V value);
    boolean equals(Object o);
    int hashCode();

含义也比较明确。

### 2 散列映射表：HashMap ###

散列映射表主要用到散列技术，可以快速对一个元素进行查找。HashMap类中的主要域如下：

transient Node<K,V>[] table;
    transient int size;
    int threshold;
    final float loadFactor;

其中使用table来存储元素，size表示映射表中键值对的个数，threshold是一个域值，当元素个数超过这个域值后，就会自动扩展映射表的大小。而loadFactor是一个加载因子，表示threshold与table长度的比值。

可以看到，table是一个数组，数组中存储Node<K,V>类型的值。Node<K,V>表示一个键值对，定义如下：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey();
        public final V getValue();
        public final String toString();
        public final int hashCode();
        public final V setValue(V newValue);
        public final boolean equals(Object o);
    }

是一个静态内部类，这表示一个键值对，可见HashMap将键值对作为一个整体来操作。

在Node中，有存储键的key，存储值的value，存储散列值的hash，还有一个next引用，可见这是一个链表。

既然有散列值hash，那么这个值是如何计算的呢？方法如下：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

是一个纯粹的数学方式。

有了散列值，HashMap又是如何散列的呢？

HashMap使用hash值确定一个键值对在table中的位置，具体方法是，用hash%table.length，结果就是在table中的下标。如果有多个hash在table中的同一个位置，那么就构成一个链表。存储方式大致是这样的：

![20160414111314525][]

在HashMap中，table的默认大小是16，以后每次扩大容量都会是原来的二倍，因此，table的大小一直是2的幂。由于这点，HashMap在计算一个hash的位置的时候，使用了非常巧妙的方法：

int n=table.length;
    int index=hash&(n-1);

这就相当于计算hash%table.length。

了解了键值对的表示方式和HashMap的存储方式之后，就要对键值对进行操作了。常见的操作有查找、插入和删除。接下来就介绍这些操作：

（1）查找

HashMap中，对于查找操作，定义了一个私有方法getNode。这个方法有两个参数：hash和key，根据哈希值和键来找键值对。定义如下：

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) {
            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)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

首先根据hash定位键值对在table中的位置，找到之后首先检查第一个元素，如果符合就返回，如果不符合就遍历这个链表，知道找到符合的键值对。如果没有找到，说明没有这个键值对，返回null。

这个方法是查找操作的基本方法，HashMap中的查找方法比如containsKey等都是调用这个方法完成操作的。

（2）添加键值对

HashMap中定义了一个基本方法putVal，这个方法将给定的键和值加入映射表中，定义如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                    boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果表为空，即里面没有元素，则使用resize方法创建一个表
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //找到给定的键值对对应的位置，如果对应位置还没有元素，则创建一个Node作为链表的头
        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;
    }

添加操作和查找操作有点类似，首先定位待插入的键值对在table中的位置，如果里面没有元素，直接插入即可；如果里面已经有元素，即发生了冲突，就将这个元素加入到这个链表中。

put方法就是调用这个方法的。

（3）删除键值对

有加入操作就有删除操作。基本方法是removeNode：

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

首先也是定位到节点的位置，matchValue是是否匹配值，如果为true，就是说只有值也匹配的时候才删除这个键值对。HashMap中的remove方法就是调用这个方法。

（4）容量扩展

当当前元素个数size等于threshold时，即使没有达到table的容量，也需要对table进行扩展。HashMap中的resize方法完成这个操作。

这个方法比较复杂，方法分为两部分，第一个部分就是确定新映射表的大小，考虑的主要问题是数值溢出。因为默认的大小是16，每次扩容都会是原来的2倍，很容易溢出。当发生这种情况时，就将threshold值置为Integer.MAX\_VALUE。

第二个部分就是将原来映射表里的内容移到新的映射表中。这只需要两层循环就好。第一层循环是在table数组上，第二层是每个table元素也是一个链表，需要循环一次。然后把每个键值对放在新的映射表中的合适位置即可。

以上就是一些基本的操作，HashMap的修删改查方法都是基于这些方法实现的。

接下来就是HashMap的视图（view）操作。

（1）键集：keySet

方法keySet可以返回一个由键构成的集，注意KeySet既不是HashSet，也不是TreeSet，而是扩展了AbstractSet抽象类的一个内部类：

final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

这个类实现了Set接口，也是一个Collection，因此可以与使用任何集合一样使用keySet。

比如，可以枚举映射表中的所有键：

Set<String> keys=map.keySet();
    for(String key:keys)
    {
        do something with key
    }

（2）值集合：values

values方法返回一个由值构成的集合，注意不是集，因为HashMap仅要求键唯一，不需要值唯一。返回的这个集合是扩展了AbstractCollection类的一个内部类：

final class Values extends AbstractCollection<V>

（3）键值对集合：entrySet

这个方法返回由所有键值对构成的集合。这个方法返回的集是扩展了AbstractSet类的内部类：

final class EntrySet extends AbstractSet<Map.Entry<K,V>>

这样，就可以同时查看键和值了，以避免对值进行查找：

for(Map.Entry<String,Employee> entry:staff.entrySet())
    {
        String key=entry.getKey();
        Employee value=entry.getValue();
        dosomething with key,value
    }

下面的代码演示了映射表的操作过程。首先将键值对添加到映射表中。然后，从映射表中删除一个键，同时与之对应的值也别删除了。接下来，修改与某一个键对应的值，并调用get方法获得这个值。最后，对元素进行迭代：

import java.util.*;
    public class MapTest
    {
       public static void main(String[] args)
       {
          Map<String, Employee> staff = new HashMap<>();
          staff.put("144-25-5464", new Employee("Amy Lee"));
          staff.put("567-24-2546", new Employee("Harry Hacker"));
          staff.put("157-62-7935", new Employee("Gary Cooper"));
          staff.put("456-62-5527", new Employee("Francesca Cruz"));
    
          // print all entries
    
          System.out.println(staff);
    
          // remove an entry
    
          staff.remove("567-24-2546");
    
          // replace an entry
    
          staff.put("456-62-5527", new Employee("Francesca Miller"));
    
          // look up a value
    
          System.out.println(staff.get("157-62-7935"));
    
          // iterate through all entries
    
          for (Map.Entry<String, Employee> entry : staff.entrySet())
          {
             String key = entry.getKey();
             Employee value = entry.getValue();
             System.out.println("key=" + key + ", value=" + value);
          }
       }
    }

结果如下：

![20160414141203551][]

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后，我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。

如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity \* load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的 Entry 数组），因此创建 HashMap 时初始化容量设置也需要小心对待。

### 3 树映射表：TreeMap ###

TreeMap用键的整体顺序对元素进行排序，底层使用红黑树实现。迭代时，会按照顺序迭代。

下面的代码演示了TreeMap的使用。这里使用的是默认的比较器：

public class MapTest
    {
       public static void main(String[] args)
       {
          Map<String, Employee> staff = new TreeMap<>();
          staff.put("144-25-5464", new Employee("Amy Lee",9000));
          staff.put("567-24-2546", new Employee("Harry Hacker",5000));
          staff.put("157-62-7935", new Employee("Gary Cooper",7500));
          staff.put("456-62-5527", new Employee("Francesca Cruz",8000));
          for(Map.Entry<String,Employee> entry:staff.entrySet()){
             String key = entry.getKey();
             Employee value = entry.getValue();
             System.out.println("key=" + key + ", value=" + value);
          }
       }
    }

结果如下：

![20160414142321290][]

TreeMap在构造时还可以指定一个比较器，根据比较器对键进行排序：

public class MapTest
    {
       public static void main(String[] args)
       {
          Map<String, Employee> staff = new TreeMap<>(new Comparator<String>() {
             @Override
             public int compare(String o1, String o2) {
                return o2.compareTo(o1);
             }
          });
          staff.put("144-25-5464", new Employee("Amy Lee",9000));
          staff.put("567-24-2546", new Employee("Harry Hacker",5000));
          staff.put("157-62-7935", new Employee("Gary Cooper",7500));
          staff.put("456-62-5527", new Employee("Francesca Cruz",8000));
          for(Map.Entry<String,Employee> entry:staff.entrySet()){
             String key = entry.getKey();
             Employee value = entry.getValue();
             System.out.println("key=" + key + ", value=" + value);
          }
       }
    }

这里构造一个比较器，使得按照键反向排列。结果如下：

![20160414142603405][]

注意，TreeMap只能对键进行排序，不能对与键关联的值进行排序。

[20160414111314525]: /images/20220724/161d59da07614991adeead8bac223c29.png
[20160414141203551]: /images/20220724/260cbdee2ec344deab38e90c3ed15627.png
[20160414142321290]: /images/20220724/f8b1a2c803964a08af592b362c7ce2dd.png
[20160414142603405]: /images/20220724/a22b735eaf54428bb8d9b2100a285de3.png