Java 集合之 ArrayList 详解，大厂越来越注重基础了，建议收藏
}
oldCapacity + (oldCapacity >> 1)
默认将数组的大小扩容到原来的 1.5 倍
newCapacity - minCapacity < 0
如果扩容后的容量不足，则将所需容量 minCapacity 赋值给 newCapacity，扩容后数组大小就是申请的容量
newCapacity - MAX_ARRAY_SIZE > 0
如果扩容后的数组容量太大，超过了 Integer.MAX_VALUE - 8 的大小，则数组的大小为 hugeCapacity(),(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
其余 add()方法大同小异
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
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;
}
4.2 remove 操作
rangeCheck(index);
检查 index 是否合法，当 index >= size 时，抛出 IndexOutOfBoundsException 异常；
modCount++;
记录集合的操作次数；
E oldValue = elementData(index);
取出移除元素，用于放回给方法调用者；
if (numMoved > 0)
判断当前删除的集合元素是否时数组的最后一个元素，如果不是最后一个元素，则调用 System.arraycopy()方法做一次数组拷贝；如果移除的元素是最后一个元素或者在数组复制结束之后，将数组的最后一个元素置为 null，等待 GC 垃圾回收；–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;
}
4.3 get 操作
rangeCheck(index);
检查 index 是否合法，当 index >= size 时，抛出 IndexOutOfBoundsException 异常；
elementData(index);
由于 ArrayList 的底层是由数组实现的，所有获取元素直接调用数组的随机访问即可；
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
5、Iterator
5.1 前言
Java 开发初级工程师在使用 for 遍历集合的时候，由于使用不正确的 API 方法对集合进行 remove()操作，经常会抛出 java.util.ConcurrentModificationException，因此我们来从源码的层面仔细的探究一下为什么会产生 ConcurrentModificationException 以及如何解决这个异常！foreach 循环又称增强 for 循环，是 jdk1.5 为了简化数组或者和容器遍历而产生，foreach 循环的适用范围：对于任何实现了 Iterable 接口的容器都可以使用 foreach 循环。foreach 语法的冒号后面可以有两种类型，一种是数组类型；一种是实现了 Iterable 接口的类，因此在使用 foreach 循环遍历 ArrayList 的时候，可以看作就是在使用 List 的迭代器进行遍历
如下代码，foreach 遍历 list 集合时，调用 list.remove(s)方法，控制台输出了预期 ConcurrentModificationException 异常
5.2 ArrayList 中 Iterator
本质上返回的是一个 Itr 实例化对象
public Iterator<E> iterator() {
return new Itr();
}
ArrayList 定义了一个 Itr 内部类实现了 Iterator 接口，Itr 内部有三个属性。
cursor：代表的是下一个访问的元素下标；
lastRet：代表的是上一个访问元素的下标，默认值为-1；
expectedModCount：代表的是对 ArrayList 修改的次数，初始值等于 modCount
/**
An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
}
hasNext();
判断是否存在下一个元素，返回值只要 cursor 下一个元素的下标不等于集合的元素个数 size 就返回 true，其他情况返回 false
public boolean hasNext() {
return cursor != size;
}
next() ;
获取集合中的下一个元素
checkForComodification();
判断 modCount 与 expectedModCount 是否相等，不相等抛出 ConcurrentModificationException 异常
i = cursor；i >= size；i >= elementData.length
判断 cursor 的大小，如果 cursor 的值大于集合中元素的个数，抛出 NoSuchElementException 异常；如果 cursor 大于了数组的长度抛出 ConcurrentModificationException 异常。
cursor = i + 1；lastRet = i
如果上述情况均满足，则正常获取下一个元素，cursor 和 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();
}
lastRet < 0；
如果 lastRet 小于 0，则抛出 IllegalStateException 异常，由此可以看出，调用 remove()之前，必须先调用 next()方法重置 lastRet 的值，否则在 lastRet 默认值为-1 的情况下，对集合中的元素进行移除会直接抛出异常；
checkForComodification()；
判断 modCount 与 expectedModCount 是否相等，不相等抛出 ConcurrentModificationException 异常
ArrayList.this.remove(lastRet);
调用 ArrayList 的 remove 方法，移除元素
cursor = lastRet;lastRet = -1;expectedModCount = modCount;
将 lastRet 的值赋值给 cursor，相当于-1；将 lastRet 重置为-1；将 modCount 赋值给 expectedModCount
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 注意这一步非常关键，重新赋值 modCount 给 expectedModCount，是不会出现 ConcurrentModificationException 异常的关键
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
5.3 图解
初始化时 Itr 中的 cursor=0；lastRet=-1；modCount = 4；expectedModCount=4；注意 modCount 的值是在调用 ArrayList 方法的 add()方法时进行 modCount++;而 expectedModCount 的值 Itr 初始化时，默认等于 modCount。
当 foreach 循环到 D 元素的时候，cursor=2；lastRet=1；modCount = 4；expectedModCount=4；
当调用 list.remove(s)移除了元素“D”之后，cursor=2；lastRet=1；modCount = 5；expectedModCount=4；注意此处调用的时 ArrayList 的 remove()方法
由于 ArrayList 的 foreach 遍历实质上相当于 ArrayList 中的 Itr 迭代，所以在 Itr 内部类中的 next()方法被调用时，checkForComodification()方法中比较 modCount 和 expectedModCount 的值，发现二者不相等，则抛出 ConcurrentModificationException 异常！
public E next() {
// 检查 modCount 与 expectedModCount 的值是否相等
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];
}
// 检查 modCount 与 expectedModCount 的值是否相等
final void checkForComodification() {
// 不相等则抛出 ConcurrentModificationException 异常
if
(modCount != expectedModCount)
throw new ConcurrentModificationException();
}
5.4 异常解决
调用 Iterator 的 remove()方法即可
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论