ArrayList常用方法和实现原理
ArrayList常用方法
ArrayList常用的方法和Collection基本一样
1.add(“AA”);向集合中添加一个元素
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
}
2.add(2, “CC”);将指定的元素插入此列表中的指定位置。索引从0开始
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
list.add("BB");
list.add("DD");
System.out.println(list);
list.add(2, "CC");
System.out.println(list);
}
结果为：
[AA, BB, DD]
[AA, BB, CC, DD]
3.addAll(list2);将形参中的集合元素全部添加到当前集合中的尾部。
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
list.add("BB");
list.add("DD");
List<String> list2 = new ArrayList<String>();
list2.add("CC");
list2.add("EE");
list.addAll(list2);
System.out.println(list);
}
结果为：
[AA, BB, DD, CC, EE]
4.addAll(2, list2);将形参中集合元素添加到当前集合指定的位置。
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
list.add("BB");
list.add("DD");
List<String> list2 = new ArrayList<String>();
list2.add("CC");
list2.add("EE");
list.addAll(2, list2);
System.out.println(list);
}
结果为：
[AA, BB, CC, EE, DD]
5.clear();清空当前集合中所有元素
list.clear();
注意：以下方法和Collection一样，都依赖元素对象的equals方法。更多的时候都需要重写equals方法。
6.contains(“aa”);返回当前 元素是否包含某一个对象。当前放回false。
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
list.add("BB");
list.add("DD");
boolean contains = list.contains("aa");
System.out.println(contains);
}
7.get(1);获取当前集合中指定位置的元素，这里返回BB
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
list.add("BB");
list.add("DD");
String string = list.get(1);
System.out.println(string);
}
8.indexOf(“BB”);返回当前集合中首次出现形参对象的位置，如果集合中不存在就返回-1.
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("AA");
list.add("BB");
list.add("BB");
int indexOf = list.indexOf("BB");
System.out.println(indexOf);
}
简单的方法就查询JDK API文档吧，下面作简要的说明：
1.size();返回当前集合元素个数.
2.isEmpty();判断集合是否为空，返回布尔类型的结果。
3.lastIndexOf(Object o);返回集合中最后一次出现形参元素的索引，不存在就返回-1。
4.toArray();将集合转换为数组
5.set(int index,E element);用指定元素替代集合中指定位置的元素。
6.remove(Object o); 移除集合中首次出现的元素。
7.remove(int index);移除集合中指定位置的元素。
ArrayList实现原理
ArrayList是List接口的可变数组的实现，允许包括null在内的所有元素，既然是数组，那么该类肯定会存在改变存储列表的数组大小的方法。每一个ArrayList实例都有一个容量，该容量是用来存储列表元素的数组的大小，他总是等于列表的大小，随着往ArrayList中添加元素，这个容量也会相应的总动增长，自动增长就会带来数据向新数组的重新拷贝。
1.底层使用数组实现
private transient Object[] elementData;
关于关键字transient:
一个对象只要实现了Serilizable接口，这个对象就可以被序列化。
不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化
2.构造方法：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
其中
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
可以看出它的默认数组为长度为0。而在之前JDK1,6中，无参数构造器代码是初始长度为10。
JDK6代码这样的：
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {//可以指定初始大小
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
3.如何实现存储和扩容的？
3.1 使用set(int index, E element) ;方法，用指定的元素替代指定位置的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
3.2 add(E e);如何扩容的？
将指定的元素添加到集合尾部
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
代码中关于size含义的源码注释
The size of the ArrayList (the number of elements it contains). 意思就是目前ArrayList中实际包含的元素数量 不一定等于elementData的长度 一般小于等于elementData的长度 ,elementData长度会大于等于size
往下看就知道了
ArrayList中的size()方法返回的值就是size
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
ensureCapacityInternal方法名的英文大致是“确保内部容量”，size表示的是执行添加之前的实际元素个数，并非ArrayList的容量，容量是数组elementData的长度。ensureCapacityInternal该方法通过将现有的元素个数数组的容量比较。看如果需要扩容，则扩容。
下面具体看 ensureCapacityInternal(size + 1);
//如何判断和扩容的
private void ensureCapacityInternal(int minCapacity) {
//如果目前实际存储数组 是空数组，则最小需要容量为 默认容量(10)和0+1=1之间最大值,也就是10,其中DEFAULT_CAPACITY=10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//当第一次插入值时，由于minCapacity 一定大于等于10 而elementData.length是0 所以需要扩容
//如果不是第一次插入则是size+1
modCount++;
//如果数组（elementData)的长度小于最小需要的容量（minCapacity）就扩容,如果还够用则不扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/*
*增加容量，以确保它至少能容纳
*由最小容量参数指定的元素数。
* @param mincapacity所需的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//>>位运算，右移动一位。 整体相当于newCapacity =oldCapacity + 0.5 * oldCapacity 即旧elementData数组长度的1.5倍 jdk1.7采用位运算比以前的计算方式更快
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//jdk1.7这里增加了对元素个数的最大个数判断,jdk1.7以前是没有最大值判断的，MAX_ARRAY_SIZE 为int最大值减去8 最大的容量之所以设为Integer.MAX_VALUE - 8，在定义上方的注释中已经说了，大概是一些JVM实现时，会在数组的前面放一些额外的数据，再加上数组中的数据大小，有可能超过一次能申请的整块内存的大小上限，出现OutOfMemoryError。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 最重要的复制元素方法 把原来数组的数据复制到新的数组中。调用了Arrays的copyOf方法。内部是System的arraycopy方法，由于是native方法，所以效率较高。
elementData = Arrays.copyOf(elementData, newCapacity);
}
如果新的容量大于数组的最大值MAX_ARRAY_SIZE
这时，又会进入另一个方法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;
}
会对minCapacity 和 MAX_ARRAY_SIZE进行比较，minCapacity 大的话，就将Integer.MAX_VALUE 作为新数组的大小，否则将MAX_ARRAY_SIZE作为数组的大小。
通过分析可以发现，ArrayList的扩容会产生一个新的数组，将原来数组的值复制到新的数组中。会消耗一定的资源。所以我们初始化ArrayList时，最好可以估算一个初始的大小。 而且就算你之后往ArrayList中添加了超过数量的元素也不会报错，会自动扩容
经过打印输出，我们可以看到
向数组中添加第一个元素时，数组容量为10.
向数组中添加到第10个元素时，数组容量仍为10.
向数组中添加到第11个元素时，数组容量扩为15.
向数组中添加到第16个元素时，数组容量扩为22.
对比执行时间要使用控制变量法，先后执行所使用的时间会有不同。
如：
public class Test {
private static void test(int n) {
long start = System.currentTimeMillis();
List<Integer> list = new ArrayList<Integer>(n);
for (int i = 0; i < n; i++) {
list.add(i);
}
long end = System.currentTimeMillis();
System.out.println(end-start);
}
private static void test0(int n) {
long start = System.currentTimeMillis();
List<Integer> list2 = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
list2.add(i);
}
long end = System.currentTimeMillis();
System.out.println(end-start);
}
public static void main(String[] args) {
test(10000000);
test0(10000000);
}
}
输出 :
2412
3898
明显可以看出初始化长度比没有初始化长度节省时间。
3.3 add(int index, E element)将指定的元素插入此列表中的指定位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
// 如果数组长度不足，将进行扩容。
ensureCapacity(size+1); // Increments modCount!!
// 将 elementData中从Index位置开始、长度为size-index的元素，
// 拷贝到从下标为index+1位置开始的新的elementData数组中。
// 即 将当前位于该位置的元素以及所有后续元素右移一个位置。
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
System.arraycopy
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
参数注释
- @param src the source array. 源数组
- @param srcPos starting position in the source array. 源数组的位置
- @param dest the destination array.目标数组
- @param destPos starting position in the destination data.目标数组的位置
- @param length the number of array elements to be copied. 数量
4.如何读取元素？
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
5.删除元素
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;
}
注意：从集合中移除一个元素，如果这个元素不是最后一个元素，那么这个元素的后面元素会向向左移动一位。
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//将当前位于该位置的元素以及所有后续元素左移一个位置。
//将index后边的对象往前复制一位，并将数组中的最后一位元素设置为null 不置为null的话最后2个元素值是一模一样的
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work 让GC来回收
}
6.手动调整底层数组的容量为列表实际元素大小的方法
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
另外有个高频率出现的属性但是我们没有提过它就是modCount ,它是当前这个ArrayList被修改的次数
JDK注释
/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;
This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接：http://hogwartsrico.github.io/2015/04/08/About-ArrayList/