目录
ArrayList
描述
重要的对象
遍历使用
与 Collection 关系
ArrayList 属性
扩展: 什么是序列化
transient 关键字解析
ArrayList 构造方法
无参构造
int 类型参数的构造方法
Collection 对象的构造方法
ArrayList 普通方法
add(E e)方法
remove()方法
快速失败机制
思考
为什么 ArrayList 继承了 AbstractList 还要实现 List 接口 ?
System.arraycopy()和 Arrays.copyof()
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()自己内部会创建一个新的数组进行拷贝
来源: https://www.cnblogs.com/alige/p/11562070.html