文章目录
ArrayList
ArrayList概述
ArrayList底层是一个Object数组,而数组在内存是连续的空间,所以使用ArrayList存储的元素与添加时的顺序是一致的,每一个ArrayList都有一个容量大小,当添加的元素数量大于该数组的容量时,ArrayList会自动扩容。
ArrayList具体框架图
ArrayList继承于AbstractList,实现了RandomAccess，Cloneable,Serializable这些接口。
实现RandomAccess接口,意味着ArrayList支持随机方法,即可以像数组一样通过下标快速的访问某一元素。
实现了Cloneable接口,意味着可以被克隆
实现Serializable,意味着可以被序列化
属性
/** * 序列化ID */ private static final long serialVersionUID = 8683452581122892189L; /** * 默认初始化的容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 用于空实例的共享空数组实例。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 共享空数组实例用于默认大小的空实例。我们将它与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时要膨胀多少。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** *保存ArrayList元素的数组 */ transient Object[] elementData; /** * * * ArrayList中元素的个数 */ private int size;
通过查看源码可知,ArrayList有2个Object数组,那么这2两数组有啥区别呢?这个问题得继续往下看。
构造方法
无参构造方法
/** * 默认无参构造函数 *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0,也就是说明初始其实是空数组,当添加第一个元素的时候数组容量才变成10,当容量超过10时,会扩大1.5倍 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
当创建使用无参构造方法创建一个ArrayList对象时, elementData引用所指向的数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
带初始容量的构造方法
/** * 带初始容量参数的构造函数（使用者可以在创建ArrayList对象时自己指定集合的初始大小） */ public ArrayList(int initialCapacity) { //初始的大小大于0则分配一个该大小的数组 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //初始的大小为0,分配一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else { //小于0抛出异常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
当创建使用带初始容量参构造方法创建一个ArrayList对象时,如果初始的容量initialCapacity大于0则分配一个相应大小的数组，如果初始的容量initialCapacity等于0则
elementData引用指向EMPTY_ELEMENTDATA,如果小于0则抛出异常。
带集合参数的构造方法
/** * 利用其他 Collection 构建 ArrayList */ public ArrayList(Collection<? extends E> c) { //将集合转换成数组 elementData = c.toArray(); //如果elementData数组的长度不为0 if ((size = elementData.length) != 0) { //如果elementData是不是Object类型 if (elementData.getClass() != Object[].class) //将原来不是Object类型的数组赋值给新的Object数组 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { //如果elementData数组的长度为0,直接给个空数组 this.elementData = EMPTY_ELEMENTDATA; } }
上述代码,首先将传入的集合转换成数组并赋值给 elementData,再将elementData的长度赋值为size，然后判断是否为0,如果不为0,则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。如果为0则将EMPTY_ELEMENTDAT赋值给elementData。
扩容机制
通过上述无参构造方法创建的ArrayList对象,该数组分配的是一个空数组,所以容量大小为0,当添加元素或者数组满了的时候会触发扩容机制。接下来就先看看add()方法。
public boolean add(E e) { ensureCapacityInternal(size + 1); //添加第一个元素时size为0 elementData[size++] = e; return true; }
向ArrayList添加一个元素
package com.kc.demo; import java.util.ArrayList; public class Demo2 { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add("叶秋涵"); } }
根据add方法在添加元素之前,会对容量进行判断已经满了,如果满了自然要扩容,下面就来看看ensureCapacityInternal()方法。
private void ensureCapacityInternal(int minCapacity) {//添加第一个元素时minCapacity为1 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
ensureCapacityInternal方法参数minCapacit的含义为所需最小的容量,ensureCapacityInternal的方法体中又调用了calculateCapacity()方法。
private static int calculateCapacity(Object[] elementData, int minCapacity) {//minCapacity为1 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY为10 } return minCapacity; }
ensureExplicitCapacity()方法会判断当前数组的引用是否为空数组,如果是就返回DEFAULT_CAPACITY(默认容量为10)以及minCapacity的最大值。否则返回minCapacity。
然后ensureExplicitCapacity()方法根据返回的最小容量与数组长度进行扩容
private void ensureExplicitCapacity(int minCapacity) {//minCapacity为10 modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0)//10>0 grow(minCapacity); }
如果最小的容量大于数组长度时就需要调用grow()方法进行扩容
private void grow(int minCapacity) {//minCapacity 为10 // overflow-conscious code int oldCapacity = elementData.length;//0 int newCapacity = oldCapacity + (oldCapacity >> 1);//原数组的1.5倍-->0 if (newCapacity - minCapacity < 0)//0<10 newCapacity = minCapacity;// newCapacity = 10 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); }
grow()方法会先计算出原数组大小的1.5倍,如果扩容后的长度比最小容量小,则newCapacity为最小容量,如果newCapacity比整数的最大值还要大,就会调用hugeCapacity()方法进行调整。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
hugeCapacity()方法会对minCapacity进行判断,如果它小于0则抛出异常。最终的newCapacity取决于minCapacity和MAX_ARRAY_SIZE,如果前者大于后者则返回
Integer.MAX_VALUE,否则返回ArrayList定义的数组最大的容量。
ArrayList有2个Object数组的区别?
看完构造方法、添加方法、扩容方法之后，new ArrayList(),elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,new ArrayList(0),会将 EMPTY_ELEMENTDATA赋值给elementData,当EMPTY_ELEMENTDATA扩容时,传入的参数是多少就是多少,而DEFAULTCAPACITY_EMPTY_ELEMENTDATA初次扩容之后的容量为10。
常用方法
在指定位置插入元素
/** * 先将原来该位置的元素以及后面的元素整体往后移动,再把这个位置的元素插入 */ 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++; }
将指定集合元素追加到ArrayList末尾
/** *将指定集合元素追加到ArrayList末尾 */ public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }
删除 index 位置元素
/** * 删除指定位置的元素,返回值为已删除的元素 * */ public E remove(int 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; }
删除遇到的第一个元素
/** *删除从某个元素,删除成功返回true,否则返回false。 */ 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; }
获取下标 index 位置元素
public E get(int index) { rangeCheck(index); return elementData(index); }
将下标 index 位置元素设置为 element
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
清空
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
判断元素是否在ArrayList中
/** * 判断集合是否包含指定的元素,有则返回true */ public boolean contains(Object o) { //调用indexOf()方法进行寻找,该方法会从集合头一直到尾去寻找指定的元素,找到就返回首次出现的索引,没有找到就返回-1 return indexOf(o) >= 0; }
返回第一个元素所在下标
/** * 从列表头到开始寻找指定的元素,找到了就返回首次出现该元素的索引,没有则返回-1 */ 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; }
返回最后一个元素的下标
/** * 从列表尾到头开始寻找指定的元素,找到了就返回首次出现该元素的索引,没有则返回-1 */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
总结
- ArrayList底层的数据结构是数组
- ArrayList可以自动扩容，不传初始容量或者初始容量是0，都会初始化一个空数组，但是如果添加元素，会自动进行扩容。
- ArrayList是线程不安全的,在单线程可以使用,多线程环境下可以使用CopyOnWriteArrayList
各位看官如果觉得文章写得不错，点赞评论关注走一波！谢谢啦！
