简介
ArrayList 是我们开发中非常常用的数据存储容器之一, 其底层是数组实现的, 我们可以在集合中存储任意类型的数据, ArrayList 是线程不安全的, 非常适合用于对元素进行查找, 效率非常高.
线程安全性
对 ArrayList 的操作一般分为两个步骤, 改变位置 (size) 和操作元素(e). 所以这个过程在多线程的环境下是不能保证具有原子性的, 因此 ArrayList 在多线程的环境下是线程不安全的.
源码分析
1. 属性分析
- /**
- * 默认初始化容量
- */
- private static final int DEFAULT_CAPACITY = 10;
- /**
- * 如果自定义容量为 0, 则会默认用它来初始化 ArrayList. 或者用于空数组替换.
- */
- private static final Object[] EMPTY_ELEMENTDATA = {};
- /**
- * 如果没有自定义容量, 则会使用它来初始化 ArrayList. 或者用于空数组比对.
- */
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- /**
- * 这就是 ArrayList 底层用到的数组
- * 非私有, 以简化嵌套类访问
- * transient 在已经实现序列化的类中, 不允许某变量序列化
- */
- transient Object[] elementData;
- /**
- * 实际 ArrayList 集合大小
- */
- private int size;
- /**
- * 可分配的最大容量
- */
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
扩展: 什么是序列化
序列化是指: 将对象转换成以字节序列的形式来表示, 以便用于持久化和传输.
实现方法: 实现 Serializable 接口.
然后用的时候拿出来进行反序列化即可又变成 Java 对象.
transient 关键字解析
Java 中 transient 关键字的作用, 简单地说, 就是让某些被修饰的成员属性变量不被序列化.
有了 transient 关键字声明, 则这个变量不会参与序列化操作, 即使所在类实现了 Serializable 接口, 反序列化后该变量为空值.
那么问题来了: ArrayList 中数组声明: transient Object[] elementData;, 事实上我们使用 ArrayList 在网络传输用的很正常, 并没有出现空值.
原来: ArrayList 在序列化的时候会调用 writeObject()方法, 将 size 和 element 写入 ObjectOutputStream; 反序列化时调用 readObject(), 从 ObjectInputStream 获取 size 和 element, 再恢复到 elementData.
那为什么不直接用 elementData 来序列化, 而采用上诉的方式来实现序列化呢?
原因在于 elementData 是一个缓存数组, 它通常会预留一些容量, 等容量不足时再扩充容量, 那么有些空间可能就没有实际存储元素, 采用上诉的方式来实现序列化时, 就可以保证只序列化实际存储的那些元素, 而不是整个数组, 从而节省空间和时间.
2. 构造方法分析
根据 initialCapacity 初始化一个空数组, 如果值为 0, 则初始化一个空数组:
- /**
- * 根据 initialCapacity 初始化一个空数组
- */
- 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);
- }
- }
不带参数初始化, 默认容量为 10:
- /**
- * 不带参数初始化, 默认容量为 10
- */
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
通过集合做参数的形式初始化: 如果集合为空, 则初始化为空数组:
- /**
- * 通过集合做参数的形式初始化
- */
- 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;
- }
- }
3. 主干方法
trimToSize()方法:
用来最小化实例存储, 将容器大小调整为当前元素所占用的容量大小.
- /**
- * 这个方法用来最小化实例存储.
- */
- public void trimToSize() {
- modCount++;
- if (size <elementData.length) {
- elementData = (size == 0)
- ? EMPTY_ELEMENTDATA
- : Arrays.copyOf(elementData, size);
- }
- }
clone()方法
用来克隆出一个新数组.
- public Object clone() {
- try {
- ArrayList<?> v = (ArrayList<?>) super.clone();
- v.elementData = Arrays.copyOf(elementData, size);
- v.modCount = 0;
- return v;
- } catch (CloneNotSupportedException e) {
- // this shouldn't happen, since we are Cloneable
- throw new InternalError(e);
- }
- }
通过调用 Object 的 clone()方法来得到一个新的 ArrayList 对象, 然后将 elementData 复制给该对象并返回.
add(E e)方法
在数组末尾添加元素
- /**
- * 在数组末尾添加元素
- */
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
看到它首先调用了 ensureCapacityInternal()方法. 注意参数是 size+1, 这是个面试考点.
- private void ensureCapacityInternal(int minCapacity) {
- ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
- }
这个方法里又嵌套调用了两个方法: 计算容量 + 确保容量
计算容量: 如果 elementData 是空, 则返回默认容量 10 和 size+1 的最大值, 否则返回 size+1
- private static int calculateCapacity(Object[] elementData, int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- return minCapacity;
- }
计算完容量后, 进行确保容量可用:(modCount 不用理它, 它用来计算修改次数)
如果 size+1> elementData.length 证明数组已经放满, 则增加容量, 调用 grow().
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- grow(minCapacity);
- }
增加容量: 默认 1.5 倍扩容.
获取当前数组长度 =>oldCapacity
oldCapacity>>1 表示将 oldCapacity 右移一位(位运算), 相当于除 2. 再加上 1, 相当于新容量扩容 1.5 倍.
如果
newCapacity<minCapacity
, 则
newCapacity = minCapacity
. 看例子更明白一点: 假设 size 为 1, 则
minCapacity=size+1=2
, 而
- elementData.length=1
- ,
- newCapacity=1+1>>1=1
,1<2 所以如果不处理该情况, 扩容将不能正确完成.
如果新容量比最大值还要大, 则将新容量赋值为 VM 要求最大值.
将 elementData 拷贝到一个新的容量中.
- 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);
- }
size+1 的问题
好了, 那到这里可以说一下为什么要 size+1.
size+1 代表的含义是:
如果集合添加元素成功后, 集合中的实际元素个数.
为了确保扩容不会出现错误.
假如不加一处理, 如果默认 size 是 0, 则 0+0>>1 还是 0.
如果 size 是 1, 则 1+1>>1 还是 1. 有人问: 不是默认容量大小是 10 吗? 事实上, jdk1.8 版本以后, ArrayList 的扩容放在 add()方法中. 之前放在构造方法中. 我用的是 1.8 版本, 所以默认 ArrayList arrayList = new ArrayList(); 后, size 应该是 0. 所以, size+1 对扩容来讲很必要.
- public static void main(String[] args) {
- ArrayList arrayList = new ArrayList();
- System.out.println(arrayList.size());
- }
输出: 0
事实上上面的代码是证明不了容量大小的, 因为 size 只会在调用 add()方法时才会自增. 有办法的小伙伴可以在评论区大显神通.
add(int index, E element)方法
- public void add(int index, E element) {
- rangeCheckForAdd(index);
- ensureCapacityInternal(size + 1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
rangeCheckForAdd()是越界异常检测方法. ensureCapacityInternal()之前有讲, 着重说一下 System.arrayCopy 方法:
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
代码解释:
Object src : 原数组
int srcPos : 从元数据的起始位置开始
Object dest : 目标数组
int destPos : 目标数组的开始起始位置
int length : 要 copy 的数组的长度
示例: size 为 6, 我们调用 add(2,element)方法, 则会从 index=2+1=3 的位置开始, 将数组元素替换为从 index 起始位置为 index=2, 长度为 6-2=4 的数据.
异常处理:
- private void rangeCheckForAdd(int index) {
- if (index> size || index <0)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
set(int index,E element)方法
- public E set(int index, E element) {
- rangeCheck(index);
- E oldValue = elementData(index);
- elementData[index] = element;
- return oldValue;
- }
- E elementData(int index) {
- return (E) elementData[index];
- }
逻辑很简单, 覆盖旧值并返回.
indexOf(Object o)方法
根据 Object 对象获取数组中的索引值.
- public int indexOf(Object o) {
- if (o == null) {
- for (int i = 0; i < size; i++)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = 0; i < size; i++)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
- }
如果 o 为空, 则返回数组中第一个为空的索引; 不为空也类似.
注意: 通过源码可以看到, 该方法是允许传空值进来的.
get(int index)方法
返回指定下标处的元素的值.
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
rangeCheck(index)会检测 index 值是否合法, 如果合法则返回索引对应的值.
remove(int index)方法
删除指定下标的元素.
- public E remove(int index) {
- // 检测 index 是否合法
- rangeCheck(index);
- // 数据结构修改次数
- modCount++;
- E oldValue = elementData(index);
- // 记住这个算法
- 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
- return oldValue;
- }
这里又碰到了 System.arraycopy()方法, 详情请查阅上文.
大概思路: 将该元素后面的元素前移, 最后一个元素置空.
ArrayList 优缺点
优点:
因为其底层是数组, 所以修改和查询效率高.
可自动扩容(1.5 倍).
缺点:
插入和删除效率不高.
线程不安全.
手写 ArrayList
那面试手写 ArrayList 应该就不是问题了.
下面贴出我手写的一个简单阉割版的 ArrayList:
- public class MyArrayList {
- // 非私有, 以简化嵌套类访问
- // transient 在已经实现序列化的类中, 不允许某变量序列化
- transient Object[] elementData;
- // 默认容量
- private static final int DEFAULT_CAPACITY = 10;
- // 用于空实例的 空数组实例
- private static final Object[] EMPTY_ELEMENTDATA = {};
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- // 实际 ArrayList 集合大小
- private int size;
- /**
- * 构造方法
- */
- public MyArrayList(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 MyArrayList(){
- this(DEFAULT_CAPACITY);
- }
- public void add(Object o){
- //1\. 判断数据容量是否大于 elementData
- ensureExplicitCapacity(size+1);
- //2\. 使用下标进行赋值
- elementData[size++] = o;
- }
- private void ensureExplicitCapacity(int minCapacity){
- if (size == elementData.length){
- // 需要扩容, 扩容 1.5 倍(ArrayList 默认扩容 1.5 倍)
- // 注意: 如果 oldCapacity 值为 1
- int oldCapacity = elementData.length;
- int newCapacity = oldCapacity + (oldCapacity>> 1);
- // 如果新容量 <最小容量, 则将最小容量赋值给新容量
- // 如果 oldCapacity=1, 则 minCapacity=1+1=2 newCapacity=1+(1>>1)=1
- if (newCapacity - minCapacity <0){
- newCapacity = minCapacity;
- }
- // 创建新数组
- Object[] objects = new Object[newCapacity];
- // 将数据复制给新数组
- System.arraycopy(elementData, 0, objects, 0, elementData.length);
- // 修改引用
- elementData = objects;
- }
- }
- public Object get(int index) {
- rangeCheck(index);
- return elementData[index];
- }
- private void rangeCheck(int index) {
- if (index>= size)
- throw new IndexOutOfBoundsException("下标越界");
- }
- /**
- * 通过下标删除
- * @param index
- * @return
- */
- public Object remove(int index) {
- rangeCheck(index);
- // modCount++;
- // 先查出元素
- Object oldValue = elementData[index];
- // 找出置换结束位置
- int numMoved = size - index - 1;
- if (numMoved> 0)
- // 从 index+1 开始 将值覆盖为 index-numMoved 的值
- System.arraycopy(elementData, index+1, elementData, index, numMoved);
- elementData[--size] = null; // clear to let GC do its work
- return oldValue;
- }
- public boolean remove(Object o) {
- for (int index = 0; index < size; index++){
- if (o.equals(elementData[index])) {
- remove(index);
- return true;
- }
- }
- return false;
- }
- }
最后
大家觉得不错可以点个赞在关注下, 以后还会分享更多文章!
来源: http://www.jianshu.com/p/5c5ad555e509