Hello大家好,本章我们简单了解一下ArrayList 。有问题可以联系我mr_beany@163.com。另求各路大神指点,感谢
ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长; 由于ArrayList不是线程安全的,所以只能在单线程下使用;
由于ArrayList是基于数组实现的,所以它有着数组的特性,即能都给存储进来的元素自动进行编号(下角标)。所以我们可以很方便的通过每个元素的编号来获取该元素
数组的长度是不可变的,既然ArrayList是基于数组实现,为什么ArrayList可以添加,删除元素?
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable复制代码
ArrayList实现了Serializable接口,因此它支持序列化; 实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问; 实现了Cloneable接口,能被克隆。
/** * 序列版本号 */ private static final long serialVersionUID = 8683452581122892189L; /** * 默认的数组大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 定义空数组时使用,即当初始化数组大小为0的时候使用 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 初始化没有设定大小的时候使用。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 存储数据的数组 */ transient Object[] elementData; /** * ArrayList中实际数据的数量 */ private int size;复制代码
/** * 当我们使用无参的构造方法时,会创建一个长度为0的数组 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * ArrayList带容量大小的构造函数。 * 可以看到当initialCapacity==0 的时候使用的是EMPTY_ELEMENTDATA */ 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); } } /** * 使用集合构造的构造函数 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { //返回若不是Object[]则调用Arrays.copyOf方法将其转为Object[] if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } } 复制代码
这个方法就是把缩小elementData大小,去掉多余的数组空间 应用程序使用该操作降低ArrayList实例占用的存储 因为清空等一些操作只改变参数而没有释放空间 public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } 函数返回集合中给定元素的第一次出现的位置,如果没有就返回-1 首先检查o是否为null,如果为null,就返回集合中第一个null元素的位置;如果不为null,就是用equals函数进行相等性检查。 之所以这样,是因为如果直接对null调用equals方法,会抛出空指针异常。 同时也不能循环遍历数组中的元素调用equals方法检查是否相等,因为ArrayList集合中允许有null元素的存在。 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; } 判断集合中是否包含某个元素 public boolean contains(Object o) { return indexOf(o) >= 0; } 函数返回给定元素最后一次出现的位置,如果没有就返回-1: 原理和indexOf一样,不过对集合元素遍历的时候是倒序遍历的。 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; } 检查数组下标越界 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } 对于get方法来说,首先调用rangeCheck检查下标,然后调用elementData返回元素: public E get(int index) { rangeCheck(index); return elementData(index); } 设置给定位置的元素为给定的元素,然后返回原来的元素 同样,函数也先进行下标检查。 public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } 重点!!add方法 这也是之前提出的疑问的地方 public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } 接下来我们看ensureCapacityInternal() private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果初始化时没有设置默认容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //返回默认容量(10) 和 指定容量 中最大值 return Math.max(DEFAULT_CAPACITY, minCapacity); } 否则返回当前长度+1 return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; //定义于ArrayList的父类AbstractList,用于存储结构修改次数 //如果指定的最小容量要超过了容器本来的长度,则需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //扩容方法 private void grow(int minCapacity) { //原始容量 int oldCapacity = elementData.length; //新容量扩大到原容量的1.5倍,(其中>>是‘位运算符’)右移一位相关于原数值除以2。 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果计算出来的容量小了就将指定容量赋值给它 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //使用新的长度进行复制,返回复制后的数组 //这里我们可以看到所谓的动态数组其实是重新创建了一个数组,并不是改变了数组的容量 elementData = Arrays.copyOf(elementData, newCapacity); } //这里之所以设置长度为Integer.MAX_VALUE - 8 是避免一些机器内存溢出,减少出错几率 但是最大还是能支持到Integer.MAX_VALUE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 删除方法 public E remove(int index) { rangeCheck(index); modCount++; //将后面的列表对象前移 E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) // 数组前移一位,size自减,空出来的位置置null System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } 带有native标志的为java调用系统的C/C++代码,该函数实际上最终调用了C语言的memmove()函数,因此它可以保证同一个数组内元素的正确复制和移动,比一般的复制方法的实现效率要高很多,很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法,以取得更高的效率。 public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); 复制代码
ArrayList是由数组实现的,可以通过下标索引直接查找到指定位置的元素,因此 查找效率高 ;其可以添加元素的原理是每次添加都会重新创建对象,拷贝原数据,频繁的添加删除操作会消耗大量内存,所以ArrayList 适用的场景为查找元素