阅读ArrayList源码的一些记录
ArrayList的底层是基于数组实现的，但是我们知道数组的长度一旦确定就不能够再次变化，ArrayList的长度是可以变化的，其实就是在需要扩容的时候，重新生成一个数组，并把原数组中的元素放到新的数组中，用新的数组替代就得数组，就完成了ArrayList的扩容。
本文是基于JDK1.8的源码，同时也会提到一些和JDK1.6的一些差别
一、构造方法
1、给定初始大小的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {// 如果大于0,就按照给定的大小来初始化数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 如果等于0,则初始化为一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {// 如果小于0,则直接抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
2、无参构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
此处的无参构造方法是初始化一个空的数组，相比于1.6来说，无参构造方法有一点变化，在1.6中，如果调用无参构造方法，会把elementData数组的长度初始化为10
3、以传入的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;
}
}
这个构造方法没什么说的，就是把传入的集合转化为数组，然后放到elementData中
下面按照增删改查依次说明
二、增
1、在数组尾部插入
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保长度够用，否则就扩容
elementData[size++] = e;// 在数组尾部添加元素
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//用无参构造方法生成对象的时候，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);// 取其中比较大的值
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 是否需要扩容，如果需要就调用grow方法
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;// 原来的容量
// 正常的扩容原则 原长度 + 原长度的一半（只取整数部分）（eg:1、原长度是10则正常扩容长度为10 + (10 >> 1)=15 2.原长度为11，则正常扩容以后的长度为11 + (11 >> 1) = 16）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果按照正常的扩容算法扩容后的长度还不能达到要求，则按照传进来的长度进行扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)// 这种情况一般不会发生，除非你往List中添加了很多很多数据
newCapacity = hugeCapacity(minCapacity);
// 把原来的数据放到新的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 如果小于0就表示溢出了
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
JDK1.6的扩容原则和这个有一定的差别，没有那么复杂，可以看一下1.6的扩容原则
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;// 原长度
if (minCapacity > oldCapacity) {// 是否需要扩容
Object oldData[] = elementData;
// 正常的扩容算法，原长度的3/2 + 1
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)// 不满足要求，则把传入的长度作为扩容后的长度
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
2、在指定位置插入
public void add(int index, E element) {
rangeCheckForAdd(index);// 检测index是否合法（0 < index < size）
ensureCapacityInternal(size + 1); // 是否要扩容
// 把index以及其后的元素往后移动，由此可以看出在特定位置插入数据的效率并不高
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
3、把一个集合的元素插入到数组的尾部
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();// 把集合转为数组
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 是否需要扩容
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
4、把一个集合插入到数组的特定位置
和插入一个元素的套路一样，此处只贴一下代码
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
三、删
1、按照索引删除
public E remove(int index) {
rangeCheck(index);// 检查index是否大于等于size，如果是会抛出异常
modCount++;
E oldValue = elementData(index);// 获取指定索引的上的值
int numMoved = size - index - 1;
if (numMoved > 0)
// 把index后面的元素前移，所以移除的效率不高
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
2、按照值来删除
如果有此值，删除成功返回true，否则返回false
// 此方法是从头开始循环查找，找到以后就删除并返回，后面相同的值不会被删除
public boolean remove(Object o) {
// 分是否为null两种情况，然后循环查找，如果找到就删除
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;
}
// 方法相比于remove(int)来说，减少了index的合法性判断，以及旧值的获取
private void fastRemove(int index) {
modCount++;
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
}
3、清空
// 循环把数组的每个元素都置为null
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
四、改
public E set(int index, E element) {
// 校验index的合法性
rangeCheck(index);
// 获取旧值，返回时用
E oldValue = elementData(index);
// 修改值
elementData[index] = element;
return oldValue;
}
五、查
public E get(int index) {
rangeCheck(index);// 校验index的合法性
return elementData(index);// 获取指定索引上的值
}
六、其他的一些方法
1、获取List的长度
因为ArrayList维护了一个size成员变量来表示其长度，直接获取size的长度即可
public int size() {
return size;
}
2、集合是否为空集合
长度为空就是空集合
public boolean isEmpty() {
return size == 0;
}
3、是否包含指定的元素
遍历去比较
public boolean contains(Object o) {
return 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;
}
七、ArrayList的遍历
以下都是个人的测试代码
三种遍历方式
public void testArrayList(){
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
// 第一种方法
for(int i = 0; i < list.size(); i ++){
System.out.println(list.get(i));
}
// 第二种
for(String str : list){
System.out.println(str);
}
// 第三种,迭代器
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
下面我们看一种情形，就是删除List中的所有与指定值相同的值
第一种（并不能达到我们预想的结果）
public void testFor(){
List<String> list = new ArrayList<>();
list.add("a");
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");
list.add("a");
list.add("a");
for(int i = 0; i < list.size(); i ++){
if("a".equals(list.get(i))){
list.remove(i);
}
}
// 经过删除以后，list中的元素为a,b,c,d,a显然没有达到我们要删除所有的a的目的
for(int i = 0; i < list.size(); i ++){
System.out.println(list.get(i));
}
}
第二种（迭代器方法 推荐使用）
public void testiter(){
List<String> list = new ArrayList<>();
list.add("a");
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");
list.add("a");
list.add("a");
Iterator<String> iterator2 = list.iterator();
while(iterator2.hasNext()){
String val = iterator2.next();
if("a".equals(val)){
iterator2.remove();
}
}
// 经过删除后 list 中的元素为b,c,d 得到了我们所期望的结果
for(int i = 0; i < list.size(); i ++){
System.out.println(list.get(i));
}
}
第三种方法
public void testFor2(){
List<String> list = new ArrayList<>();
list.add("a");
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");
list.add("a");
list.add("a");
for(int i = 0; i < list.size(); i ++){
if("a".equals(list.get(i))){
list.remove(i);
i --;
}
}
// 经过删除以后，list中的元素为b,c,d 同样达到了我们的要求，不过不建议用这种方法，推荐用迭代器去删除
for(int i = 0; i < list.size(); i ++){
System.out.println(list.get(i));
}
}
由于比较好奇foreach的实现就写了两个测试方法，代码如下
public void testForEach(){
List<String> list = new ArrayList<>();
for(String str : list){
System.out.println(str);
}
}
public void testIter(){
List<String> list = new ArrayList<>();
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
String s = iterator.next();
System.out.println(s);
}
}
通过idea反编译后生成的内容如下
public void testForEach() {
List<String> list = new ArrayList();
Iterator var2 = list.iterator();
while(var2.hasNext()) {
String str = (String)var2.next();
System.out.println(str);
}
}
public void testIter() {
List<String> list = new ArrayList();
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
String s = (String)iterator.next();
System.out.println(s);
}
}
然后顺带用javap去看了一下字节码文件，发现两个方法的字节码几乎是一样的，如下图
由此可见foreach是依赖于迭代器实现的。