数据结构与算法之线性表(ArrayList原理&源码分析)
ArrayList概述
ArrayList是List接口的大小可变数组的实现,允许存储null元素,容量可自动增加,非线程安全。多线程并发操作可以使用CopyOnWriteArrayList或者Collections.synchronizedList方法包装。
类结构图
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList继承了AbstractList抽象类,实现了RandomAccess、Serializable、Cloneable接口,支持快速随机访问、支持克隆和序列化操作。
属性
/**
*默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
ArrayList arrayList=new ArrayList(0);
* 创建ArrayList指定容量为0时,返回的空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
ArrayList arrayList=new ArrayList();
*当调用无参构造方法,返回的是该数组。刚创建一个ArrayList 时,数据量为0。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
存储ArrayList元素数组,ArrayList的容量就是该数组的长度,当elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,第一个元素添加到ArrayList,
elementData数组扩容到DEFAULT_CAPACITY大小
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList元素个数,不一定等于elementData.length
*
* @serial
*/
private int size;
/**
* 分派给arrays的最大容量
某些vm中会在数组中保留一些头字节,这样会导致数组容量大于vm limit,因此减去8
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造器
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始容量大于0,初始化elementData大小为容量大小
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//初始化容量为0,EMPTY_ELEMENTDATA赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
//初始化容量小于0抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
//初始化容量为10的空列表,这里没有指定大小,当第一次add时,elementData的默认长度为10
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 创建一个包含指定collection的元素列表,列表元素的排列顺序是按照collection迭代器返回的元素顺序排列
*/
public ArrayList(Collection<? extends E> c) {
//将collection转换成数组,然后赋给elementData
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
/**
此处需要判断的原因是,有些方式创建的collection,即使转换城object类型数组,还是原本类型
比如:Integer[] array = {1, 2};
List list = Arrays.asList(array);
list元素还是Integer类型
**/
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果collection长度为0,将空数组EMPTY_ELEMENTDATA赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
}
}
主要方法
方法名 | 功能 |
---|---|
E get(int index) | 获取指定位置元素 |
boolean add(E e) | 末尾添加元素 |
void add(int index, E element) | 指定位置添加元素 |
E remove(int index) | 删除指定位置元素 |
boolean remove(Object o) | 删除值为o的第一个元素 |
E set(int index, E element) | 设置指定位置元素值 |
void removeRange(int fromIndex, int toIndex) | 删除两个索引之间的所有元素,包含fromIndex不包含toIndex |
int indexOf(Object o) | 返回列表中制定元素第一次出现的索引,如果列表中不包含此元素,返回-1 |
int lastIndexOf(Object o) | 返回列表中制定元素最后一次次出现的索引,如果列表中不包含此元素,返回-1 |
boolean contains(Object o) | 判断列表中是否包含元素o |
boolean removeAll(Collection<?> c) | 删除列表中与c交集部分 |
boolean retainAll(Collection<?> c) | 删除列表中与c差集部分 |
void clear() | 清空列表 |
Iterator iterator | 返回元素的迭代器用户遍历列表数据 |
get(int index)
public E get(int index) {
//检测索引位置是否合法
rangeCheck(index);
//返回数组指定位置值
return elementData(index);
}
boolean add(E e) 列表末尾添加元素
public boolean add(E e){
//确保内部容量,如果容量不够容量+1,调用add方法一次,modCount++这个跟fail-fast机制有关参数,后面细讲
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//数组容量检测,不够进行扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 如果数组为空,则minCapacity取默认容量DEFAULT_CAPACITY=10,这个// 就是使用无参构造器创建时默认容量为10的原理
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
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;
//扩容容量=当前容量+当前容量*1/2
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();
//如果需要分配的容量大于最大容量值,则分配Integer.MAX_VALUE,否///则分配容量值为MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
void add(int index, E element) 列表指定位置添加元素
public void add(int index, E element) {
//检测添加位置是否合法
rangeCheckForAdd(index);
//确保容量
ensureCapacityInternal(size + 1); // Increments modCount!!
//数组复制,空出i位置,i之后元素往后移动一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//设置指定位置数组值
elementData[index] = element;
//列表长度+1
size++;
}
remove(int index)
public E remove(int index) {
//检测位置是否合法
rangeCheck(index);
modCount++;
//index位置 值
E oldValue = elementData(index);
//需要移动元素数量,index位置之后的元素需要往前移动一个位置
int numMoved = size - index - 1;
if (numMoved > 0)
//arraycopy(原数组,源数组中的起始位置,目标数组,目标数据中的起始///位置,要复制的数组元素的数量)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//elementData最后一个元素设置为null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove(Object o)
public boolean remove(Object o) {
//删除元素为null
if (o == null) {
for (int index = 0; index < size; index++)
//数组中第一个为null元素删除,后面元素往前移动一个位置
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//删除元素不为null,遍历元素,元素值等于o的第一个元素删除,后面元素往前移动一个位置
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//快速删除指定位置元素
private void fastRemove(int index) {
//修改次数+1
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最后一个元素设置为null
elementData[--size] = null; // clear to let GC do its work
}
set(int index, E element)
public E set(int index, E element) {
//检测索引
rangeCheck(index);
//获取index位置老数据
E oldValue = elementData(index);
//设置index位置新值
elementData[index] = element;
//返回老值
return oldValue;
}
removeRange(int fromIndex, int toIndex)
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
//需要移动的元素个数
int numMoved = size - toIndex;
//移动数据
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
//新数组长度
int newSize = size - (toIndex-fromIndex);
//删除元素设置为null,好让垃圾回收机制回收内存
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
indexOf(Object o)
public int indexOf(Object o) {
//元素为null,遍历数组中等于null元素,然后返回索引
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
//元素不为null,判断查询元素o与数组中元素是否相等,相等直接返回索引
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
//列表中不包含o,直接返回-1
return -1;
}
lastIndexOf(Object o)
public int lastIndexOf(Object o) {
//元素为null,从size-1位置往前遍历数组中等于null元素,然后返回索引
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
//元素不为null,从size-1位置往前判断查询元素o与数组中元素是否相等,相等直接返回索引
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
//列表中不包含o,直接返回-1
return -1;
}
contains(Object o)
public boolean contains(Object o) {
//indexOf包含元素返回索引位置 不包含元素返回-1
return indexOf(o) >= 0;
}
removeAll(Collection<?> c)
public boolean removeAll(Collection<?> c) {
//检测c集合是否为null,如果为null抛出空指针异常
Objects.requireNonNull(c);
//批量删除元素
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
//原始数据
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//遍历elementData元素
//此处分2种情况 remvoveAll complement=false,将集合c中没有的元素赋值到elementData
//retainAll complement=true,将集合c中有的元素赋值到elementData
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//finally语句主要是防止c.contains有异常抛出时能保证elementData数据的完整性
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//elementData没有遍历完
if (r != size) {
//没有遍历到的元素复制到elementData
System.arraycopy(elementData, r,
elementData, w,
size - r);
//size - r的大小等于没有遍历到的元素
w += size - r;
}
//元素有删除
if (w != size) {
// clear to let GC do its work
//删除的元素设置为null
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
retainAll(Collection<?> c)
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
//complement=true,batchRemove
//if (c.contains(elementData[r]) == complement)
// elementData[w++] = elementData[r];
// 将集合c中有的元素赋值到elementData
return batchRemove(c, true);
}
clear()
public void clear() {
//修改次数+1
modCount++;
// clear to let GC do its work
//设置数组中所有元素为null
for (int i = 0; i < size; i++)
elementData[i] = null;
//列表大小设置为0
size = 0;
}
iterator()
public Iterator<E> iterator() {
//返回内部类Itr
return new Itr();
}
private class Itr implements Iterator<E> {
//下一个迭代元素的数组下表
int cursor; // index of next element to return
//记录最后一个返回元素的数组下表,如果没有返回-1
int lastRet = -1; // index of last element returned; -1 if no such
//expectedModCount则是modCount的值,主要用来检测在迭代器使用期间有没有修改过ArrayList,修改了之//后如果调用迭代器内的next方法,则会抛出ConcurrentModificationException异常。这个就是fail-fast机制。
int expectedModCount = modCount;
Itr() {}
//是否有下一个元素
public boolean hasNext() {
return cursor != size;
}
//返回下一个元素
@SuppressWarnings("unchecked")
public E next() {
//检测List是否倍修改,如果被修改抛出异常
checkForComodification();
int i = cursor;
//如果下一个元素的索引大于等于数组长度抛出异常,因为数组最大下标是size-1
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返回的元素
public void remove() {
//如果最后一次调用next元素不存在抛出异常
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//调用ArrayList的remove方法
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
//此处保证expectedModCount=modCount,因此调用Iterator的remove方法不会抛出异常
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
//JDK1.8加入的遍历集合方法,Consumer函数式接口,调用此方法传入一个自定义的consumer接口,每个元素就可以执行函数中定义的操作
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
//调用consumer.accept遍历数组数据
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
什么是快速失败(fail-fast)与安全失败(fail-safe)
在JAVA Collection集合框架的类中,有线程安全和不安全的2类。对线程不安全的类并发情况下修改可能会出现fail-fast,而线程安全类可能出现fail-safe情况。
fail-fast快速失败
当遍历一个集合对象时,如果集合对象结构被修改(添加,删除,修改),会抛出ConcurrentModificationException。
ArrayList arrayList = new ArrayList(Arrays.asList(1, 2, 3, 4));
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
Object i = iterator.next();
arrayList.remove(i);
// iterator.remove();这样调用不会抛出异常
}
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)
单线程环境下如果不想抛出异常,可以调研Iterator的remove()方法。
ArrayList是怎么样实现fail-fast机制了?
在ArrayList集成的抽象类AbstractList中有个属性
//集合被修改次数,调用add remove等方法时,modCount++
protected transient int modCount = 0;
当调用ArrayList.iterator()返回对象,有个一属性expectedModCount,这个属性会被赋值为modCount,相当于这个点modCount的副本,expectedModCount的值在iterator内部不会变化,但是modCount的值会在外部有修改情况下变化。
当调研iterator.remove为什么不会抛出异常,因为这个方法内部没有使用modCout++操作,而是 expectedModCount = modCount。
fail-safe安全失败
fail-fast机制发生时程序会抛出异常,fail-safe机制发生程序不会抛出异常,但是它返回的数据时某个时间点的快照,并发容器的iterate方法返回的数据内部保存的是集合对象的一个快照,没有是有modCount值做校验,所以fail-fast机制返回的数据不是集合本身的最终正确数据,CopyOnWriteArrayList就是fail-fast机制。
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
//快照
snapshot = elements;
}
本文地址:https://blog.csdn.net/RenPeng_Ben/article/details/107624058
上一篇: 求随机数
推荐阅读
-
JavaScript数据结构与算法之队列原理与用法实例详解
-
JavaScript数据结构与算法之检索算法实例分析【顺序查找、最大最小值、自组织查询】
-
【数据结构与算法Python描述】——Python列表实现原理探究及常用操作时间复杂度分析
-
数据结构与算法之线性表(ArrayList原理&源码分析)
-
数据结构与算法分析 之 数据结构和算法概述
-
Python数据结构与算法之算法分析详解
-
Python 数据结构与算法分析 七、图算法之广度优先搜索
-
sphinx 源码阅读之数据结构与算法
-
sphinx 源码阅读之数据结构与算法
-
【数据结构与算法Python描述】——Python列表实现原理探究及常用操作时间复杂度分析