带着十四个问题学 ArrayList源码

ArrayList源码解析

1.问题一：名称由来(Collection)

2.问题二:ArrayList底层实现是靠什么?

3.问题三:ArrayList的默认长度是多少？

4.问题四:ArrayList之add如何实现？

5.问题五:ArrayList的扩容机制[1.5倍数扩容]

6.问题六:为什么它要右移？

7.问题七:能add（null）吗？

8.问题八:ArrayList之remove【值】?

9.问题九：ArrayList之remove【索引】？

10.问题十:subList的用法细节注意【视图的作用】?

11.问题十一:怎么遍历ArrayList？

12.问题十二:遍历细节？

13.问题十三:for与Iterator 试一下把“1”换成“2”？

14.问题十四:if (“1”.equals(item)) 为什么不报错？

1.问题一：我是谁?

如图所示:

2.问题二:ArrayList底层实现是靠什么?

transient Object[] elementData; // non-private to simplify nested class access
//ArrayList 的元素存储在其中的数组缓冲区。//结论:ArrayList是由Object的数组存储的元素

3.问题三:ArrayList的默认长度是多少？

/*** Constructs an empty list with an initial capacity of ten.* 构造一个初始容量为 10 的空列表。*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//ArrayList利用无参的构造器定义了默认大小为 10 
//注意:执行完无参构造器后并没有分配空间 
//在添加元素时才开始分配空间

4.问题四:ArrayList之add如何实现？

    /*** Appends the specified element to the end of this list.* 将指定的元素追加到此列表的末尾。*/public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;  //这里可以看出 ---> 尾部添加return true;}
//注意:add采用尾插法//DEFAULTCAPACITY_EMPTY_ELEMENTDATA ---> 问题二的疑问,在初始化时不分配空间,在添加元素时才分配空间private void ensureCapacityInternal(int minCapacity) {   //minCapacity 所需的最小容量if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断是否创建的空数组minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }ensureExplicitCapacity(minCapacity); //这个方法判断是否扩容,以及涉及到一个修改次数的问题}/*** Default initial capacity.* 默认初始容量。*/private static final int DEFAULT_CAPACITY = 10;
//-----------ensureExplicitCapacity---------------private void ensureExplicitCapacity(int minCapacity) {modCount++;                               // 利用 "modCount" 参数可以做线程安全问题 //Arraylist线程不安全,但是效率高.[效率高的原因:未作线程安全的问题]// overflow-conscious codeif (minCapacity - elementData.length > 0)   //判断是否扩容grow(minCapacity);                     //扩容机制 [问题四：ArrayList的扩容机制[1.5倍数扩容]]}

5.问题五:ArrayList的扩容机制[1.5倍数扩容]

    /*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.* 增加容量以确保它至少可以容纳* 由最小容量参数指定的元素数。** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;        		//获取原ArrayList长度int newCapacity = oldCapacity + (oldCapacity >> 1);  // 原ArrayList长度+原ArrayList长度 右移 一位  [为什么不用 乘 1.5:问题五：为什么它要右移？]if (newCapacity - minCapacity < 0)                   //如果新的长度[newCapacity]小于所需的最小容量 则使用最小长度newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新的长度[newCapacity]大于数组最大长度[MAX_ARRAY_SIZE] 这个最大长度为Integer的最大长度-8 //防止无线扩容  为什么选这个是 涉及到java虚拟机的问题// @Native public static final int   MAX_VALUE = 0x7fffffff; // 2的31次方-1.newCapacity = hugeCapacity(minCapacity);  // hugeCapacity 最大长度溢出导致长度为负数,则抛异常 // 超过 MAX_ARRAY_SIZE 则使用 Integer.MAX_VALUE // minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}/***要分配的数组的最大大小。一些 VM 在数组中保留一些头字。尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超出 VM 限制*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//-----------------hugeCapacity------------------private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

6.问题六:为什么它要右移？

计算机的运算中只有1和0,底层实现的乘、除、减法实际上都是用补码加法和位移实现的，故采用位移可以提高效率。

具体实现在计《算机组成原理》唐朔飞 第六章 计算机的运算方法

7.问题七:能add（null）吗？

//回到问题一：ArrayList底层实现是靠什么?
transient Object[] elementData; // non-private to simplify nested class access
//Object 类似的数据当容可以存空值//多个null，删除哪一个？ 【问题七：问题三:ArrayList之remove【值】】

8.问题八:ArrayList之remove【值】?

//按值删除，返回是否成功 
public boolean remove(Object o) {if (o == null) {                // equals有空指针异常 所以采用了if elsefor (int index = 0; index < size; index++)if (elementData[index] == null) {     //问题：多个null，删除哪一个？  显然是索引位置在前面的先删除fastRemove(index);     //快速删除，减少了边界检测的额比较提高效率//数组删除要移动元素，而移动元素伴随着效率问题，所以有了链表。return true;}} else { 										for (int index = 0; index < size; index++)  // equals有空指针异常 所以采用了if elseif (o.equals(elementData[index])) {     //逐个遍历fastRemove(index);          return true;}}return false;
}
//-----------fastRemove------------------------/** 跳过边界检查并且不返回移除的值的私有移除方法。*/
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
}//-----------arraycopy-------------------
//src 原数组
//srcPos 原数组开始位置
//dest 目标数组
//destPos 目标数组开始位置
//length  复制长度
public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

9.问题九：ArrayList之remove【索引】

//返回被删除的值
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 workreturn oldValue;
}//---------rangeCheck----------
private void rangeCheck(int index) {if (index >= size)  //简单的比较 index是否大于size 判断是否越界throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

10.问题十:subList的用法细节注意【视图的作用】?

【强制】 ArrayList的subList结果不可强转成ArrayList，否则会抛出 ClassCastException 异常， 即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList。

说明： subList 返回的是 ArrayList 的内部类 SubList，并不是 ArrayList 而是 ArrayList的一个视图，对于 SubList 子列表的所有操作最终会反映到原列表上。

——————————源自《阿里巴巴代码开发手册1.4.0》

private class SubList extends AbstractList<E> implements RandomAccess // 是ArrayList的一个视图//------如：SubList set()-------------    
public E set(int index, E e) {rangeCheck(index);checkForComodification();E oldValue = ArrayList.this.elementData(offset + index);//对于 SubList 子列表的所有操作最终会反映到原列表上。 映射到了原表的数据上ArrayList.this.elementData[offset + index] = e;return oldValue;
}

11.问题十一:怎么遍历ArrayList？

// 1. foreach [增强for 底层是迭代器]
// 2. for
// 3. 迭代器【Collection集合实现了Iterable】

12.问题十二:遍历细节？

【强制】不要在 foreach 循环里进行元素的 remove/add 操作。 remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

正例：
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {String item = iterator.next();if (删除元素的条件) {iterator.remove();}
}反例：
for (String item : list) {if ("1".equals(item)) {list.remove(item);}
}——————————源自《阿里巴巴代码开发手册1.4.0》
*/

说明： 以上代码的执行结果肯定会出乎大家的意料，那么试一下把“1”换成“2”，会是同样的 结果吗？

13.问题十三:for与Iterator 试一下把“1”换成“2”？

//for 中remove 的异常 
Exception in thread "main" java.util.ConcurrentModificationExceptionat java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)at java.util.ArrayList$Itr.next(ArrayList.java:851)at list.ArrayListSource.main(ArrayListSource.java:37)

原因：

list.remove(item)和iterator.remove() 的区别

//增强for的底层使用的还是迭代器
public Iterator<E> iterator() {return new Itr();
}
private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;//expectedModCount 保证多线程下数据一致的参数
}//list.remove(item)
//------remove---------
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;
}
//----------fastRemove--------------
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
}
// 没有修改 expectedModCount
//-------checkForComodification--------------
final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

//iterator.remove()
public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;       // 重点  修改 expectedModCount} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}
}

14.问题十四:if (“1”.equals(item)) 为什么不报错？

//上面说了增强for的本质---》迭代器
//当集合中只有两个元素的时候 cursor指向当前位置==1【0位置的元素被删除了】size 在删除 if ("1".equals(item)) 的时候修改成 1 
//所以 cursor==size //当三个元素的时候就会报  【ConcurrentModificationException】
public boolean hasNext() {return cursor != size;
}OfBoundsException ex) {throw new ConcurrentModificationException();}
}

14.问题十四:if (“1”.equals(item)) 为什么不报错？

//上面说了增强for的本质---》迭代器
//当集合中只有两个元素的时候 cursor指向当前位置==1【0位置的元素被删除了】size 在删除 if ("1".equals(item)) 的时候修改成 1 
//所以 cursor==size //当三个元素的时候就会报  【ConcurrentModificationException】
public boolean hasNext() {return cursor != size;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！