Java Map接口常用实现类

Map用来存储key-value（键值对），它是Java集合框架的一部分。

接口

public interface Map<K,V> {
	// Query Operations

    // Map中的键值对数量
    int size();

    // Map是否为空，即没有键值对
    boolean isEmpty();

    // Map中是否包含特定的键
    boolean containsKey(Object key);

    // Map中是否包含特定的值
    boolean containsValue(Object value);

    // 根据key获取对应的value，如果key不存在则返回null
    V get(Object key);

    // Modification Operations

    // 向Map中放入一个键值对，返回键值对的值
    // 如果键在Map中已存在，则使用给定的值来更新原来的键值对的值，返回原来的旧值
    V put(K key, V value);

    // 根据key移除键值对，如果key在Map中不存在，则返回null，否则返回key对应的value
    V remove(Object key);

    // Bulk Operations

    // 把另一个Map的键值对放入该Map，向当于将另一个Map的键值对调用put方法放到该Map中
    void putAll(Map<? extends K, ? extends V> m);

    // 移除Map中所有的键值对
    void clear();

    // Views

    // 返回该Map中所有键的集合，返回类型为Set，因为键都是不相同的
    Set<K> keySet();

    // 返回该Map中的所有值的集合，返回类型为Colleectino
    Collection<V> values();

    // 返回该Map中所有键值对的集合，返回类型为Set<Map.Entry<K, V>>
    // Map.Entry表示一个键值对
    Set<Map.Entry<K, V>> entrySet();

    // 表示一个键值对
    interface Entry<K,V> {
        // 返回该键值对的key
        K getKey();

        // 返回该键值对的value
        V getValue();

        // 修改该键值对的value
        V setValue(V value);

        // 判断该键值对与指定的键值对是否相等
        boolean equals(Object o);

        int hashCode();

        // 省略了部分方法
    }

    // Comparison and hashing

    boolean equals(Object o);

    int hashCode();
}

非线程的实现类

HashMap

HashMap是Map接口的一种哈希表实现，它可以存放null（key和value都可以为null），它的get和put等操作时间复杂度均为0(1)

构造器

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

    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);
    }

    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
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
}

默认值
默认值比较多，而且作用比较大，最主要的是阈值（threshold，根据容量和负载因此进行计算）和负载因子（loadFactor，默认为0.75），默认的容量为16。扩容的时候新容量变成旧容量×2（newCap = oldCap << 1）

/**
 * 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;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor;

底层存储结构
底层存储结构为数组+链表，哈希冲突严重的时候（链表的元素大于等于8且Map容量大于64）会变成数组+红黑树

transient Node<K,V>[] table; // 数组
// 普通节点，组成链表
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;
}

LinkedHashMap

LinkedHashMap是有序的Map，这里的有序指的是遍历Map的元素（key-value）的时候，是按照元素的插入顺序进行的，而不是指按照自然顺序排序。也就是说它的迭代顺序确定的（按照元素的插入顺序）。

构造器

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
}

默认值
无

底层存储结构
底层存储结构为自己的静态内部类Entry还有HashMap的底层存储结构，自己的静态内部类主要增加加了before, after两个变量使得插入的key-value能够被按照插入顺序访问，因为利用了HashMap，所以扩容策略和HashMap一样

/**
 * 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);
    }
}

TreeMap

TreeMap是有序的Map，这里的有序是指它的元素（key-value）按照自然顺序或者指定的Comparator进行排序，它的底层存储结构为红黑树，添加和获取等操作时间复杂度为Olog(n)，key不允许为null，value可以为null，这使得使用get方法得到null的时候后有两重含义，key不存在或者key对应的value为null

构造器

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    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) {
        }
    }    
}

默认值
Comparator没有指定的是默认为null，即按照自然顺序进行排序

底层存储结构
底层存储结构为红黑树，一般树都是没有容量限制的，所以没有容量增长策略

// 红黑树的根节点
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; // 节点默认为黑色
}

线程安全的实现类

Hashtable

HashTable不允许存放null（key和value都不能为null，因为它的hash算法会调用key的hashCode方法，并且检测到value为null会抛出异常），添加和获取等操作的时间复杂度和HashMap一致（哈希冲突严重的时候性能会比HashMap差很多）

构造器

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);
}

默认值
initialCapacity和loadFactor是影响HashTable性能的两个关系参数，initialCapacity默认为11，loadFactor，threshold是根据当前容量和loadFactor动态计算的

/**
 * The table is rehashed when its size exceeds this threshold.  (The
 * value of this field is (int)(capacity * loadFactor).)
 *
 * @serial
 */
private int threshold;

/**
 * The load factor for the hashtable.
 *
 * @serial
 */
private float loadFactor;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

底层存储结构
数组 + 链表，哈希冲突严重时不会转换成红黑树，所以在哈希冲突严重的时候性能会比较差。扩容的时候容量新会变成旧容量×2 + 1（int newCapacity = (oldCapacity << 1) + 1;）
/**
* The hash table data.
*/
private transient Entry<?,?>[] table;

private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
}

ConcurrentHashMap

ConcurrentHashMap适用于高并发场景，它的get操作不需要加锁，添加和获取操作的时间复杂度均为O(1)，不允许存放null（key和value都不可以为null）

构造器

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    public ConcurrentHashMap() {
    }

    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

    public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }

    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }
}

默认值

/* ---------------- Constants -------------- */

/**
 * The largest possible table capacity.  This value must be
 * exactly 1<<30 to stay within Java array allocation and indexing
 * bounds for power of two table sizes, and is further required
 * because the top two bits of 32bit hash fields are used for
 * control purposes.
 */
private static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The default initial table capacity.  Must be a power of 2
 * (i.e., at least 1) and at most MAXIMUM_CAPACITY.
 */
private static final int DEFAULT_CAPACITY = 16;

/**
 * The largest possible (non-power of two) array size.
 * Needed by toArray and related methods.
 */
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * The default concurrency level for this table. Unused but
 * defined for compatibility with previous versions of this class.
 */
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

/**
 * The load factor for this table. Overrides of this value in
 * constructors affect only the initial table capacity.  The
 * actual floating point value isn't normally used -- it is
 * simpler to use expressions such as {@code n - (n >>> 2)} for
 * the associated resizing threshold.
 */
private static final float LOAD_FACTOR = 0.75f;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2, and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * The value should be at least 4 * TREEIFY_THRESHOLD to avoid
 * conflicts between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * Minimum number of rebinnings per transfer step. Ranges are
 * subdivided to allow multiple resizer threads.  This value
 * serves as a lower bound to avoid resizers encountering
 * excessive memory contention.  The value should be at least
 * DEFAULT_CAPACITY.
 */
private static final int MIN_TRANSFER_STRIDE = 16;

/**
 * The number of bits used for generation stamp in sizeCtl.
 * Must be at least 6 for 32bit arrays.
 */
private static int RESIZE_STAMP_BITS = 16;

/**
 * The maximum number of threads that can help resize.
 * Must fit in 32 - RESIZE_STAMP_BITS bits.
 */
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

/**
 * The bit shift for recording size stamp in sizeCtl.
 */
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

/*
 * Encodings for Node hash fields. See above for explanation.
 */
static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

/** Number of CPUS, to place bounds on some sizings */
static final int NCPU = Runtime.getRuntime().availableProcessors();

/** For serialization compatibility. */
private static final ObjectStreamField[] serialPersistentFields = {
    new ObjectStreamField("segments", Segment[].class),
    new ObjectStreamField("segmentMask", Integer.TYPE),
    new ObjectStreamField("segmentShift", Integer.TYPE)
};

底层存储结构
数组+链表，或者数组+红黑树。每次拓容后的新容量均为2的指数幂。

/**
 * The array of bins. Lazily initialized upon first insertion.
 * Size is always a power of two. Accessed directly by iterators.
 */
transient volatile Node<K,V>[] table;

/**
 * The next table to use; non-null only while resizing.
 */
private transient volatile Node<K,V>[] nextTable;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    // values for lockState
    static final int WRITER = 1; // set while holding write lock
    static final int WAITER = 2; // set when waiting for write lock
    static final int READER = 4; // increment value for setting read lock
}

static final class TreeNode<K,V> extends Node<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;
}

ConcurrentSkipListMap

ConcurrentSkipListMap是有序的Map（实现了SortedMap接口），这里有序指的是获取它的所有key组成的Set视图的时候里面的元素（key）按照自然顺序（或者指定的Comparator）升序或者降序排列。它的特点是添加、移除和查找等操作的时间复杂度均为Olog(n)

构造器

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {

    public ConcurrentSkipListMap() {
        this.comparator = null;
        initialize();
    }

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

    public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
        this.comparator = null;
        initialize();
        putAll(m);
    }

    public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
        this.comparator = m.comparator();
        initialize();
        buildFromSorted(m);
    }

    public ConcurrentSkipListMap<K,V> clone() {
        try {
            @SuppressWarnings("unchecked")
            ConcurrentSkipListMap<K,V> clone =
                (ConcurrentSkipListMap<K,V>) super.clone();
            clone.initialize();
            clone.buildFromSorted(this);
            return clone;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }
}

默认值

/**
 * Special value used to identify base-level header
 */
private static final Object BASE_HEADER = new Object();

底层存储结构
底层存储结构为多个分层的链表，具体结构如下：

 /**
 * This class implements a tree-like two-dimensionally linked skip
 * list in which the index levels are represented in separate
 * nodes from the base nodes holding data.  There are two reasons
 * for taking this approach instead of the usual array-based
 * structure: 1) Array based implementations seem to encounter
 * more complexity and overhead 2) We can use cheaper algorithms
 * for the heavily-traversed index lists than can be used for the
 * base lists.  Here's a picture of some of the basics for a
 * possible list with 2 levels of index:     
 * Head nodes          Index nodes
 * +-+    right        +-+                      +-+
 * |2|---------------->| |--------------------->| |->null
 * +-+                 +-+                      +-+
 *  | down              |                        |
 *  v                   v                        v
 * +-+            +-+  +-+       +-+            +-+       +-+
 * |1|----------->| |->| |------>| |----------->| |------>| |->null
 * +-+            +-+  +-+       +-+            +-+       +-+
 *  v              |    |         |              |         |
 * Nodes  next     v    v         v              v         v
 * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
 * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 *
 */

/**
 * The topmost head index of the skiplist.
 */
private transient volatile HeadIndex<K,V> head;
/**
 * Nodes hold keys and values, and are singly linked in sorted
 * order, possibly with some intervening marker nodes. The list is
 * headed by a dummy node accessible as head.node. The value field
 * is declared only as Object because it takes special non-V
 * values for marker and header nodes.
 */    
static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
}
/**
 * Index nodes represent the levels of the skip list.  Note that
 * even though both Nodes and Indexes have forward-pointing
 * fields, they have different types and are handled in different
 * ways, that can't nicely be captured by placing field in a
 * shared abstract class.
 */
static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
}
/**
 * Nodes heading each level keep track of their level.
 */
static final class HeadIndex<K,V> extends Index<K,V> {
    final int level;
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
        super(node, down, right);
        this.level = level;
    }
}

疑问

在JDK里面，并没有找到线程安全的LinkedHashMap的实现，LinkedHashMap是基于HashMap实现的，所以两者都不是线程安全的。用LinkedHashMap的主要目的是在迭代的时候能够按照元素的插入顺序进行迭代，或者可以用来实现LRU缓存。

接口
非线程的实现类
线程安全的实现类
疑问