目录
集合框架的作用：用于存储数据的容器
概要：
集合框架的优点：
集合框架的关系图：
list集合
list的常用方法：
ArrayList、linkedlist与vector的区别
list集合的增删改查的操作：
增加：
修改：
查询：
删除：
list集合的扩容原理：
集合框架的作用：用于存储数据的容器
集合框架就是为了表示和操作集合而规定的一种统一的标准的体系结构。
概要：
任何的集合框架都会包含三大快内容：
1.对外的接口
2.接口的实现
3.集合运算的算法
集合框架的优点：
- 容器能够自增长
- 提供了高性能的数据结构和算法，使编码更轻松，提高了程序速度和质量、
- 允许不同API之间的互操作，API之间可以来回传递集合
- 可以方便地扩展或改写集合，提高代码复用性和可操作性
- 通过使用JDK自带的集合类，可以降低代码维护和学习新API版本。
集合框架的关系图：
这次我们先来讲解一下list集合：
list集合
list的常用方法：
ArrayList、linkedlist与vector的区别
| ArrayList | LinkedList | Vector | |
| 底层实现 | 数组 | 双向链表 | 数组 |
| 同步性及效率 | 不同步 ，非线程安全，效率高，支持随机访问 | 不同步，非线程安全，效率高 | 同步，线程安全，效率低 |
| 特点 | 查询快，增删慢 | 查询慢，增删快 | 查询快，增删慢 |
| 默认容量 | 10 | / | 10 |
| 扩容机制 | int newCapacity = oldCapacity + (oldCapacity >> 1)；//1.5 倍 | / | 2倍 |
总结：
- ArrayList 和 Vector 基于数组实现，对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
- LinkedList 不会出现扩容的问题，所以比较适合随机位置增、删。但是其基于链表实现，所以在定位时需要线性扫描，效率比较低。
- 当操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能；
- 当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。
list集合的增删改查的操作：
增加：
private List list = new ArrayList();
// 在每个测试方法之前都会执行
@Before
public void setup() {
list.add(1);
list.add(2);
list.add(3);
list.add(3);
list.add(4);
}
private Listlist = new ArrayList (); // 在每个测试方法之前都会执行 @Before public void setup() { list.add(1); list.add(2); list.add(3); list.add(3); list.add(4); }
注意：@Test、@Before、@After注释是需要导入单元测试包吗，导入顺序如下：
1.选中项目然后alt+enter
2.选中classpath，然后点击 Add Library
3.选中JUnit,然后点击 next
4.这里建议选择版本4，因为版本5可能会存在注释失效的情况 。最后点击finish即可。
- @Test:目的是为了测试单个 方法，我们之前的代码都是在main方法中进行测试的，我们通过@Test注释就能够使相应的方法不用main方法就可以直接运行了。对于测试而言也是相当方便的。就像我们上面的增加值的方法就是用到了@before注释，就是为了下面每次测试的时候都会自动往集合里面增加值。方便了测试。
- @before：目的是将@before作为首先执行的代码，用于资源的申请
- @after：目的是为了让 每次释放资源后都会执行注释下的代码。即使出现了异常任然会执行对应的代码，用于资源的释放
修改：
将下标为3的值修为5
@Test
public void update() {
list.set(3, 5);
System.out.println(list);
}
然后双击方法名，然后右键：
结果如下：
查询：
查询主要有三种方式：
三种的运行结果都是一样的：
1.for循环遍历
@Test
public void query01() {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
2.foreach遍历
@Test
public void query02() {
for (Integer i : list) {
System.out.println(i);
}
}
3.使用迭代器遍历
@Test
public void query03() {
Iterator i = list.iterator();
while(i.hasNext()) {
System.out.println(i.next());
}
删除：
为了方便测试我们准备了一组数据：
12334
要求：将数组中的3全部删除
1.for循环顺遍历根据下标删除：
@Test
public void remove01() {
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 3)
list.remove(i);
}
System.out.println(list);
}
我们会发现任然还有一个3，为什么会出现这种问题呢？
原因其实很简单，就是因为当数组的第一个3被删除的时候，它的下标为2，第一个3被删除的时候后面的数的下标就会向前面进一位，也就是说第二个3下标会变成2，但是刚刚已经遍历过下标为2的了，只会继续往后面遍历了，所以这就是list集合中的移位。为了防止这个bug，下面有对这个方法的改进。
2.for循环顺遍历(根据下标删除)2：
@Test
public void remove02() {
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 3)
list.remove(i--);
}
System.out.println(list);
}
控制台结果：
我们会发现我们的程序没有问题，3也全部都删除了，这又是什么原理呢？
我们发现改进后的代码只有一处变动：
list.remove(i--),这其中的算法其实很简单的：当第一个3被删除的时候此时遍历的下标是2，按道理来说，循环接下来会遍历下标为3的值，这种情况就是上面那种方法，但是这种方式是会存在bug的，所以这个地方在i的后面加上了一个--，就巧妙的避免了这个问题。当删除的操作执行成功之后，后面的值都会进行移位的操作(下标都-1)，那么第二个3下标就会为2，所以当i进行了--的操作，循环就会回到下标为2的地方，这个时候第二个3就不会“逃之夭夭”了，还是会进行删除的操作。
3.for循环逆遍历(根据下标删除)：
@Test
public void remove03() {
for (int i = list.size() - 1; i >= 0; i--) {
if (list.get(i) == 3) {
list.remove(i);
}
}
System.out.println(list);
}
运行结果：
这种方法与第一种方法其实就是遍历的顺序变了。
那么这种方式为什么变了一下遍历顺序就不会出现bug呢？
如上图：当我们第一次进行删除的操作应该是下标为3的那个3，当这个3被删除的时候，后面的4移位上来，但是你会发现，这个时候4移位上来并不会影响我们后面的操作，是吧，因为程序是从后面开始执行的，也就是从4开始的，那既然4已经执行过了，它移位上来又什么意义呢？我们仔细想一下这就是与方法一的高明之处。
4.使用foreach遍历删除：
@Test
public void remove04() {
for (Integer i : list) {
if (i == 3)
list.remove(i);
}
System.out.println(list);
}
当我们测试这个代码的时候，会发现，完了芭比q了报错了
这个时候我硬是不信邪了，又重新创建了一个集合，为[1，2，3，4]，删除倒数第二个数：
如果不是倒数第二个数就会报一样的错！
@Test
public void remove04() {
ArrayList list2 = new ArrayList();
list2.add(1);
list2.add(2);
list2.add(3);
list2.add(4);
for (Integer i : list2) {
if (i == 3)
list2.remove(i);
}
System.out.println(list2);
}
这个时候，我们发现它又能够正常运行了，这是为什么，电脑出错了？
其实不是，我们在讨论之前先来看看foreach的遍历原理：
foreach的本质上就是创建了一个迭代器，利用iterator实现遍历，即：
Iteratorit = list.iterator(); while (it.hasNext()) { if (it.next() == 3) { it.remove(); } }
瞧一瞧，
但是我现在要知道我为什么报错，跟这个有时候关系呢？不急，我们先来看看源码：
private class Itr implements Iterator{ int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} //1. public boolean hasNext() { return cursor != size; } //2. 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]; } //3. public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } //4. final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
好家伙，好像还不是特别清楚
那我们先拆开来看问题！
首先想：为什么遍历list的时候，删除元素会报错？
仔细看下报错的异常：
我们发现抛出的异常为：checkForComodification()
源码如下：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
我发现里面判断有一个值是modCount，它就是修改次数
就是说当list调用add()方法时，add方法会对modCount实现++的操作，如上例，共调用了add()4次
则modCount=4
而在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,
而此时：modCount=expectedModCount。
然而，当进行一次删除的操作后，即对list进行了一次修改，则modCount+1，此时的modCount=5,
而expectedmodCount依然为4，因为modCount ！=expectedmodCount，所以就会抛出异常。
那既然我们知道了为什么报错，那咱再看看为啥倒数第二个数不抛出异常了！
迭代器实际上调用了两个方法，即：hashNext()和next()
而且我们可以看到抛异常的处理是在next()的方法中
哦可啊
再来看看源码：
//1.
public boolean hasNext() {
return cursor != size;
}
//2.
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];
}
所以，不抛出异常的2最佳方法，就是不进hashNext()方法，前提是：删除的元素必须为倒数第二个元素。
cursor：保存当前iterator的位置信息，从0开始
其实很简单的，让cursor==size即可，当cursor==size时，返回false。也就是说：当next()方法接收到hashNext()发来的信息，得知，没有下一个元素了，就不会再进行处理了。
可能说到这，还不是很清晰，那就再举个例子：
删除倒数第二个元素，cursor=3，而size-1，即size=3.，当再调用hasNext()判断的时候，cursor==size，return false，自然就不会执行next的方法了，而是执行remove操作删除元素后，直接退出循环，也就不会走到最后抛异常的环节了。
所以，经验所得学会看源码是个好东西！！！
5.使用迭代器遍历删除：
@Test
public void remove05() {
Iterator it = list.iterator();
while (it.hasNext()) {
if (it.next() == 3) {
it.remove();
}
}
System.out.println(list);
}
运行结果：
这个就要说到迭代器的删除原理了，这里我们看到源码：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
我们会发现当我们执行了删除的操作之后会重新赋值给cursor和expectModCount，那么关于这两值，咱在已经详细的提到，讲到这，大家应该知道原理了吧，使用迭代器删除与foreach遍历删除的两则的区别就是在于这两个值变不变 。
6.迭代器的稍微变动：
@Test
public void remove06() {
Iterator it = list.iterator();
while (it.hasNext()) {
Integer value = it.next();
if (value == 3) {
list.remove(value);
}
}
}
呕吼，又报错了：
这个错误大家熟悉吧，没错就是我们在使用foreach遍历删除的时候抛出的异常。
那么问题又来了，这个为什么又报错呢？不是已经使用了迭代器的删除的方法吗
大家仔细看代码会发现
我们的删除方法并不是迭代器的删除方法
查看源码：
boolean remove(Object o);
调用的list删除方法，里面的参数是一个object类型，说明这个删除的方法是根据对象删除的
我们再使用另外一个集合测试：
@Test
public void remove06() {
ArrayList list2 = new ArrayList();
list2.add(1);
list2.add(2);
list2.add(3);
list2.add(4);
Iterator it = list2.iterator();
while (it.hasNext()) {
Integer value = it.next();
if (value == 3) {
list2.remove(value);
}
}
System.out.println(list2);
}
输出的结果为：
这个问题又出现了，为什么呢？其实跟上面是一样的原理，因为调用的不是迭代器的删除方法，所以每次遍历后并没有对cursor和expectModCount进行重新设值，才会出现这个问题的。
7.根据下标删除：
@Test
public void remove07() {
list.remove(2);
System.out.println(list);
}
查询结果：
8.根据对象删除：
@Test
public void remove08() {
list.remove(Integer.valueOf(2));
System.out.println(list);
}
结果：
list集合的扩容原理：
@Test
public void listKR() throws Exception {
List list = new ArrayList();
for (int i = 0; i <= 100; i++) {
list.add(i);
System.out.println("i :" + i);
System.out.println("length :" + getListElsSize(list));
}
}
运行结果：
我们可以看到，当下标为9的时候容量为10，这个时候刚好满了 ，此时还不会进行扩容，当下一个元素进来的时候 ，才进行扩容、
扩容原理：新容量=旧容量*扩容因子
从图中我们不难发现list集合的默认的扩容因子是0.5，当然这个也是能够设置的。
好啦 ，这期的分享就到了，大家有没有发现当你自己去研究一些底层原理算法的时候是不是特别有意思。
