集合ArrayList分析
ArrayList
描述
- 继承AbstractList类，实现List接口
- 实现了RandmoAccess接口，即提供了随机访问功能
- 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
- 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
- 基于泛型动态数组(List)扩容(碰到数组先想到连续的内存空间，故空间效率不高)
ArrayList可以以O(1)的时间复杂度去根据下标访问元素。(时间效率很高)- 线程不安全的，允许元素为null
重要的对象
elementData (Object类型的数组)
size(int 类型)
遍历使用
使用for循环，通过索引随机访问效率最高，其次是foreach循环，最慢是迭代器循环
foreach 最终会被转换成迭代器遍历的形式，所以是不如for循环的
与Collection关系
ArrayList属性
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
// 序列化id
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始的容量
private static final int DEFAULT_CAPACITY = 10;
// 一个空对象
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
// 一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
// 当前数据对象存放地方，当前对象不参与序列化
transient Object[] elementData;
// 当前数组长度
private int size;
// 数组最大长度
private static final int MAX_ARRAY_SIZE = 2147483639;
}
扩展：什么是序列化(这里序列化又是一大知识点)
序列化是指：将对象转换成以字节序列的形式来表示，以便用于持久化和传输。
实现方法：实现Serializable接口。
然后用的时候拿出来进行反序列化即可又变成Java对象。
transient关键字解析
Java中transient关键字的作用，简单地说，就是让某些被修饰的成员属性变量不被序列化。
有了transient关键字声明，则这个变量不会参与序列化操作，即使所在类实现了Serializable接口，反序列化后该变量为空值。
那么问题来了：ArrayList中数组声明：
transient Object[] elementData;，事实上我们使用ArrayList在网络传输用的很正常，并没有出现空值。
原来：ArrayList在序列化的时候会调用writeObject()方法，将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。
那为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？
原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
所以ArrayList的设计者将elementData设计为transient，然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。
见源码：
// Write out all elements in the proper order.for (int i=0; i<size; i++) { s.writeObject(elementData[i]);}
从源码中，可以观察到 循环时是使用i<size而不是 i<elementData.length，说明序列化时，只需实际存储的那些元素，而不是整个数组。
ArrayList构造方法
无参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
默认无参构建方法创建ArrayList对象
new ArrayList() 创建对象，数组长度size=0，而elementData数组的长度为size+1，
第一次add时，elementData会变成默认长度=10(DEFAULT_CAPACITY)
int类型参数的构造方法
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);
}
}
initialCapacity指定初始数组长度。
Collection对象的构造方法
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;
}
}
- 将collection对象转换成数组，然后将数组的地址赋给elementData。
- 更新size的值，同时判断size的大小，如果是size等于0，直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData
- 如果size的值大于0，则执行Arrays.copyOf方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中。
注意：this.elementData = arg0.toArray(); 这里执行的简单赋值是浅拷贝，所以要执行Arrays.copyOf做深拷贝
ArrayList普通方法
add(E e)方法
/**
*增加指定的元素到ArrayList的最后位置
* @param e 要添加的元素
* @return
*/
public boolean add(E e) {
// 确定ArrayList的容量大小---严谨
// 注意：size + 1，保证资源空间不被浪费，
// ☆☆☆按当前情况，保证要存多少个元素，就只分配多少空间资源
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 私有方法：明确 ArrayList 的容量，提供给本类使用的方法
* - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效
* @param minCapacity 指定的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
// 若 elementData == {}，则取 minCapacity 为 默认容量和参数 minCapacity 之间的最大值
// 注：ensureCapacity() 是提供给用户使用的方法，在 ArrayList 的实现中并没有使用
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity= Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 私有方法：明确 ArrayList 的容量
* - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效
* @param minCapacity 指定的最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
// 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的
modCount++;
// 防止溢出代码：确保指定的最小容量 > 数组缓冲区当前的长度
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 数组缓冲区最大存储容量
* - 一些 VM 会在一个数组中存储某些数据--->为什么要减去 8 的原因
* - 尝试分配这个最大存储容量，可能会导致 OutOfMemoryError(当该值 > VM 的限制时)
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 私有方法：扩容，以确保 ArrayList 至少能存储 minCapacity 个元素
* - 扩容计算：newCapacity = oldCapacity + (oldCapacity >> 1); 扩充当前容量的1.5倍
* @param minCapacity 指定的最小容量
*/
private void grow(int minCapacity) {
// 防止溢出代码
int oldCapacity = elementData.length;// 旧容量大小
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍
if (newCapacity - minCapacity < 0) // 若 newCapacity新容量小于参数指定容量，修改新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 若 newCapacity 大于最大存储容量，则进行大容量分配
newCapacity = hugeCapacity(minCapacity);
// 拷贝扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 私有静态方法：大容量分配，最大分配 Integer.MAX_VALUE
* @param 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）确保数组已使用长度（size）加1之后足够存下 下一个数据
2）修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组，grow方法会将当前数组的长度变为原来容量的1.5倍。
3）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
4）返回添加成功布尔值。
remove()方法
删除指定位置的元素。
//删除指定位置的元素，返回被删除的元素
public E remove(int index) {
rangeCheck(index);
modCount++; //被删除时 modCount也会改变
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 将 index + 1 及之后的元素向前移动一位，覆盖被删除值
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将最后一个元素置空，并将 size 值减1
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;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
删除操作的步骤：
- 获取指定位置 index 处的元素值
- 将 index + 1 及之后的元素向前移动一位
- 将最后一个元素置空，并将 size 值减 1
- 返回被删除值，完成删除操作
快速失败机制
在 Java 集合框架中，很多类都实现了快速失败机制。该机制被触发时，会抛出并发修改异常ConcurrentModificationException。
- < p > < name = "快速失败" >
*该类的{@link #iterator() iterator}和返回的迭代器
- {@link #listIterator(int) listIterator}方法是fail-fast:
*如果列表在迭代器之后的任何时候在结构上被修改
*创建的，除了通过迭代器自己创建之外的任何方式
{@link ListIterator#remove() remove}或
{@link ListIterator#add(Object) add}方法，迭代器将抛出一个
{@link ConcurrentModificationException}。于是，面对
*并发修改，迭代器会快速而干净地失败
*而不是冒着不确定行为的风险
未来的时间。
注意，不能保证迭代器的快速故障行为
*一般来说，在……方面是不可能作出任何硬性保证的
*存在不同步的并发修改。快速失败迭代器
*尽最大努力抛出{@code ConcurrentModificationException}。
因此，编写依赖于此的程序是错误的
*正确性异常:迭代器的快速故障行为
*应该只用于检测bug。
这个类是
< a href = " {@docRoot} / . . /技术说明/指导/收藏/ index . html " >
Java集合框架。
源码注释总结：
在遇到并发修改时，迭代器会尽最大努力抛出ConcurrentModificationException这个异常，
但不能百分之百的保证，而迭代器的快速失败，会避免程序在将来不确定的时间里出现不确定的行为。
思考
为什么ArrayList继承了AbstractList还要实现List接口 ？
防止在代理时出错
其实没有必要，实现与不实现都是可以的。
System.arraycopy()和Arrays.copyof()
- Arrays.copyOf()内部还调用了System.arraycopy()这个方法
- System.arraycopy()需要传一个数组的参数进行拷贝。
- 而Arrays.copyof()自己内部会创建一个新的数组进行拷贝
最新文章
- 【荐】MongoDB基本命令大全
- 黑马程序员_ Objective-c 内存管理笔记
- SQLserver 查看数据库包含指定数据的表（字段）
- 【POJ3691】DNA repair（AC自动机，DP）
- [转]七天学会NodeJS
- javaScript入门--引用类型
- MD5加密相关
- [技术翻译]Guava官方文档Ordering
- 我在Yahoo与ATS 九死一生的故事
- tomcat部署项目
- quartz 使用问题，小坑
- 变量新声明之let、const
- 强大而灵活的字体图标替代库iconfont
- SpringBank 开发日志 使用maven构建dubbo服务的可执行jar包
- 删除Mac OS X中Finder文件打开方式列表的重复程序或失效的
- 01 mysql
- Servlet------EL表达式
- go语言之进阶篇创建goroutine协程
- SQLServer 中的SYSPROCESSES表
- SQL Server ->> 数据类型不一致比较时的隐式转换