Java集合

参考https://javaguide.cn/

ArrayList

构造函数

1. 校验初始容量
2. 如果是无参构造，那么还是赋值一个空的数组，但是插入的时候会辨别;反之则构造一个空的数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，但是下次扩容会取最小扩容量与默认初始化长度（一般为10）进行比较。

扩容过程

add函数

校验大小获取最少需要长度通常是插入数量+当前长度，

grow函数

如果不够就进行扩容，并确定扩容大小，每次扩容变成原来的1.5倍，0.5倍由无符号右移一位得到，新长度有最少需要长度与原来长度的1.5倍的最大值得到，但是不超过SOFT_MAX_ARRAY_LENGTH，该值为Int的最大值-8，是由于部分java虚拟机需要存放object header会导致堆栈溢出，Java中的对象头信息（数组长度）需要占用8个字节的空间，所以选择了个略小于最大值的值。

System.arraycopy(elementData, index, elementData, index + 1,size - index);

数组前移和后移的时候：将元素赋值到新地方

Arrays.copyOf(elementData, newCapacity);

扩容的时候：将元素赋值到新地方，底层还是用了System.arraycopy(),做了一层封装（创建新数组）

HashMap

解决hash冲突

1. 链地址法，统一链接到后面的链表当中（冲突多了查询时间不够高效）
2. 再哈希使用多个hash函数直到不再发生冲突（不易聚集但是，增加了计算时间）
3. 溢出表，凡是发生了冲突的都写到溢出表里（冲突多了查询时间不够高效）
4. 开放定址法（增加了计算时间，删除元素复杂，只能做标记，删除了会导致后面的元素查找失败）

TableSizeFor()

通过-1无符号右移给定容量的前导零长度+1得到最接近的2幂次-1，同时与最大容量进行比较

int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

构造函数

给定的默认容量为 16，负载因子为 0.75。

参数带容量或者负载因子那就需要TableSizeFor()函数确定table大小

哈希方法

//JDK1.7
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
//JDK1.8
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

定位方法

(n - 1) & hash

n为哈希表长度

put 方法

首先判断数组是否经过初始化，如果没有则需要进行初始化

定位数组位置，如果无节点，则直接插入,并检验容量是否达到上限

如果存在相同的key，则直接覆盖并返回，因为没有节点增加

如果该节点是树节点，则使用红黑树的方法插入

如果该节点是普通链表节点，插入节点先判断插入后（链表长度大于阈值（默认为 8）并且 HashMap 数组长度超过 64 的时候才会执行链表转红黑树的操作，否则就只是对数组扩容）

resize()方法

容量参数设置

首先判断原来的table是否为空，为空则进行初始化，如果也没有指定loadFactor和threshold则使用默认的，

如果不为空，容量变为原来的两倍。

同时更新threshold参数，并开辟新的node数组空间

进行迁移

如果table为空，直接跳过。

遍历node数组{

​ 如果只有一个元素，则newTab[e.hash & (newCap - 1)] = e;

​ 如果是红黑树，会遍历红黑树，根据e.hash & oldCap的值区分不同的位置(在原来位置j，还是j+oldcap)，且当拆分开的红黑树的节点数小于6的时候会变成链表插入到node数组中

​ 链表同理，遍历链表根据e.hash & oldCap的值区分不同的位置(在原来位置j，还是j+oldcap)

}

ConcurrentHashMap

翻了ConcurrentHashMap1.7 和1.8的源码，我总结了它们的主要区别。 - 掘金 (juejin.cn)

线程安全实现

• 使用volatile保证当Node中的值变化时对于其他线程是可见的
• 使用table数组的头结点作为synchronized的锁来保证写操作的安全
• 当头结点为null时，使用CAS操作来保证数据能正确的写入。

1.7

segment+hashentry +链表的形式

ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发

默认初始化容量16;默认负载因子 0.75f;默认并发级别16;

1.8

(38条消息) ConcurrentHashMap底层详解(图解扩容)（JDK1.8）_concurrenthashmap扩容_编程芝士的博客-CSDN博客

static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

变量sizeCtl

1. -1 说明正在初始化，如果发现正在初始化Thread.yield();
2. -N 说明有N-1个线程正在进行扩容
3. 0 表示 table 初始化大小，如果 table 没有初始化
4. >0 表示 table 扩容的阈值，如果 table 已经初始化。

初始化表

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // 类似CAS方法 循环初始化表
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // CAS
        else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
            try {
                // 检查表是否初始化
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    // 0.75
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

put()

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        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<K,V>(hash, key, value)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent // check first node without acquiring lock
                 && fh == hash
                 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                 && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> 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<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

根据 key 计算出 hashcode，key和value均不能为null 。

判断是否需要进行初始化

即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。

如果当前位置的 hashcode == MOVED == -1,则帮助扩容。

如果都不满足，则利用 synchronized 锁住这个桶,找到对应key替换值，或者插入到末尾

如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度≥64时才会将链表转换为红黑树，与链表不同的是这个时候哈希桶里面存放的是TreeBin类，该类中有各种红黑树的方法

get()

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> 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;
}

根据 hash 值计算位置。

查找到指定位置，如果头节点就是要找的，直接返回它的 value.

如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。

static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations

如果是链表，遍历查找之。

addCount()

private final void addCount(long x, int check) {
    CounterCell[] cs; long b, s;
    if ((cs = counterCells) != null ||
        !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell c; long v; int m;
        boolean uncontended = true;
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
            if (sc < 0) {
                if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
                    (nt = nextTable) == null || transferIndex <= 0)
                    break;
                if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

1. 使用了countercell数组的方法来计数，单个成员变量进行修改的时候冲突较大，所以采用分片的方法进行计数，方法类似于LongAdder计数
2. 如果countercells数组为空，那么直接cas设置baseCount变量，失败了才进入if里面，初始化counterCells，使用fullCount初始化和重新计数counterCells，使用sumCount方法遍历counterCells 获取最后容量
3. 如果check大于0，如果检查添加的元素量是否需要进行扩容。如果当前需要扩容，先判断是否有其他线程正在扩容有就更新sizeCTL+1（线程数+1），如果没有就更新sizeCTl rs+2（如果没有因为-1为初始化）重新计数，并且也要小于最大扩容线程数

Transfer()

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    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<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // to ensure sweep before committing nextTab
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSetInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        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<K,V> ln, hn;
                    if (fh >= 0) {
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        for (Node<K,V> 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;
                        }
                        for (Node<K,V> 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<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) {
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (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<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
        }
    }
}

1. 首先先划分每个线程的步长 为(n >>> 3) / NCPU，如果只有一个cpu那么步长为整个表，同时还会在校验一次步长，小于16则设置为16
2. 如果nextTab为空则，对数组进行扩容，申请原有数量两倍的数组，如果oom了则sizeCtl设为int最大值
3. 然后就开始划分数组，如果node数组位置为空则直接设置fwd节点表示已经完成，moved标志表示该位置已经完成迁移无需操作，否则才会进入到链表和红黑树的迁移过程，类似于HashMap就不在赘述，最后一步同样也会设置fwd节点表示已经完成
4. 完成特定步长后，sizeCtl-1设置结束标志退出，当最后一个线程完成后，他还会对全部数组进行个遍历确认是否有遗漏。