写在后面的话
有的同学问我，开始讲的很根底，节奏比较慢，这个是因为一个为了让大家缓缓进入状态，前面的节奏会越来越快的，大家不要焦急，另一个是因为简略的货色反复，温故而知新，更心愿给你们带来的是思维和观点的成长，这个须要铺垫。这个有点像练武功，要想练就浅近的文治, 须要循序渐进，不然很容易走火入魔的，所以要把根基打扎实，不能焦急。这里剧透下，前面会给大家带来一个一个绝世功法：《HDFS 成长记》、《ZK 成长记》、《Spring Cloud Alibaba 成长记》、《Spring Cloud 成长记》、《Kafka 成长记》、《Redis 成长记》、《MySQL 成长记》等等。也会有一些根底心法，比方《Netty 成长记》、《JVM 成长记》《OS 成长记》、《网络成长记》等等。
好了，不多说了，让咱们开始吧！
通过之前的三节，置信你曾经对 ArrayList 中大多办法的底层逻辑都有了很深刻的理解，最为 ArrayList 的最初一节，这节跟大家看下 ArrayList 的遍历和一些高级办法的底层原理，最初让你能够对 ArrayList 底层了如执掌，面对各种 ArrayList 的面试题能对答如流，甚至能够手撸一个 ArrayList 的代码进去。
ArrayList 的遍历到底有什么猫腻呢？
当你应用 ArrayList 的时候，最罕用的除了 add 办法，是不是就是 for 循环的遍历。个别你遍历 ArrayList，无非就是一下几种办法：
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ArrayListDemo {public static void main(String[] args) {List<String> hostList = new ArrayList<>(3);
hostList.add("host1");
hostList.add("host2");
hostList.add("host3");
// 办法 1
for (int i = 0; i < hostList.size(); i++) {System.out.println(hostList.get(i));
}
// 办法 2
for (String host : hostList) {System.out.println(host);
}
// 办法 3
for (Iterator<String> iterator = hostList.iterator(); iterator.hasNext();) {String host = iterator.next();
System.out.println(host);
}
// 办法 4
hostList.forEach(host->System.out.println(host));
// 办法 5 这种遍历波及 stream 底层源码，这里咱们不做过多摸索
hostList.stream().forEach(host->System.out.println(host));
}
}办法 1，这种形式应用了 for 循环，通过 get 办法拜访元素，你应该晓得底层就是数组基本操作 elementData[index]。
办法 2 底层其实和办法 3 是截然不同的，只不过办法 2 只是一种便捷的语法糖而已，不便让你应用。
办法 4 底层和办法 1 是一样的，都是用来 for 循环 + 数组基本操作 elementData[index]。
办法 5 是通过 Java8 stream 的 API 进行 forEach，这里咱们不做过多摸索，个别也不倡议这么应用，不如应用办法 4 有效率。
所以值得你摸索的两个办法是办法 3 和办法 4 的源码，先看下 forEach 的源码：
@Override
public void forEach(Consumer<? super E> action) {Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {action.accept(elementData[i]);
}
if (modCount != expectedModCount) {throw new ConcurrentModificationException();
}
}间接看到外围脉络就是 for 循环，通过数组基本操作 elementData[index] 拜访数组获取到对应元素，传递给了 Java8 的 Consumer 函数表达式，执行对应的逻辑。这个和你本人写 for 循环，执行本人的逻辑是不是一样的，所以说这种办法和之前的办法 1 实质没有什么区别，也就是换了一个语法糖而已。
办法 1 和办法 4 的源码原理，如下图：
咱们再看看办法 3 Iterator 的源码：
for (Iterator<String> iterator = hostList.iterator(); iterator.hasNext();) {String host = iterator.next();
System.out.println(host);
}依据 for 循环执行逻辑，第一句执行的办法应该是 hostList.iterator()，你能够在 ArrayList 的源码中看到这个办法：
public Iterator<E> iterator() {return new Itr();
}能够看到间接返回了一个 new Itr()对象，这个类不晓得你还有没有印象？记得第一节看 ArrayList 的源码脉络的时候，有几个外部类，其中是不是就有一个 lrt 类。如下图所示：
没错，这个就是咱们常称的迭代器，他是汇合中常见的遍历工具。你能够接着往下看：
private class Itr implements Iterator<E> {Itr() {}
// 省略无关代码
}你会发现构造函数什么都没有做。那么 for 循环接着执行条件表达式 iterator.hasNext(); 即如下代码：
private int size;
private class Itr implements Iterator<E> {
int cursor;
public boolean hasNext() {return cursor != size;}
// 省略无关代码
}这里意思是如果 cursor 的值和数组大小不相等，就返回 false。cursor 是 int 类型，所以默认值是 0。下面的 Demo 中，size=3，第一次遍历必定 cursor=0 != size= 3 所以间接返回 true。
源码原理如下所示：
之后 for 循环执行循环体，会执行 Stringhost = iterator.next(); 这句话的源码如下：
private int size;
transient Object[] elementData;
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
public E next() {checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();}
// 省略无关代码
}还是先看下脉络，首先 checkForComodification 应该是在做并发拜访查看，应用 i 变量保留了 cusor 值，之后 if 在做了校验，再之后获取到了 ArrayList 的 elementData 数组，再次做了并发拜访查看，之后批改了下 cursor 值，将 i 的值赋值给了 lastRet 变量，并且通过下标拜访了下数组，最初就返回了。看上去是不是有点找不到重点？让咱们 抓大放小 下，其实去掉并发校验和一般校验，代码逻辑就很分明了，就会变成如下所示：
private int size;
transient Object[] elementData;
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
public E next() {
int i = cursor;
Object[] elementData = ArrayList.this.elementData;
cursor = i + 1;
return (E) elementData[lastRet = i];
}
// 省略无关代码
}只有四行代码是不是就个很清晰了？你还能够在画个图：
执行过程就如右边的图所示，后果就是如右图所示。通过抓大放小和画图，是不是对源码的思路就清晰很多了？
执行实现一次循环后，Itr 变量如下图所示：
ltr 的 next()办法实质其实就是通过一个外部 cursor 变量，每次向后遍历数组时，保留遍历数组的地位，通过数组根本的下标拜访元素返回而已，这下你就把握了 ArrayList 迭代器的实质或者说是底层原理了吧。
ArrayList 居然有一个优化后的迭代器！
看过了各种遍历形式的源码，大家不晓得有什么感觉？是不是感觉也没有神秘的，其实原理很简略，让你本人写一个相似的性能是不是就能够参考这个思路呢？然而不晓得你有没有发现 ArrayList 还有一个迭代器叫做 ListItr 的外部类，它劣势做什么的呢？
间接能够看下源码：
private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {super();
cursor = index;
}
public boolean hasPrevious() {return cursor != 0;}
public int nextIndex() {return cursor;}
public int previousIndex() {return cursor - 1;}
@SuppressWarnings("unchecked")
public E previous() {checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
// 省略无关代码
}从能够发现它继承了 Itr 这个类, 之后你能够依据办法名字 连蒙带猜 下，能够猜到它只是实现了向前遍历的性能而已，因为失常状况的迭代器是只能向后迭代，不能向前拜访的。然而你能够通过这个 ListItr 迭代器实现向前拜访。比方：
public static void main(String[] args) {List<String> hostList = new ArrayList<>(3);
hostList.add("host1");
hostList.add("host2");
hostList.add("host3");
// 办法 3
for (ListIterator<String> iterator = hostList.listIterator(); iterator.hasNext();) {System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.previous());
break;
}
}后果会输入如下：
host1
host2
host2
其实这是一个优化后的迭代器，能够向前向后挪动 cursor，previous()源码逻辑和 next()向后挪动没什么区别。你到这里就能够总结下：
1. ArrayList 有两个迭代器 Itr 和 ListItr，一个能够向后迭代，一个能够既向前又向后迭代拜访 ArrayList。(其实 ArrayList 父类 AbstractList 有 2 个通用的迭代器，和这个原理是一样的，大家有趣味能够去看看，如果子类没有自定义本人的迭代器，会应用父类的迭代器。)
2. 这两个迭代器不是并发平安的，如果有别的线程批改 modCount，通过 fail-fast 机制，迭代拜访会抛出 ConcurrentModificationException，并发批改的异样，中断迭代。
3. 遍历 List 的思维万变不离其宗，次要就是通过 for 循环 + 下标的形式或者指针挪动的两种形式实现思路而已。
ArrayList 的高级办法摸索
<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>ArrayList 的高级办法摸索 </span></h3></div>
最初你还须要来看下 ArrayList 的一些高级办法的源码，这里倡议你看下它外部提供的 toArray 办法、subList 办法的源码。至于其余的 addAll()、indexof()之类的办法大家能够自行去看下。这里次要看下 toArray 和 subList 相干的外部类和办法，它们次要有如下脉络：
能够先看下 toArray 办法的源码：
public Object[] toArray() {return Arrays.copyOf(elementData, size);
}}
public <T> T[] toArray(T[] a) {if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}第一个 toArray 办法的源码，底层间接应用了 Arrays.copyOf。你应该晓得它底层其实就是应用 System.arraycopy 办法，拷贝的元素个数是 size 个，也就是全副元素到一个 copy 数组中，之后就间接返回了。
第二个 T[]toArray(T[] a)，须要你传递一个指标数组，它外部有两个 if 判断，依据指标数组大小，拷贝元素。
- 如果指标数组比 ArrayList 的数据少，通过 Arrays.copyOf 扩容成和 ArrayList 一样大小的数组返回。
- 如果指标数组比以后 ArrayList 的大，就间接用 System.arraycopy 拷贝 ArrayList 中所有元素，指标数组多余元素置为 null。
toArray 办法实质就是应用 System.arraycopy 从 ArrayList 的 Obeject 数组拷贝元素到新数组。
原理图如下：
之后咱们再看下 subList 办法，能够先写个 demo 体验下：
public static void main(String[] args) {List<String> hostList = new ArrayList<>(3);
hostList.add("host1");
hostList.add("host2");
hostList.add("host3");
List<String> subList = hostList.subList(1,2);
System.out.println(subList);
System.out.println(hostList);
subList.set(0, "host4");
System.out.println(subList);
System.out.println(hostList);
}
为什么呢？能够看源码来找下起因。这就是浏览源码的益处之一。因为很多时候当你线上遇到技术问题的时候，你对源码很相熟，就能很快定位问题起因，解决问题。当你技术调研的时候，选型后，最好要摸下你选的技术的源码，当应用除了问题你也能 hold 住，是不是？
subList 的源码如下：
public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}和 Itr 相似，创立了一个外部类 SubList 的对象。持续点进去看下：
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {checkForComodification();
return this.size;
}
public void add(int index, E e) {rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
// 省略其余办法
}能够看进去在构造函数的传入了 this, new SubList(this, 0, fromIndex, toIndex); 而这个 this 就是 ArrayList 创立的对象自身，将 this 赋值给了 Sublist 的一个变量：private final AbstractList<E> parent。再看看 subList 的其余办法，都是基于原数组的数据进行操作，只不过是本人依据 fromIndex,toIndex 限定了拜访范畴而已。
那最终意思不就是说 SubList 和 ArrayList 共用了通过 Object[]数组的数据么，所以当批改的时候都会变动。这是你应用 subList 肯定要要留神的。
源码原理图如下所示：
到这里，ArrayList 的源码你应该把握了大部分了，然而记住还是那句话，重要的不是常识和技能自身，你更应该需学会的是看源码的思维和技巧，解决问题的思路和办法。
ArrayList 的小结
对了这里，附加一个小结，总结也是十分重要的思维。前面我会逐步讲到。学完 ArrayList 你如果曾经把握了如下内容，就十分好了。
常识和技能
- ArrayList 底层数据结构是 Objec[]数组，长处是便于随机拜访，常用语向尾部增加元素后，遍历拜访。毛病是频繁扩容或者两头减少数据，删除数据会造成拷贝，影响性能。
- ArrayList 默认初始化大小为 0，第一次增加元素时，大小初始为 10。
- ArrayList 第一次增加就会产生扩容，为 10，之后每次扩容大小为原来的 1.5 倍。外部通过右移 1 位进行扩容大小的计算的。
- ArrayList add 元素到尾部产生的扩容时或 add 元素到某个地位时，又或者删除元素时，会产生数组拷贝，底层通过 system.copyOf 实现拷贝性能。
- ArrayList 不是线程平安的，多线程操作，在遍历和 removeIf 等时候，会触发 fail-fast 机制，通过 modCount 来实现的。
- 把握了根本的根本办法和高级办法 toArray、subList、迭代器 Itr、ListItr 等底层源码的原理
观点和思维
- 学会了先脉络后细节、抓大放小、连蒙带猜等浏览源码的思维
- 学会了画图、举例子剖析问题的办法
- 有了成长比胜利更重要、楷模比说服力更重要、扭转本人比扭转他人更重要、借力比致力更重要的观点
金句甜点
除了明天常识，技能的成长，给大家带来一个金句甜点，完结我明天的分享：借力比致力更重要。
一个人的致力诚然很重要，然而很多时候借力更重要。就像有句名言所说：站在伟人的肩膀上。这个不是真的站在某个人的肩膀上，而是指的前人的智慧和教训上很重要。就比方有一次我加入公司的降职演讲，本人做好了 PPT，还练习了几次，感觉必定没有问题了，就间接加入了降职演讲评审。后果，很可怜的是，PPT 右下角的公司 log 是去年的，公司曾经更换了品牌 log，最初一页的致谢的 PPT，公司名称也写错了。导致有一位评审收入，起初我才晓得他是人力部门的 HR 总监。很遗憾的因为错失了她这一票，刚好导致我落选了。其实演讲前，我的 Leader 跟我说过，写好了 PPT 要给他看一下，我当初感觉齐全没必要。其实就是犯了很大一个谬误，因为我的 Leader 的教训比我丰盛，他降职过很屡次，汇报过很屡次，在这不便很有见地，我没有借他的力，导致了这次失败。所以我吸取教训，下次降职时，找了 Leader，他帮我一页一页的过 PPT，最终顺利的通过了降职。
这个故事其实就通知咱们，借力比致力更重要。你肯定要向比你有教训的人求教，他就是你的老师，这就是一种借力。当然选一个平台也是借力，就像大家通过成长记来成长本人，站在我的教训上少走弯路是不是一样在借力。所以欢送大家持续关注成长记。
最初，你能够浏览完源码后，在茶余饭后的时候问问共事或同学，你也能够分享下，讲给他听听。
欢送大家在评论区留言和我交换。
（申明：JDK 源码成长记基于 JDK 1.8 版本，局部章节会提到旧版本特点）
本文由博客一文多发平台 OpenWrite 公布！