ArrayList
2019-09-26 本文已影响0人
sizuoyi00
几句话证明你看过ArrayList的源码
数组（查询快，增删慢，线程安全，允许元素重复和null，扩容1.5倍，增删都是在末尾效率会很高)
关于循环删除元素，普通for循环，不会报错，会导致下标紊乱，产生数据错误或数组越界
增强for循环，由于删除修改了modCount，导致fail-fast，所以会报错ConcurrentModificationException
迭代器删除(iterator.remove()，而不是list.remove())，每次都会重新赋值expectedModCount = modCount;所以迭代器支持删除
1.动态数组
ArrayList底层是一个动态数组Object[] elementData
size 则是动态数组的实际大小
2.动态数组修饰符为transient
transient关键字了解
简单概括：实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中
集合类一般都没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。
自定义序列化原因：多数情况下内部数组是无法被存满的，序列化未使用的部分，浪费空间
3.ArrayList构造器
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
注意：默认new ArrayList()没有构造默认动态数组Default initial capacity = 10的，而是在add添加元素时进行的扩容 JDK "1.8.0_171"
4.数组扩容方法Arrays.copyOf(elementData, newCapacity)
底层使用System.arraycopy(src, 0, dest, 0, length);
System.arraycopy用法
/**
* src:源数组;
* srcPos:源数组要复制的起始位置;
* dest:目标数组;
* destPos:目标数组放置的起始位置;
* length:复制的长度
*/
System.arraycopy(src, 0, dest, 0, length);
思考
当数组长度不够时进行扩容，那么remove时为什么不进行反扩容？
5.add方法
确认是否扩容，扩容条件：当前size达到最大容量。扩容1.5倍
/**
* 将e添加到ArrayList中 数组尾
*/
public boolean add(E e) {
//确保是否扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 将e添加到ArrayList的指定位置
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
//确保是否扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//角标从index整体后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//1. size + 1新增元素所需最小容量
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//2. 判断数组是否为空，取max(数组默认容量,size + 1)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//3. 所需最小容量达到数组长度则扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//4. 扩容 计算最小容量 正常情况默认1.5倍
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;
}
6.remove方法
/**
* 删除某个角标
*
* 过程同fastmove方法
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
//移动的长度
int numMoved = size - index - 1;
if (numMoved > 0)
//1.角标从index+1整体前移
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
//--size先移动角标，2.后将最后一个值赋值为null
//--size，做遍历删除的时候，
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 删除某个元素
*/
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;
//1.角标从index+1整体前移
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
//--size先移动角标，2.后将最后一个值赋值为null
elementData[--size] = null; // clear to let GC do its work
}
7.fail-fast机制
fail-fast 机制是java集合中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
注意：可简单观看前边add与remove代码，都有对modCount变量的操作，多线程使用Iterator或使用增强for循环时，会对比modCount与迭代器中expectedModCount值时，不相符则会报ConcurrentModificationException异常
/**
* List对应迭代器。实际上，是new了一个Itr对象。
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* Itr是Iterator(迭代器)的实现类
*/
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
/**
修改数的记录值
每次新建Itr()对象时，都会保存新建该对象时对应的modCount；
以后每次遍历List中的元素的时候，都会比较expectedModCount和modCount是否相等；
若不相等，则抛出ConcurrentModificationException异常，产生fail-fast事件。
*/
int expectedModCount = modCount;
Itr() {
}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//获取下一个元素之前，会判断“新建Itr对象时保存的modCount”和“当前的modCount”是否相等；
// 增强for循环删除元素，由于删除修改了modCount，所以这里会报错，‘
// 迭代器删除则不会有问题，因为迭代器删除最后会赋值expectedModCount = modCount
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
//remove之前，也会判断“新建Itr对象时保存的modCount”和“当前的modCount”是否相等；
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
防止fail-fast
多线程场景使用CopyOnWriteArrayList，详见：CopyOnWriteArrayList
8.自定义ArrayList练习
import lombok.ToString;
import java.util.Arrays;
@ToString
public class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 10;
private int size;
private E[] data;
public MyArrayList(int initialCapacity) {
data = (E[]) new Object[initialCapacity];
}
public MyArrayList() {
this(DEFAULT_CAPACITY);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(E o) {
return indexOf(o) == -1;
}
@Override
public boolean add(E o) {
final int minCapacity = size + 1;
if (minCapacity == data.length) {
//扩容
grow(minCapacity);
}
data[size++] = o;
return true;
}
/**
* 扩容，默认1.5 如果扩容后小于需要的最小容量，则使用传入的容量
*
* @param minCapacity
*/
private void grow(int minCapacity) {
//扩容1.5倍
int newCapacity = data.length + (data.length >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
data = Arrays.copyOf(data, newCapacity);
}
@Override
public boolean remove(E o) {
if (o == null) {
for (int i = 0; i < size; i++) {
E e = data[i];
if (e == null) {
fastRemove(i);
}
}
} else {
for (int i = 0; i < size; i++) {
E e = data[i];
if (o.equals(e)) {
fastRemove(i);
}
}
}
return false;
}
/**
* 向前移动
*
* @param index
*/
private void fastRemove(int index) {
// for (int j = 0; j < size - 1; j++) {
// if (j >= index) {
// data[j] = data[j + 1];
// }
// }
System.arraycopy(data, index + 1, data, index, size - 1 - index);
//size要减少一个
data[--size] = null;
}
@Override
public E get(int index) {
return data[index];
}
@Override
public E set(int index, E element) {
data[index] = element;
return element;
}
/**
* 向后移动
*
* @param index
* @param element
*/
@Override
public void add(int index, E element) {
final int minCapacity = size + 1;
if (minCapacity == data.length) {
//扩容
grow(minCapacity);
}
//移动
System.arraycopy(data, index, data, index + 1, 4);
//赋值
data[index] = element;
size++;
}
@Override
public E remove(int index) {
E e = data[index];
fastRemove(index);
return e;
}
@Override
public int indexOf(E o) {
if (o == null) {
for (int i = 0; i < size; i++) {
E e = data[i];
if (e == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
E e = data[i];
if (o.equals(e)) {
return i;
}
}
}
return -1;
}
public static void main(String[] args) {
MyList<Integer> l = new MyArrayList<>();
l.isEmpty();
l.add(1);
l.add(3);
l.add(4);
l.add(7);
l.add(12);
System.out.println(l);
l.add(2, 6);
System.out.println(l);
l.remove(3);
System.out.println(l);
System.out.println(l.indexOf(1));
l.set(3, 33);
System.out.println(l);
System.out.println(l.get(1));
l.remove(new Integer(1));
System.out.println(l);
System.out.println(l.isEmpty());
System.out.println(l.size());
}
}
参考：https://www.cnblogs.com/skywang12345/p/3323085.html
集合遍历采坑记：https://www.rabbitwfly.com/articles/2019/04/18/1555580979871.html
