Java集合-Map篇

JDK提供的集合类型主要分为四种类型：

List：支持重复元素
Set：不支持重复元素
Map：键/值对的映射集
Queue/Deque（double ended queue）：queue是在集合尾部添加元素，在头部删除元素的队列，deque是可在头部和尾部添加或者删除元素的双端队列，deque既可以实现队列又可以实现栈。

本文基于JDK8，java version “1.8.0_251”

HashMap

数组+链表/红黑树，非线程安全

在JDK8之前，hashMap是数组+链表的结构，JDK8引入了红黑树。当链表元素大于等于8，且table数组长度大于64，链表会转换成红黑树（链表元素个数大于等于8但table数组的长度小于64时，只触发扩容），若红黑树的节点个数小于等于6，树结构还原成链表。因为红黑树的平均查找长度是log_2 n，而链表的平均查找长度是n/2。中间有个差值，可以防止链表和树频繁转换。

默认容量为16，默认负载因子为0.75，最大容量为2^30

 /**
 * 默认的初始容量是16
 */
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;
/**
 * 树化阈值。当添加元素到桶中，如果桶中链表长度被添加到至少8，链表就转换为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 链表还原阈值。
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 最小数形化容量。桶中链表被转换为红黑树的最小容量是64
 */
static final int MIN_TREEIFY_CAPACITY = 64;

容量总是为2的次幂（数组索引计算为与运算，i = (n - 1) & hash），在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

懒加载，使用空参构造方法初始完后，只是给负载因子赋值，table并没有初始化，执行put方法后，才会将table初始化为默认大小16；且values方法和keySet方法也为懒加载，没有调用values和keySet方法之前，values和keySet为空，调用时才初始化。

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;
/**
 * 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
}

动态扩容，当 元素数量大于容量*负载因子时触发扩容，不存在缩容。新的容量为旧容量的2倍。然后将原来的Node节点放入新的bucket数组中。这个过程叫作再散列，因为它调用hash方法找到新的bucket位置。在JDK8之前，采用的是头插法，多个线程发现需要调整hashmap的大小，他们会同时进行rehashing，这样可能导致链表产生环，rehashing过程也会死循环，其他线程执行get方法也可能会导致死循环。而JDK8采用尾插法，避免了这一点，同时JDK8如果单个链表长度大于等于8且table数组长度大于等于64时，链表会转为红黑树，这点也需要计算链表长度，正好一举两得。
非线程安全，通过Collections.synchronizedMap()方法把它转成线程安全的集合，效率较低，推荐使用ConcurrentHashMap。
支持fail-fast机制，KeyIterator和ValueIterator都继承自HashIterator，而HashIterator的nextNode方法中包含会检查modCount的值，如果modCount != expectedModCount会抛出ConcurrentModificationException异常。
允许key和value为null，hash函数做了判空处理
1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
注：Concurrent Key 和 Value 不允许为 null，原因是在并发编程中 null 值存在歧义，若调用 get 方法返回的结果是 null 值，此时无法确定这个 key 对应的 value 本身就是 null，还是该 key 根本就不存在。在非并发编程中，可以进一步通过 containsKey 来进行判断，但是在并发编程中无法保证两个方法之间没有其他线程来修改该 key，所以应该禁用 null 值。

HashTable

和JDK8之前的HashMap很相似，线程安全

基于数组+链表实现

默认容量为11，默认负载因子为0.75，显式定义了数组的长度最大为Integer.MAX_VALUE - 8，没有定义节点的最大数量。

/**
 * Constructs a new, empty hashtable with a default initial capacity (11)
 * and load factor (0.75).
 */
public Hashtable() {
    this(11, 0.75f);
}

无懒加载，默认容量就是11
动态扩容，当 元素数量 = 容量*负载因子时触发扩容，不存在缩容。新的容量为旧容量的2倍+1。链表新增元素采用头插法，由于put方法使用synchronized修饰，所以不会出现多个线程同时扩容。
线程安全，get、put、remove等方法均使用synchronized修饰，效率较低，推荐使用ConcurrentHashMap。

支持fail-fast机制，但是Enumerator无法获取，获取迭代器是私有方法，只能先获取keySet()或values()，再获取iterator

public T next() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    return nextElement();
}
private <T> Iterator<T> getIterator(int type) {
    if (count == 0) {
        return Collections.emptyIterator();
    } else {
        return new Enumerator<>(type, true);
    }
}

key和value都不允许为null，为空会抛出NullPointerException异常
计算数组索引采用与运算，(hash & 0x7FFFFFFF) % tab.length，hash & 0x7FFFFFFF的作用是为了得到一个正数。

TreeMap

红黑树结构，有序Map集合，非线程安全,

基于红黑树结构的有序Map集合，元素的顺序基于键的compareTo方法，或者自定义的comparator。
基于红黑树，无懒加载
非线程安全，通过Collections.synchronizedSortedMap()方法把它转成线程安全的集合，效率较低
支持fail-fast机制，如果在创建了Interator后，有其他线程修改了集合导致modCount != expectedModCount则会抛出ConcurrentModificationException异常。
key不允许为null，value允许为null，key为空会抛出NullPointerException异常

LinkedHashMap

继承自HashMap，有序集合，非线程安全，可以用来实现FIFO和LRU缓存淘汰算法

继承自HashMap的有序集合，根据初始化参数accessOrder是false还是true来选择是按插入元素时的顺序还是按访问顺序进行排序。默认accessOrder=false，按插入元素的顺序进行排序
1
2
3
4
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{

新增双向链表结构，在HashMap结构的基础上，新增了一个双向链表的结构。重写了HashMap的部分方法，比如创建Node节点，会调用linkNodeLast方法，将元素加到链表的尾部；get方法，查询到了元素，会根据accessOrder判断，如果为true，会将元素移动到链表的尾部。

/**
 * 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;
/**
 * 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);
    }
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

懒加载，主要是调用HashMap构造函数，HashMap是懒加载，所以将它也定义为懒加载。
1
2
3
4
public LinkedHashMap() {
super();
accessOrder = false;
}
动态扩容，JDK8之前重写了部分数据迁移的方法transfer（通过遍历双向链表），JDK8直接使用HashMap的扩容机制。从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。
非线程安全，通过Collections.synchronizedMap()方法把它转成线程安全的集合，效率较低
支持fail-fast机制，nextNode方法中会判断modCount值，如果modCount != expectedModCount，则会抛出ConcurrentModificationException异常。
允许key和value为null，因为基于HashMap，所以它也允许key和value为null

linkNodeLast

添加一个对象，创建Node节点，然后调用linkNodeLast方法，将元素加到链表的尾部

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

afterNodeAccess

当一个节点被访问时，如果 accessOrder 为 true，则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion

在 put 等操作之后执行，当 removeEldestEntry() 方法返回 true 时（默认返回false）会移除最晚的节点，也就是链表首部节点 first。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

要实现LRU或者FIFO，首先就需要重写removeEldestEntry()，当元素容量>缓存容量时，返回true。

private final static MAX_ENTRIES = 10;
boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

LRU实现思路：accessOrder设置为true，最新添加的元素在链表的头部，如果一个元素被访问了，这个元素会被移动到链表尾部，链表头部的元素首先被删除。

FIFO实现思路：accessOrder设置为false，最新添加的元素在链表头，最旧的元素在链表尾，链表头部的元素首先被删除。

LFU实现思路：使用HashMap，key就是缓存key，value包含缓存value，访问次数，创建时间。查询缓存，修改元素的访问次数；添加缓存，先判断当前缓存容量是否等于最大容量，如果是，则遍历values，找出访问次数最少（次数相同则比较创建时间）的元素并将其移除，然后再添加缓存元素。

IdentityHashMap

和JDK8之前的HashMap很相似，IdentityHashMap比较的是引用，HashMap是比较equal方法

基于数组存储，且key，value是连续存储。
1
2
tab[i] = k;
tab[i + 1] = value;

线性探测法解决hash冲突

1
2
3

private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);
}

数组默认长度为32，既容量为16，默认负载因子为2/3（没有显示定义负载因子，而是在代码中写死），最大容量为1 << 29，
容量总是为2的次幂（数组索引计算为与运算，i = hash & (n - 1) ），在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。
无懒加载，使用空参构造或指定大小都会初始化table数组。
动态扩容，当 元素数量 = 容量*负载因子时触发扩容，不存在缩容。新的容量为旧容量的2倍。扩容之后需要再散列。
非线程安全，通过Collections.synchronizedMap()方法把它转成线程安全的集合，效率较低
支持fail-fast机制，nextNode方法中会判断modCount值，如果modCount != expectedModCount，则会抛出ConcurrentModificationException异常。
允许key和value为null
key 和 value 比较引用判断是否相等（HashMap通过equeal方法）

WeakHashMap

和HashMap很相似，弱引用，实现缓存（Tomcat中的ConcurrentCache）

基于数组+链表的结构，默认容量为16，默认负载因子为0.75，最大容量为2^30。
容量总是为2的次幂（数组索引计算为与运算，i = (n - 1) & hash），在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效
无懒加载，使用空参构造或指定大小都会初始化table数组。
动态扩容，当 元素数量 = 容量*负载因子时触发扩容。新的容量为旧容量的2倍。插入和再散列过程采用头插法，多个线程执行再散列可能会导致链表产生环（和上文HashMap类似）。将元素从旧Map迁移到新表时，若size小于threshold/2，重新将数据从新表迁移到旧表（因为迁移的时候会删除已经被回收的条目：key为null）。
非线程安全，通过Collections.synchronizedMap()方法把它转成线程安全的集合，效率较低。
支持fail-fast机制，nextNode方法中会判断modCount值，如果modCount != expectedModCount，则会抛出ConcurrentModificationException异常。
允许key和value为null
Entry继承自WeakReference，被 WeakReference 关联的对象在下一次垃圾回收时会被回收。

expungeStaleEntries方法清除过时的条目，当key失效时，GC会自动将对应的Entry添加到ReferenceQueue queue中，在调用getTable size resize方法时会调用expungeStaleEntries方法，这些方法会被几乎所有方法调用。

/**
 * Reference queue for cleared WeakEntries
 */
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
/**
 * Expunges stale entries from the table.
 */
private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);

            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

ConcurrentHashMap

线程安全的HashMap，Synchronized + CAS

基于数组+链表/红黑树，当链表元素大于等于8，且table数组长度大于64，链表会转换成红黑树（链表元素个数大于等于8但table数组长度小于64时，只触发扩容），若红黑树的节点个数小于等于6，树结构还原成链表。因为红黑树的平均查找长度是log_2 n，而链表的平均查找长度是n/2。中间有个差值，可以防止链表和树频繁转换。
默认容量为16，默认负载因子为0.75，最大容量为2^30。指定的负载因子只在构造方法中有效，用来计算扩容阈值，不会存储负载因子。后续扩容还是使用0.75。
容量总是为2的次幂（数组索引计算为与运算，i = (n - 1) & hash），在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。

懒加载，空参构造方法什么也没干，指定容量的构造方法中，计算了 sizeCtl，sizeCtl = 【 (1.5 * initialCapacity + 1)，然后向上取最近的 2 的 n 次方】。如 initialCapacity 为 10，那么得到 sizeCtl 为 16，如果 initialCapacity 为 11，得到 sizeCtl 为 32

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

线程安全，JDK7采用分段锁（Segment）设计，而JDK8采用Synchronized + CAS设计实现线程安全。
动态扩容。新的容量是旧容量的2倍。数据迁移。扩容的第一次初始化新表（扩容后的新表）这个动作，只能由一个线程完成。其他线程都是在帮助迁移元素到新数组。数据迁移从后向前进行，通过改变transferIndex的值从n到0，每个线程迁移数组中指定长度Node节点（这个长度叫做步长）。transferIndex到0后，还会将其值改回n，检查一遍是否迁移成功。扩容和数据迁移数concurrentHashMap中最难的一部分，参考下面的资料方便理解。
添加元素采用尾插法（方便计数），数据迁移时采用头插法。
对于获取size，使用CounterCell避免大量的CAS ，当需要修改元素数量时，线程会先去 CAS 修改 baseCount 加1，若成功即返回。若失败，则线程被分配到某个 CounterCell ，然后操作 value 加1。若成功，则返回。否则，给当前线程重新分配一个 CounterCell，再尝试给 value 加1。（这里简略的说，实际更复杂），遍历CounterCell的值和baseCount相加的结果就是容量。
对于get读操作，如果当前节点有数据，还没迁移完成，此时不影响读，能够正常进行。如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时get线程会帮助扩容。
对于put/remove写操作，如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时写线程会帮助扩容，如果扩容没有完成，当前链表的头节点会被锁住，所以写线程会被阻塞，直到扩容完成。
Node类的value和next使用volatile修饰，保证可见性。
sizeCtl，默认为0，用来控制table的初始化和扩容操作。-1 代表table正在初始化，-N 表示有N-1个线程正在进行扩容操作。如果table未初始化，表示table需要初始化的大小。如果table初始化完成，表示table的容量，默认是table大小的0.75倍。用来控制扩容操作时，高16位是数据校验标识，低16位代表当前有几个线程正在帮助扩容。扩容时候会判断这个值，如果超过阈值就要扩容，首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素f，初始化一个forwardNode实例fwd，如果f == null，则在table中的i位置放入fwd，否则采用头插法的方式把当前旧table数组的指定任务范围的数据给迁移到新的数组中，然后
给旧table原位置赋值fwd。直到遍历过所有的节点以后就完成了复制工作，把table指向nextTable，并更新sizeCtl为新数组大小的0.75倍，扩容完成。在此期间如果其他线程的有读写操作都会判断head节点是否为forwardNode节点，如果是就帮助扩容。
红黑树的根节点的哈希值为-2，判断的是否为红黑树直接判断第一个元素的哈希值是否大于0。
不支持fail-fast机制
key和value都不能为null，否则会抛出空指针异常。
线程安全，并发粒度细，性能强。
弱一致性，因为使用了Counter来帮助计算容量，遍历Counter时没有加锁，所以存在弱一致性问题（实际上juc集合里面的size方法所返回的元素个数都是不保证准确的）。另外JDK8之前迭代器也存在弱一致性问题，HashEntry的next属性定义为final，这意味着它是不可变的，如果线程A 删掉了第 7 个元素，线程B 已经遍历到了第 3 个元素，那么 B 还是可以遍历到被删除的第 7 个元素。

笔记：

Thread.yield()；让掉当前线程 CPU 的时间片，使正在运行中的线程重新变成就绪状态，并重新竞争 CPU 的调度权。作用：避免一个线程长时间占有 CPU 资源

参考资料：

ConcurrentSkipListMap

跳跃表，线程安全，CAS，无锁，有序，空间换时间

基于跳跃表，理论上能够O(log(n))时间内完成查找、插入、删除操作。
有序Map集合，key是有序的，元素的顺序基于键的compareTo方法，或者自定义的comparator。
线程安全，基于CAS+volatile实现，并发粒度细，性能强。
空间换时间，基于跳跃表实现的有序，包含多级索引，每个级别的索引节点按照其关联数据节点的关键字升序排列，且高级别索引是其低级别索引的子集，如果关键字key在级别level=i的索引中出现，则级别level<=i的所有索引中都包含key。

节点主要由 Node, Index, HeadIndex 构成，横向纵向都是链表。最下面那层链表是Node层(数据节点层), 上面几层都是Index层(索引)。从纵向链表来看, 最左边的是 HeadIndex 层, 右边的都是Index 层, 且每层的最底端都是对应Node, 纵向上的索引都是指向最底端的Node。

static final class Node<K, V>{
    final K key;  // key 是 final 的, 说明节点一旦定下来, 除了删除, 不然不会改动 key 了
    volatile Object value; // 对应的 value
    volatile Node<K, V> next; // 下一个节点
}
static class Index<K, V>{
    final Node<K, V> node; // 索引指向的节点, 纵向上所有索引指向链表最下面的节点
    final Index<K, V> down; // 下边level层的 Index
    volatile Index<K, V> right; // 右边的  Index
}
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); // 所有的 HeadIndex 都指向同一个 Base_header 节点
        this.level = level;
    }
}

元素的增删改查都从最上层的head指针指向的结点开始。
头插法创建Index结点，在删除键值对时，不会立即执行删除，而是通过引入标记结点，以懒删除的方式进行，以提高并发效率。
每次put操作都会生成随机数，然后用来获取level (50%的几率返回0，25%的几率返回1，12.5%的几率返回2…最大返回31)，如果level大于最大的level，则会新增level。否则只插入一个Index节点。
key和value都不能为null，否则会抛出空指针异常。
不支持fail-fast机制。
无懒加载

参考资料：

问题

性能谁更强？ConcurrentSkipListMap VS ConcurrentHashMap

在4线程1.6万数据的条件下，ConcurrentHashMap 存取速度是ConcurrentSkipListMap 的4倍左右。

但ConcurrentSkipListMap有几个ConcurrentHashMap 不能比拟的优点：

1、ConcurrentSkipListMap 的key是有序的。

2、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是log（N），和线程数几乎无关。也就是说在数据量一定的情况下，并发的线程越多，ConcurrentSkipListMap越能体现出他的优势。