内容简介:Java集合干货——ArrayList源码分析
在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学 java 的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如:初始化的长度,扩容等。
本篇主要通过一些对源码的分析,讲解几个ArrayList常见的方法,以及和Vector的区别。
ArrayList
定义
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList实际上是一个动态数组,容量可以动态的增长,其继承了AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
RandomAccess接口,被List实现之后,为List提供了随机访问功能,也就是通过下标获取元素对象的功能。
实现了Cloneable, java.io.Serializable意味着可以被克隆和序列化。
初始化
在使用中我们经常需要new出来各种泛型的ArrayList,那么在初始化过程是怎样的呢?
如下一行代码,创建一个ArrayList对象
List<Person> list = new ArrayList<>();
我们来看源码,是如何初始化的,找到构造方法
//无参构造方法 public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; }
看到这些代码的时候,我也是不解的,elementData和EMPTY_ELEMENTDATA是什么啊?但是很明显EMPTY_ELEMENTDATA是一个常量,追本溯源我们去看一下成员属性。
//如果是无参构造方法创建对象的话,ArrayList的初始化长度为10,这是一个静态常量 private static final int DEFAULT_CAPACITY = 10; //在这里可以看到我们不解的EMPTY_ELEMENTDATA实际上是一个空的对象数组 private static final Object[] EMPTY_ELEMENTDATA = {}; //保存ArrayList数据的对象数组缓冲区 空的ArrayList的elementData = EMPTY_ELEMENTDATA 这就是为什么说ArrayList底层是数组实现的了。elementData的初始容量为10,大小会根据ArrayList容量的增长而动态的增长。 private transient Object[] elementData; //集合的长度 private int size;
执行完构造方法,如下图
可以说ArrayList的作者真的是很贴心,连缓存都处理好了,多次new出来的新对象,都执行同一个引用。
添加方法add
add(E e)
/** * Appends the specified element to the end of this list. */ //增加元素到集合的最后 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! //因为++运算符的特点 先使用后运算 这里实际上是 //elementData[size] = e //size+1 elementData[size++] = e; return true; }
先不管ensureCapacityInternal的话,这个方法就是将一个元素增加到数组的size++位置上。
再说回ensureCapacityInternal,它是用来扩容的,准确说是用来进行扩容检查的。下面我们来看一下整个扩容的过程
//初始长度是10,size默认值0,假定添加的是第一个元素,那么minCapacity=1 这是最小容量 如果小于这个容量就会报错 //如果底层数组就是默认数组,那么选一个大的值,就是10 private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //调用另一个方法ensureExplicitCapacity ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { //记录修改的次数 modCount++; // overflow-conscious code //如果传过来的值大于初始长度 执行grow方法(参数为传过来的值)扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //真正的扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //新的容量是在原有的容量基础上+50% 右移一位就是二分之一 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: //这里是重点 调用 工具 类Arrays的copyOf扩容 elementData = Arrays.copyOf(elementData, newCapacity); } //Arrays public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
add(int index, E element)
添加到指定的位置
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; //长度加1 size++; } //判断是否出现下标是否越界 private void rangeCheckForAdd(int index) { //如果下标超过了集合的尺寸 或者 小于0就是越界 if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
remove(int index)
ArrayList支持两种删除元素的方式
- remove(int index) 按照下标删除 常用
- remove(Object o) 按照元素删除 会删除和参数匹配的第一个元素
下面我们看一下ArrayList的实现
/** 移除list中指定位置的元素 * Removes the element at the specified position in this list. 所有后续元素左移 下标减1 * Shifts any subsequent elements to the left (subtracts one from their * indices). *参数是要移除元素的下标 * @param index the index of the element to be removed 返回值是被移除的元素 * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { //下标越界检查 rangeCheck(index); //修改次数统计 modCount++; //获取这个下标上的值 E oldValue = elementData(index); //计算出需要移动的元素个数 (因为需要将后续元素左移一位 此处计算出来的是后续元素的位数) int numMoved = size - index - 1; //如果这个值大于0 说明后续有元素需要左移 是0说明被移除的对象就是最后一位元素 if (numMoved > 0) //索引index只有的所有元素左移一位 覆盖掉index位置上的元素 System.arraycopy(elementData, index+1, elementData, index,numMoved); // 将最后一个元素赋值为null 这样就可以被gc回收了 elementData[--size] = null; // clear to let GC do its work //返回index位置上的元素 return oldValue; } //移除特定元素 public boolean remove(Object o) { //如果元素是null 遍历数组移除第一个null if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { //遍历找到第一个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 }
ArrayList总结
- 底层数组实现,使用默认构造方法初始化出来的容量是10
- 扩容的长度是在原长度基础上加二分之一
- 实现了RandomAccess接口,底层又是数组,get读取元素性能很好
- 线程不安全,所有的方法均不是同步方法也没有加锁,因此多线程下慎用
- 顺序添加很方便
- 删除和插入需要复制数组 性能很差(可以使用LinkindList)
为什么ArrayList的elementData是用transient修饰的?
transient修饰的属性意味着不会被序列化,也就是说在序列化ArrayList的时候,不序列化elementData。
为什么要这么做呢?
- elementData不总是满的,每次都序列化,会浪费时间和空间
- 重写了writeObject 保证序列化的时候虽然不序列化全部 但是有的元素都序列化
所以说不是不序列化 而是不全部序列化。
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out array length s.writeInt(elementData.length); // Write out all elements in the proper order. for (int i=0; i<size; i++) s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
ArrayList和Vector的区别
标准答案
- ArrayList是线程不安全的,Vector是线程安全的
- 扩容时候ArrayList扩0.5倍,Vector扩1倍
那么问题来了
ArrayList有没有办法线程安全?
Collections工具类有一个synchronizedList方法
可以把list变为线程安全的集合,但是意义不大,因为可以使用Vector
Vector为什么是线程安全的?
老实讲,抛开多线程 它俩区别没多大,但是多线程下就不一样了,那么Vector是如何实现线程安全的,我们来看几个关键方法
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return oldValue; }
就代码实现上来说,和ArrayList并没有很多逻辑上的区别,但是在Vector的关键方法都使用了synchronized修饰。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Java集合干货——CopyOnWriteArrayList源码分析
- 干货 | Java 读写锁 ReentrantReadWriteLock 源码分析
- 详尽干货!从源码角度看 Golang 的调度
- 干货 | 视频显著性目标检测(文末附有完整源码)
- 我入行以来java框架的几个阶段&论什么是真正的组件开发&项目中部分源码干货分享
- 前端面试题干货集合
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Elements of Programming
Alexander A. Stepanov、Paul McJones / Addison-Wesley Professional / 2009-6-19 / USD 39.99
Elements of Programming provides a different understanding of programming than is presented elsewhere. Its major premise is that practical programming, like other areas of science and engineering, mus......一起来看看 《Elements of Programming》 这本书的介绍吧!