Java容器知识体系

引言

最近在从头到脚梳理知识体系，这次带来的是Java容器，比较系统且全面，输出我的知识笔记～
打算走这个图谱梳理：

文章导航 

容器概述（Set、List、Queue、Map）
List(ArrayList、Vector、CopyOnWriteArrayList，LinkedList)
Map（HashMap，解决hash冲突的方法、ConcurrentHashMap、LinkedHashMap）

一、概述

Java容器包括Collection和Map，Collection存对象的集合，Map存键值对映射。

1. Collection

collection包含Set、List、Queue。

Set

List 

Queue 

2. Map 

二、List 

1. ArrayList

基于动态数组实现，数组默认大小为10，支持快速随机访问，实现了RandomAccess接口标识能快速随机访问。

    public ArrayList(int initialCapacity) {
        //如果指定了容量，就按指定的容量初始化
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
添加元素

添加到对应位置，并且更新数组size。

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将index前的元素copy，index的位置腾给新元素，index后的按顺序赋值到+1的位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
扩容

add前会先调用ensureExplicitCapacity()确保容量足够，如果不够会调用grow()触发扩容机制。新容量为oldcapacity+（oldcapacity>>1 ），也就是扩容1.5倍左右。

扩容过程走Arrays.copyof()，复制原数组，开销比较大，最好创建时就预估好容量，减少扩容。

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //如果期望的size比当前数组长度大就要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
删除元素

时间复杂度为O(N)，删除的代价比较高。

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            //将index+1开始的元素都往前挪一个
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
Fail-Fast 快速失败

当异常产生时，直接抛出异常，程序终止。
ArrayList用modCount结构变化的次数，在add、remove、数组大小调整时会变更。在进行迭代时，会比较前后modCount是否改变，如果改了就要抛异常（ConcurrentModificationException），防止继续遍历。

Fail-Safe 安全失败

采用安全失败机制的集合容器，在遍历时先复制原有集合内容，在拷贝的集合上进行遍历。在遍历过程中对原集合所作的修改不能被迭代器检测到，所以不会触发ConcurrentModificationException。

缺点：基于拷贝内容的优点是避免了ConcurrentModificationException，但同样地，迭代器并不能访问到修改后的内容。遍历的时候，原集合修改了，迭代器并不知道。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

2. Vector

和ArrayList类似，用synchronized同步。构造方法能传入扩容步长capacityIncrement，每次扩容增加capacityIncrement，这个值小于等于0时扩容为原来两倍。

与ArrayList差异

Vector是同步的，开销大，访问慢。
每次扩容2倍或对应步长个，ArrayList是1.5倍。
3. CopyOnWriteArrayList

读写分离

写时在复制的数组上进行，读时在原数组进行，做到读写分离。写时加锁，防止并发写入数据丢失；写结束后原数组指向新数组。

    public boolean add(E e) {
        //写时加锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            //赋值到原数组
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
适用场景

CopyOnWriteArrayList提高了读性能，适合读多写少的场景。

缺点：

内存占用。写时复制，让内存变为原来的两倍。
数据不一致。读时不能保证数据实时。
不适合内存敏感和数据实时性高的场景。

4. LinkedList

LinkedList存储了first和last指针，每个节点存储了前后两个指针。

与ArrayList差异

数组支持随机访问，插入删除代价高
链表不支持随机访问，插入删除代价低
三、Map

1. HashMap

存储结构

HashMap是Entry[]的table数组，数组中一个坑位是一个桶，一个桶放一个链表，基于哈希函数存放。

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
     /**
     * table数组
     */
     transient Node[] table;
     transient Set> entrySet;
     /**
      * 键值对的数量
      */
     transient int size;

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
}
当两个不同的key最终落在同一个桶的位置就会产生hash碰撞。因此，如果hashCode()实现方法太挫，HashMap将退化成链表。

使用拉链法解决冲突，使用key的hashCode和数组长度取模，落入对应坑位。完美哈希的情况下，查找的时间复杂度为O(1)。

put的过程 

可以插入为null的k-v，key为null时不能计算hashCode，所以用第0个桶存放。
链表使用头插法，新key插入链表的头部。
数组的默认大小是16，加载因子限制数组长度，链表长度超过8时变成红黑树。

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //初始化数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //计算key落在哪个桶，(n - 1) & hash和hash%n结果一致
        //如果没hash碰撞，就直接写入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //当前坑位就一个节点，哈希值和key都相等则记录，p在上面的if判断中已经赋值了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是红黑树，用树的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode)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);
                        //如果插入后链表长度大于TREEIFY_THRESHOLD（默认8），就转成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到key在该链表对应的节点，并记录
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //只有key在hashMap中已经存在时，e不为null，新value覆盖旧value，返回旧值
            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;
    }
put的过程

1.根据key.hashCode()调用key.hash()计算得到hash值。
注：2.2 hash方法计算介绍。

2.控制这个整型的数在0~n-1之间(n-1)&key.hash()成为数组的下标。没用key.hash()%n计算，这样性能更高，位运算的代价比取模小很多，保证n为2的n次方能让他的结果和取模一致。

3.如果该索引存的数组等于空（没hash碰撞），就直接存入；否则，分为3个分支判断：

if 当节点key值相同，就替换掉原来的value
else if 判断p当前的节点是否为TreeNode，是的话用红黑树的插入方式
else 链表的存储方式，尾插法
扩容的过程

数组初始化，或者数组坑位被占用了就会判断是否需要扩容，如果元素大于capacity * load factor的时候就要用resize()方法扩容，不然效率会下降的比较快。

    final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //最大值兜底
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //新阈值就是旧阈值的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //容量为0，新阈值是旧阈值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //容量<==0且旧阈值<=0，需要初始化
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        //把旧的table赋值到新的table
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //有节点，下面为空，说明当前坑位就一个节点
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //有节点，下面不为空且是红黑树，以红黑树的方式进行split
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    //有节点，下面不为空，且为链表
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        //遍历这个链表
                        do {
                            next = e.next;
                            //生成低位的链表
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //生成高位的链表
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //如果结果为0，还是在原来的位置保持不动
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //如果结果为1，新位置是原来的位置+oldCap
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
resize()会双倍扩容，让原来的容量大小向左移一位，阈值也会左移一位成双倍。 

为什么要扩容成双倍？

为了使雨露均沾，尽量使hash不会重复；保证(n-1)&key.hash()与key.hash()%n结果一致，位运算减少开销。

resize()的过程

节点重新进行分配，需要开启一个for循环，有3种情况：

1.有节点，但是下面为空 key.hash & (newCap-1)作为新数组下表

2.有节点，下面不为空，但是为红黑树 以红黑树的方式进行split

3.有节点，下面不为空，但是为链表

计算key.hash & oldCap ==0
如果结果为0，那么位置还是在原来的位置保持不动
如果结果为1，那么位置就是原来的位置+oldCap
hash方法计算
很多操作都离不开hash()方法。
hash()方法会结合hashCode()用来定位在数组中的位置，而equal()用来比较数组链表展开元素是否相等。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
为了保证hash计算结果尽可能不一样，将hashCode的高16位与其低16位做异或运算。

hash()方法为什么要这么实现，为什么不用&运算而是异或运算？为什么要处理高16位和低16位的数据，是否多此一举？
因为如果使用&运算，结果趋近于1，使用|运算结果趋近于0，不能很好的把高16位和低16位的特征表达出来。处理高低16位是要将他们的特征混合，得到新的数值中高位和低位的信息被保留。

计算数组容量

构造方法允许传入非2的n次方的容量，hashMap会将他转换为大于该数组，最小的2的n次方。

    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;
    }
get的过程

    public V get(Object key) {
        Node e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        //hash值在table中存在
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //在table首位就返回
            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)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;
    }
在table首部或链表或红黑树中查找对应节点。

remove的过程

    public V remove(Object key) {
        Node e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    final Node removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node[] tab; Node p; int n, index;
        //hash值在table中存在才会删除
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node node = null, e; K k; V v;
            //在table首位就记录对应节点
            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)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)node).removeTreeNode(this, tab, movable);
                //在table首部，直接删除
                else if (node == p)
                    tab[index] = node.next;
                //在链表中，删除node节点
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
根据key.hash()查找到对应节点，删除分为3种情况：红黑树、table首部、链表，删除对应数据结构中的节点。

HashTable对比

Hashtable 使用 synchronized 来进行同步。
HashMap 可以插入键为 null 的 Entry。
HashMap 的迭代器是 fail-fast 迭代器。
HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
2. 解决hash冲突的方法

有四种：开放定址法，再哈希法，链地址法，建立公共溢出区。

开放定址法

开放定址法包括线性探测再散列、二次探测再散列、伪随机探测再散列。

1）线性探测再散列
dii=1，2，3，…，m-1
冲突发生时，顺序查看表中下一个单元，直到找出一个空单元或查遍全表。

2）二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
冲突发生时，在表的左右进行跳跃式探测，比较灵活。

3）伪随机探测再散列
di=伪随机数序列
先建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

再哈希法

同时构造多个不同的哈希函数
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法

所有哈希地址为i的元素构成一个单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

3. ConcurrentHashMap

JDK1.7的底层是：segments+HashEntry数组。 
JDK1.8的底层是：散列表+红黑树。在数组层面采用CAS无锁化机制，节点下面使用synchronized保证线程安全。
通过volatile保证变量对其他线程的可见性；一些变量包括size，isEmpty，containsValue都是无法准确返回的。

存储结构

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

这里需要说明一下，ForwardingNode是一个特殊的节点，hash值为-1，存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当扩容时标记头部节点是否为空，是否迁移好了。

final class ForwardingNode extends Node {
    final Node[] nextTable;
    ForwardingNode(Node[] tab) {
        super(MOVED, null, null, null);
        this.nextTable = tab;
    }
}
下面是一些基本变量：

   //散列表
   transient volatile Node[] table;
   //扩容的时候有值，下一张表
   private transient volatile Node[] nextTable;
   //基础计数器，通过CAS更新
   private transient volatile long baseCount;
   //控制初始化或扩容的变量
   //-1：表示正在初始化
   //-N：N-1个线程在进行扩容
   //0：缺省值
   //初始化之后，保存下一次扩容的大小
   private transient volatile int sizeCtl;
   //分割表时用的索引值
   private transient volatile int transferIndex;
   //与计算size相关
   private transient volatile int cellsBusy;
   private transient volatile CounterCell[] counterCells;
put操作

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        //对key进行散列，获取哈希值
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            //当链表为空，进行初始化
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //如果这个哈希值直接可以存到数组，就直接插入进去（不用加锁）
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break; 
            }
            //插入的位置是表的链接点时，表明在扩容，帮助当前线程扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                //加锁
                synchronized (f) {
                    //节点的处理方式
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                     ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //按照树的方式插入
                        else if (f instanceof TreeBin) {
                            Node p;
                            binCount = 2;
                            if ((p = ((TreeBin)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                //链表长度>8，把链表转换为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        } 
        //判断扩容
        addCount(1L, binCount);
        return null;
    }
过程和HashMap的put有点类似：

1. 当哈希表为空则初始化。

2. 如果table对应坑位为空，就用CAS的方式直接插入。

3.如果当前坑位不为空且正在扩容，当前线程帮忙一起扩容helpTrasfer()

4.如果当前节点下有大于1个节点且为没在扩容，就对table[i]加锁，按下面2种情况：

判断p当前的节点是否为TreeNode，是的话用红黑树的插入方式
链表的存储方式，尾插法
initTable

    private final Node[] initTable() {
        Node[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            //有线程正在初始化，告诉其他线程不要进来了
            if ((sc = sizeCtl) < 0)
                Thread.yield(); 
            //设置为-1说明本线程正在初始化
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node[] nt = (Node[])new Node[n];
                        table = tab = nt;
                        //相当于0.75*n设置一个扩容阈值
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }
如何保证初始化时线程安全？

如果一个线程发现sizeCtl<0，意味着另外的线程执行CAS操作成功，当前线程只需要让出cpu时间片。保证只有一个线程在初始化。

扩容操作 transfer

扩容的时机？

当addCount()>sizeCtl或者put时当前坑位在扩容，触发helpTransfer()。
转红黑树的时候如果节点的数量不超过64，不能进行转红黑树，而是要扩容，然后调整map的节点。

    private final void transfer(Node[] tab, Node[] nextTab) {
        int n = tab.length, stride;
        //通过计算CPU核心数与Map数组的长度得到每个CPU要帮助处理多少个桶
        //并且每个线程的处理都是平均的。默认每个线程处理16个桶
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        //根据当前数组长度n，新建一个两倍长度的数组nextTable
        if (nextTab == null) {            // initiating
            try {
                //扩容两倍
                Node[] nt = (Node[])new Node[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {
                //扩容失败，sizeCtl使用int最大值
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            //更新成员变量
            nextTable = nextTab;
            //更新转移下标，n就是老的table的length
            transferIndex = n;
        }
        //初始化ForwardingNode节点，其中保存了新数组nextTable的引用，
        //当别的线程发现这个槽位中是fwd类型的节点，则跳过这个节点
        int nextn = nextTab.length;
        ForwardingNode fwd = new ForwardingNode(nextTab);
        //首次推进为true，true表示需要再次推进一个目标（i--）
        //如果是false，不能推进下标，需要当前的下标处理完毕才能继续推进
        boolean advance = true;
        //完成状态，true则表示结束此方法
        boolean finishing = false; 
        //死循环，处理每个槽位中的链表元素，通过CAS设置transferIndex属性值，
        //i指当前处理的槽位序号，bound指当前线程可以处理的当前桶区间最小下标
        //，先处理槽位15的节点
        for (int i = 0, bound = 0;;) {
            Node f; int fh;
            //如果当前线程可以向后推进，这个循环就是控制i递减
            //同时，每个线程都会进入这里取得自己需要转移的桶的区间
            while (advance) {
                int nextIndex, nextBound;
                //
                if (--i >= bound || finishing)
                    //这里设置 false，是为了防止在没有成功处理一个桶的情况下
                   //却进行了推进
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    //如果小于等于0，说明没有区间了 ，i 改成 -1，
                    //推进状态变成 false，不再推进，表示，扩容结束了，
                    //当前线程可以退出了
                    // 这个 -1 会在下面的 if 块里判断，从而进入完成状态判断
                    i = -1;
                    advance = false;
                }
                //CAS 修改 transferIndex，即 length - 区间值，
                //留下剩余的区间值供后面的线程使用
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    //这个值就是当前线程可以处理的最小当前区间最小下标
                    bound = nextBound;
                    //初次对i 赋值，这个就是当前线程可以处理的当前区间的最大下标
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                // 如果完成了扩容
                if (finishing) {
                    // 删除成员变量
                    nextTable = null;
                    // 更新 table
                    table = nextTab;
                    // 更新阈值
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            //获取老 tab i 下标位置的变量，如果是 null，就使用 fwd 占位。
            else if ((f = tabAt(tab, i)) == null)
                // 如果成功写入 fwd 占位，再次推进一个下标
                advance = casTabAt(tab, i, null, fwd);
            // 说明别的线程已经处理过了，再次推进一个下标
            else if ((fh = f.hash) == MOVED)
                advance = true; 
            else {
                //说明这个位置有实际值了，且不是占位符。
                //对这个节点上锁。为什么上锁，防止 putVal 的时候向链表插入数据
                //处理槽位14的节点，是一个链表结构，
                //先定义两个变量节点ln和hn，
                //分别保存hash值的第X位为0和1的节点
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node ln, hn;
                        if (fh >= 0) {
                            //runBit为0或1，f是节点，fh是节点的hash值
                            int runBit = fh & n;
                            Node lastRun = f;
                            //通过遍历链表，记录runBit和lastRun
                            for (Node p = f.next; p != null; p = p.next) {
                                // 取与桶中每个节点的 hash 值
                                int b = p.hash & n;
                                if (b != runBit) {
                                    //runBit是节点hash值，lastRun是某个节点，
                                    //作为后续循环的结束条件
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            // 如果最后更新的 runBit 是 0 ，设置低位节点
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            // 如果最后更新的 runBit 是 1， 设置高位节点
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            //重新遍历链表，以lastRun节点为终止条件，
                            //这样就是避免无谓的循环（（lastRun 后面都是相同的取与结果））
                            //根据第X位的值分别构造ln链表和hn链表
                            for (Node p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                // 如果与运算结果是 0，创建低位节点
                                if ((ph & n) == 0)
                                    ln = new Node(ph, pk, pv, ln);
                                else
                                    hn = new Node(ph, pk, pv, hn);
                            }
                            //通过CAS把ln链表设置到新数组的i位置，hn链表设置到i+n的位置
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        //如果该槽位是红黑树结构，则构造树节点lo和hi，
                        //遍历红黑树中的节点，同样根据hash&n算法，把节点分为两类，
                        //分别插入到lo和hi为头的链表中，
                        //根据lo和hi链表中的元素个数分别生成ln和hn节点
                        else if (f instanceof TreeBin) {
                            TreeBin t = (TreeBin)f;
                            TreeNode lo = null, loTail = null;
                            TreeNode hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode p = new TreeNode
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            //lo链表的元素个数小于等于UNTREEIFY_THRESHOLD，
                            //默认为6，则通过untreeify方法把树节点链表转化成普通节点链表
                            //否则判断hi链表中的元素个数是否等于0
                            //如果等于0，表示lo链表中包含了所有原始节点，
                            //则设置原始红黑树给ln，否则根据lo链表重新构造红黑树。
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin(hi) : t;
                            //通过CAS把ln设置到新数组的i位置，hn设置到i+n位置
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }
扩容的过程：

1. 根据当前数组长度n，新建一个两倍长度的数组（nextTable）。
2. 初始化ForwardingNode节点，其中保存了新数组nextTable的引用，在处理完每个槽位的节点之后当作占位节点，表示该槽位已经处理过了。
3. 处理每个槽位中链表元素，通过CAS设置transferIndex属性值，i为当前处理的槽位序号，bound指需要处理的槽位边界，先处理槽位最后一个节点。
4. 假设槽位15没有节点，通过CAS插入在第二步中初始化ForwardingNode节点，告诉其他线程该槽位已经处理过了。
5. 如果槽位15已经被处理过了，那么线程B处理到这会发现该节点的hash是-1，直接跳过，继续处理下一个槽位14的节点。
6. 如果槽位14节点是链表，则先定义两个变量节点ln（lowNode）和hn（highNode），分别存储hash值的第X位为0和1的节点（当前数组容量为2^x）。使用fn&n可以把链表中的元素区分成2类，A类是hash值的第X为为0，B类是hash值的第X位为1，并通过lastRun记录最后需要处理的节点
7. 遍历链表，记录runBit和lastRun；重新遍历链表，以lastRun节点为终止条件，根据第X位的值分别构造ln链表和hn链表。
ln链表（0）：和原来链表相比，顺序已经不一样了
hn链表（1）：顺序与原链表一致
通过CAS把ln链表设置到新数组的i位置，hn链表设置到i+n的位置；

8. 如果该槽位是红黑树结构，则构造节点lo和hi。遍历红黑树中的节点，同样根据hash&n算法，把节点分为两类，分别插入到lo和hi为头的链表中，根据lo和hi链表中元素个数分别生成ln和hn节点。
ln的生成逻辑：
如果lo链表元素个数<=UNTREEIFY_THRESHOLD（默认是6），则通过untreeify方法把树节点链表转化成普通节点链表；
否则判断hi链表中的元素个数是否等于0，若是0，表示lo链表中包含了所有原始节点，则设置原始红黑树给ln，否则根据lo链表重新构造红黑树。

同样的通过CAS把ln设置到新数组的i位置，hn设置到i+n位置。

get操作

    public V get(Object key) {
        Node[] tab; Node e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            //在桶上，就直接获取
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            //在树形结构上
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                //在链表上
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }
get比较简单和HashMap一样，不多赘述。

4. LinkedHashMap

内部维护了双向链表，用于维护插入或LRU顺序。accessOrder决定是否维护插入顺序，默认false。 

    transient LinkedHashMap.Entry head;

    transient LinkedHashMap.Entry tail;

    final boolean accessOrder;
afterNodeAccess(Node p)和afterNodeInsertion(boolean evict) 是维护顺序的重要方法。

afterNodeAccess(Node p)

当节点被get时，如果accessOrder为true，会将被get的节点移到链表尾部，相当于维护了LRU顺序，保证尾部是最近访问的，首部是最久未访问的。

    void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            p.after = null;
            //移动p，处理before和after前后关系，然后把p放到last后
            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(boolean evict)

当节点被put时，如果removeEldestEntry()返回true，就干掉首个节点。removeEldestEntry()需要子类实现，默认为false。如果要用LinkedHashMap实现一个LRU缓存，需要实现removeEldestEntry()，当容量超过规定的最大容量时，removeEldestEntry()返回true，put时就会删掉最久没访问的节点。

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