说说集合系列（三）：Map

【引言】说完了Collection，接下来就要说说比Collection的结构稍稍复杂一些的Map了，作为一个key-value模式的数据结构，我们日常的编码过程中用到它的几率还是很高的，那么不同的Map实现之间有哪些区别呢？且看此篇文章一一道来。

Map

  Map接口中键和值一一映射. 可以通过键来获取值。这个接口本身也有许许多多不同的实现，所使用的结构和线程安全保障方面也是不完全相同的，所以接下来就针对每种类型做个简单的解读。

HashMap

接口/类定义

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        ......
    }
    
    /* ---------------- Public operations -------------- */

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     */
    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);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
}

继承关系简图

数据结构扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ......
    ++modCount;
    
    // 重点
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node<K,V>[] resize() {
    // 流程过于复杂，可参照源码解析系列详细了解
}

特性微总结

  对HashMap的基本特性：非线程安全、初始容量是16、扩容因子是0.75、key和value值均可为null、key不可重复、value可重复；关于具体的细节，因为此数据类型比较常用，后面会单独对此进行一个细节的分析。

LinkedHashMap

接口/类定义

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     * true表示最近最少使用次序，false表示插入顺序
     */
    final boolean accessOrder;
    
     /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the specified initial capacity and load factor.
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the specified initial capacity and a default load factor (0.75).
     */
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the default initial capacity (16) and load factor (0.75).
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    /**
     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
     * the same mappings as the specified map. 
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    /**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
}

继承关系简图

数据结构扩容

// 因为是链表模式，不涉及扩容

特性微总结

• 底层存储结构：链表（可以认为是HashMap+LinkedList）
• 初始化大小：链表不涉及大小的说法，所以没有初始化大小
• 扩容：不涉及
• 构造：多种参数
• 线程安全性：不安全
• 有序性：有序（通过维护一个运行于所有条目的双向链表，保证了元素迭代的顺序）
• 空数据：Key和Value都允许空
• 重复性：Key重复会覆盖、Value允许重复

TreeMap

接口/类定义

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     */
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

    /**
     * Constructs
     */
    public TreeMap() {
        comparator = null;
    }

    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
}

继承关系简图

数据结构扩容

// 树结构，不涉及

特性微总结

• 底层存储结构：Tree
• 初始化大小：树不涉及大小的说法，所以没有初始化大小
• 扩容：不涉及
• 构造：多种参数
• 线程安全性：不安全
• 有序性：有序（通过红黑树实现）
• 空数据：
  • 当未实现 Comparator 接口时，key 不可以为null，否则抛 NullPointerException 异常；
  • 当实现 Comparator 接口时，若未对 null 情况进行判断，则可能抛 NullPointerException 异常。
• 重复性：Key重复会覆盖、Value允许重复

WeakHashMap

  对于不怎么常用的类型，这里就不细究内部实现了；这里的Weak顾名思义是弱的，那么弱在哪里呢？
  引用在Java中指的是一个对象对另一对象的使用（指向），可以有以下三种类型：强引用（Strong Reference）、软引用（Soft Reference）、弱引用（Weak Reference）。

强引用

  被强引用指向的对象，绝对不会被垃圾收集器回收。Integer prime = 1;，这个语句中prime对象就有一个强引用。

软引用

  被SoftReference指向的对象可能会被垃圾收集器回收，但是只有在JVM内存不够的情况下才会回收；如下代码可以创建一个软引用：

Integer prime = 1;  
SoftReference<Integer> soft = new SoftReference<Integer>(prime);
prime = null;

弱引用

  当一个对象仅仅被WeakReference引用时，在下个垃圾收集周期时候该对象就会被回收。我们通过下面代码创建一个WeakReference：

Integer prime = 1;  
WeakReference<Integer> soft = new WeakReference<Integer>(prime);
prime = null;

WeakHashMap的特殊Entry

/**
 * The entries in this hash table extend WeakReference, using its main ref
 * field as the key.
 */
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;
......

特性微总结

  简单来说，WeakHashMap实现了Map接口，基于hash-table实现，在这种Map中，key的类型是WeakReference。如果对应的key被回收，则这个key指向的对象会被从Map容器中移除。
  所以WeakHashMap跟普通HashMap相比较的话，有些特性就会失效的，比如size()方法的返回值会随着程序的运行变小，isEmpty()方法的返回值会从false变成true等等。

EnumMap

特性微总结

  EnumMap是一个与枚举类一起使用的Map实现，EnumMap中所有key都必须是单个枚举类的枚举值。创建EnumMap时必须显式或隐式指定它对应的枚举类。
  EnumMap在内部以数组形式保存，所以这种实现形式非常紧凑、高效。
  EnumMap根据key的自然顺序（即枚举值在枚举类中的定义顺序）来维护来维护key-value对的次序。当程序通过keySet()、entrySet()、values()等方法来遍历EnumMap时即可看到这种顺序。
  EnumMap不允许使用null作为key值，但允许使用null作为value。如果试图使用null作为key将抛出NullPointerException异常。如果仅仅只是查询是否包含值为null的key、或者仅仅只是使用删除值为null的key，都不会抛出异常。

小Demo

枚举定义

package com.example.demo;

/**
 * Created by chenglin on 2018/8/24.
 */
public enum Season {
    SPRING, SUMMER
}

测试Demo

package com.example.demo;

import java.util.EnumMap;

/**
 * Created by chenglin on 2018/8/23.
 */
public class Test {

    public static void main(String[] args) {
        // 该Map的所有key都是Season的枚举值
        EnumMap enumMap = new EnumMap(Season.class);
        enumMap.put(Season.SPRING , "满园春色关不住");
        enumMap.put(Season.SUMMER , "小荷才露尖尖角");
        System.out.println(enumMap);
    }
}

[Console log]:
{SPRING=满园春色关不住, SUMMER=小荷才露尖尖角}

HashTable

接口/类定义

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

    /**
     * The hash table data.
     */
    private transient Entry<?,?>[] table;

    /**
     * The total number of entries in the hash table.
     */
    private transient int count;

    private int threshold;

    private float loadFactor;

    private transient int modCount = 0;


    /**
     * Constructs
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    public Hashtable() {
        this(11, 0.75f);
    }

    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }
}

继承关系简图

数据结构扩容

/**
 * 容量翻倍+1即:capacity*2+1
 */
@SuppressWarnings("unchecked")
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code ***
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

特性微总结

• Hashtable是线程安全
• Hashtable不允许使用null值和null键
• Synchronized是针对整张Hash表的，即每次锁住整张表让线程独占（比如put：public synchronized V put(K key, V value)）；所以效率偏低
• 底层使用entry<k,v>[]加链表加红黑树实现
• 计算hash，然后取模来计算key的位置（这个和hashmap是一样的）
• Hashtable初始容量为11，扩容容量:capacity*2+1

ConcurrentHashMap

  后面会单独针对这个类进行源码分析的，所以这里就不贴源码结构了。
  对于这种Map，最重要的一点我们需要知道的就是ConcurrentHashMap是线程安全的，而且比Hashtable高效；具体的原因是因为它用到了分段锁和CAS机制，并没有像Hashtable一样对整个hash表加锁，而且HashMap本身的segment设计也对访问的粒度进行了缩减，对效率提升也是大有益处的。