ArrayList的底层是动态数组,它的容量能动态增长。
索引存取元素,有序,可重复,允许多个null
1、ArrayList初始容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
// 无参构造器,初始化为空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_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);
}
}
// 根据传入集合做初始化,若集合为空,则为空,还要对得到的数组判断是否为对象数组类型
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;
}
}
2、扩容
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。默认情况下,新的容量会是原容量的1.5倍
// list结构变化的次数(影响迭代器)
protected transient int modCount = 0;
// 一些JVM需要保存数组头信息,申请更大的数组可能会OOM
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 第一次添加元素,size=0
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 末尾插入元素
return true;
}
// 对容量判断,不足则扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 若使用无参构造器初始化,则容量为默认10和需要的最小容量之间的最大值(第一次添加变为10)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity; // 若使用带参构造器初始化,不管是否为空,都取需要的最小容量,即第一次添加为1
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 记录结构变动
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 容量不足,扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
if (newCapacity - minCapacity < 0) // 1.5倍不够,则取需要的最小容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 最大的数组容量不满足,最大可取Integer.MAX_VALUE
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;
}
3、删除元素
安全的删除元素:使用迭代器
使用for删除,会导致ConcurrentModificationException
public class Test {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("1111");
list.add("2222");
list.add("3333");
list.add("4444");
list.add("5555");
for (String str : list){
if (str == "2222"){
list.remove(str);
}
}
for (String str : list){
System.out.println(str);
}
}
}
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at file.Test.main(Test.java:15)
Process finished with exit code 1
反编译后代码为
import java.util.ArrayList;
import java.util.Iterator;
public class Test {
public static void main(String[] var0) {
ArrayList var1 = new ArrayList();
var1.add("1111");
var1.add("2222");
var1.add("3333");
var1.add("4444");
var1.add("5555");
Iterator var2 = var1.iterator();
String var3;
while(var2.hasNext()) {
var3 = (String)var2.next();
if(var3 == "2222") {
var1.remove(var3); // 迭代器中调用了list的remove方法
}
}
var2 = var1.iterator();
while(var2.hasNext()) {
var3 = (String)var2.next();
System.out.println(var3);
}
}
}
ArrayList的remove方法:
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 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
}
迭代器的变动次数modCount
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; // 初始化时为当前list的变动次数
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); // 先判断modCount
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) // list调用remove后已经加1,不一致
throw new ConcurrentModificationException();
}
// ...
}
4、迭代器
Iterator
Iterator模式用同一种逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来,不需要了解集合内部实现便可以遍历集合元素,统一使用 Iterator 提供的接口去遍历。它的特点是更加安全,因为它可以保证,在当前遍历的集合元素被更改的时候,就会抛出 ConcurrentModificationException 异常
主要有三个方法:hasNext()、next()和remove()
**ListIterator **
ListIterator 是 Iterator的增强版。
- ListIterator遍历可以是逆向的,因为有previous()和hasPrevious()方法,而Iterator不可以。
- ListIterator有add()方法,可以向List添加对象,而Iterator却不能。
- ListIterator可以定位当前的索引位置,因为有nextIndex()和previousIndex()方法,而Iterator不可以。
- ListIterator可以实现对象的修改,set()方法可以实现。Iierator仅能遍历,不能修改。
- ListIterator只能用于遍历List及其子类,Iterator可用来遍历所有集合
5、fail fast
fast-fail是Java集合的一种错误机制。当多个线程对同一个集合进行操作时,就有可能会产生fast-fail事件。例如:当线程a正通过iterator遍历集合时,另一个线程b修改了集合的内容,此时modCount(记录集合操作过程的修改次数)会加1,不等于expectedModCount,那么线程a访问集合的时候,就会抛出ConcurrentModificationException,产生fast-fail事件。边遍历边修改集合也会产生fast-fail事件(上面例子)。
解决方法:
- 使用Colletions.synchronizedList方法或在修改集合内容的地方加上synchronized。这样的话,增删集合内容的同步锁会阻塞遍历操作,影响性能。
- 使用CopyOnWriteArrayList来替换ArrayList。在对CopyOnWriteArrayList进行修改操作的时候,会拷贝一个新的数组,对新的数组进行操作,操作完成后再把引用移到新的数组(每写一个就要复制一次,很耗时,推荐读多写少的场景)
6、CopyOnWrite
Copy-On-Write,写时复制。当我们往容器添加元素时,不直接往容器添加,而是先将当前容器进行复制,复制出一个新的容器,然后往新的容器添加元素,添加完元素之后,再将原容器的引用指向新容器。这样做的好处就是可以对CopyOnWrite
容器进行并发的读而不需要加锁,因为当前容器不会被修改
缺点:
- 内存占用问题。由于CopyOnWrite的写时复制机制,在进行写操作的时候,内存里会同时驻扎两个对象的内存。
- CopyOnWrite容器不能保证数据的实时一致性,可能读取到旧数据。
CopyOnWriteArrayList
CopyOnWriteArrayList
中add方法添加的时候是需要加锁的,保证同步,避免了多线程写的时候复制出多个副本。读的时候不需要加锁,如果读的时候有其他线程正在向CopyOnWriteArrayList
添加数据,还是可以读到旧的数据。
CopyOnWrite并发容器用于读多写少的并发场景。
优点:
读操作性能很高,因为无需任何同步措施,比较适用于读多写少的并发场景。Java的list在遍历时,若中途有别的线程对list容器进行修改,则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想,遍历和修改操作分别作用在不同的list容器,所以在使用迭代器进行遍历时候,也就不会抛出ConcurrentModificationException异常了。
缺点:
一是内存占用问题,毕竟每次执行写操作都要将原容器拷贝一份,数据量大时,对内存压力较大,可能会引起频繁GC;
二是无法保证实时性,Vector对于读写操作均加锁同步,可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因,写和读分别作用在新老不同容器上,在写操作执行过程中,读不会阻塞但读取到的却是老容器的数据
7、fail safe
采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。
原理:由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发Concurrent Modification Exception。
缺点:基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的
8、让集合不能被修改
Collections包下的unmodifiableMap/unmodifiableList/unmodifiableSet方法,通过这个方法返回的集合,是不可以修改的。如果修改的话,会抛出 java.lang.UnsupportedOperationException异常
List<String> list = new ArrayList<>();
list.add("1111");
list.add("2222");
List list1 = Collections.unmodifiableList(list);
list1.remove(1);
报错:
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.Collections$UnmodifiableList.remove(Collections.java:1319)
at file.Test.main(Test.java:18)
public static <T> List<T> unmodifiableList(List<? extends T> list) {
return (list instanceof RandomAccess ?
new UnmodifiableRandomAccessList<>(list) :
new UnmodifiableList<>(list));
}
9、ArrayList、Vector、LinkedList
ArrayList与Vector:
-
ArrayList在内存不够时扩容为原来的1.5倍,Vector是扩容为原来的2倍。
-
Vector属于线程安全级别的,但是大多数情况下不使用Vector,因为操作Vector效率比较低。
ArrayList与LinkedList:
- ArrayList基于动态数组实现,LinkedList基于链表实现
- 对于随机index访问的get和set方法,ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素;LinkedList要移动指针遍历每个元素直到找到为止
- 新增和删除元素,LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时,可能扩容和复制数组;LinkedList实例化对象需要时间外,只需要修改指针即可
10、ArrayDeque
ArrayDeque实现了双端队列,内部使用循环数组实现,默认大小为16。它的特点有:
- 在两端添加、删除元素的效率较高
- 根据元素内容查找和删除的效率比较低。
- 没有索引位置的概念,不能根据索引位置进行操作。
ArrayDeque和LinkedList都实现了Deque接口,如果只需要从两端进行操作,ArrayDeque效率更高一些。如果同时需要根据索引位置进行操作,或者经常需要在中间进行插入和删除(LinkedList有相应的 api,如add(int index, E e)),则应该选LinkedList。
ArrayDeque和LinkedList都是线程不安全的,可以使用Collections工具类中synchronizedXxx()转换成线程同步
11、ConcurrentLinkedQueue
非阻塞队列。高效的并发队列,使用链表实现。可以看做一个线程安全的 LinkedList
,通过 CAS 操作实现。
如果对队列加锁的成本较高则适合使用无锁的 ConcurrentLinkedQueue
来替代。适合在对性能要求相对较高,同时有多个线程对队列进行读写的场景
对于非阻塞队列,一般情况下建议使用offer(插入队尾)、poll(获取并移除队头)和peek(获取队头)三个方法,不建议使用add和remove方法。因为使用offer、poll和peek三个方法可以通过返回值判断操作成功与否,而使用add和remove方法却不能达到这样的效果(失败抛异常)
12、阻塞队列
阻塞队列是java.util.concurrent
包下重要的数据结构,BlockingQueue
提供了线程安全的队列访问方式:当阻塞队列进行插入数据时,如果队列已满,线程将会阻塞等待直到队列非满;从阻塞队列取数据时,如果队列已空,线程将会阻塞等待直到队列非空。并发包下很多高级同步类的实现都是基于BlockingQueue
实现的。BlockingQueue
适合用于作为数据共享的通道。
使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现。
阻塞队列和一般的队列的区别就在于:
-
多线程支持,多个线程可以安全的访问队列
-
阻塞操作,当队列为空的时候,消费线程会阻塞等待队列不为空;当队列满了的时候,生产线程就会阻塞直到队列不满