ArrayList
阅读目录
各种原因，前两年做C语言去了，现在重新做JAVA, 感觉自己基础很不扎实，要好好学习啦， 先从简单的开始~
以下内容基于jdk1.7.0_79源码；
什么是ArrayList
可以简单的认为是一个动态数组；实际上ArrayList就是用数组实现的，长度不够时，调用Arrays.copyOf方法，拷贝当前数组到一个新的长度更大的数组；
ArrayList特点
随机访问速度快，插入和移除性能较差(数组的特点)；
支持null元素；
有顺序；
元素可以重复；
线程不安全；
ArrayList继承的类和实现的接口
如下图，是与ArrayList相关的接口和类，下面将一一介绍各个接口和类中的方法；
PS:ArrayList中的方法主要是由Collection接口和List接口定义的；
Iterable接口
实现此接口以便支持foreach语法，如下代码，ArrayList可以直接使用foreach语句遍历元素：
View Code
Collection接口
int size()方法：
返回集合的大小，在ArrayList类中有一个int类型的size私有属性，当调用size方法时，直接返回该属性；
boolean isEmpty()方法：
判断集合是否为空，在ArrayList中，通过判断size == 0来判断集合是否为空；
boolean contains(Object o)方法：
判断集合是否含有对象o，在ArrayList中，通过判断indexOf(o) >= 0来判断是否含有o对象；
查看indexOf(o)方法，代码如下，主要功能是返回元素第一次出现时的下标索引，所以当下标索引大于等于0时，表示集合中存在该元素：
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;
}
注意这里的相等判断，调用的是o对象的equals方法，所以在调用contains方法时，要特别关注集合中对象的equals方法，是否有被重写过，如Integer、String的equals方法是被重写过的，一般我们自己定义的对象，如果没重写equals的话，默认调用的是Object的equals方法，举个例子，看一下就明白了：
package com.pichen.basis.col;
import java.util.ArrayList;
import java.util.List;
class Dog{
}
public class ContainsTest {
public static void main(String[] args) {
List<Dog> dogList = new ArrayList<Dog>();
Dog dog1 = new Dog();
Dog dog2 = new Dog();
dogList.add(dog1);
System.out.println(dogList.contains(dog2));//false
List<String> strList = new ArrayList<String>();
strList.add("teststr");
String str = new String("teststr");
System.out.println(strList.contains(str));//true
}
}
Iterator<E> iterator()方法：
返回一个迭代器对象，用于遍历集合，事实上，ArrayList类里有两个内部类ArrayList.Itr和ArrayList.ListItr，分别对应Iterator迭代器和ListIterator迭代器，后者比前者功能更加强大；从ArrayList.ListItr继承自ArrayList.Itr就可以看出来，ListIterator迭代器支持更多的操作，如判断前面还有没有元素，即hasPrevious()方法，等；
Object[] toArray()方法：
将集合ArrayList转换成Object数组,有时候需要用到数组的一些api时，可以使用该方法，注意返回的结果是Object类型的数组，如果想返回指定类型的数组，可以使用以下方法，<T> T[] toArray(T[] a);
<T> T[] toArray(T[] a)方法：
集合转数组，返回指定类型的数组，注意入参T[] a需要指定数组存储的空间，返回值为指定类型的数组；举个例子，假如有一个Integer类型的集合，如果想把它转换成Integer类型的数组，可以这样写：Integer[] arr = list.toArray(new Integer[list.size()]);
boolean add(E e)方法：
在集合最后面增加一个元素，在ArrayList中，其实现就是在其内部数组后面增加一个元素，不过要先保证内部数组长度足够，如下代码：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
boolean remove(Object o)方法：
在集合中移除对象o，在ArrayList中，其实现较add方法复杂，涉及空对象判断，equals比较，数组移动等，性能相对较差；
boolean containsAll(Collection<?> c)方法：
判断是否包含集合c中的所有元素，在ArrayList中，其实现方法是遍历集合c中的每一个元素，调用contains方法，判断集合是否包含该元素，只要有一个不包含就返回false，如下代码：
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
boolean addAll(Collection<? extends E> c)方法：
将集合c中的所有元素加到目标集合中去，在ArrayList中，其实现是先将集合c转换成数组，然后通过数组拷贝实现；
boolean removeAll(Collection<?> c)方法：
移除目标集合中含有‘集合c中元素’的所有元素，在ArrayList中，最终还是操作数组，性能相对较差；
boolean retainAll(Collection<?> c)方法：
移除目标集合中‘不包含集合c中元素’的所有元素，在ArrayList中removeAll方法和retainAll方法都是通过调用ArrayList的batchRemove方法来实现的，后续详细了解该方法的实现；
void clear()方法：
移除目标集合中的所有元素，在ArrayList中，就是将其内部数组所有元素赋null；
boolean equals(Object o)和int hashCode()方法
在ArrayLisy中，上面两个方法都被重写，equals方法依次取出集合中的所有元素进行比较，通过元素的equals方法，判断是否相等，全部相等返回true；
hashCode方法的计算是通过所有元素的hashCode计算得到；顺便说下hashcode，在java中随处可见，一般用在HashMap, Hashtable, HashSet等等中，可用于减少equals方法的调用，快速访问元素等，其实就是散列表的概念，如比较元素先比较其hashcode，如果hashcode不相等，那么这两个元素肯定不相等，也就不用调用其equals方法了；
demo代码:以上方法的简单使用
package com.pichen.basis.col;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < 10; i++){
list.add(i);
}
//直接打印
System.out.println(list.toString());
//size()
System.out.println(list.size());
//contains
System.out.println(list.contains(2));
//iterator
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
//toArray
Object[] objArr = list.toArray();
Integer[] intArr = list.toArray(new Integer[list.size()]);
System.out.println("\n" + list.toArray());
//add
list.add(5);
//remove
list.remove(5);
System.out.println(list);
//containsAll
System.out.println(list.containsAll(Arrays.asList(5,6)));
//addAll
list.addAll(Arrays.asList(555,666));
System.out.println(list);
//removeAll
list.removeAll(Arrays.asList(555,666));
System.out.println(list);
//clear
list.clear();
System.out.println(list);
}
}
List接口
除了Collection中定义的方法为，该接口增加了以下方法
boolean addAll(int index, Collection<? extends E> c);
在ArrayList中，该方法是在指定位置处增加一个集合中的所有元素，该操作涉及数组移动；
E get(int index);
返回下标为index的元素；
E set(int index, E element);
改变下标为index的元素的值
void add(int index, E element);
在下标为index的地方插入元素element，该操作涉及数组移动；
E remove(int index);
移除下标为index的元素，该操作涉及数组移动；
int indexOf(Object o);
返回元素o的最小下标，通过调用o的equals方法与集合中的元素进行比较；
int lastIndexOf(Object o);
返回元素o的最大下标，通过调用o的equals方法与集合中的元素进行比较；
ListIterator<E> listIterator();
返回listIterator迭代器，该迭代器支持向前操作；
ListIterator<E> listIterator(int index);
返回listIterator迭代器，从特定的位置开始，该迭代器支持向前操作；
List<E> subList(int fromIndex, int toIndex);
返回下标在fromIndex和toIndex之间的元素集合；
demo代码:以上方法的简单使用：
View Code
RandomAccess, Cloneable, java.io.Serializable接口
这三个接口是标识接口，里面都是空的；
RandomAccess标识其支持快速随机访问；
Cloneable标识其支持对象复制；
Serializable标识其可序列化；
AbstractCollection类
大部分方法前面已经说明过了，不过该类下的contains方法、toArray方法等，遍历的时候都是使用更加通用的迭代器方式进行遍历；
AbstractList类
大部分方法前面已经说明过了，不过该类中有两个私有内部类Itr和ListItr，对应的分别是两个迭代器；
ArrayList类
ArrayList的具体实现
成员属性：
private static final int DEFAULT_CAPACITY = 10;//初始容量
private static final Object[] EMPTY_ELEMENTDATA = {};//空ArrayList实例共享的一个空数组
private transient Object[] elementData; //真正存储ArrayList中的元素的数组；
private int size;//存储ArrayList的大小，注意不是elementData的长度；
除了其父接口定义的方法外，该类增加了以下方法
public ArrayList(int initialCapacity)：
构造函数，指定初始大小
public ArrayList()
构造函数，使用共享的EMPTY_ELEMENTDATA空数组
public ArrayList(Collection<? extends E> c)
构造函数，通过集合初始化ArrayList
public void trimToSize()
节省空间用的，ArrayList是通过数组实现的，大小不够时，增加数组长度，有可能出现数组长度大于ArrayList的size情况；
public void ensureCapacity(int minCapacity)
保证ArrayList能容纳minCapacity个元素；
私有方法
略
ArrayList内部数组扩容
查看ArrayList的add源码方法，如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
在往ArrayList增加e对象前，要先保证内部数组空间足够，即调用ensureCapacityInternal判断，查看其代码，如下：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
入参minCapacity为ArrayList要保证的最小空间大小，首先判断内部数组elementData是否是初始的空数组(当ArrayList是空实例的情况)，如果是的话，且minCapacity比DEFAULT_CAPACITY小，则设minCapacity为默认的初始容量大小DEFAULT_CAPACITY；接着调用ensureExplicitCapacity方法，查看其代码，如下：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
首先，是对修改次数modCount加一，这里的modCount给ArrayList的迭代器使用的，在并发操作被修改时，提供快速失败行为（保证modCount在迭代期间不变，否则抛出ConcurrentModificationException异常，可以查看源码859行），接着判断minCapacity是否大于当前ArrayList内部数组长度，大于的话调用grow方法对内部数组elementData扩容，grow方法代码如下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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:
elementData = Arrays.copyOf(elementData, newCapacity);
}
首先，获取内部数组elementData长度，并对它的大小增加1.5倍（oldCapacity + (oldCapacity >> 1)），赋给newCapacity，当newCapacity仍然比minCapacity（要保证的最小空间大小）小的时候，直接让newCapacity 等于minCapacity；然后再判断newCapacity 是不是大于MAX_ARRAY_SIZE，如果大于的话，调用hugeCapacity方法，处理大容量空间的情况，该方法判断是否溢出（抛出OutOfMemoryError），以及当minCapacity大于MAX_ARRAY_SIZE时，直接返回Integer.MAX_VALUE；最后就是真正地数组扩容了，调用Arrays.copyOf方法，拷贝旧的内部数组内容到一个新的（长度为newCapacity）的数组，并更改内部数组elementData的引用为新数组；
ArrayList遍历
一般工作中用的比较多的是遍历操作，ArrayList支持三种方式
- for循环下标遍历；
- 迭代器(Iterator和ListIterator)；
- foreach语句。
package com.pichen.basis.col;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class Test {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < 10; i++){
list.add(i);
}
//直接打印
System.out.println(list.toString());
//for循环
System.out.println("for循环：");
for(int i = 0; i < list.size(); i++){
System.out.print(list.get(i) + " ");
}
//foreach
System.out.println("\nforeach:");
for(Integer i : list){
System.out.print(i + " ");
}
//iterator
System.out.println("\niterator:");
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
//listIterator
System.out.println("\nlistIterator:");
ListIterator<Integer> listIterator = list.listIterator();
while(listIterator.hasNext()){
System.out.print(listIterator.next() + " ");
}
System.out.println();
while(listIterator.hasPrevious()){
System.out.print(listIterator.previous() + " ");
}
}
}
