ArrayList感觉是在做项目中遇到最多的，先从添加元素开始讲起，请跟随我的思路
1.add(E e)，最常用的，其他添加元素的方法和这个方法的实现都差不多
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
在添加元素之前，所有方法都会进行一次检查，是否需要进行扩容，如果在指定位置添加元素，则会调用rangeCheckForAdd(index)对index进行检查，是否越界
重点看一下ensureCapacityInternal(size + 1)方法
private void ensureCapacityInternal(int minCapacity) {
//这个判断是针对默认构造函数
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//在小于10之前最大值一直都是DEFAULT_CAPACITY
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
为什么说那个if判断是针对默认构造函数的呢
默认构造函数：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
而Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
其实默认构造函数并没有对elementData进行初始化
而非默认构造函数，比如：
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
是直接对elementData进行了一个初始化的
ensureCapacityInternal(int minCapacity)方法会调用ensureExplicitCapacity(minCapacity)方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount记录的是对数据结构进行修改的次数
如果添加了一个数组元素以后会导致数组溢出，就会进行扩容，真正进行扩容操作的是grow()函数
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩大为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//超过容器允许的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 进行数组拷贝
elementData = Arrays.copyOf(elementData, newCapacity);
}
所以对于调用默认构造函数时，数组的初始化是在第一次添加元素的时候调用grow()函数进行初始化的，对于已经初始化的容器，扩容以后扩大为原容器的1.5倍，而对于没有进行初始化的容器（即调用默认构造函数）初始化为10。如果扩容以后超过最大值将调用hugeCapacity(int minCapacity)方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
超过最大值以后（扩容1.5被），则只能扩容为最大值的大小
还是有必要讲讲 add(int index, E element)方法的，因为这里暴露出了ArrayList的缺陷
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++;
}
有些方法和add(E e)相同，就不累述了。在指定位置上添加元素时，会进行数组拷贝
2.get(int index)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
方法非常简单易懂，不多说，因为是基于数组查找到所需元素，查找速度非常快
3.remove(int index)也是一个非常基本的方法
public E remove(int index) {
//越界检查
rangeCheck(index);
//会对表结构进行修改，modCount进行加1操作
modCount++;
//获得指定位置上的元素
E oldValue = elementData(index);
//因为移除一个元素以后会对数组位置进行移动，这里计算了需
要移动的距离
int numMoved = size - index - 1;
//数组的拷贝
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//标记为null，不可达，让垃圾收集器进行回收
elementData[--size] = null;
//返回旧值
return oldValue;
}
因为remove操作会修改数组的结构，所以会对modCount进行加1操作。数组上的删除操作是非常慢的，因为需要进行数组拷贝。所以ArrayList适合读多写少的场景
remove(Object o)方法
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;
}
这个方法就是首先找到o元素在数组中的位置，然后调用fastRemove(index)移除指定位置上的元素
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
}
为什么是fastRemove呢，就是少了一次对index的check，得瑟死了。因为你在数组中找到那个元素的位置肯定是合法的，所以不需要进行检查
从这里也可以看出，ArrayList中可以添加null值，写个测试demo
AddNull.java
public class AddNull {
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
arrayList.add(null);
System.out.println("size: " + arrayList.size());
Object o = arrayList.get(0);
System.out.println("o: " + o);
}
}
运行结果：
size: 1
o: null
果然添加成功了
4.对ArrayList集合进行不正确操作可能引起的fail-fast
什么是fail-fast:
java集合中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的结构被其他线程所改变了，那么线程A访问集合时，就会抛出
ConcurrentModificationException异常，产生fail-fast事件
测试代码：TestFailFast.java
public class TestFailFast {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
System.out.println("没删除元素之前进行一次遍历");
for (String s: list) {
System.out.println(s);
}
//使用foreach就相当于使用迭代器
// for (String s : list) {
// if (s.equals("B")) {
// list.remove(s);
// }
// }
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("B")) {
list.remove(s);
}
}
//删除B元素进行一次遍历
System.out.println("删除B元素以后进行一次遍历");
for (String s: list) {
System.out.println(s);
}
}
}
程序运行结果：
没删除元素之前进行一次遍历
Exception in thread "main" java.util.ConcurrentModificationException
A
B
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
C
D
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at TestFailFast.main(TestFailFast.java:32)
而对内容的修改是不会引起fail-fast的，对上述代码进行了修改，修改的部分代码如下：
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("B")) {
list.set(1, "test"); //该方法只适用于remove方法，且是在单线程环境下
}
}
程序运行结果：
没删除元素之前进行一次遍历
A
B
C
D
删除B元素以后进行一次遍历
A
test
C
D
没有引起fail-fast
出现fail-fast的源码分析：
出现这个问题的原因是迭代器Iterator，Iterator是一个接口，ArrayList中Itr类实现了这个接口，这个类中的一个next()方法
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];
}
调用next()方法时会进行一次核对，即调用 checkForComodification()方法，这个方法中将会抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
当modCount != expectedModCount不等时就会抛出异常，而Itr类中的expectedModCount值等于集合未发生修改时的modCount值，Itr类中的代码：int expectedModCount = modCount;
如果此时你对集合的结构（比如调用了add(xxx)、remove(xxx)这类方法）进行了修改引起了modCount的变化，就会使两个值不相等，当调用迭代器的next()方法时就会抛出异常
在单线程的情况下，可以通过调用迭代器的remove()或add(E e)方法，对集合的结构进行修改，因为此时expectedModCount会被重新赋值，以remove()方法为例：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
AbstractList.this.remove(lastRet)方法会调用集合的add方法
expectedModCount = modCount;重新赋值
但是这个方法有个缺陷，只适合在单线程下，多线程下避免这种情况应该使用CopyOnWriteArrayList
网友评论