Java 容器（Map）

本篇文章主要讲解Map下的实现类，重点讲解HashMap，ConcurrentHashMap。容器中其它文章看下面连接：

Collection下List，Set，Queue讲解

红黑树详解

容器相关问题

1 Map 1.1 hashMap源码

javaguide-hashMap讲述

红黑树详解

数组+链表+红黑树

1.1.1 类的常量

// 序列号
private static final long serialVersionUID = 362498820763181265L;

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;


static final int TREEIFY_THRESHOLD = 8;


static final int UNTREEIFY_THRESHOLD = 6;


static final int MIN_TREEIFY_CAPACITY = 64;

1.1.2 类的字段

transient Node[] table;


transient Set> entrySet;


transient int size;


transient int modCount;


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


final float loadFactor;

1.1.3 Node

static class Node implements Map.Entry {
    //key经过hash计算的值
    final int hash;
    final K key;
    V value;
    Node next;

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(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;
    }
}

1.1.4 构造方法

hashMap构造方法采用的都是懒加载。

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;
    //tableSizeFor 因为数组的长度必须是2的n次幂，该方法返回2的n次幂。
    this.threshold = tableSizeFor(initialCapacity);
}


public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

1.1.5 put方法

hashMap 在第一次put值的时候才会初始化，并不是在构造函数中初始化，所以put操作中首先会判断是否初始化过，如果没有就会执行resize()方法

插入值分为4种情况：

所在桶位置头节点是null，那么就创建一个Node 放入该位置所在桶位置头节点不是null，判断key值是否和插入的key值是否相等，如果相等，替换value值(有一个参数决定)即可所在桶位置头节点不是null并且是树节点，执行树的插入流程，首先找到树的根节点，然后遍历树，在遍历过程中，如果出现key相同的情况，那么直接返回该节点，后序步骤会替换value值(有参数决定)，如果遍历到叶子节点，那么就创建一个新节点插入进去，然后进行树的自平衡操作。最后有一个方法保证根节点是该桶位置的头节点。所在桶位置头节点不是null并且是链表节点，那么遍历链表节点，检查key值是否相同，相同就替换value值(有一个参数决定)，如果没有找到，那么就插入到链表的结尾处，然后检查链表的长度，超过8并且数组长度达到64就会树化。判断树化流程：首先判断table数组的长度是否达到了树化阈值(默认64)，如果没有达到，那么进行扩容操作。如果达到了，那么将这个桶内的链表(Node)，转化为链表(TreeNode) 。然后 执行treeify方法 进行树化。树化流程：将链表(TreeNode) 树化，并且在每一次节点插入树中时执行balanceInsertion方法自平衡**，最后执行**moveRootToFront方法保证根节点是桶位置的第一个节点即头节点，

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab: 当前的节点数组
    // p: 当前的key的索引位置上的节点 tab[i = (n - 1) & hash]
    // n: 当前节点数组的长度
    // i: 当前key的索引位置
    Node[] tab; Node p; int n, i;
    //判断节点数组是否为空，或者节点数组长度为0 如果是那么进行resize()
    // 从这里可以看出HashMap在第一次put时，才进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //判断key所在位置的节点是否为空，如果是，那么直接创建一个新节点放到这个位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //此时说明key的位置上的节点不为null，那么开始操作链表
        // e : 当前节点
        // k : 当前节点的 key值
        Node e; K k;
        // 当前p是key的位置上的第一个节点，如果该节点和key相同，
        // 那么就可以直接将value替换掉该节点的value值（代码在下面）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) //如果头节点的key和要放入的key不相同，那么判断头节点是否是树节点
            //是树节点，就进行树的操作
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        else { // 这里说明头节点的key和放入的key不同并且头节点是链表节点
            //遍历操作，直到链表的最后一个节点或者找到与放入的key相同的节点停止遍历
            for (int binCount = 0; ; ++binCount) {
                //e等于最后一个节点，说明不存在与key相同的节点，那么直接放到链表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //判断 节点数量是否超过TREEIFY_THRESHOLD，树化的条件是否达到
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //进一步判断数组长度是否达到条件，达到：进行树化，未达到：扩容
                        treeifyBin(tab, hash);
                    break;
                }
                //遍历到和key相同的节点，将该节点赋值给e
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //e != null说明链表中存在与key相同的节点
        if (e != null) { // existing mapping for key
            //重复key的节点的value
            V oldValue = e.value;
            //如果onlyIfAbsent为false，那么就修改重复key的节点的value值。旧值为null直接修改为value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //访问后回调
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //结构性修改
    ++modCount;// 修改一个节点的value值不会+1
    //实际大小，大于阈值 进行扩容
    if (++size > threshold)
        resize();
    //插入后回调
    afterNodeInsertion(evict);
    return null;

1.1.6 resize方法

首先计算capacity，thershold的值，然后创建一个新的散列表数组（长度为旧数组长度<<1），最后数据迁移。

数据迁移分为3种情况：

迁移桶位置只有一个节点，直接计算在新数组中的位置放入。

将桶位置的链表分为两个链表：1.低位链表，2.高位链表。最后直接将链表放入对应位置。原数组中一个桶位置里的链表的节点，数据迁移到新的数组中，只会进入新数组两个桶位置之一，这两个桶分别是与原数组相同桶号的位置，原数组桶号+原数组长度。迁移桶位置是一个树结构，树结构中其实还维护了一个链表结构，所以迁移数据和链表迁移是相同的，不同的是，在得到低位高位链表之后的时候会检查这两个链表节点的数量，如果<=6 那么就转化为链表结构(Node)，否则还是转化为树结构，放入对应桶位置。

final Node[] resize() {
    // oldTab：旧的散列表数组，扩容之前散列表数组
    Node[] oldTab = table;
    // oldCap: 旧的散列表的容量，扩容之前散列表容量
    //oldTab == null 时 说明还没有初始化
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // oldThr: 旧的用于判断扩容的阈值，扩容之前散列表数组扩容的条件
    int oldThr = threshold;
    // newCap：新的散列表容量，扩容之后散列表容量
    // newThr: 新的阈值，扩容之后散列表数组再次扩容的条件
    int newCap, newThr = 0;
    // oldCap > 0 说明 说明散列表中已经有节点了，是一次正常的到达条件进行扩容
    if (oldCap > 0) {
        // 判断旧的散列表的容量是否大于最大容量，如果是就不在进行扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新的散列表容量 = 旧的散列表容量*2 并且小于最大容量，并且 旧的容量大于最小的容量
        // 为什么要判断旧的容量大于最小容量？因为HashMap的构造函数可以初始化容量。
        // 满足条件-> 新的阈值 = 旧的阈值 * 2;
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap = 0  oldThr > 0; 什么时候会出现这种情况呢？ 可以看HashMap的构造函数
    // 1, new HashMap<>(int initialCapacity); 这个构造方法调用的下面的构造方法。
    // 2, new HashMap<>(int initialCapacity, float loadFactor); 在这个构造方法中 threshold = 旧散列表容量（是2的n次幂）
    // 3, new HashMap<>(Map m); Map是有数据的，同上面一样，threshold = 旧散列表容量（是2的n次幂）
    // 是使用上面三种构造方法创建的HashMap 就会 进入条件，新的容量就等于旧的阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;

    // oldCap = 0, oldThr = 0; //什么时候会出现这种情况呢？
    // new HashMap<>() 不传参数的构造方法;
    // 那么新的容量就等于默认值(16) 新的阈值就根据默认值计算出来
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新的阈值等于0，说明新的阈值没有赋值，那么就根据现在新的容量赋值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 新的阈值赋值给 threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建一个新的散列表数组，并赋值给当前table
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    // 下面要进行将旧的散列表数组中的值，重新放到新的散列表数组中，如果旧的数组=null，那么就没必要执行了，直接返回新的散列表
    if (oldTab != null) {
        //遍历旧的散列表，进行节点迁移工作
        for (int j = 0; j < oldCap; ++j) {
            // e: 当前节点
            Node e;
            //当前节点不等于null，才会进行迁移工作
            if ((e = oldTab[j]) != null) {
                //将旧的散列表中当前位置=null，因为当前节点要放入新的散列表数组，方便JVM垃圾回收
                oldTab[j] = null;
                //如果当前节点的下一个节点=null，说明当前桶位置只有一个节点
                if (e.next == null)
                    //直接计算当前节点在新的散列表中的位置，直接放入当前节点
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) //当前节点不等于null，是树节点
                    // 执行树节点的操作
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order // 说明当前桶位置是一个链表结构
                    // 将该桶位置的链表的节点，放入新散列表数组中，只会有两种情况：
                    // 1, 该节点放入新散列表数组中的桶位置 = 该节点旧散列表数组中的桶位置
                    // 2, 该节点放入新散列表数组中的桶位置 = 该节点旧散列表数组中的桶位置 + 旧散列表数组长度
                    // 为什么呢？ 例如：
                    // 旧数组容量：16，新数组容量：32，那么在旧数组桶位置为 15 的节点 应该放入新数组那个桶内
                    // 在旧数组桶位置为 15 的节点 说明 该节点的 hash值为  ....01111 或 ....11111
                    // 为什么呢 因为 15 = hash & 1111(16 - 1) 计算而来
                    // 那么 在新的散列表数组中 桶位置 =  hash & 11111(32 - 1) = 15 或 31(15 + 16)

                    //综上：在一个桶位置的节点，放入到新的散列表中，只会有两个桶位置1,原索引位置2,原索引+原容量位置。所以分为以下两种链表


                    // 低位链表：存放在扩容之后的数组的下标位置与旧数组的下标位置一致
                    Node loHead = null, loTail = null;
                    // 高位链表：存放在扩容之后的数组的下标位置为 旧数组下标位置 + 旧数组的长度
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        // 这个条件 就是判断 当前节点应该放入低位链表还是高位链表
                        // 还是上面的例子，e.hash = ....01111 || ....11111 oldCap = 10000
                        // 如果是....01111 那么 ....01111 & 11111(32 - 1) = 15; 放入低位链表
                        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);
                    //将低位链表放入新的散列表数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //将高位链表放入新的散列表数组
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1.1.7 get方法

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//get 方法实际逻辑执行代码是 getNode()方法，传入 hash(key)和key
final Node getNode(int hash, Object key) {
    // hash：hash(key)
    // tab: 当前的散列表数组
    // n: 当前散列表数组的容量
    // first: 根据key的hash算法得到的hash值与n-1 计算出的桶位置上的头节点
    // e: 用于遍历链表查找key的变量
    // k: first.Key
    Node[] tab; Node first, e; int n; K k;
    // 判断 当前散列表!=null && 容量>0 && 计算出的桶位置上的头节点!= null 如果不满足说明没有找到key
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 根据key的hash值计算出的桶位置上的节点的key 就和查询的key相同，那么直接返回头节点。
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 计算出的头节点不是要查询的key，那么就说明当前桶位置是树，或者链表
        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;

1.1.8 remove方法

删除一个键值对，先查找到之后，在执行删除操作。

//remove有两个方法，这个方法就是说：如果存在key，那么就删除这个key-value对
public V remove(Object key) {
    Node e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
//如果存在key并且key对应的value与传入的value相同，那么就删除这个key-value对
public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }


final Node removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // tab: 当前table数组
    // p: 要删除的key经过计算的桶位置的头节点
    // n: table数组长度
    // index: 要删除key的桶位置的索引
    Node[] tab; Node p; int n, index;
    // 首先还是判断数组是否存在，长度是否大于0，桶位置是否有节点，如果不满足直接返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // node: 存放与要删除key相同的节点（即满足删除条件的）、
        // e: 遍历链表的临时变量
        // k: 用于和key比较
        // v: 用于和value比较
        Node node = null, e; K k; V v;
        //如果桶位置的头节点就是要删除的，那么交给node
        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
                node = ((TreeNode)p).getTreeNode(hash, key);
            else {
                //该桶位置是链表，那么遍历查找，找到后交给node
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // node != null 说明找到了要与key相同的节点node，后面的判断是如果要求value相同那么value也要相同
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode) // 如果是树节点，执行树的删除操作
                ((TreeNode)node).removeTreeNode(this, tab, movable);
            else if (node == p) // 如果直接等于头节点，那么直接将头节点的下一个节点放到桶位置上
                tab[index] = node.next;
            else// 如果是链表中的某一个节点，那么指向node.next
                p.next = node.next;
            //只要执行了删除，那么modCount就+1，size-1;
            ++modCount;
            --size;
            //linkedHashMap 的后序操作
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

1.1.9 replace方法

@Override
public V replace(K key, V value) {
    Node e;
    //查找key的节点
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node e; V v;
    //查找到的节点的key == key value = oldValue
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}
//调用的getNode()方法和get()方法中的调用的getNode()方法相同，看get()方法即可。

1.2 linkedHashMap源码

看到linkedHashMap中并没有什么操作数据结构的方法，也就是说linkedHashMap操作数据结构（比如put一个数据），和HashMap操作数据的方法完全一样，无非就是细节上有一些的不同罢了。

因为linkedHashMap 就是基于HashMap来实现的，只是一些方法重写了，来完成对双向链表的维护，通过put流程和remove流程看一下，linkedHashMap是如何通过重写利用多态来完成对双向链表的维护。

1.2.1 类的字段

// 版本序列号
private static final long serialVersionUID = 3801124242820219131L;


transient linkedHashMap.Entry head;


transient linkedHashMap.Entry tail;


final boolean accessOrder;

// 看下面的一个示例：
HashMap map = new linkedHashMap<>();
map.put(1,3);
map.put(2,5);
map.put(3,6);
System.out.println(map);//{1=3, 2=5, 3=6}
System.out.println(map.get(2));//5
System.out.println(map);//{1=3, 2=5, 3=6}

HashMap map1 = new linkedHashMap(5, 0.75f, true);
map1.put(1,3);
map1.put(2,5);
map1.put(3,6);
System.out.println(map1);//{1=3, 2=5, 3=6}
System.out.println(map1.get(2));//5
System.out.println(map1);//{1=3, 3=6, 2=5}
//当accessOrder参数为true的时候 访问一个元素之后，就会将该元素放到链表的尾部

1.2.2 Entry

static class Entry extends HashMap.Node {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

1.2.3 构造方法

linkedHashMap 一共有5个构造方法，每一个构造方法都会先调用父类（HashMap）的构造方法，其实linkedHashMap就是在HashMap的基础上扩展的，多维护一个双向链表。

AccessOrder 字段 在没有显示的赋值为true的情况下，都为false。

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 m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}


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

1.2.4 put 流程

linkedHashMap使用的put方法就是HashMap的put操作，put方法讲解 去看HashMap即可。put操作与linkedHashMap相关的有三个地方：

创建Node节点执行afterNodeAccess()方法执行afterNodeInsertion()方法

1，创建Node节点

newNode(hash, key, value, null); //创建一个Node节点

看一下newNode方法

// HashMap中的newNode方法
Node newNode(int hash, K key, V value, Node next) {
    return new Node<>(hash, key, value, next);
}
//linkedHashMap中的newNode方法
Node newNode(int hash, K key, V value, Node e) {
    linkedHashMap.Entry p =
        new linkedHashMap.Entry(hash, key, value, e);
    //添加一个节点到链表末尾
    linkNodeLast(p);
    return p;
}

可以知道，当我们使用linkedHashMap的时候，put方法中执行newNode 就会执行linkedHashMap中重写的newNode方法，不会执行HashMap中的newNode方法。

然后我们再看一下linkNodeLast方法。

// link at the end of list 添加一个节点到链表末尾
private void linkNodeLast(linkedHashMap.Entry p) {
    linkedHashMap.Entry last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

这就完成了向链表中添加节点的功能。

2，afterNodeAccess(e) 访问后回调

在Map中添加一个key-value，如果key存在，那么有两种处理方式将value替换（默认）或者不替换直接返回。

当put操作一个已经存在的key时，就说明这个key可能会使用的频繁，那么就会考虑要不要将该节点加到链表的末尾。是否执行这个操作，决定性的是在创建linkedHashMap时是否指定了accessOrder为true

afterNodeAccess方法就是做这个判断的。

// hashMap中对这个方法只有声明
void afterNodeAccess(Node p) { }

//linkedHashMap 中

void afterNodeAccess(Node e) { // move node to last
    linkedHashMap.Entry last;
    // accessOrder在构造方法中指定的值，默认情况下为false
    if (accessOrder && (last = tail) != e) {
        linkedHashMap.Entry p =
            (linkedHashMap.Entry)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;
    }
}

3，afterNodeInsertion方法

该方法：是否要删除头节点。在linkedHashMap中不会删除头节点，至于为什么不会看下面代码

// hashMap对该方法的声明
void afterNodeInsertion(boolean evict) { }

//linkedHashMap对该方法的实现
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);
    }
}
// 直接返回false
protected boolean removeEldestEntry(Map.Entry eldest) {
    return false;
}

put流程到这里就结束了。下面看删除一个节点的流程。

1.2.5 remove 流程

同样，删除操作使用的还是HashMap的方法，这里只看与linkedHashMap相关的地方，remove详细流程看上面HashMap的讲解。

afterNodeRemoval()：删操作执行完之后，执行的回调方法。

//HashMap只对该方法进行了声明
void afterNodeRemoval(Node p) { }

//linkedHashMap的实现

void afterNodeRemoval(Node e) { // unlink
    linkedHashMap.Entry p =
        (linkedHashMap.Entry)e, b = p.before, a = p.after;
    p.before = p.after = null;//移除引用，方便GC
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

上面就是linkedHashMap对链表的删除操作。

1.3 HashTable 源码

底层结构：数组+链表

HashMap中table数组的的最大长度是1 << 30，HashTable中table数组的最大长度：Integer.MAX_VALUE - 8

HashMap是懒加载，Hashtable是在构造函数中就加载table数组，并且HashMap的容量一定是2的n次方，HashTable就是自己指定，默认情况下是11，不会为0，最小为1 。

HashTable的value值不能为null。

HashTable计算hash值是直接调用hashCode方法，计算桶位置(hash & 0x7FFFFFFF) % tab.length

0x7FFFFFFF 的意思

7fffffff是8位16进制每个16进制代表4个bit8✖4bit=32bit=4Bytef的二进制为：1111，7的二进制位0111int类型的长度位4Byte左边起，第一位为符号位，0代表正数，1代表负数0x7fffffff代表int的最大值

对外提供的方法，add，put，get，remove等 都是用了synchronized修饰，是线程安全的。

1.3.1 类的字段

和HashMap不同的是：

HashMap中table数组的的最大长度是1 << 30，HashTable中table数组的最大长度：Integer.MAX_VALUE - 8

private transient Entry[] table;


private transient int count;


private int threshold;


private float loadFactor;


private transient int modCount = 0;


private static final long serialVersionUID = 1421746759512286392L;

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

private transient volatile Set keySet;
private transient volatile Set> entrySet;
private transient volatile Collection values;
// Types of Enumerations/Iterations
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;

1.3.2 Entry

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

    protected Entry(int hash, K key, V value, Entry next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }

    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Entry<>(hash, key, value,
                           (next==null ? null : (Entry) next.clone()));
    }

    // Map.Entry Ops

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public V setValue(V value) {
        if (value == null)
            throw new NullPointerException();

        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;

        return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
            (value==null ? e.getValue()==null : value.equals(e.getValue()));
    }

    public int hashCode() {
        return hash ^ Objects.hashCode(value);
    }

    public String toString() {
        return key.toString()+"="+value.toString();
    }
}

1.3.3 构造方法

HashMap是懒加载，Hashtable是在构造函数中就加载table数组，并且HashMap的容量一定是2的n次方，HashTable就是自己指定，默认情况下是11，不会为0，最小为1 。

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() {
    // 默认情况下 table数组的长度是11
    this(11, 0.75f);
}


public Hashtable(Map t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

1.3.4 put方法

HashTable的value值不能为null，

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    // tab：hash数组
    Entry tab[] = table;
    // 添加key的hash值
    int hash = key.hashCode();
    // 计算桶位置，hash值 & Integer的最大值 % tab数组长度
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // entry 当前桶位置的头节点
    Entry entry = (Entry)tab[index];
    // 遍历当前桶位置的链表
    for(; entry != null ; entry = entry.next) {
        // 遇到与key相同的节点，将value的值替换
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 添加到链表的头节点，头插法
    addEntry(hash, key, value, index);
    return null;
}



private void addEntry(int hash, K key, V value, int index) {
    modCount++;
    // tab： 散列表数组
    Entry tab[] = table;
    // 当前节点数量 大于等于 阈值时扩容
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        // 扩容后重新计算要添加的节点的桶位置
        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    // e：当前桶位置的头节点
    Entry e = (Entry) tab[index];
    // 创建一个节点，将新节点放到链表的first位置
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

1.3.5 rehash方法

@SuppressWarnings("unchecked")
protected void rehash() {
    // 扩容前数组长度
    int oldCapacity = table.length;
    // 扩容前数组
    Entry[] oldMap = table;

    // overflow-conscious code
    // 新的数组长度：旧数组长度 * 2 + 1
    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 old = (Entry)oldMap[i] ; old != null ; ) {
            Entry e = old;
            old = old.next;
            // 计算新的桶位置
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            // 放入新的数组中
            e.next = (Entry)newMap[index];
            newMap[index] = e;
        }
    }
}

1.4 ConCurrentHashMap 源码

ConcurrentHashMap参考

1.4.1 基本数据结构

ConcurrentHashMap内部维护了一个Node类型的数组：table

table一共包含 4 种不同类型的桶，不同的桶用不同颜色表示，这是jdk1.8版本的特点；

[注]：TreeBin结点所连接的是一颗红黑树，红黑树的结点用TreeNode表示，所以ConcurrentHashMap中实际上一共有 五 种不同类型的Node结点；

这里我们思考一个问题，为什么没有直接用TreeNode呢？

主要是因为红黑树的操作比较复杂，包括构建、左旋、右旋、删除，平衡等操作，用一个代理结TreeBin来包含这些复杂操作，其实是一种 “职责分离”的思想，另外TreeBin中也包含了一些加/解锁操作。

数组的每一个位置table[i]代表一个桶，当插入键值对时，会根据键的hash值映射到不同的桶位置；

1.4.2 节点定义

1.4.2.1 Node

Node是其它四种类型结点的父类；默认链接到table[i]，即桶上的结点就是Node结点；当出现hash冲突时，Node结点会首先以链表的形式链接到table上：当结点数量超过一定数目时，链表会转化为红黑树；

【注】：因为链表查找的时间复杂度为O(n)，而红黑树是一种平衡二叉树，其平均时间复杂度为O(logn)，这样就提高了效率。

static class Node implements Map.Entry {
    final int hash;
    final K key;
    volatile V val; // volatile修饰 保证了可见性，有序性
    volatile Node next;

    Node(int hash, K key, V val, Node next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    
    Node find(int h, Object k) {
        Node e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

1.4.2.2 ForwardingNode

ForwardingNode结点仅仅在扩容时才会使用

static final class ForwardingNode extends Node {
    final Node[] nextTable;
    ForwardingNode(Node[] tab) {
        super(MOVED, null, null, null);
        this.nextTable = tab;
    }
    // 在新的数组(nextTable)上进行查找
    Node find(int h, Object k) {
        // loop to avoid arbitrarily deep recursion on forwarding nodes
        outer: for (Node[] tab = nextTable;;) {
            Node e; int n;
            if (k == null || tab == null || (n = tab.length) == 0 ||
                (e = tabAt(tab, (n - 1) & h)) == null)
                return null;
            for (;;) {
                int eh; K ek;
                if ((eh = e.hash) == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                if (eh < 0) {
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode)e).nextTable;
                        continue outer;
                    }
                    else
                        return e.find(h, k);
                }
                if ((e = e.next) == null)
                    return null;
            }
        }
    }
}

1.4.2.3 ReservationNode

static final class ReservationNode extends Node {
    ReservationNode() {
        super(RESERVED, null, null, null);
    }
    Node find(int h, Object k) {
        return null;
    }
}

1.4.2.4 TreeNode

TreeNode是红黑树的结点，TreeNode不会直接链接到桶上面，而是由TreeBin链接，TreeBin会指向红黑树的根结点;

static final class TreeNode extends Node {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    //prev指针是为了方便删除，
    //删除链表的非头结点时，需要知道它的前驱结点才能删除，所以直接提供一个prev指针
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node next,
             TreeNode parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

    Node find(int h, Object k) {
        return findTreeNode(h, k, null);
    }

    
    final TreeNode findTreeNode(int h, Object k, Class kc) {
        if (k != null) {
            TreeNode p = this;
            do  {
                int ph, dir; K pk; TreeNode q;
                TreeNode pl = p.left, pr = p.right;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.findTreeNode(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
        }
        return null;
    }
}

1.4.2.5 TreeBin

TreeBin相当于TreeNode的代理结点；TreeBin会直接链接到 table[i] 上，该结点提供了一系列红黑树相关的操作，以及加锁、解锁操作：

static final class TreeBin extends Node {
    TreeNode root;					// 红黑树结构的根结点
    volatile TreeNode first;		// 链表结构的头结点
    volatile Thread waiter;				// 最近的一个设置WAITER标识位的线程
    volatile int lockState;				// 整体的锁状态标识位，0为初始态
    // values for lockState
    static final int WRITER = 1; // 二进制001，红黑树的写锁状态
    static final int WAITER = 2; // 二进制010，红黑树的等待获取写锁状态（优先锁，当有锁等待，读就不能增加了）
    // 二进制100，红黑树的读锁状态，读可以并发，每多一个读线程，lockState都加上一个READER值，
    static final int READER = 4; 
    
    static int tieBreakOrder(Object a, Object b) {
        int d;
        if (a == null || b == null ||
            (d = a.getClass().getName().
             compareTo(b.getClass().getName())) == 0)
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?  -1 : 1);
        return d;
    }

    // 将以b为头结点的链表转换为红黑树
    TreeBin(TreeNode b) {...}
    // 通过lockState,对红黑树的根结点➕写锁.
    private final void lockRoot() {
        if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
            contendedLock(); // offload to separate method ，Possibly blocks awaiting root lock.
    }

    //释放写锁
    private final void unlockRoot() { lockState = 0; }

    //  从根结点开始遍历查找，找到“相等”的结点就返回它，没找到就返回null，当存在写锁时，以链表方式进行查找，后会面会介绍
    final Node find(int h, Object k) {... }

    
    final TreeNode putTreeval(int h, K k, V v) {...} 
    
    final boolean removeTreeNode(TreeNode p) {...}

    // 以下是红黑树的经典操作方法，改编自《算法导论》
    static  TreeNode rotateLeft(TreeNode root , TreeNode p) { ...}
    static  TreeNode rotateRight(TreeNode root , TreeNode p) {...}
    static  TreeNode balanceInsertion(TreeNode root , TreeNode x) {...}
    static  TreeNode balanceDeletion(TreeNode root, TreeNode x) { ... }
    static  boolean checkInvariants(TreeNode t) {...} //递归检查红黑树的正确性
    private static final long LOCKSTATE= U.objectFieldOffset(TreeBin.class, "lockState");
}

1.4.3 类的属性 1.4.3.1 常量

private static final int MAXIMUM_CAPACITY = 1 << 30;


private static final int DEFAULT_CAPACITY = 16;


static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


private static final int DEFAULT_CONCURRENCY_LEVEL = 16;


private static final float LOAD_FACTOR = 0.75f;


static final int TREEIFY_THRESHOLD = 8;


static final int UNTREEIFY_THRESHOLD = 6;


static final int MIN_TREEIFY_CAPACITY = 64;


private static final int MIN_TRANSFER_STRIDE = 16;


private static int RESIZE_STAMP_BITS = 16;


private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;


private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;


static final int MOVED     = -1; // hash for forwarding nodes 标识ForwardingNode结点（在扩容时才会出现，不存储实际数据）
static final int TREEBIN   = -2; // hash for roots of trees 标识红黑树的根结点
static final int RESERVED  = -3; // hash for transient reservations 标识ReservationNode结点（）
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 标识Node结点，自然数0，1，2..


static final int NCPU = Runtime.getRuntime().availableProcessors();

1.4.3.2 字段

可以看到一些字段都使用了Volatile保证可见性和有序性。

transient volatile Node[] table;


private transient volatile Node[] nextTable;


private transient volatile long baseCount;


private transient volatile int sizeCtl;


private transient volatile int transferIndex;


private transient volatile int cellsBusy;


private transient volatile CounterCell[] counterCells;

// views 视图相关字段
private transient KeySetView keySet;
private transient ValuesView values;
private transient EntrySetView entrySet;

1.4.4 构造方法

public ConcurrentHashMap() {
}


public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    //通过提供初始容量，计算了 sizeCtl，sizeCtl = 【 (1.5 * initialCapacity + 1)，然后向上取最近的 2 的 n 次方】。
    // 如 initialCapacity 为 10，那么得到 sizeCtl 为 16，如果 initialCapacity 为 11，得到 sizeCtl 为 32。
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}


public ConcurrentHashMap(Map 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;
}

1.4.5 put方法

put 方法并没有使用synchronized修饰，那么他是如何保证并发安全呢？下面就看一下

public V put(K key, V value) {  
    return putVal(key, value, false);
}


final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key vlaue 都不能为null
    if (key == null || value == null) throw new NullPointerException();
    // 计算key的hash值：(h ^ (h >>> 16)) & HASH_BITS; 相比HashMap 多了一个 & HASH_BITS(Integer的最大值)
    int hash = spread(key.hashCode());
    
    int binCount = 0;
    // 自旋插入结点，直到成功，tab：table数组
    for (Node[] tab = table;;) {
        // f: 桶位置的头节点
        // n: table数组的容量
        // i: 要插入的key所在桶位置的索引
        // fh: 头节点的hash值
        Node f; int n, i, fh;
        // 还没有初始化，第一次插入值
        if (tab == null || (n = tab.length) == 0)
            // 初始化 table数组
            tab = initTable();
        //table[i]对应的桶为null，则直接插入节点
        // tabAt(tab, i)方法是调用 Unsafe 类的方法查看值，保证每次获取到的值都是最新的
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 如果数组该位置为空，
            // 用一次 CAS 操作将这个新值放入其中即可，这个 put 操作差不多就结束了，可以拉到最后面了
            // 如果 CAS 失败，那就是有并发操作，进到下一个循环就好了
            if (casTabAt(tab, i, null,
                         new Node(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // 发现ForwardingNode结点（通过MOVED标识ForwardingNode结点存在），说明此时table正在扩容，那么尝试协助数据迁移
        else if ((fh = f.hash) == MOVED)
            // 协助数据迁移操作
            tab = helpTransfer(tab, f);
        // 出现hash冲突,也就是table[i]桶中已经有了结点
        else {
            V oldVal = null;
            // 对table[i]头节点上锁，避免并发情况
            synchronized (f) {
                // 再次检查 table[i] 是否是该桶位置的头节点， 防止其它线程的写修改
                if (tabAt(tab, i) == f) {
                    // 说明 table[i] 是链表节点 hash = -1 说明是forward节点，-2说明是TreeBin节点，-3保留节点
                    if (fh >= 0) {
                        //记录结点数，超过阈值后，需要转为红黑树，提高查找效率
                        binCount = 1;
                        // 遍历链表
                        for (Node e = f;; ++binCount) {
                            K ek;
                            // 找到“相等”的结点，判断是否需要更新value值（onlyIfAbsent为false则可以替换）
                            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;
                            }
                        }
                    }
                    //上面判断不是链表结点，则继续判断table[i]是不是红黑树结点
                    else if (f instanceof TreeBin) {
                        // p：如果key存在，那么红黑树的插入方法会返回“相等的节点”
                        Node p;
                        //红黑树对应的基值，我认为哈是包括了treeBin和root，所以以2为基础
                        binCount = 2;
                        // 调用红黑树的插入方法
                        if ((p = ((TreeBin)f).putTreeval(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 链表节点数超过 阈值 树化
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                // 表明本次put操作只是替换了旧值，不用更改计数值
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //表明本次操作增加了新值， 计数值加 1
    addCount(1L, binCount);
    return null;
}

【注】 ：计算索引的方式是 i = (n - 1) & hash；n - 1 == table.length - 1，table.length 的大小必须为2的幂次的原因就在这里；

这是因为当table.length为2的幂次时，(table.length-1) 的二进制形式的特点是除最高位外全部是1，配合这种索引

计算方式可以实现key在table中的均匀分布 ，减少hash冲突——出现hash冲突时，结点就需要以链表或红黑树的

形式链接到table[i]，这样无论是插入还是查找都需要额外的时间。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YkcZU6h7-1641905869483)(C:UsersFunctionPicturestyporaConcurrentHashMap-put流程图.png)]

1.4.5.1 putVal方法中的四种情况

1️⃣、首次初始化table —— 懒加载

扩容的时候，判断sizeCtl的值是否小于0，如果是说明其他线程正在初始化，如果不是使用cas修改sizeCtl的值为-1，如果成功就说明初始化操作由当前线程完成。最后将扩容的阈值赋值给sizeCtl。

private final Node[] initTable() {
    // tab: 数组
    // sc : sizeCtl的值，在初始化之前该值就是数组的初始容量
    Node[] tab; int sc;
    // 自旋直到初始化成功（每次循环都获取最新的Node数组引用）
    while ((tab = table) == null || tab.length == 0) {
        // 说明已经有线程在进行初始化了，所以让出CPU时间片
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // CAS尝试将sizeCtl更新成-1,表示正在初始化中
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            //如果CAS操作成功了，代表本线程将负责初始化工作
            try {
                // 再次检查是否需要初始化
                if ((tab = table) == null || tab.length == 0) {
                    //在初始化Map时，sizeCtl代表数组大小，默认16，所以此时n默认为16
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    // 创建一个数组
                    Node[] nt = (Node[])new Node[n];
                    // 赋值个table，tab
                    table = tab = nt;
                    // sc : // n - (n >>> 2) = n - n/4 = 0.75n 扩容的阈值
                    sc = n - (n >>> 2);
                }
            } finally {
                //将计算后的sc（12）直接赋值给sizeCtl，表示达到12长度就扩容,由于这里只会有一个线程在执行，直接赋值即可，没有线程安全问题
                //只需要保证可见性
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

2️⃣、table[i]对应的桶为空： 直接CAS操作占用桶table[i]；

3️⃣、发现ForwardingNode结点，说明此时table正在扩容，则尝试协助进行数据迁移；

ForwardingNode结点是ConcurrentHashMap中的五类结点之一，相当于一个占位结点，表示当前table正在进行扩容，当前线程可以尝试协助数据迁移；
后面会对helpTransfer()调用的核心方法transfer()进行分析，这里简单了解一下helpTransfer()：

final Node[] helpTransfer(Node[] tab, Node f) {
    // nextTab：扩容的新的table数组
    // sc: sizeCtl
    Node[] nextTab; int sc;
    // 检查头节点是forwarding节点，扩容的新的数组已经创建了
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        // 自旋检查数据迁移操作是否完成
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            // 位运算
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            // CAS尝试协助数据迁移 将sizeCtl的值 + 1
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

4️⃣、出现hash冲突,也就是table[i]桶中已经有了结点

当两个不同key映射到同一个 table[i] 桶中时，就会出现这种情况：

当table[i]的结点类型为Node——链表结点时，就会将新结点以“尾插法”的形式插入链表的尾部；当table[i]的结点类型为TreeBin——红黑树代理结点时，就会将新结点通过红黑树的插入方式插入； 1.4.6 get方法

流程：

首先：根据key的hash值计算映射到table的哪个桶，table[i]；

其次：如果table[i]的key和待查找key相同，那直接返回（这时候不用判断是不是特殊节点）；

最后：如果table[i]对应的结点是特殊结点（hash值小于0），则通过 find() 查找，如果不是特殊节点，则按链表查找；

public V get(Object key) {
    // tab: table数组，e：key所在桶位置的头节点，p：，n: 数组长度
    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) {
        // 看table[i]当前节点是不是要找的值
        if ((eh = e.hash) == h) {
            // 说明要查找的key就是桶位置上的第一个节点
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 说明当前桶位置是特殊节点，正在数据迁移操作，执行find方法去扩容后的新数组中查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // 遍历当前桶位置，查找key，找到就返回。
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

1.4.7 find方法

不同的节点内部有不同的find()实现，这里的find()，是去新数组newtable中查找的

①： Node结点的查找

当 槽table[i] 被普通Node结点占用，说明是链表链接的形式，直接从链表头开始查找：

Node find(int h, Object k) {
    Node e = this;
    if (k != null) {
        do {
            K ek;
            if (e.hash == h &&
                ((ek = e.key) == k || (ek != null && k.equals(ek))))
                return e;
        } while ((e = e.next) != null);
    }
    return null;
}

② ：TreeBin结点的查找

TreeBin的查找比较特殊，我们知道当桶table[i]被TreeBin结点占用时，说明链接的是一棵红黑树；

由于红黑树的插入、删除等操作会涉及整个结构的调整，所以通常存在读写并发操作的时候，是需要加锁的；

【注】：ConcurrentHashMap采用了一种类似读写锁的方式：当线程持有写锁（修改红黑树）时，如果读线程需要查找，不会像传统的读写锁那样阻塞等待，而是转而以链表的形式进行查找（TreeBin本身是Node类型的子类，所有拥有Node的所有字段） 

final Node find(int h, Object k) {
    if (k != null) {
        //
        for (Node e = first; e != null; ) {
            int s; K ek;
            
            if (((s = lockState) & (WAITER|WRITER)) != 0) {
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                e = e.next;
            }
            //这时候就是按红黑树找了，读线程数量加1(读读)，读状态进行累加, READER==4
            else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                         s + READER)) {
                TreeNode r, p;
                try {
                    p = ((r = root) == null ? null :
                         r.findTreeNode(h, k, null));//根节点不能为null
                } finally {
                    Thread w;
                    // 如果当前线程是最后一个读线程，且有写线程w因为读锁而阻塞，则告诉写线程，它可以尝试获取写锁了，就是条件2
                    if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                        (READER|WAITER) && (w = waiter) != null)
                        LockSupport.unpark(w);
                }
                return p;
            }
        }
    }
    return null;
}

③ ：ForwardingNode结点的查找

ForwardingNode是一种临时结点，在扩容进行中才会出现，所以查找也在扩容的table ----》nextTable上进行：

Node find(int h, Object k) {
    // loop to avoid arbitrarily deep recursion on forwarding nodes
    outer:
    for (Node[] tab = nextTable; ; ) {
        Node e;
        int n;
        if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null)
            return null;
        for (; ; ) {
            int eh;
            K ek;
            if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek))))
                return e;
            if (eh < 0) {
                if (e instanceof ForwardingNode) {
                    tab = ((ForwardingNode) e).nextTable;
                    continue outer;
                } else
                    return e.find(h, k);
            }
            if ((e = e.next) == null)
                return null;
        }
    }
}

④ ： ReservationNode结点的查找**

ReservationNode是保留结点，不保存实际数据，所以直接返回null：

Node find(int h, Object k) {
    return null;
}

1.4.8 计数的相关方法 1.4.8.1 size方法

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

//调用sumCount方法
final long sumCount() {
    // as：计数槽，在并发情况下不同的线程向不同的槽内计数
    CounterCell[] as = counterCells; CounterCell a;
    // 基础值，就是在没有并发的情况下记录的值
    long sum = baseCount;
    // 将所有的计数累加
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}


static final class CounterCell {
    volatile long value;

    CounterCell(long x) {
        value = x;
    }
}

// 计数基值,当没有线程竞争时，计数将加到该变量上。类似于LongAdder的base变量
private transient volatile long baseCount;

// 计数数组，出现并发冲突时使用。类似于LongAdder的cells数组
private transient volatile CounterCell[] counterCells;

// 自旋标识位，用于CounterCell[]扩容时使用。类似于LongAdder的cellsBusy变量
private transient volatile int cellsBusy;

CounterCell 这个槽对象，当出现并发冲突时，每个线程会根据自己的hash值找到对应的槽位置：

【注】：在设计中，使用了分而治之的思想，将每一个计数都分散到各个countCell对象里面，使竞争最小化，又使用了CAS操作，就算有竞争，也可以对失败了的线程进行其他的处理。

乐观锁的实现方式与悲观锁不同之处就在于乐观锁可以对竞争失败了的线程进行其他策略的处理，而悲观锁只能等待锁释放，所以这里使用CAS操作对竞争失败的线程做了其他处理，很巧妙的运用了CAS乐观锁。

1.4.8.2 addCount方法

putval() 的最后，当插入新的结点后，通过 addCount() 将计数值为加1，我们接下来看看 addCount() 的具体实现

private final void addCount(long x, int check) {
    CounterCell[] as; //计数桶
    long b, s;
    // !U.compareAndSwapLong(this, baseCOUNT, b = baseCount, s = b + x)：尝试更新baseCount
    //1、如果counterCells不为null，则代表已经初始化了，直接进入if语句块
    //2、若竞争不严重，counterCells有可能还未初始化，为null，先尝试CAS操作递增baseCount值
    if ((as = counterCells) != null ||!U.compareAndSwapLong(this, baseCOUNT, b = baseCount, s = b + x)) { 
        //进入此语句块有两种可能：
        //1.counterCells被初始化完成了，不为null
        //2.CAS操作递增baseCount值失败了，说明出现并发冲突,则将计数值累加到Cell槽
        CounterCell a;
        long v;
        int m;
        boolean uncontended = true;    //标志是否存在竞争
        //1.先判断计数桶是否初始化,如果as=null，说明没有，进入语句块
        //2.判断计数桶长度是否为空，若是进入语句块
        //3.这里做了一个线程变量随机数，若桶的这个位置为空，进入语句块（根据线程hash值计算槽索引）
        //4.到这里说明桶已经初始化了，且随机的这个位置不为空，尝试CAS操作使桶加1，失败进入语句块
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||   
            !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);       // 槽更新也失败, 则会执行fullAddCount
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    if (check >= 0) {  // 检测是否扩容
        Node[] tab, nt;
        int n, sc;
        while (s >= (long) (sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();  //统计容器大小
        }
    }
}

总结：

首先，如果counterCells为null，说明之前一直没有出现过冲突，直接将值累加到baseCount上即可；

否则，尝试更新counterCells[i]中的值，更新成功就退出， 如果失败说明槽中也出现了并发冲突，可能涉及槽数组，即counterCells的扩容，所以调用fullAddCount方法。

【注】：由此可见，统计容器大小其实是用了两种思路：

CAS方式直接递增：在线程竞争不大的时候，直接使用CAS操作递增baseCount值即可，这里说的竞争不大指的是CAS操作不会失败的情况分而治之桶计数：若出现了CAS操作失败的情况，则证明此时有线程竞争了，计数方式从CAS方式转变为分而治之的桶计数方式

1.4.8.3 fullAddCount方法

当出现了并发冲突，则不会再用CAS方式来计数了，直接使用桶方式，从上面的addCount方法可以看出来，此时的countCell是为空的，最终一定会进入fullAddCount方法来进行初始化桶

private final void fullAddCount(long x, boolean wasUncontended) {
    int h;
    if ((h = ThreadLocalRandom.getProbe()) == 0) {
        ThreadLocalRandom.localInit();      // force initialization
        h = ThreadLocalRandom.getProbe();
        wasUncontended = true;
    }
    boolean collide = false;                // True if last slot nonempty
    for (;;) {
        CounterCell[] as; CounterCell a; int n; long v;
        ...
            //如果计数桶!=null，证明已经初始化，此时不走此语句块
            if ((as = counterCells) != null && (n = as.length) > 0) {
                ...
            }
        //进入此语句块进行计数桶的初始化
        //CAS设置cellsBusy=1，表示现在计数桶Busy中...
        else if (cellsBusy == 0 && counterCells == as &&
                 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
            //若有线程同时初始化计数桶，由于CAS操作只有一个线程进入这里
            boolean init = false;
            try {                           // Initialize table
                //再次确认计数桶为空
                if (counterCells == as) {
                    //初始化一个长度为2的计数桶
                    CounterCell[] rs = new CounterCell[2];
                    //h为一个随机数，与上1则代表结果为0、1中随机的一个
                    //也就是在0、1下标中随便选一个计数桶，x=1，放入1的值代表增加1个容量
                    rs[h & 1] = new CounterCell(x);
                    //将初始化好的计数桶赋值给ConcurrentHashMap
                    counterCells = rs;
                    init = true;
                }
            } finally {
                //最后将busy标识设置为0，表示不busy了
                cellsBusy = 0;
            }
            if (init)
                break;
        }
        //若有线程同时来初始化计数桶，则没有抢到busy资格的线程就先来CAS递增baseCount
        else if (U.compareAndSwapLong(this, baseCOUNT, v = baseCount, v + x))
            break;                          // Fall back on using base
    }
}

1,什么条件下会进行计数桶的扩容？

答：在CAS操作递增计数桶失败了3次之后，会进行扩容计数桶操作，注意此时同时进行了两次随机定位计数桶来进行CAS递增的，所以此时可以保证大概率是因为计数桶不够用了，才会进行计数桶扩容；

2、扩容操作是怎么样的？

答：计数桶长度增加到两倍长度，数据直接遍历迁移过来，由于计数桶不像HashMap数据结构那么复杂，有hash算法的影响，加上计数桶只是存放一个long类型的计数值而已，所以直接赋值引用即可；

总结：

利用CAS递增baseCount值来感知是否存在线程竞争，若竞争不大直接CAS递增baseCount值即可，性能与直接baseCount++差别不大；若存在线程竞争，则初始化计数桶，若此时初始化计数桶的过程中也存在竞争，多个线程同时初始化计数桶，则没有抢到初始化资格的线程直接尝试CAS递增baseCount值的方式完成计数，最大化利用了线程的并行。此时使用计数桶计数，分而治之的方式来计数，此时两个计数桶最大可提供两个线程同时计数，同时使用CAS操作来感知线程竞争，若两个桶情况下CAS操作还是频繁失败（失败3次），则直接扩容计数桶，变为4个计数桶，支持最大同时4个线程并发计数，以此类推…同时使用位运算和随机数的方式"负载均衡"一样的将线程计数请求接近均匀的落在各个计数桶中。

1.4.9 扩容机制 1.4.9.1 扩容

通过前面相关介绍，我们知道，当往table[i]中插入结点时，如果链表的结点数目超过一定阈值（8），就会触发链表 -> 红黑树的转换，这样提高了 查找效率：

if (binCount >= TREEIFY_THRESHOLD)
    treeifyBin(tab, i);             // 链表 -> 红黑树 转换

接下来我们分析这个 链表 -> 红黑树 的转换操作，treeifyBin(tab, i)：

private final void treeifyBin(Node[] tab, int index) {
    Node b; int n;
    if (tab != null) {
        // CASE 1: table的容量 < MIN_TREEIFY_CAPACITY时，直接进行table扩容，不进行红黑树转换，MIN_TREEIFY_CAPACITY默认为64
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        // CASE 2: table的容量 ≥ MIN_TREEIFY_CAPACITY时，进行相应桶的链表 -> 红黑树的转换
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {  //同步,对相应的桶的对象加锁
                if (tabAt(tab, index) == b) {
                    TreeNode hd = null, tl = null;
                    //遍历链表，建立红黑树
                    for (Node e = b; e != null; e = e.next) {
                        TreeNode p = new TreeNode(e.hash, e.key, e.val, null, null);//结点类型转换
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // 以TreeBin类型包装，并链接到table[index]中，并且这new TreeBin中 对红黑树自平衡
                    setTabAt(tab, index, new TreeBin(hd));
                }
            }
        }
    }
}

// ====================================tryPresize扩容操作=============


private final void tryPresize(int size) {
    // 视情况将size调整为2的整数次幂，与0.5 * MAXIMUM_CAPACITY来比较 ， tableSizeFor求二次幂
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
    tableSizeFor(size + (size >>> 1) + 1);
    // sc；sizeCtl
    int sc;
    // 自旋一直到扩容完成
    while ((sc = sizeCtl) >= 0) {
        Node[] tab = table; int n;
        //table还未初始化，则先进行初始化
        if (tab == null || (n = tab.length) == 0) {
            n = (sc > c) ? sc : c; //取最大值
            // CAS尝试进行扩容
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    // 没有其它线程进行过初始化
                    if (table == tab) {
                        // 创建新的数组
                        @SuppressWarnings("unchecked")
                        Node[] nt = (Node[])new Node[n];
                        table = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
            }
        }
        //c <= sc说明已经被扩容过了；n >= MAXIMUM_CAPACITY说明table数组已达到最大容量
        else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        //进行table扩容
        else if (tab == table) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                Node[] nt;
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                // 这个CAS操作可以保证，仅有一个线程会执行扩容
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
        }
    }
}

ConcurrentHashMap运用CAS操作，将扩容操作的并发性能实现最大化，在扩容过程中，就算有线程调用get查询方法，也可以安全的查询数据，若有线程进行put操作，还会协助扩容，利用sizeCtl标记位和各种volatile变量进行CAS操作达到多线程之间的通信、协助，在迁移过程中只锁一个Node节点，即保证了线程安全，又提高了并发性能。

1.4.9.2 数据迁移

private final void transfer(Node[] tab, Node[] nextTab) {
    // n: 旧数组的长度，
    // stride可理解成“步长”，即“数据迁移”时，每个线程要负责旧table中的多少个桶，根据几核的CPU决定“步长”，最少要负责16个
    int n = tab.length, stride;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    // 说明是第一次扩容
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            // 创建新数组，容量时旧数组的两倍
            Node[] nt = (Node[])new Node[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME 处理内存溢出的情况OOM
            // 将表示容量的sizeCtl设为最大值
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        // 扩容后的数组
        nextTable = nextTab;
        // [transferIndex-stride, transferIndex-1]：表示当前线程要进行数据迁移的桶区间
        transferIndex = n;
    }
    // 新数组的长度
    int nextn = nextTab.length;
    // 创建一个Forwarding节点，当旧table的某个桶中的所有结点都迁移完后，用该结点占据这个桶
    ForwardingNode fwd = new ForwardingNode(nextTab);
    // 标识一个桶的迁移工作是否完成，advance == true 表示可以进行下一个位置的迁移
    boolean advance = true;
    // true表示所有的桶都迁移成功
    boolean finishing = false; // to ensure sweep before committing nextTab
    // i：桶位置，bound标识边界
    for (int i = 0, bound = 0;;) {
        // f：当前桶位置的头节点
        Node f; int fh;
        // 每一次自旋前的预处理，主要是为了定位本轮处理的桶区间
        // 正常情况下，预处理完成后：i == transferIndex-1：右边界；
        // bound == transferIndex-stride：左边界
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        //当前是处理最后一个transfer任务的线程或出现扩容冲突
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) { // 所有的桶都迁移完成
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            // 扩容线程数减1,表示当前线程已完成自己的transfer任务
            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
            }
        }
        //旧桶本身为null，不用迁移，直接尝试放一个ForwardingNode
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        //该旧桶已经迁移完成，直接跳过
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        //该旧桶未迁移完成，进行数据迁移
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node ln, hn;
                    //桶的hash>0，说明是链表迁移
                    if (fh >= 0) {
                        
                        int runBit = fh & n;// 由于n是2的幂次，所以runBit要么是0，要么高位是1
                        Node lastRun = f;// lastRun指向最后一个相邻,runBit不同的结点
                        for (Node p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        // 以lastRun所指向的结点为分界，将链表拆成2个子链表ln、hn
                        for (Node p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node(ph, pk, pv, ln);
                            else
                                hn = new Node(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);		// ln链表存入新桶的索引i位置
                        setTabAt(nextTab, i + n, hn); // hn链表存入新桶的索引i+n位置
                        setTabAt(tab, i, fwd);			// 设置ForwardingNode占位
                        advance = true;					// 表示当前旧桶的结点已迁移完毕
                    }
                    // 红黑树迁移
                    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;
                            }
                        }
                        // 判断是否需要进行 红黑树 <-> 链表 的转换
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                        (hc != 0) ? new TreeBin(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                        (lc != 0) ? new TreeBin(hi) : t;

                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);				// 设置ForwardingNode占位
                        advance = true;						// 表示当前旧桶的结点已迁移完毕
                    }
                }
            }
        }
    }
}

①、我们先看 tranfer() 的开头，会计算出一个stride变量的值，这个stride其实就是每个线程处理的桶区间，也就是步长：

// stride可理解成“步长”，即“数据迁移”时，每个线程要负责旧table中的多少个桶，根据CPU决定步长
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)  //MIN_TRANSFER_STRIDE默认16
    stride = MIN_TRANSFER_STRIDE; // subdivide range  

根据是否是多核的CPU确定步长，不过最小步长为16，因为MIN_TRANSFER_STRIDE的默认值为16；

②、接下来就是进行扩容，当首次扩容时，将table数组的容量变成原来的2倍

if (nextTab == null) { // 第二个参数，即新的table为null说明第一次扩容
    try {
        @SuppressWarnings("unchecked")
        // 创建新table数组，扩大一倍
        Node[] nt = (Node[])new Node[n << 1];
        nextTab = nt;   
    } catch (Throwable ex) {      // 处理内存溢出（OOME）的情况
        sizeCtl = Integer.MAX_VALUE;   //将表示容量的sizeCtl 设置为最大值，然后返回
        return;
    }
    nextTable = nextTab;		//扩容后的数组nextTable 
    transferIndex = n;  // [transferIndex-stride, transferIndex-1]表示当前线程要进行数据迁移的桶区间
}
int nextn = nextTab.length;

注意上面的transferIndex变量，这是一个字段，table[transferIndex-stride, transferIndex-1]就是当前线程要进行数据迁移的桶区间，这个桶区间可以用扩容时的下标变量表示： private transient volatile int

transferIndex;

整个transfer()几乎都在一个自旋操作中完成，从右往左开始进行数据迁移，transfer的退出点是当某个线程处理完最后的table区段——table[0,stride-1]。

transfer()主要包含4个迁移分类，即对4种不同情况进行处理，上面的源码已经标注，现在我们按照难易程度

来更详细的解释下各个分类③---->⑥所做的事情：

③、CASE2 : 桶table[i]为空：

当旧table的桶table[i] == null，说明原来这个桶就没有数据，那就直接尝试通过CAS操作放置一个ForwardingNode，表示这个桶已经处理完成，CAS设置成功则advance为true，表示该桶已经完成迁移

// CASE2：旧桶本身为null，不用迁移，直接尝试放一个ForwardingNode
else if ((f = tabAt(tab, i)) == null)
    advance = casTabAt(tab, i, null, fwd);

ForwardingNode，主要做占用，多线程进行数据迁移时，其它线程看到这个桶中是ForwardingNode结点，就知道该桶数据迁移已经完成了。另外，当最后一个线程完成迁移任务后，会遍历所有桶，看看是否都是ForwardingNode，如果是，那么说明整个扩容/数据迁移的过程就完成了。

④、CASE3 : 桶table[i]不为空，但已经迁移完：

桶已经被ForwardingNode结点占用了，表示该桶的数据都迁移完了，当然标志位advance设为true：

// CASE3：该旧桶已经迁移完成，直接跳过
else if ((fh = f.hash) == MOVED)
    advance = true; // already processed

⑤、CASE4 : 桶table[i]未迁移完成：

如果旧桶的数据未迁移完成，就要进行迁移，这里根据桶中结点的类型分为：链表迁移、红黑树迁移；

⒈、链表迁移：

链表迁移的过程大致分为2步：

首先会遍历一遍原链表，找到最后一个相邻runBit不同的结点（为了充当链表头），runBit是根据key.hash和旧table长度n进行与运算得到的值，由于table的长度为2的幂次，所以runbit只可能为0或最高位为1其次会进行第二次链表遍历，按照第一次遍历找到的结点为界，将原链表分成2个子链表，再链接到新table的槽中。可以看到，新table的索引要么是i，要么是i+n

// CASE4.1：桶的hash>0，说明是正常结点，则链表迁移
if (fh >= 0) {
    
    int runBit = fh & n;	// 由于n是2的幂次，所以runBit要么是0，要么高位是1，fh是桶上的哈希值
    Node lastRun = f; 	// lastRun指向最后一个相邻runBit不同的结点
    for (Node p = f.next; p != null; p = p.next) {
        int b = p.hash & n;  //b要么是0，要么高位是1
        if (b != runBit) {
            runBit = b;
            lastRun = p;
        }
    }
    if (runBit == 0) {
        ln = lastRun;
        hn = null;
    }else {
        hn = lastRun;
        ln = null;
    }
    // 以lastRun所指向的结点为分界，将链表拆成2个子链表ln、hn
    for (Node p = f; p != lastRun; p = p.next) {
        int ph = p.hash; K pk = p.key; V pv = p.val;
        if ((ph & n) == 0)
            ln = new Node(ph, pk, pv, ln);
        else
            hn = new Node(ph, pk, pv, hn);
    }
    setTabAt(nextTab, i, ln);		// ln链表存入新桶的索引i位置
    setTabAt(nextTab, i + n, hn); 	// hn链表存入新桶的索引i+n位置
    setTabAt(tab, i, fwd);			// 设置ForwardingNode占位
    advance = true;					// 表示当前旧桶的结点已迁移完毕
}

⒉、红黑树迁移： 

红黑树的迁移按照链表遍历的方式进行，当链表结点超过/小于阈值时，涉及红黑树<->链表的相互转换：

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;
        }
    }
    // 判断是否需要进行 红黑树 <-> 链表 的转换
    ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :     //判断门限，如果大于则继续用树，树没改变则直接返回t
    (hc != 0) ? new TreeBin(lo) : t;
    hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
    (lc != 0) ? new TreeBin(hi) : t;
    setTabAt(nextTab, i, ln);
    setTabAt(nextTab, i + n, hn);
    setTabAt(tab, i, fwd);				// 设置ForwardingNode占位
    advance = true;					// 表示当前旧桶的结点已迁移完毕
}

⑥、CASE5: 当前是最后一个迁移任务或出现扩容冲突：

我们刚才说了，调用transfer() 的线程会自动领用某个区段的桶，进行数据迁移操作，当区段的初始索引i变成负数的时候，说明当前线程处理的其实就是最后剩下的桶，并且处理完了，然后操作如下：

首先会更新sizeCtl变量，将扩容线程数减1，然后会做一些收尾工作；其次设置table指向扩容后的新数组；最后遍历一遍旧数组，确保每个桶的数据都迁移完成——被ForwardingNode占用；

[注]：可能在扩容过程中，出现扩容冲突的情况，比如多个线程领用了同一区段的桶，这时任何一个线程都不能进

行数据迁移。

if (i < 0 || i >= n || i + n >= nextn) {    // CASE1：当前是处理最后一个tranfer任务的线程或出现扩容冲突
    int sc;
    if (finishing) {    // 所有桶迁移均已完成
        nextTable = null;
        table = nextTab;
        sizeCtl = (n << 1) - (n >>> 1);   //阈值为newTable的0.75倍
        return;
    }

    // 扩容线程数减1,表示当前线程已完成自己的transfer任务
    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        // 判断当前线程是否是本轮扩容中的最后一个线程，如果不是，则直接退出，如果是则设置标志位finishing
        if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
            return;
        finishing = advance = true;

        
        i = n; // recheck before commit
    }
}

参考文档

javaguide-hashMap讲述

红黑树详解

ConcurrentHashMap介绍