一, ArrayList 的集合特点
问题 | 结 论 |
ArrayList 是否允许空 | 允许 |
ArrayList 是否允许重复数据 | 允许 |
ArrayList 是否有序 | 有序 |
ArrayList 是否线程安全 | 非线程安全 < br ztid="55" ow="0" oh="0"> |
二, ArrayList 的原理
ArrayList 底层是一个 Object[] elementData 数组, 能够实现动态扩容, 增减.
从源码看 ArrayList 实现了 RandomAccess, Cloneable,Serializable 接口, RandomAccess 用于快速存取提高循环的效率. Cloneable 该接口可以实现对象的克隆方法. Serializable 可以进行序列化, 序列化是将对象的状态信息转换为可以存储或传输的形式的过程.
三, 源码解析
1. 属性和构造方法
源码解析主要是从集合从增加元素, 删除元素, 查询元素, 以及修改元素这几个常用方法进行解析.
ArrayList 属性
- transient Object[] elementData;// 定义一个 elementData 数组
- private int size;//size 是数组大小实现数组增减 size 进行增减
ArrayList 无参构造方法
- /**
- * Constructs an empty list with an initial capacity of ten.
- */
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;// 将 elementData 进行初始化 elementData 也是个 Object[]类型. 空的 Object[]会给默认大小 10
- }
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
ArrayList 有参构造方法
- public ArrayList(int initialCapacity) {
- if (initialCapacity> 0) {
- this.elementData = new Object[initialCapacity];// 将自定义的容量大小当成初始化 elementData 的大小
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA;// 为 0 直接进行初始化
- } else {
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);// 判断如果自定义大小的容量小于 0, 则报下面这个非法数据异常
- }
- }
ArrayList(Collection<? extends E> c)构造方法
- // 就是将个 Collection 转换为 ArrayList
- 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;
- }
- }
2.add()方法
add 确保数组已使用长度(size), size+1 确保之后足够存下 下一个数据.
如果当前数组已使用长度 (size) 加 1 后的大于当前的数组长度, 则调用 grow 方法, 增长数组, grow 方法会将当前数组的长度变为原来容量的 1.5 倍.
当第一次添加元素的时候 this.size+1 的值是 1, 所以第一次添加的时候会将当前 elementData 数组的长度变为 10.
新增的数据有地方存储之后, 则将新元素添加到位于 size 的位置上.
返回添加成功布尔值.
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!! 确定内部容量是否够了
- elementData[size++] = e;// 赋值
- return true;
- }
从源码看 add 方法就是很正常的进行赋值的操作, 这里 ensureCapacityInternal 是数组的核心下面进行详细介绍.
- 1 private static int calculateCapacity(Object[] elementData, int minCapacity) {
- 2 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- 3 return Math.max(DEFAULT_CAPACITY, minCapacity);
- 4
- }
- 5 return minCapacity;
- 6
- }
- // 确保添加的元素有地方存储, 当第一次添加元素的时候 this.size+1 的值是 1, 所以第一次添加的时候会将当前 elementData 数组的长度变为 10:
数组扩容条件判断: 当前所需的数组最小长度与数组的长度对比, 如果大于 0, 则增长数组长度.
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- grow(minCapacity);
- }
数组扩容:
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length; // 将扩充前的 elementData 大小给 oldCapacity
- int newCapacity = oldCapacity + (oldCapacity>> 1);//newCapacity 就是 1.5 倍的 oldCapacity
- if (newCapacity - minCapacity <0)//elementData 就空数组的时候, length=0, 那么 oldCapacity=0,newCapacity=0 判断成立, 初始化 elementData 的大小了, 就是为 10.
- newCapacity = minCapacity;
- if (newCapacity - MAX_ARRAY_SIZE> 0)// 如果 newCapacity 超过了最大的容量限制, 就调用 hugeCapacity, 也就是将能给的最大值给 newCapacity
- newCapacity = hugeCapacity(minCapacity);
- // minCapacity is usually close to size, so this is a win:
- // 新的容量大小已经确定好了, 就 copy 数组, 改变容量大小咯.
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
hugeCapacity()用来赋最大值.
- // 这个就是上面用到的方法
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity <0) // overflow
- throw new OutOfMemoryError();
- // 如果 minCapacity 都大于 MAX_ARRAY_SIZE, 那么就 Integer.MAX_VALUE 返回, 反之将 MAX_ARRAY_SIZE 返回.
- //Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE:2147483639 也就是说最大也就能给到第一个数值. 还是超过了这个限制, 就要溢出了. 相当于 arraylist 给了两层防护.
- return (minCapacity> MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
3.void add(int,E); 在特定位置添加元素, 也就是插入元素
在制定位置赋值, 主要进行以下步骤, arryList 集合的核心是 arraycopy 这个, 这个后面具体介绍.
判断索引有没有越界
自增修改次数
将指定位置 (index) 上的元素保存到 oldValue
将指定位置 (index) 上的元素都往前移动一位
将最后面的一个元素置空, 好让垃圾回收器回收
将原来的值 oldValue 返回
- 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++;//size 增加 1
- }
4.remove(int): 通过删除指定位置上的元素
remove 执行的方法如下:
判断索引有没有越界
自增修改次数
将指定位置 (index) 上的元素保存到 oldValue
. 将指定位置 (index) 上的元素都往前移动一位
将最后面的一个元素置空
将原来的值 oldValue 返回
- public E remove(int index) {
- rangeCheck(index);// 检查
- modCount++;// 这个作用很多, 比如用来检测快速失败 (failfast) 的一种标志.
- E oldValue = elementData(index);// 通过索引直接找到该元素
- int numMoved = size - index - 1;// 计算要移动的位数.
- if (numMoved> 0)
- // 这个方法也已经解释过了, 就是用来移动元素的.
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- // 将 --size 上的位置赋值为 null, 让 gc 回收它.
- elementData[--size] = null; // clear to let GC do its work
- // 返回删除的元素.
- return oldValue;
- }
5.System.arrayCopy 这个是数组的扩容的核心 API
如图属性详解:
参数 | 说明 |
src | 原数组 |
srcPos | 原数组 |
dest | 目标数组 |
destPos | 目标数组的起始位置 |
length | 要复制的数组元素的数目 |
1 public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)// 这个是 native 方法
具体使用请查看这个案例:
- int data[] = new int[]{
- 1, 2, 3, 4
- };
- int bigdata[] = new int[6];
- System.arraycopy(data, 0, bigdata, 0, 4);
结果:{1,2,3,4,0,0}
如图所示:
四, 总结:
arrayList 可以存放 null.
arrayList 本质上就是一个 elementData 数组.
arrayList 中 removeAll(collection c)和 clear()的区别就是 removeAll 可以删除批量指定的元素, 而 clear 是删除集合中的全部元素.
arrayList 由于本质是数组, 所以它在数据的查询方面会很快, 而在插入删除这些方面, 性能下降很多.
arrayList 实现了 RandomAccess, 所以在遍历它的时候推荐使用 for 循环.
arrayList 的实质是 System.arraycopy 方法, arraycopy 其实是浅拷贝.
来源: https://www.cnblogs.com/hang-on/p/11491771.html