AI 摘要 文章对比分析了 Java 7 与 Java 8 的 ConcurrentHashMap 源码：Java 7 采用固定 16 段 Segment 加分段锁，扩容两倍，链表头插；Java 8 改用 Node 数组+链表/红黑树，以 CAS+synchronized 保证并发，扩容时容量翻倍并可能树化，get 均通过 hash 定位再遍历或树查找。 此摘要根据文章内容自动生成，仅用于文章内容的解释与总结title: ConcurrentHashMap 源码分析category: Javatag:Java集合ConcurrentHashMap 作为线程安全的 HashMap ，它的使用频率也是很高。那么它的存储结构和实现原理是怎么样的呢？1. ConcurrentHashMap 1.71. 存储结构Java 7 中 ConcurrentHashMap 的存储结构如上图，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。2. 初始化通过 ConcurrentHashMap 的无参构造探寻 ConcurrentHashMap 的初始化流程。 /** * Creates a new, empty map with a default initial capacity (16), * load factor (0.75) and concurrencyLevel (16). */ public ConcurrentHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); }无参构造中调用了有参构造，传入了三个参数的默认值，他们的值是。 /** * 默认初始化容量 */ static final int DEFAULT_INITIAL_CAPACITY = 16; /** * 默认负载因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 默认并发级别 */ static final int DEFAULT_CONCURRENCY_LEVEL = 16;接着看下这个有参构造函数的内部实现逻辑。@SuppressWarnings("unchecked") public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) { // 参数校验 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); // 校验并发级别大小，大于 1<<16，重置为 65536 if (concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // Find power-of-two sizes best matching arguments // 2的多少次方 int sshift = 0; int ssize = 1; // 这个循环可以找到 concurrencyLevel 之上最近的 2的次方值 while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1; } // 记录段偏移量 this.segmentShift = 32 - sshift; // 记录段掩码 this.segmentMask = ssize - 1; // 设置容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // c = 容量 / ssize ，默认 16 / 16 = 1，这里是计算每个 Segment 中的类似于 HashMap 的容量 int c = initialCapacity / ssize; if (c * ssize < initialCapacity) ++c; int cap = MIN_SEGMENT_TABLE_CAPACITY; //Segment 中的类似于 HashMap 的容量至少是2或者2的倍数 while (cap < c) cap <<= 1; // create segments and segments[0] // 创建 Segment 数组，设置 segments[0] Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]); Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize]; UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0] this.segments = ss; }总结一下在 Java 7 中 ConcurrentHashMap 的初始化逻辑。必要参数校验。校验并发级别 concurrencyLevel 大小，如果大于最大值，重置为最大值。无参构造默认值是 16.寻找并发级别 concurrencyLevel 之上最近的 2 的幂次方值，作为初始化容量大小，默认是 16。记录 segmentShift 偏移量，这个值为【容量 = 2 的 N 次方】中的 N，在后面 Put 时计算位置时会用到。默认是 32 - sshift = 28.记录 segmentMask，默认是 ssize - 1 = 16 -1 = 15.初始化 segments[0]，默认大小为 2，负载因子 0.75，扩容阀值是 2*0.75=1.5，插入第二个值时才会进行扩容。3. put接着上面的初始化参数继续查看 put 方法源码。/** * Maps the specified key to the specified value in this table. * Neither the key nor the value can be null. * * The value can be retrieved by calling the get method * with a key that is equal to the original key. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key , or * null if there was no mapping for key * @throws NullPointerException if the specified key or value is null */ public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); int hash = hash(key); // hash 值无符号右移 28位（初始化时获得），然后与 segmentMask=15 做与运算 // 其实也就是把高4位与segmentMask（1111）做与运算 int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment // 如果查找到的 Segment 为空，初始化 s = ensureSegment(j); return s.put(key, hash, value, false); } /** * Returns the segment for the given index, creating it and * recording in segment table (via CAS) if not already present. * * @param k the index * @return the segment */ @SuppressWarnings("unchecked") private Segment<K,V> ensureSegment(int k) { final Segment<K,V>[] ss = this.segments; long u = (k << SSHIFT) + SBASE; // raw offset Segment<K,V> seg; // 判断 u 位置的 Segment 是否为null if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { Segment<K,V> proto = ss[0]; // use segment 0 as prototype // 获取0号 segment 里的 HashEntry<K,V> 初始化长度 int cap = proto.table.length; // 获取0号 segment 里的 hash 表里的扩容负载因子，所有的 segment 的 loadFactor 是相同的 float lf = proto.loadFactor; // 计算扩容阀值 int threshold = (int)(cap * lf); // 创建一个 cap 容量的 HashEntry 数组 HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap]; if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck // 再次检查 u 位置的 Segment 是否为null，因为这时可能有其他线程进行了操作 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab); // 自旋检查 u 位置的 Segment 是否为null while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // 使用CAS 赋值，只会成功一次 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) break; } } } return seg; }上面的源码分析了 ConcurrentHashMap 在 put 一个数据时的处理流程，下面梳理下具体流程。计算要 put 的 key 的位置，获取指定位置的 Segment。如果指定位置的 Segment 为空，则初始化这个 Segment.初始化 Segment 流程：检查计算得到的位置的 Segment 是否为 null.为 null 继续初始化，使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。再次检查计算得到的指定位置的 Segment 是否为 null.使用创建的 HashEntry 数组初始化这个 Segment.自旋判断计算得到的指定位置的 Segment 是否为 null，使用 CAS 在这个位置赋值为 Segment.Segment.put 插入 key,value 值。上面探究了获取 Segment 段和初始化 Segment 段的操作。最后一行的 Segment 的 put 方法还没有查看，继续分析。final V put(K key, int hash, V value, boolean onlyIfAbsent) { // 获取 ReentrantLock 独占锁，获取不到，scanAndLockForPut 获取。 HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue; try { HashEntry<K,V>[] tab = table; // 计算要put的数据位置 int index = (tab.length - 1) & hash; // CAS 获取 index 坐标的值 HashEntry<K,V> first = entryAt(tab, index); for (HashEntry<K,V> e = first;;) { if (e != null) { // 检查是否 key 已经存在，如果存在，则遍历链表寻找位置，找到后替换 value K k; if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { oldValue = e.value; if (!onlyIfAbsent) { e.value = value; ++modCount; } break; } e = e.next; } else { // first 有值没说明 index 位置已经有值了，有冲突，链表头插法。 if (node != null) node.setNext(first); else node = new HashEntry<K,V>(hash, key, value, first); int c = count + 1; // 容量大于扩容阀值，小于最大容量，进行扩容 if (c > threshold && tab.length < MAXIMUM_CAPACITY) rehash(node); else // index 位置赋值 node，node 可能是一个元素，也可能是一个链表的表头 setEntryAt(tab, index, node); ++modCount; count = c; oldValue = null; break; } } } finally { unlock(); } return oldValue; }由于 Segment 继承了 ReentrantLock，所以 Segment 内部可以很方便的获取锁，put 流程就用到了这个功能。tryLock() 获取锁，获取不到使用 scanAndLockForPut 方法继续获取。计算 put 的数据要放入的 index 位置，然后获取这个位置上的 HashEntry 。遍历 put 新元素，为什么要遍历？因为这里获取的 HashEntry 可能是一个空元素，也可能是链表已存在，所以要区别对待。如果这个位置上的 HashEntry 不存在：如果当前容量大于扩容阀值，小于最大容量，进行扩容。直接头插法插入。如果这个位置上的 HashEntry 存在：判断链表当前元素 key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值不一致，获取链表下一个节点，直到发现相同进行值替换，或者链表表里完毕没有相同的。如果当前容量大于扩容阀值，小于最大容量，进行扩容。直接链表头插法插入。如果要插入的位置之前已经存在，替换后返回旧值，否则返回 null.这里面的第一步中的 scanAndLockForPut 操作这里没有介绍，这个方法做的操作就是不断的自旋 tryLock() 获取锁。当自旋次数大于指定次数时，使用 lock() 阻塞获取锁。在自旋时顺表获取下 hash 位置的 HashEntry。private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { HashEntry<K,V> first = entryForHash(this, hash); HashEntry<K,V> e = first; HashEntry<K,V> node = null; int retries = -1; // negative while locating node // 自旋获取锁 while (!tryLock()) { HashEntry<K,V> f; // to recheck first below if (retries < 0) { if (e == null) { if (node == null) // speculatively create node node = new HashEntry<K,V>(hash, key, value, null); retries = 0; } else if (key.equals(e.key)) retries = 0; else e = e.next; } else if (++retries > MAX_SCAN_RETRIES) { // 自旋达到指定次数后，阻塞等到只到获取到锁 lock(); break; } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { e = first = f; // re-traverse if entry changed retries = -1; } } return node; } 4. 扩容 rehashConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。private void rehash(HashEntry<K,V> node) { HashEntry<K,V>[] oldTable = table; // 老容量 int oldCapacity = oldTable.length; // 新容量，扩大两倍 int newCapacity = oldCapacity << 1; // 新的扩容阀值 threshold = (int)(newCapacity * loadFactor); // 创建新的数组 HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity]; // 新的掩码，默认2扩容后是4，-1是3，二进制就是11。 int sizeMask = newCapacity - 1; for (int i = 0; i < oldCapacity ; i++) { // 遍历老数组 HashEntry<K,V> e = oldTable[i]; if (e != null) { HashEntry<K,V> next = e.next; // 计算新的位置，新的位置只可能是不便或者是老的位置+老的容量。 int idx = e.hash & sizeMask; if (next == null) // Single node on list // 如果当前位置还不是链表，只是一个元素，直接赋值 newTable[idx] = e; else { // Reuse consecutive sequence at same slot // 如果是链表了 HashEntry<K,V> lastRun = e; int lastIdx = idx; // 新的位置只可能是不便或者是老的位置+老的容量。 // 遍历结束后，lastRun 后面的元素位置都是相同的 for (HashEntry<K,V> last = next; last != null; last = last.next) { int k = last.hash & sizeMask; if (k != lastIdx) { lastIdx = k; lastRun = last; } } // ，lastRun 后面的元素位置都是相同的，直接作为链表赋值到新位置。 newTable[lastIdx] = lastRun; // Clone remaining nodes for (HashEntry<K,V> p = e; p != lastRun; p = p.next) { // 遍历剩余元素，头插法到指定 k 位置。 V v = p.value; int h = p.hash; int k = h & sizeMask; HashEntry<K,V> n = newTable[k]; newTable[k] = new HashEntry<K,V>(h, p.key, v, n); } } } } // 头插法插入新的节点 int nodeIndex = node.hash & sizeMask; // add the new node node.setNext(newTable[nodeIndex]); newTable[nodeIndex] = node; table = newTable; }有些同学可能会对最后的两个 for 循环有疑惑，这里第一个 for 是为了寻找这样一个节点，这个节点后面的所有 next 节点的新位置都是相同的。然后把这个作为一个链表赋值到新位置。第二个 for 循环是为了把剩余的元素通过头插法插入到指定位置链表。这样实现的原因可能是基于概率统计，有深入研究的同学可以发表下意见。5. get到这里就很简单了，get 方法只需要两步即可。计算得到 key 的存放位置。遍历指定位置查找相同 key 的 value 值。public V get(Object key) { Segment<K,V> s; // manually integrate access methods to reduce overhead HashEntry<K,V>[] tab; int h = hash(key); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; // 计算得到 key 的存放位置 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); e != null; e = e.next) { // 如果是链表，遍历查找到相同 key 的 value。 K k; if ((k = e.key) == key || (e.hash == h && key.equals(k))) return e.value; } } return null; }2. ConcurrentHashMap 1.81. 存储结构可以发现 Java8 的 ConcurrentHashMap 相对于 Java7 来说变化比较大，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树。2. 初始化 initTable/** * Initializes table, using the size recorded in sizeCtl. */ private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { // 如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。 if ((sc = sizeCtl) < 0) // 让出 CPU 使用权 Thread.yield(); // lost initialization race; just spin 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<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }从源码中可以发现 ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl （sizeControl 的缩写），它的值决定着当前的初始化状态。-1 说明正在初始化，其他线程需要自旋等待-N 说明 table 正在进行扩容，高 16 位表示扩容的标识戳，低 16 位减 1 为正在进行扩容的线程数0 表示 table 初始化大小，如果 table 没有初始化\>0 表示 table 扩容的阈值，如果 table 已经初始化。3. put直接过一遍 put 源码。public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { // key 和 value 不能为空 if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { // f = 目标位置元素 Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值 if (tab == null || (n = tab.length) == 0) // 数组桶为空，初始化数组桶（自旋+CAS) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出 if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; // 使用 synchronized 加锁加入节点 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, null); 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; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }根据 key 计算出 hashcode 。判断是否需要进行初始化。即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。如果都不满足，则利用 synchronized 锁写入数据。如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥64 时才会将链表转换为红黑树。4. getget 流程比较简单，直接过一遍源码。public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // key 所在的 hash 位置 int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 如果指定位置元素存在，头结点hash值相同 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) // key hash 值相等，key值相同，直接返回元素 value return e.val; } else if (eh < 0) // 头结点hash值小于0，说明正在扩容或者是红黑树，find查找 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 过程：根据 hash 值计算位置。查找到指定位置，如果头节点就是要找的，直接返回它的 value.如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。如果是链表，遍历查找之。总结：总的来说 ConcurrentHashMap 在 Java8 中相对于 Java7 来说变化还是挺大的，3. 总结Java7 中 ConcurrentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。有些同学可能对 Synchronized 的性能存在疑问，其实 Synchronized 锁自从引入锁升级策略后，性能不再是问题，有兴趣的同学可以自己了解下 Synchronized 的锁升级。
AI 摘要 文章梳理了Java并发包中的核心容器：ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue、BlockingQueue及ConcurrentSkipListMap，分别阐述其线程安全机制、适用场景与性能特点，并对比JDK7/8实现差异，为并发编程选型提供参考。 此摘要根据文章内容自动生成，仅用于文章内容的解释与总结title: Java 常见并发容器总结category: Javatag:Java并发JDK 提供的这些容器大部分在 java.util.concurrent 包中。ConcurrentHashMap : 线程安全的 HashMapCopyOnWriteArrayList : 线程安全的 List，在读多写少的场合性能非常好，远远好于 Vector。ConcurrentLinkedQueue : 高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，这是一个非阻塞队列。BlockingQueue : 这是一个接口，JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列，非常适合用于作为数据共享的通道。ConcurrentSkipListMap : 跳表的实现。这是一个 Map，使用跳表的数据结构进行快速查找。ConcurrentHashMap我们知道 HashMap 不是线程安全的，在并发场景下如果要保证一种可行的方式是使用 Collections.synchronizedMap() 方法来包装我们的 HashMap。但这是通过使用一个全局的锁来同步不同线程间的并发访问，因此会带来不可忽视的性能问题。所以就有了 HashMap 的线程安全版本—— ConcurrentHashMap 的诞生。在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。关于 ConcurrentHashMap 的详细介绍，请看我写的这篇文章：ConcurrentHashMap 源码分析。CopyOnWriteArrayList在 JDK1.5 之前，如果想要使用并发安全的 List 只能选择 Vector。而 Vector 是一种老旧的集合，已经被淘汰。Vector 对于增删改查等方法基本都加了 synchronized，这种方式虽然能够保证同步，但这相当于对整个 Vector 加上了一把大锁，使得每个方法执行的时候都要去获得锁，导致性能非常低下。JDK1.5 引入了 Java.util.concurrent（JUC）包，其中提供了很多线程安全且并发性能良好的容器，其中唯一的线程安全 List 实现就是 CopyOnWriteArrayList 。对于大部分业务场景来说，读取操作往往是远大于写入操作的。由于读取操作不会对原有数据进行修改，因此，对于每次读取都进行加锁其实是一种资源浪费。相比之下，我们应该允许多个线程同时访问 List 的内部数据，毕竟对于读取操作来说是安全的。这种思路与 ReentrantReadWriteLock 读写锁的设计思想非常类似，即读读不互斥、读写互斥、写写互斥（只有读读不互斥）。CopyOnWriteArrayList 更进一步地实现了这一思想。为了将读操作性能发挥到极致，CopyOnWriteArrayList 中的读取操作是完全无需加锁的。更加厉害的是，写入操作也不会阻塞读取操作，只有写写才会互斥。这样一来，读操作的性能就可以大幅度提升。CopyOnWriteArrayList 线程安全的核心在于其采用了 写时复制（Copy-On-Write） 的策略，从 CopyOnWriteArrayList 的名字就能看出了。当需要修改（ add，set、remove 等操作） CopyOnWriteArrayList 的内容时，不会直接修改原数组，而是会先创建底层数组的副本，对副本数组进行修改，修改完之后再将修改后的数组赋值回去，这样就可以保证写操作不会影响读操作了。关于 CopyOnWriteArrayList 的详细介绍，请看我写的这篇文章：CopyOnWriteArrayList 源码分析。ConcurrentLinkedQueueJava 提供的线程安全的 Queue 可以分为阻塞队列和非阻塞队列，其中阻塞队列的典型例子是 BlockingQueue，非阻塞队列的典型例子是 ConcurrentLinkedQueue，在实际应用中要根据实际需要选用阻塞队列或者非阻塞队列。 阻塞队列可以通过加锁来实现，非阻塞队列可以通过 CAS 操作实现。从名字可以看出，ConcurrentLinkedQueue这个队列使用链表作为其数据结构．ConcurrentLinkedQueue 应该算是在高并发环境中性能最好的队列了。它之所有能有很好的性能，是因为其内部复杂的实现。ConcurrentLinkedQueue 内部代码我们就不分析了，大家知道 ConcurrentLinkedQueue 主要使用 CAS 非阻塞算法来实现线程安全就好了。ConcurrentLinkedQueue 适合在对性能要求相对较高，同时对队列的读写存在多个线程同时进行的场景，即如果对队列加锁的成本较高则适合使用无锁的 ConcurrentLinkedQueue 来替代。BlockingQueueBlockingQueue 简介上面我们己经提到了 ConcurrentLinkedQueue 作为高性能的非阻塞队列。下面我们要讲到的是阻塞队列——BlockingQueue。阻塞队列（BlockingQueue）被广泛使用在“生产者-消费者”问题中，其原因是 BlockingQueue 提供了可阻塞的插入和移除的方法。当队列容器已满，生产者线程会被阻塞，直到队列未满；当队列容器为空时，消费者线程会被阻塞，直至队列非空时为止。BlockingQueue 是一个接口，继承自 Queue，所以其实现类也可以作为 Queue 的实现来使用，而 Queue 又继承自 Collection 接口。下面是 BlockingQueue 的相关实现类：下面主要介绍一下 3 个常见的 BlockingQueue 的实现类：ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue 。ArrayBlockingQueueArrayBlockingQueue 是 BlockingQueue 接口的有界队列实现类，底层采用数组来实现。public class ArrayBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, Serializable{}ArrayBlockingQueue 一旦创建，容量不能改变。其并发控制采用可重入锁 ReentrantLock ，不管是插入操作还是读取操作，都需要获取到锁才能进行操作。当队列容量满时，尝试将元素放入队列将导致操作阻塞;尝试从一个空队列中取一个元素也会同样阻塞。ArrayBlockingQueue 默认情况下不能保证线程访问队列的公平性，所谓公平性是指严格按照线程等待的绝对时间顺序，即最先等待的线程能够最先访问到 ArrayBlockingQueue。而非公平性则是指访问 ArrayBlockingQueue 的顺序不是遵守严格的时间顺序，有可能存在，当 ArrayBlockingQueue 可以被访问时，长时间阻塞的线程依然无法访问到 ArrayBlockingQueue。如果保证公平性，通常会降低吞吐量。如果需要获得公平性的 ArrayBlockingQueue，可采用如下代码：private static ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(10,true);LinkedBlockingQueueLinkedBlockingQueue 底层基于单向链表实现的阻塞队列，可以当做无界队列也可以当做有界队列来使用，同样满足 FIFO 的特性，与 ArrayBlockingQueue 相比起来具有更高的吞吐量，为了防止 LinkedBlockingQueue 容量迅速增，损耗大量内存。通常在创建 LinkedBlockingQueue 对象时，会指定其大小，如果未指定，容量等于 Integer.MAX_VALUE 。相关构造方法: /** *某种意义上的无界队列 * Creates a {@code LinkedBlockingQueue} with a capacity of * {@link Integer#MAX_VALUE}. */ public LinkedBlockingQueue() { this(Integer.MAX_VALUE); } /** *有界队列 * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity. * * @param capacity the capacity of this queue * @throws IllegalArgumentException if {@code capacity} is not greater * than zero */ public LinkedBlockingQueue(int capacity) { if (capacity <= 0) throw new IllegalArgumentException(); this.capacity = capacity; last = head = new Node<E>(null); }PriorityBlockingQueuePriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序进行排序，也可以通过自定义类实现 compareTo() 方法来指定元素排序规则，或者初始化时通过构造器参数 Comparator 来指定排序规则。PriorityBlockingQueue 并发控制采用的是可重入锁 ReentrantLock，队列为无界队列（ArrayBlockingQueue 是有界队列，LinkedBlockingQueue 也可以通过在构造函数中传入 capacity 指定队列最大的容量，但是 PriorityBlockingQueue 只能指定初始的队列大小，后面插入元素的时候，如果空间不够的话会自动扩容）。简单地说，它就是 PriorityQueue 的线程安全版本。不可以插入 null 值，同时，插入队列的对象必须是可比较大小的（comparable），否则报 ClassCastException 异常。它的插入操作 put 方法不会 block，因为它是无界队列（take 方法在队列为空的时候会阻塞）。推荐文章： 《解读 Java 并发队列 BlockingQueue》ConcurrentSkipListMap下面这部分内容参考了极客时间专栏《数据结构与算法之美》以及《实战 Java 高并发程序设计》。为了引出 ConcurrentSkipListMap，先带着大家简单理解一下跳表。对于一个单链表，即使链表是有序的，如果我们想要在其中查找某个数据，也只能从头到尾遍历链表，这样效率自然就会很低，跳表就不一样了。跳表是一种可以用来快速查找的数据结构，有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，你会需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，你只需要部分锁即可。这样，在高并发环境下，你就可以拥有更好的性能。而就查询的性能而言，跳表的时间复杂度也是 O(logn) 所以在并发数据结构中，JDK 使用跳表来实现一个 Map。跳表的本质是同时维护了多个链表，并且链表是分层的，最低层的链表维护了跳表内所有的元素，每上面一层链表都是下面一层的子集。跳表内的所有链表的元素都是排序的。查找时，可以从顶级链表开始找。一旦发现被查找的元素大于当前链表中的取值，就会转入下一层链表继续找。这也就是说在查找过程中，搜索是跳跃式的。如上图所示，在跳表中查找元素 18。查找 18 的时候原来需要遍历 18 次，现在只需要 7 次即可。针对链表长度比较大的时候，构建索引查找效率的提升就会非常明显。从上面很容易看出，跳表是一种利用空间换时间的算法。使用跳表实现 Map 和使用哈希算法实现 Map 的另外一个不同之处是：哈希并不会保存元素的顺序，而跳表内所有的元素都是排序的。因此在对跳表进行遍历时，你会得到一个有序的结果。所以，如果你的应用需要有序性，那么跳表就是你不二的选择。JDK 中实现这一数据结构的类是 ConcurrentSkipListMap。参考《实战 Java 高并发程序设计》https://javadoop.com/post/java-concurrent-queuehttps://juejin.im/post/5aeebd02518825672f19c546
AI 摘要 CopyOnWriteArrayList 通过“写时复制”实现线程安全，读无锁、写不阻塞读，仅写写互斥，适合读多写少场景；写操作需复制数组，内存与性能开销大，数据弱一致。 此摘要根据文章内容自动生成，仅用于文章内容的解释与总结title: CopyOnWriteArrayList 源码分析category: Javatag:Java集合CopyOnWriteArrayList 简介在 JDK1.5 之前，如果想要使用并发安全的 List 只能选择 Vector。而 Vector 是一种老旧的集合，已经被淘汰。Vector 对于增删改查等方法基本都加了 synchronized，这种方式虽然能够保证同步，但这相当于对整个 Vector 加上了一把大锁，使得每个方法执行的时候都要去获得锁，导致性能非常低下。JDK1.5 引入了 Java.util.concurrent（JUC）包，其中提供了很多线程安全且并发性能良好的容器，其中唯一的线程安全 List 实现就是 CopyOnWriteArrayList 。关于java.util.concurrent 包下常见并发容器的总结，可以看我写的这篇文章：Java 常见并发容器总结 。CopyOnWriteArrayList 到底有什么厉害之处？对于大部分业务场景来说，读取操作往往是远大于写入操作的。由于读取操作不会对原有数据进行修改，因此，对于每次读取都进行加锁其实是一种资源浪费。相比之下，我们应该允许多个线程同时访问 List 的内部数据，毕竟对于读取操作来说是安全的。这种思路与 ReentrantReadWriteLock 读写锁的设计思想非常类似，即读读不互斥、读写互斥、写写互斥（只有读读不互斥）。CopyOnWriteArrayList 更进一步地实现了这一思想。为了将读操作性能发挥到极致，CopyOnWriteArrayList 中的读取操作是完全无需加锁的。更加厉害的是，写入操作也不会阻塞读取操作，只有写写才会互斥。这样一来，读操作的性能就可以大幅度提升。CopyOnWriteArrayList 线程安全的核心在于其采用了 写时复制（Copy-On-Write） 的策略，从 CopyOnWriteArrayList 的名字就能看出了。Copy-On-Write 的思想是什么？CopyOnWriteArrayList名字中的“Copy-On-Write”即写时复制，简称 COW。下面是维基百科对 Copy-On-Write 的介绍，介绍的挺不错：写入时复制（英语：Copy-on-write，简称 COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。这里再以 CopyOnWriteArrayList为例介绍：当需要修改（ add，set、remove 等操作） CopyOnWriteArrayList 的内容时，不会直接修改原数组，而是会先创建底层数组的副本，对副本数组进行修改，修改完之后再将修改后的数组赋值回去，这样就可以保证写操作不会影响读操作了。可以看出，写时复制机制非常适合读多写少的并发场景，能够极大地提高系统的并发性能。不过，写时复制机制并不是银弹，其依然存在一些缺点，下面列举几点：内存占用：每次写操作都需要复制一份原始数据，会占用额外的内存空间，在数据量比较大的情况下，可能会导致内存资源不足。写操作开销：每一次写操作都需要复制一份原始数据，然后再进行修改和替换，所以写操作的开销相对较大，在写入比较频繁的场景下，性能可能会受到影响。数据一致性问题：修改操作不会立即反映到最终结果中，还需要等待复制完成，这可能会导致一定的数据一致性问题。……CopyOnWriteArrayList 源码分析这里以 JDK1.8 为例，分析一下 CopyOnWriteArrayList 的底层核心源码。CopyOnWriteArrayList 的类定义如下：public class CopyOnWriteArrayList<E> extends Object implements List<E>, RandomAccess, Cloneable, Serializable { //... }CopyOnWriteArrayList 实现了以下接口：List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。初始化CopyOnWriteArrayList 中有一个无参构造函数和两个有参构造函数。// 创建一个空的 CopyOnWriteArrayList public CopyOnWriteArrayList() { setArray(new Object[0]); } // 按照集合的迭代器返回的顺序创建一个包含指定集合元素的 CopyOnWriteArrayList public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; if (c.getClass() == CopyOnWriteArrayList.class) elements = ((CopyOnWriteArrayList<?>)c).getArray(); else { elements = c.toArray(); // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elements.getClass() != Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); } setArray(elements); } // 创建一个包含指定数组的副本的列表 public CopyOnWriteArrayList(E[] toCopyIn) { setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); }插入元素CopyOnWriteArrayList 的 add()方法有三个版本：add(E e)：在 CopyOnWriteArrayList 的尾部插入元素。add(int index, E element)：在 CopyOnWriteArrayList 的指定位置插入元素。addIfAbsent(E e)：如果指定元素不存在，那么添加该元素。如果成功添加元素则返回 true。这里以add(E e)为例进行介绍：// 插入元素到 CopyOnWriteArrayList 的尾部 public boolean add(E e) { final ReentrantLock lock = this.lock; // 加锁 lock.lock(); try { // 获取原来的数组 Object[] elements = getArray(); // 原来数组的长度 int len = elements.length; // 创建一个长度+1的新数组，并将原来数组的元素复制给新数组 Object[] newElements = Arrays.copyOf(elements, len + 1); // 元素放在新数组末尾 newElements[len] = e; // array指向新数组 setArray(newElements); return true; } finally { // 解锁 lock.unlock(); } }从上面的源码可以看出：add方法内部用到了 ReentrantLock 加锁，保证了同步，避免了多线程写的时候会复制出多个副本出来。锁被修饰保证了锁的内存地址肯定不会被修改，并且，释放锁的逻辑放在 finally 中，可以保证锁能被释放。CopyOnWriteArrayList 通过复制底层数组的方式实现写操作，即先创建一个新的数组来容纳新添加的元素，然后在新数组中进行写操作，最后将新数组赋值给底层数组的引用，替换掉旧的数组。这也就证明了我们前面说的：CopyOnWriteArrayList 线程安全的核心在于其采用了 写时复制（Copy-On-Write） 的策略。每次写操作都需要通过 Arrays.copyOf 复制底层数组，时间复杂度是 O(n) 的，且会占用额外的内存空间。因此，CopyOnWriteArrayList 适用于读多写少的场景，在写操作不频繁且内存资源充足的情况下，可以提升系统的性能表现。CopyOnWriteArrayList 中并没有类似于 ArrayList 的 grow() 方法扩容的操作。Arrays.copyOf 方法的时间复杂度是 O(n)，其中 n 表示需要复制的数组长度。因为这个方法的实现原理是先创建一个新的数组，然后将源数组中的数据复制到新数组中，最后返回新数组。这个方法会复制整个数组，因此其时间复杂度与数组长度成正比，即 O(n)。值得注意的是，由于底层调用了系统级别的拷贝指令，因此在实际应用中这个方法的性能表现比较优秀，但是也需要注意控制复制的数据量，避免出现内存占用过高的情况。读取元素CopyOnWriteArrayList 的读取操作是基于内部数组 array 并没有发生实际的修改，因此在读取操作时不需要进行同步控制和锁操作，可以保证数据的安全性。这种机制下，多个线程可以同时读取列表中的元素。// 底层数组，只能通过getArray和setArray方法访问 private transient volatile Object[] array; public E get(int index) { return get(getArray(), index); } final Object[] getArray() { return array; } private E get(Object[] a, int index) { return (E) a[index]; }不过，get方法是弱一致性的，在某些情况下可能读到旧的元素值。get(int index)方法是分两步进行的：通过getArray()获取当前数组的引用；直接从数组中获取下标为 index 的元素。这个过程并没有加锁，所以在并发环境下可能出现如下情况：线程 1 调用get(int index)方法获取值，内部通过getArray()方法获取到了 array 属性值；线程 2 调用CopyOnWriteArrayList的add、set、remove 等修改方法时，内部通过setArray方法修改了array属性的值；线程 1 还是从旧的 array 数组中取值。获取列表中元素的个数public int size() { return getArray().length; }CopyOnWriteArrayList中的array数组每次复制都刚好能够容纳下所有元素，并不像ArrayList那样会预留一定的空间。因此，CopyOnWriteArrayList中并没有size属性CopyOnWriteArrayList的底层数组的长度就是元素个数，因此size()方法只要返回数组长度就可以了。删除元素CopyOnWriteArrayList删除元素相关的方法一共有 4 个：remove(int index)：移除此列表中指定位置上的元素。将任何后续元素向左移动（从它们的索引中减去 1）。boolean remove(Object o)：删除此列表中首次出现的指定元素，如果不存在该元素则返回 false。boolean removeAll(Collection<?> c)：从此列表中删除指定集合中包含的所有元素。void clear()：移除此列表中的所有元素。这里以remove(int index)为例进行介绍：public E remove(int index) { // 获取可重入锁 final ReentrantLock lock = this.lock; // 加锁 lock.lock(); try { //获取当前array数组 Object[] elements = getArray(); // 获取当前array长度 int len = elements.length; //获取指定索引的元素(旧值) E oldValue = get(elements, index); int numMoved = len - index - 1; // 判断删除的是否是最后一个元素 if (numMoved == 0) // 如果删除的是最后一个元素，直接复制该元素前的所有元素到新的数组 setArray(Arrays.copyOf(elements, len - 1)); else { // 分段复制，将index前的元素和index+1后的元素复制到新数组 // 新数组长度为旧数组长度-1 Object[] newElements = new Object[len - 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index + 1, newElements, index, numMoved); //将新数组赋值给array引用 setArray(newElements); } return oldValue; } finally { // 解锁 lock.unlock(); } }判断元素是否存在CopyOnWriteArrayList提供了两个用于判断指定元素是否在列表中的方法：contains(Object o)：判断是否包含指定元素。containsAll(Collection<?> c)：判断是否保证指定集合的全部元素。// 判断是否包含指定元素 public boolean contains(Object o) { //获取当前array数组 Object[] elements = getArray(); //调用index尝试查找指定元素，如果返回值大于等于0，则返回true，否则返回false return indexOf(o, elements, 0, elements.length) >= 0; } // 判断是否保证指定集合的全部元素 public boolean containsAll(Collection<?> c) { //获取当前array数组 Object[] elements = getArray(); //获取数组长度 int len = elements.length; //遍历指定集合 for (Object e : c) { //循环调用indexOf方法判断，只要有一个没有包含就直接返回false if (indexOf(e, elements, 0, len) < 0) return false; } //最后表示全部包含或者制定集合为空集合，那么返回true return true; }CopyOnWriteArrayList 常用方法测试代码：// 创建一个 CopyOnWriteArrayList 对象 CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); // 向列表中添加元素 list.add("Java"); list.add("Python"); list.add("C++"); System.out.println("初始列表：" + list); // 使用 get 方法获取指定位置的元素 System.out.println("列表第二个元素为：" + list.get(1)); // 使用 remove 方法删除指定元素 boolean result = list.remove("C++"); System.out.println("删除结果：" + result); System.out.println("列表删除元素后为：" + list); // 使用 set 方法更新指定位置的元素 list.set(1, "Golang"); System.out.println("列表更新后为：" + list); // 使用 add 方法在指定位置插入元素 list.add(0, "PHP"); System.out.println("列表插入元素后为：" + list); // 使用 size 方法获取列表大小 System.out.println("列表大小为：" + list.size()); // 使用 removeAll 方法删除指定集合中所有出现的元素 result = list.removeAll(List.of("Java", "Golang")); System.out.println("批量删除结果：" + result); System.out.println("列表批量删除元素后为：" + list); // 使用 clear 方法清空列表中所有元素 list.clear(); System.out.println("列表清空后为：" + list);输出：列表更新后为：[Java, Golang] 列表插入元素后为：[PHP, Java, Golang] 列表大小为：3 批量删除结果：true 列表批量删除元素后为：[PHP] 列表清空后为：[]
AI 摘要 文章系统剖析ThreadLocal：从弱引用key、ThreadLocalMap结构、黄金分割哈希、线性探测解决冲突，到set/get、探测式与启发式清理、扩容机制，再延伸到InheritableThreadLocal及分布式链路traceId实战，覆盖原理、源码与项目踩坑。 此摘要根据文章内容自动生成，仅用于文章内容的解释与总结title: ThreadLocal 详解category: Javatag:Java并发前言全文共 10000+字，31 张图，这篇文章同样耗费了不少的时间和精力才创作完成，原创不易，请大家点点关注+在看，感谢。对于ThreadLocal，大家的第一反应可能是很简单呀，线程的变量副本，每个线程隔离。那这里有几个问题大家可以思考一下：ThreadLocal的 key 是弱引用，那么在 ThreadLocal.get()的时候，发生GC之后，key 是否为null？ThreadLocal中ThreadLocalMap的数据结构？ThreadLocalMap的Hash 算法？ThreadLocalMap中Hash 冲突如何解决？ThreadLocalMap的扩容机制？ThreadLocalMap中过期 key 的清理机制？探测式清理和启发式清理流程？ThreadLocalMap.set()方法实现原理？ThreadLocalMap.get()方法实现原理？项目中ThreadLocal使用情况？遇到的坑？……上述的一些问题你是否都已经掌握的很清楚了呢？本文将围绕这些问题使用图文方式来剖析ThreadLocal的点点滴滴。目录注明： 本文源码基于JDK 1.8ThreadLocal代码演示我们先看下ThreadLocal使用示例：public class ThreadLocalTest { private List<String> messages = Lists.newArrayList(); public static final ThreadLocal<ThreadLocalTest> holder = ThreadLocal.withInitial(ThreadLocalTest::new); public static void add(String message) { holder.get().messages.add(message); } public static List<String> clear() { List<String> messages = holder.get().messages; holder.remove(); System.out.println("size: " + holder.get().messages.size()); return messages; } public static void main(String[] args) { ThreadLocalTest.add("一枝花算不算浪漫"); System.out.println(holder.get().messages); ThreadLocalTest.clear(); } }打印结果：[一枝花算不算浪漫] size: 0ThreadLocal对象可以提供线程局部变量，每个线程Thread拥有一份自己的副本变量，多个线程互不干扰。ThreadLocal的数据结构Thread类有一个类型为ThreadLocal.ThreadLocalMap的实例变量threadLocals，也就是说每个线程有一个自己的ThreadLocalMap。ThreadLocalMap有自己的独立实现，可以简单地将它的key视作ThreadLocal，value为代码中放入的值（实际上key并不是ThreadLocal本身，而是它的一个弱引用）。每个线程在往ThreadLocal里放值的时候，都会往自己的ThreadLocalMap里存，读也是以ThreadLocal作为引用，在自己的map里找对应的key，从而实现了线程隔离。ThreadLocalMap有点类似HashMap的结构，只是HashMap是由数组+链表实现的，而ThreadLocalMap中并没有链表结构。我们还要注意Entry， 它的key是ThreadLocal<?> k ，继承自WeakReference， 也就是我们常说的弱引用类型。GC 之后 key 是否为 null？回应开头的那个问题， ThreadLocal 的key是弱引用，那么在ThreadLocal.get()的时候，发生GC之后，key是否是null？为了搞清楚这个问题，我们需要搞清楚Java的四种引用类型：强引用：我们常常 new 出来的对象就是强引用类型，只要强引用存在，垃圾回收器将永远不会回收被引用的对象，哪怕内存不足的时候软引用：使用 SoftReference 修饰的对象被称为软引用，软引用指向的对象在内存要溢出的时候被回收弱引用：使用 WeakReference 修饰的对象被称为弱引用，只要发生垃圾回收，若这个对象只被弱引用指向，那么就会被回收虚引用：虚引用是最弱的引用，在 Java 中使用 PhantomReference 进行定义。虚引用中唯一的作用就是用队列接收对象即将死亡的通知接着再来看下代码，我们使用反射的方式来看看GC后ThreadLocal中的数据情况：(下面代码来源自：https://blog.csdn.net/thewindkee/article/details/103726942 本地运行演示 GC 回收场景)public class ThreadLocalDemo { public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException, InterruptedException { Thread t = new Thread(()->test("abc",false)); t.start(); t.join(); System.out.println("--gc后--"); Thread t2 = new Thread(() -> test("def", true)); t2.start(); t2.join(); } private static void test(String s,boolean isGC) { try { new ThreadLocal<>().set(s); if (isGC) { System.gc(); } Thread t = Thread.currentThread(); Class<? extends Thread> clz = t.getClass(); Field field = clz.getDeclaredField("threadLocals"); field.setAccessible(true); Object ThreadLocalMap = field.get(t); Class<?> tlmClass = ThreadLocalMap.getClass(); Field tableField = tlmClass.getDeclaredField("table"); tableField.setAccessible(true); Object[] arr = (Object[]) tableField.get(ThreadLocalMap); for (Object o : arr) { if (o != null) { Class<?> entryClass = o.getClass(); Field valueField = entryClass.getDeclaredField("value"); Field referenceField = entryClass.getSuperclass().getSuperclass().getDeclaredField("referent"); valueField.setAccessible(true); referenceField.setAccessible(true); System.out.println(String.format("弱引用key:%s,值:%s", referenceField.get(o), valueField.get(o))); } } } catch (Exception e) { e.printStackTrace(); } } }结果如下：弱引用key:java.lang.ThreadLocal@433619b6,值:abc 弱引用key:java.lang.ThreadLocal@418a15e3,值:java.lang.ref.SoftReference@bf97a12 --gc后-- 弱引用key:null,值:def如图所示，因为这里创建的ThreadLocal并没有指向任何值，也就是没有任何引用：new ThreadLocal<>().set(s);所以这里在GC之后，key就会被回收，我们看到上面debug中的referent=null, 如果改动一下代码：这个问题刚开始看，如果没有过多思考，弱引用，还有垃圾回收，那么肯定会觉得是null。其实是不对的，因为题目说的是在做 ThreadLocal.get() 操作，证明其实还是有强引用存在的，所以 key 并不为 null，如下图所示，ThreadLocal的强引用仍然是存在的。如果我们的强引用不存在的话，那么 key 就会被回收，也就是会出现我们 value 没被回收，key 被回收，导致 value 永远存在，出现内存泄漏。ThreadLocal.set()方法源码详解ThreadLocal中的set方法原理如上图所示，很简单，主要是判断ThreadLocalMap是否存在，然后使用ThreadLocal中的set方法进行数据处理。代码如下：public void set(T value) { Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t); if (map != null) map.set(this, value); else createMap(t, value); } void createMap(Thread t, T firstValue) { t.threadLocals = new ThreadLocalMap(this, firstValue); }主要的核心逻辑还是在ThreadLocalMap中的，一步步往下看，后面还有更详细的剖析。ThreadLocalMap Hash 算法既然是Map结构，那么ThreadLocalMap当然也要实现自己的hash算法来解决散列表数组冲突问题。int i = key.threadLocalHashCode & (len-1);ThreadLocalMap中hash算法很简单，这里i就是当前 key 在散列表中对应的数组下标位置。这里最关键的就是threadLocalHashCode值的计算，ThreadLocal中有一个属性为HASH_INCREMENT = 0x61c88647public class ThreadLocal<T> { private final int threadLocalHashCode = nextHashCode(); private static AtomicInteger nextHashCode = new AtomicInteger(); private static final int HASH_INCREMENT = 0x61c88647; private static int nextHashCode() { return nextHashCode.getAndAdd(HASH_INCREMENT); } static class ThreadLocalMap { ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) { table = new Entry[INITIAL_CAPACITY]; int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1); table[i] = new Entry(firstKey, firstValue); size = 1; setThreshold(INITIAL_CAPACITY); } } }每当创建一个ThreadLocal对象，这个ThreadLocal.nextHashCode 这个值就会增长 0x61c88647 。这个值很特殊，它是斐波那契数 也叫 黄金分割数。hash增量为 这个数字，带来的好处就是 hash 分布非常均匀。我们自己可以尝试下：可以看到产生的哈希码分布很均匀，这里不去细纠斐波那契具体算法，感兴趣的可以自行查阅相关资料。ThreadLocalMap Hash 冲突注明： 下面所有示例图中，绿色块Entry代表正常数据，灰色块代表Entry的key值为null，已被垃圾回收。白色块表示Entry为null。虽然ThreadLocalMap中使用了黄金分割数来作为hash计算因子，大大减少了Hash冲突的概率，但是仍然会存在冲突。HashMap中解决冲突的方法是在数组上构造一个链表结构，冲突的数据挂载到链表上，如果链表长度超过一定数量则会转化成红黑树。而 ThreadLocalMap 中并没有链表结构，所以这里不能使用 HashMap 解决冲突的方式了。如上图所示，如果我们插入一个value=27的数据，通过 hash 计算后应该落入槽位 4 中，而槽位 4 已经有了 Entry 数据。此时就会线性向后查找，一直找到 Entry 为 null 的槽位才会停止查找，将当前元素放入此槽位中。当然迭代过程中还有其他的情况，比如遇到了 Entry 不为 null 且 key 值相等的情况，还有 Entry 中的 key 值为 null 的情况等等都会有不同的处理，后面会一一详细讲解。这里还画了一个Entry中的key为null的数据（Entry=2 的灰色块数据），因为key值是弱引用类型，所以会有这种数据存在。在set过程中，如果遇到了key过期的Entry数据，实际上是会进行一轮探测式清理操作的，具体操作方式后面会讲到。ThreadLocalMap.set()详解ThreadLocalMap.set()原理图解看完了ThreadLocal hash 算法后，我们再来看set是如何实现的。往ThreadLocalMap中set数据（新增或者更新数据）分为好几种情况，针对不同的情况我们画图来说明。第一种情况： 通过hash计算后的槽位对应的Entry数据为空：这里直接将数据放到该槽位即可。第二种情况： 槽位数据不为空，key值与当前ThreadLocal通过hash计算获取的key值一致：这里直接更新该槽位的数据。第三种情况： 槽位数据不为空，往后遍历过程中，在找到Entry为null的槽位之前，没有遇到key过期的Entry：遍历散列数组，线性往后查找，如果找到Entry为null的槽位，则将数据放入该槽位中，或者往后遍历过程中，遇到了key 值相等的数据，直接更新即可。第四种情况： 槽位数据不为空，往后遍历过程中，在找到Entry为null的槽位之前，遇到key过期的Entry，如下图，往后遍历过程中，遇到了index=7的槽位数据Entry的key=null：散列数组下标为 7 位置对应的Entry数据key为null，表明此数据key值已经被垃圾回收掉了，此时就会执行replaceStaleEntry()方法，该方法含义是替换过期数据的逻辑，以index=7位起点开始遍历，进行探测式数据清理工作。初始化探测式清理过期数据扫描的开始位置：slotToExpunge = staleSlot = 7以当前staleSlot开始 向前迭代查找，找其他过期的数据，然后更新过期数据起始扫描下标slotToExpunge。for循环迭代，直到碰到Entry为null结束。如果找到了过期的数据，继续向前迭代，直到遇到Entry=null的槽位才停止迭代，如下图所示，slotToExpunge 被更新为 0：以当前节点(index=7)向前迭代，检测是否有过期的Entry数据，如果有则更新slotToExpunge值。碰到null则结束探测。以上图为例slotToExpunge被更新为 0。上面向前迭代的操作是为了更新探测清理过期数据的起始下标slotToExpunge的值，这个值在后面会讲解，它是用来判断当前过期槽位staleSlot之前是否还有过期元素。接着开始以staleSlot位置(index=7)向后迭代，如果找到了相同 key 值的 Entry 数据：从当前节点staleSlot向后查找key值相等的Entry元素，找到后更新Entry的值并交换staleSlot元素的位置(staleSlot位置为过期元素)，更新Entry数据，然后开始进行过期Entry的清理工作，如下图所示：向后遍历过程中，如果没有找到相同 key 值的 Entry 数据：从当前节点staleSlot向后查找key值相等的Entry元素，直到Entry为null则停止寻找。通过上图可知，此时table中没有key值相同的Entry。创建新的Entry，替换table[stableSlot]位置：替换完成后也是进行过期元素清理工作，清理工作主要是有两个方法：expungeStaleEntry()和cleanSomeSlots()，具体细节后面会讲到，请继续往后看。ThreadLocalMap.set()源码详解上面已经用图的方式解析了set()实现的原理，其实已经很清晰了，我们接着再看下源码：java.lang.ThreadLocal.ThreadLocalMap.set():private void set(ThreadLocal<?> key, Object value) { Entry[] tab = table; int len = tab.length; int i = key.threadLocalHashCode & (len-1); for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<?> k = e.get(); if (k == key) { e.value = value; return; } if (k == null) { replaceStaleEntry(key, value, i); return; } } tab[i] = new Entry(key, value); int sz = ++size; if (!cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }这里会通过key来计算在散列表中的对应位置，然后以当前key对应的桶的位置向后查找，找到可以使用的桶。Entry[] tab = table; int len = tab.length; int i = key.threadLocalHashCode & (len-1);什么情况下桶才是可以使用的呢？k = key 说明是替换操作，可以使用碰到一个过期的桶，执行替换逻辑，占用过期桶查找过程中，碰到桶中Entry=null的情况，直接使用接着就是执行for循环遍历，向后查找，我们先看下nextIndex()、prevIndex()方法实现：private static int nextIndex(int i, int len) { return ((i + 1 < len) ? i + 1 : 0); } private static int prevIndex(int i, int len) { return ((i - 1 >= 0) ? i - 1 : len - 1); }接着看剩下for循环中的逻辑：遍历当前key值对应的桶中Entry数据为空，这说明散列数组这里没有数据冲突，跳出for循环，直接set数据到对应的桶中如果key值对应的桶中Entry数据不为空 2.1 如果k = key，说明当前set操作是一个替换操作，做替换逻辑，直接返回 2.2 如果key = null，说明当前桶位置的Entry是过期数据，执行replaceStaleEntry()方法(核心方法)，然后返回for循环执行完毕，继续往下执行说明向后迭代的过程中遇到了entry为null的情况 3.1 在Entry为null的桶中创建一个新的Entry对象 3.2 执行++size操作调用cleanSomeSlots()做一次启发式清理工作，清理散列数组中Entry的key过期的数据 4.1 如果清理工作完成后，未清理到任何数据，且size超过了阈值(数组长度的 2/3)，进行rehash()操作 4.2 rehash()中会先进行一轮探测式清理，清理过期key，清理完成后如果size >= threshold - threshold / 4，就会执行真正的扩容逻辑(扩容逻辑往后看)接着重点看下replaceStaleEntry()方法，replaceStaleEntry()方法提供替换过期数据的功能，我们可以对应上面第四种情况的原理图来再回顾下，具体代码如下：java.lang.ThreadLocal.ThreadLocalMap.replaceStaleEntry():private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) { Entry[] tab = table; int len = tab.length; Entry e; int slotToExpunge = staleSlot; for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len)) if (e.get() == null) slotToExpunge = i; for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) { ThreadLocal<?> k = e.get(); if (k == key) { e.value = value; tab[i] = tab[staleSlot]; tab[staleSlot] = e; if (slotToExpunge == staleSlot) slotToExpunge = i; cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); return; } if (k == null && slotToExpunge == staleSlot) slotToExpunge = i; } tab[staleSlot].value = null; tab[staleSlot] = new Entry(key, value); if (slotToExpunge != staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); }slotToExpunge表示开始探测式清理过期数据的开始下标，默认从当前的staleSlot开始。以当前的staleSlot开始，向前迭代查找，找到没有过期的数据，for循环一直碰到Entry为null才会结束。如果向前找到了过期数据，更新探测清理过期数据的开始下标为 i，即slotToExpunge=ifor (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len)){ if (e.get() == null){ slotToExpunge = i; } }接着开始从staleSlot向后查找，也是碰到Entry为null的桶结束。如果迭代过程中，碰到 k == key，这说明这里是替换逻辑，替换新数据并且交换当前staleSlot位置。如果slotToExpunge == staleSlot，这说明replaceStaleEntry()一开始向前查找过期数据时并未找到过期的Entry数据，接着向后查找过程中也未发现过期数据，修改开始探测式清理过期数据的下标为当前循环的 index，即slotToExpunge = i。最后调用cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);进行启发式过期数据清理。if (k == key) { e.value = value; tab[i] = tab[staleSlot]; tab[staleSlot] = e; if (slotToExpunge == staleSlot) slotToExpunge = i; cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); return; }cleanSomeSlots()和expungeStaleEntry()方法后面都会细讲，这两个是和清理相关的方法，一个是过期key相关Entry的启发式清理(Heuristically scan)，另一个是过期key相关Entry的探测式清理。如果 k != key则会接着往下走，k == null说明当前遍历的Entry是一个过期数据，slotToExpunge == staleSlot说明，一开始的向前查找数据并未找到过期的Entry。如果条件成立，则更新slotToExpunge 为当前位置，这个前提是前驱节点扫描时未发现过期数据。if (k == null && slotToExpunge == staleSlot) slotToExpunge = i;往后迭代的过程中如果没有找到k == key的数据，且碰到Entry为null的数据，则结束当前的迭代操作。此时说明这里是一个添加的逻辑，将新的数据添加到table[staleSlot] 对应的slot中。tab[staleSlot].value = null; tab[staleSlot] = new Entry(key, value);最后判断除了staleSlot以外，还发现了其他过期的slot数据，就要开启清理数据的逻辑：if (slotToExpunge != staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);ThreadLocalMap过期 key 的探测式清理流程上面我们有提及ThreadLocalMap的两种过期key数据清理方式：探测式清理和启发式清理。我们先讲下探测式清理，也就是expungeStaleEntry方法，遍历散列数组，从开始位置向后探测清理过期数据，将过期数据的Entry设置为null，沿途中碰到未过期的数据则将此数据rehash后重新在table数组中定位，如果定位的位置已经有了数据，则会将未过期的数据放到最靠近此位置的Entry=null的桶中，使rehash后的Entry数据距离正确的桶的位置更近一些。操作逻辑如下：如上图，set(27) 经过 hash 计算后应该落到index=4的桶中，由于index=4桶已经有了数据，所以往后迭代最终数据放入到index=7的桶中，放入后一段时间后index=5中的Entry数据key变为了null如果再有其他数据set到map中，就会触发探测式清理操作。如上图，执行探测式清理后，index=5的数据被清理掉，继续往后迭代，到index=7的元素时，经过rehash后发现该元素正确的index=4，而此位置已经有了数据，往后查找离index=4最近的Entry=null的节点(刚被探测式清理掉的数据：index=5)，找到后移动index= 7的数据到index=5中，此时桶的位置离正确的位置index=4更近了。经过一轮探测式清理后，key过期的数据会被清理掉，没过期的数据经过rehash重定位后所处的桶位置理论上更接近i= key.hashCode & (tab.len - 1)的位置。这种优化会提高整个散列表查询性能。接着看下expungeStaleEntry()具体流程，我们还是以先原理图后源码讲解的方式来一步步梳理：我们假设expungeStaleEntry(3) 来调用此方法，如上图所示，我们可以看到ThreadLocalMap中table的数据情况，接着执行清理操作：第一步是清空当前staleSlot位置的数据，index=3位置的Entry变成了null。然后接着往后探测：执行完第二步后，index=4 的元素挪到 index=3 的槽位中。继续往后迭代检查，碰到正常数据，计算该数据位置是否偏移，如果被偏移，则重新计算slot位置，目的是让正常数据尽可能存放在正确位置或离正确位置更近的位置在往后迭代的过程中碰到空的槽位，终止探测，这样一轮探测式清理工作就完成了，接着我们继续看看具体实现源代码：private int expungeStaleEntry(int staleSlot) { Entry[] tab = table; int len = tab.length; tab[staleSlot].value = null; tab[staleSlot] = null; size--; Entry e; int i; for (i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) { ThreadLocal<?> k = e.get(); if (k == null) { e.value = null; tab[i] = null; size--; } else { int h = k.threadLocalHashCode & (len - 1); if (h != i) { tab[i] = null; while (tab[h] != null) h = nextIndex(h, len); tab[h] = e; } } } return i; }这里我们还是以staleSlot=3 来做示例说明，首先是将tab[staleSlot]槽位的数据清空，然后设置size--接着以staleSlot位置往后迭代，如果遇到k==null的过期数据，也是清空该槽位数据，然后size--ThreadLocal<?> k = e.get(); if (k == null) { e.value = null; tab[i] = null; size--; }如果key没有过期，重新计算当前key的下标位置是不是当前槽位下标位置，如果不是，那么说明产生了hash冲突，此时以新计算出来正确的槽位位置往后迭代，找到最近一个可以存放entry的位置。int h = k.threadLocalHashCode & (len - 1); if (h != i) { tab[i] = null; while (tab[h] != null) h = nextIndex(h, len); tab[h] = e; }这里是处理正常的产生Hash冲突的数据，经过迭代后，有过Hash冲突数据的Entry位置会更靠近正确位置，这样的话，查询的时候 效率才会更高。ThreadLocalMap扩容机制在ThreadLocalMap.set()方法的最后，如果执行完启发式清理工作后，未清理到任何数据，且当前散列数组中Entry的数量已经达到了列表的扩容阈值(len*2/3)，就开始执行rehash()逻辑：if (!cleanSomeSlots(i, sz) && sz >= threshold) rehash();接着看下rehash()具体实现：private void rehash() { expungeStaleEntries(); if (size >= threshold - threshold / 4) resize(); } private void expungeStaleEntries() { Entry[] tab = table; int len = tab.length; for (int j = 0; j < len; j++) { Entry e = tab[j]; if (e != null && e.get() == null) expungeStaleEntry(j); } }这里首先是会进行探测式清理工作，从table的起始位置往后清理，上面有分析清理的详细流程。清理完成之后，table中可能有一些key为null的Entry数据被清理掉，所以此时通过判断size >= threshold - threshold / 4 也就是size >= threshold * 3/4 来决定是否扩容。我们还记得上面进行rehash()的阈值是size >= threshold，所以当面试官套路我们ThreadLocalMap扩容机制的时候 我们一定要说清楚这两个步骤：接着看看具体的resize()方法，为了方便演示，我们以oldTab.len=8来举例：扩容后的tab的大小为oldLen * 2，然后遍历老的散列表，重新计算hash位置，然后放到新的tab数组中，如果出现hash冲突则往后寻找最近的entry为null的槽位，遍历完成之后，oldTab中所有的entry数据都已经放入到新的tab中了。重新计算tab下次扩容的阈值，具体代码如下：private void resize() { Entry[] oldTab = table; int oldLen = oldTab.length; int newLen = oldLen * 2; Entry[] newTab = new Entry[newLen]; int count = 0; for (int j = 0; j < oldLen; ++j) { Entry e = oldTab[j]; if (e != null) { ThreadLocal<?> k = e.get(); if (k == null) { e.value = null; } else { int h = k.threadLocalHashCode & (newLen - 1); while (newTab[h] != null) h = nextIndex(h, newLen); newTab[h] = e; count++; } } } setThreshold(newLen); size = count; table = newTab; }ThreadLocalMap.get()详解上面已经看完了set()方法的源码，其中包括set数据、清理数据、优化数据桶的位置等操作，接着看看get()操作的原理。ThreadLocalMap.get()图解第一种情况： 通过查找key值计算出散列表中slot位置，然后该slot位置中的Entry.key和查找的key一致，则直接返回：第二种情况： slot位置中的Entry.key和要查找的key不一致：我们以get(ThreadLocal1)为例，通过hash计算后，正确的slot位置应该是 4，而index=4的槽位已经有了数据，且key值不等于ThreadLocal1，所以需要继续往后迭代查找。迭代到index=5的数据时，此时Entry.key=null，触发一次探测式数据回收操作，执行expungeStaleEntry()方法，执行完后，index 5,8的数据都会被回收，而index 6,7的数据都会前移。index 6,7前移之后，继续从 index=5 往后迭代，于是就在 index=6 找到了key值相等的Entry数据，如下图所示：ThreadLocalMap.get()源码详解java.lang.ThreadLocal.ThreadLocalMap.getEntry():private Entry getEntry(ThreadLocal<?> key) { int i = key.threadLocalHashCode & (table.length - 1); Entry e = table[i]; if (e != null && e.get() == key) return e; else return getEntryAfterMiss(key, i, e); } private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) { Entry[] tab = table; int len = tab.length; while (e != null) { ThreadLocal<?> k = e.get(); if (k == key) return e; if (k == null) expungeStaleEntry(i); else i = nextIndex(i, len); e = tab[i]; } return null; }ThreadLocalMap过期 key 的启发式清理流程上面多次提及到ThreadLocalMap过期 key 的两种清理方式：探测式清理(expungeStaleEntry())、启发式清理(cleanSomeSlots())探测式清理是以当前Entry 往后清理，遇到值为null则结束清理，属于线性探测清理。而启发式清理被作者定义为：Heuristically scan some cells looking for stale entries.具体代码如下：private boolean cleanSomeSlots(int i, int n) { boolean removed = false; Entry[] tab = table; int len = tab.length; do { i = nextIndex(i, len); Entry e = tab[i]; if (e != null && e.get() == null) { n = len; removed = true; i = expungeStaleEntry(i); } } while ( (n >>>= 1) != 0); return removed; }InheritableThreadLocal我们使用ThreadLocal的时候，在异步场景下是无法给子线程共享父线程中创建的线程副本数据的。为了解决这个问题，JDK 中还有一个InheritableThreadLocal类，我们来看一个例子：public class InheritableThreadLocalDemo { public static void main(String[] args) { ThreadLocal<String> ThreadLocal = new ThreadLocal<>(); ThreadLocal<String> inheritableThreadLocal = new InheritableThreadLocal<>(); ThreadLocal.set("父类数据:threadLocal"); inheritableThreadLocal.set("父类数据:inheritableThreadLocal"); new Thread(new Runnable() { @Override public void run() { System.out.println("子线程获取父类ThreadLocal数据：" + ThreadLocal.get()); System.out.println("子线程获取父类inheritableThreadLocal数据：" + inheritableThreadLocal.get()); } }).start(); } }打印结果：子线程获取父类ThreadLocal数据：null 子线程获取父类inheritableThreadLocal数据：父类数据:inheritableThreadLocal实现原理是子线程是通过在父线程中通过调用new Thread()方法来创建子线程，Thread#init方法在Thread的构造方法中被调用。在init方法中拷贝父线程数据到子线程中：private void init(ThreadGroup g, Runnable target, String name, long stackSize, AccessControlContext acc, boolean inheritThreadLocals) { if (name == null) { throw new NullPointerException("name cannot be null"); } if (inheritThreadLocals && parent.inheritableThreadLocals != null) this.inheritableThreadLocals = ThreadLocal.createInheritedMap(parent.inheritableThreadLocals); this.stackSize = stackSize; tid = nextThreadID(); }但InheritableThreadLocal仍然有缺陷，一般我们做异步化处理都是使用的线程池，而InheritableThreadLocal是在new Thread中的init()方法给赋值的，而线程池是线程复用的逻辑，所以这里会存在问题。当然，有问题出现就会有解决问题的方案，阿里巴巴开源了一个TransmittableThreadLocal组件就可以解决这个问题，这里就不再延伸，感兴趣的可自行查阅资料。ThreadLocal项目中使用实战ThreadLocal使用场景我们现在项目中日志记录用的是ELK+Logstash，最后在Kibana中进行展示和检索。现在都是分布式系统统一对外提供服务，项目间调用的关系可以通过 traceId 来关联，但是不同项目之间如何传递 traceId 呢？这里我们使用 org.slf4j.MDC 来实现此功能，内部就是通过 ThreadLocal 来实现的，具体实现如下：当前端发送请求到服务 A时，服务 A会生成一个类似UUID的traceId字符串，将此字符串放入当前线程的ThreadLocal中，在调用服务 B的时候，将traceId写入到请求的Header中，服务 B在接收请求时会先判断请求的Header中是否有traceId，如果存在则写入自己线程的ThreadLocal中。图中的requestId即为我们各个系统链路关联的traceId，系统间互相调用，通过这个requestId即可找到对应链路，这里还有会有一些其他场景：针对于这些场景，我们都可以有相应的解决方案，如下所示Feign 远程调用解决方案服务发送请求：@Component @Slf4j public class FeignInvokeInterceptor implements RequestInterceptor { @Override public void apply(RequestTemplate template) { String requestId = MDC.get("requestId"); if (StringUtils.isNotBlank(requestId)) { template.header("requestId", requestId); } } }服务接收请求：@Slf4j @Component public class LogInterceptor extends HandlerInterceptorAdapter { @Override public void afterCompletion(HttpServletRequest arg0, HttpServletResponse arg1, Object arg2, Exception arg3) { MDC.remove("requestId"); } @Override public void postHandle(HttpServletRequest arg0, HttpServletResponse arg1, Object arg2, ModelAndView arg3) { } @Override public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception { String requestId = request.getHeader(BaseConstant.REQUEST_ID_KEY); if (StringUtils.isBlank(requestId)) { requestId = UUID.randomUUID().toString().replace("-", ""); } MDC.put("requestId", requestId); return true; } }线程池异步调用，requestId 传递因为MDC是基于ThreadLocal去实现的，异步过程中，子线程并没有办法获取到父线程ThreadLocal存储的数据，所以这里可以自定义线程池执行器，修改其中的run()方法：public class MyThreadPoolTaskExecutor extends ThreadPoolTaskExecutor { @Override public void execute(Runnable runnable) { Map<String, String> context = MDC.getCopyOfContextMap(); super.execute(() -> run(runnable, context)); } @Override private void run(Runnable runnable, Map<String, String> context) { if (context != null) { MDC.setContextMap(context); } try { runnable.run(); } finally { MDC.remove(); } } }使用 MQ 发送消息给第三方系统在 MQ 发送的消息体中自定义属性requestId，接收方消费消息后，自己解析requestId使用即可。
AI 摘要 文章剖析ArrayList底层Object数组实现，详解无参构造初始为空、首次添加扩为10、后续1.5倍扩容机制，对比Vector、LinkedList，并说明System.arraycopy与Arrays.copyOf区别及ensureCapacity预扩容性能调优。 此摘要根据文章内容自动生成，仅用于文章内容的解释与总结title: ArrayList 源码分析category: Javatag:Java集合ArrayList 简介ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ }List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。ArrayList 和 Vector 的区别?（了解即可）ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全 。Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。ArrayList 可以添加 null 值吗？ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。示例代码：ArrayList<String> listOfStrings = new ArrayList<>(); listOfStrings.add(null); listOfStrings.add("java"); System.out.println(listOfStrings);输出：[null, java]Arraylist 与 LinkedList 区别?是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）插入和删除是否受元素位置的影响：ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。ArrayList 核心源码解读这里以 JDK1.8 为例，分析一下 ArrayList 的底层源码。public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * 默认初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 空数组（用于空实例）。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; //用于默认大小空实例的共享空数组实例。 //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 保存ArrayList数据的数组 */ transient Object[] elementData; // non-private to simplify nested class access /** * ArrayList 所包含的元素个数 */ private int size; /** * 带初始容量参数的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小） */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //如果传入的参数大于0，创建initialCapacity大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //如果传入的参数等于0，创建空数组 this.elementData = EMPTY_ELEMENTDATA; } else { //其他情况，抛出异常 throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } /** * 默认无参构造函数 * DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。 */ public ArrayList(Collection<? extends E> c) { //将指定集合转换为数组 elementData = c.toArray(); //如果elementData数组的长度不为0 if ((size = elementData.length) != 0) { // 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断） if (elementData.getClass() != Object[].class) //将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 其他情况，用空数组代替 this.elementData = EMPTY_ELEMENTDATA; } } /** * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。 */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //下面是ArrayList的扩容机制 //ArrayList的扩容机制提高了性能，如果每次只扩充一个， //那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。 /** * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量 * * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { //如果是true，minExpand的值为0，如果是false,minExpand的值为10 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; //如果最小容量大于已有的最大容量 if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } // 根据给定的最小容量和当前数组元素来计算所需容量。 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果当前数组元素为空数组（初始情况），返回默认容量和最小容量中的较大值作为所需容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } // 否则直接返回最小容量 return minCapacity; } // 确保内部容量达到指定的最小容量。 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //判断是否需要扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) //调用grow方法进行扩容，调用此方法代表已经开始扩容了 grow(minCapacity); } /** * 要分配的最大数组大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList扩容的核心方法。 */ private void grow(int minCapacity) { // oldCapacity为旧容量，newCapacity为新容量 int oldCapacity = elementData.length; //将oldCapacity 右移一位，其效果相当于oldCapacity /2， //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量， if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //再检查新容量是否超出了ArrayList所定义的最大容量， //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE， //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。 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); } //比较minCapacity和 MAX_ARRAY_SIZE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * 返回此列表中的元素数。 */ public int size() { return size; } /** * 如果此列表不包含元素，则返回 true 。 */ public boolean isEmpty() { //注意=和==的区别 return size == 0; } /** * 如果此列表包含指定的元素，则返回true 。 */ public boolean contains(Object o) { //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1 return indexOf(o) >= 0; } /** * 返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1 */ public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i] == null) return i; } else { for (int i = 0; i < size; i++) //equals()方法比较 if (o.equals(elementData[i])) return i; } return -1; } /** * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。. */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size - 1; i >= 0; i--) if (elementData[i] == null) return i; } else { for (int i = size - 1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } /** * 返回此ArrayList实例的浅拷贝。 （元素本身不被复制。） */ public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); //Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度 v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // 这不应该发生，因为我们是可以克隆的 throw new InternalError(e); } } /** * 以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。 * 返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。 * 因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; * 返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组，则返回其中。 * 否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。 * 如果列表适用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在集合结束后的数组中的元素设置为null 。 * （这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。） */ @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) // 新建一个运行时类型的数组，但是ArrayList数组的内容 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //调用System提供的arraycopy()方法实现数组之间的复制 System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } // Positional Access Operations @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * 返回此列表中指定位置的元素。 */ public E get(int index) { rangeCheck(index); return elementData(index); } /** * 用指定的元素替换此列表中指定位置的元素。 */ public E set(int index, E element) { //对index进行界限检查 rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; //返回原来在这个位置的元素 return oldValue; } /** * 将指定的元素追加到此列表的末尾。 */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! //这里看到ArrayList添加元素的实质就相当于为数组赋值 elementData[size++] = e; return true; } /** * 在此列表中的指定位置插入指定的元素。 * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大； * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } /** * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。 */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work //从列表中删除的元素 return oldValue; } /** * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。 * 返回true，如果此列表包含指定的元素 */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } /** * 从列表中删除所有元素。 */ public void clear() { modCount++; // 把数组中所有的元素的值设为null for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } /** * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。 */ public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } /** * 将指定集合中的所有元素插入到此列表中，从指定的位置开始。 */ public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; } /** * 从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素。 * 将任何后续元素移动到左侧（减少其索引）。 */ protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex - fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } /** * 检查给定的索引是否在范围内。 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * add和addAll使用的rangeCheck的一个版本 */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 返回IndexOutOfBoundsException细节信息 */ private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size; } /** * 从此列表中删除指定集合中包含的所有元素。 */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); //如果此列表被修改则返回true return batchRemove(c, false); } /** * 仅保留此列表中包含在指定集合中的元素。 * 换句话说，从此列表中删除其中不包含在指定集合中的所有元素。 */ public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } /** * 从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。 * 指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。 * 返回的列表迭代器是fail-fast 。 */ public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index); return new ListItr(index); } /** * 返回列表中的列表迭代器（按适当的顺序）。 * 返回的列表迭代器是fail-fast 。 */ public ListIterator<E> listIterator() { return new ListItr(0); } /** * 以正确的顺序返回该列表中的元素的迭代器。 * 返回的迭代器是fail-fast 。 */ public Iterator<E> iterator() { return new Itr(); }ArrayList 扩容机制分析先从 ArrayList 的构造函数说起ArrayList 有三种方式来初始化，构造方法源码如下（JDK8）：/** * 默认初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 默认构造函数，使用初始容量10构造一个空列表(无参数构造) */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 带初始容量参数的构造函数。（用户自己指定容量） */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//初始容量大于0 //创建initialCapacity大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//初始容量等于0 //创建空数组 this.elementData = EMPTY_ELEMENTDATA; } else {//初始容量小于0，抛出异常 throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } /** *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回 *如果指定的集合为null，throws NullPointerException。 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }细心的同学一定会发现：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。 下面在我们分析 ArrayList 扩容时会讲到这一点内容！补充：JDK6 new 无参构造的 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组 elementData 。一步一步分析 ArrayList 扩容机制这里以无参构造函数创建的 ArrayList 为例分析。add 方法/** * 将指定的元素追加到此列表的末尾。 */ public boolean add(E e) { // 加元素之前，先调用ensureCapacityInternal方法 ensureCapacityInternal(size + 1); // Increments modCount!! // 这里看到ArrayList添加元素的实质就相当于为数组赋值 elementData[size++] = e; return true; }注意：JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法ensureCapacityInternal 方法的源码如下：// 根据给定的最小容量和当前数组元素来计算所需容量。 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果当前数组元素为空数组（初始情况），返回默认容量和最小容量中的较大值作为所需容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } // 否则直接返回最小容量 return minCapacity; } // 确保内部容量达到指定的最小容量。 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }ensureCapacityInternal 方法非常简单，内部直接调用了 ensureExplicitCapacity 方法：//判断是否需要扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; //判断当前数组容量是否足以存储minCapacity个元素 if (minCapacity - elementData.length > 0) //调用grow方法进行扩容 grow(minCapacity); }我们来仔细分析一下：当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。当 add 第 2 个元素时，minCapacity 为 2，此时 elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。grow 方法/** * 要分配的最大数组大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList扩容的核心方法。 */ private void grow(int minCapacity) { // oldCapacity为旧容量，newCapacity为新容量 int oldCapacity = elementData.length; // 将oldCapacity 右移一位，其效果相当于oldCapacity /2， // 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); // 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量， if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE， // 如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。 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); }int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.">>"（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源我们再来通过例子探究一下grow() 方法：当 add 第 1 个元素时，oldCapacity 为 0，经比较后第一个 if 判断成立，newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true,size 增为 1。当 add 第 11 个元素进入 grow 方法时，newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。以此类推······这里补充一点比较重要，但是容易被忽视掉的知识点：Java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.Java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.Java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!hugeCapacity() 方法从上面 grow() 方法源码我们知道：如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 对minCapacity和MAX_ARRAY_SIZE进行比较 // 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小 // 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小 // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }System.arraycopy() 和 Arrays.copyOf()方法阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！System.arraycopy() 方法源码： // 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义 /** * 复制数组 * @param src 源数组 * @param srcPos 源数组中的起始位置 * @param dest 目标数组 * @param destPos 目标数组中的起始位置 * @param length 要复制的数组元素的数量 */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);场景： /** * 在此列表中的指定位置插入指定的元素。 *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大； *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //arraycopy()方法实现数组自己复制自己 //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量； System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }我们写一个简单的方法测试以下：public class ArraycopyTest { public static void main(String[] args) { // TODO Auto-generated method stub int[] a = new int[10]; a[0] = 0; a[1] = 1; a[2] = 2; a[3] = 3; System.arraycopy(a, 2, a, 3, 3); a[2]=99; for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } }结果：0 1 99 2 3 0 0 0 0 0Arrays.copyOf()方法源码： public static int[] copyOf(int[] original, int newLength) { // 申请一个新的数组 int[] copy = new int[newLength]; // 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }场景： /** 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。 */ public Object[] toArray() { //elementData：要复制的数组；size：要复制的长度 return Arrays.copyOf(elementData, size); }个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下：public class ArrayscopyOfTest { public static void main(String[] args) { int[] a = new int[3]; a[0] = 0; a[1] = 1; a[2] = 2; int[] b = Arrays.copyOf(a, 10); System.out.println("b.length"+b.length); } }结果：10两者联系和区别联系：看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法区别：arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。ensureCapacity方法ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？ /** 如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。 * * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } 理论上来说，最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数我们通过下面的代码实际测试以下这个方法的效果：public class EnsureCapacityTest { public static void main(String[] args) { ArrayList<Object> list = new ArrayList<Object>(); final int N = 10000000; long startTime = System.currentTimeMillis(); for (int i = 0; i < N; i++) { list.add(i); } long endTime = System.currentTimeMillis(); System.out.println("使用ensureCapacity方法前："+(endTime - startTime)); } }运行结果：使用ensureCapacity方法前：2158public class EnsureCapacityTest { public static void main(String[] args) { ArrayList<Object> list = new ArrayList<Object>(); final int N = 10000000; long startTime1 = System.currentTimeMillis(); list.ensureCapacity(N); for (int i = 0; i < N; i++) { list.add(i); } long endTime1 = System.currentTimeMillis(); System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1)); } }运行结果：使用ensureCapacity方法后：1773通过运行结果，我们可以看出向 ArrayList 添加大量元素之前使用ensureCapacity 方法可以提升性能。不过，这个性能差距几乎可以忽略不计。而且，实际项目根本也不可能往 ArrayList 里面添加这么多元素。