一、数组和ArrayList的区别
既然提到ArrayList就不能不提一下数组,你知道什么时候用数组,什么时候用ArrayList么?他们有什么区别?
1.效率:当执行Add、AddRange、Insert、InsertRange等添加元素时,都会检查内部的数组的容量是否达到扩容的界限,如果达到,将会以当前容量大约1.5倍来创建一个新数组,然后将进行数据的Copy,并将引用指向新数组。这个临界点的扩容操作是比较消耗效率的。
2.扩容:相当与1,数组不能扩容,而ArrayList可以。
3.存储数据类型:Array 数组可以包含基本类型和对象类型,而ArrayList只能存储对象类型。
所以,如果数组长度不固定,使用ArrayList。
二、ArrayList源码:
ArrayList继承了AbstractList类,实现了List、RandomAccess、Cloneable、Serializable接口。
RandomAccess:是一种标记接口,随机访问任意下标元素。当要实现某些算法时,会判断当前类是否实现了RandomAccess接口会根据结果选择不同的算法。
public static int binarySearch(List extends Comparable super T>> list, T key) {if (list instanceof RandomAccess || list.size()
从源码中我们可以看到,在进行二分查找的时候,list会先判断是否是RandomAccess也即是否实现了RandomAccess接口,接着在调用想用的二分查找算法来进行,(其中: BINARYSEARCH_THRESHOLD Collections的一个常量(5000),它是二分查找的阀值。)如果实现了RandomAccess接口的List,执行indexedBinarySearch方法,否则执行 iteratorBinarySearch方法。
private static int indexedBinarySearch(List extends Comparable super T>> list, T key) {int low = 0;int high = list.size()-1;while (low <= high) {int mid = (low + high) >>> 1;Comparable super T> midVal = list.get(mid);int cmp = midVal.compareTo(key);if (cmp < 0)low = mid + 1;else if (cmp > 0)high = mid - 1;elsereturn mid; // key found}return -(low + 1); // key not found}
private static int iteratorBinarySearch(List extends Comparable super T>> list, T key){int low = 0;int high = list.size()-1;ListIterator extends Comparable super T>> i = list.listIterator();while (low <= high) {int mid = (low + high) >>> 1;Comparable super T> midVal = get(i, mid);int cmp = midVal.compareTo(key);if (cmp < 0)low = mid + 1;else if (cmp > 0)high = mid - 1;elsereturn mid; // key found}return -(low + 1); // key not found}
注:实现RandomAccess接口的的List可以通过简单的for循环来访问数据比使用iterator访问来的高效快速。并不是所有List实现RondomAccess接口都可以提高查询效率。JDK中说的很清楚,在对List特别是Huge size的List的遍历算法中,要尽量来判断是属于RandomAccess(如ArrayList)还是Sequence List (如LinkedList),因为适合RandomAccess List的遍历算法,用在Sequence List上就差别很大。
三、ArrayList成员变量
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable {// 序列化idprivate static final long serialVersionUID = 8683452581122892189L;// 默认初始的容量private static final int DEFAULT_CAPACITY = 10;// 一个空对象private static final Object[] EMPTY_ELEMENTDATA = {};// 一个空对象,如果使用默认构造函数创建,则默认对象内容默认是该值private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 当前数据对象存放地方,当前对象不参与序列化transient Object[] elementData;// 当前数组长度private int size;// 数组最大长度private static final int MAX_ARRAY_SIZE = 2147483639;// 省略方法。。}
1.当创建一个ArrayList对象时,内部的数组长度不为10,而是0.
2.数组elementData用了transient修饰,不参与序列化。
?:那么如何传输数据,为什么这个数组用transient修饰?
因为数组的容量并不是数组数据的长度。而是较大。ArrayList在序列化的时候会调用writeObject,直接将size和element写入ObjectOutputStream。
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.for (int i=0; i
只将有数据的数组进行序列化,减少冗余数据。
四、ArrayList
add(E e)public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}
将数组实际长度+1,并判断是不是新空数组,如果为空,则在10和size+1中取最大值。然后判断长度是否达到限定值。如果达到,则进行扩容。
contains()
public boolean contains(Object o) {return indexOf(o) >= 0;}
调用index方法对数组进行遍历,如果找到元素,返回true,否则返回空。
remove
根据索引remove
1.判断索引有没有越界
2.自增修改次数
3.将指定位置(index)上的元素保存到oldValue
4.将指定位置(index)上的元素都往前移动一位
5.将最后面的一个元素置空,好让垃圾回收器回收
6.将原来的值oldValue返回
clear方法
添加操作次数(modCount),将数组内的元素都置空,等待垃圾收集器收集,不减小数组容量。
public void clear() {modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}
trimToSize方法
1.修改次数加1
2.将elementData中空余的空间(包括null值)去除,例如:数组长度为10,其中只有前三个元素有值,其他为空,那么调用该方法之后,数组的长度变为3
iterator方法
interator方法返回的是一个内部类,由于内部类的创建默认含有外部的this指针,所以这个内部类可以调用到外部类的属性。
public Iterator iterator() {return new Itr();}
一般的话,调用完iterator之后,我们会使用iterator做遍历,这里使用next做遍历的时候有个需要注意的地方,就是调用next的时候,可能会引发ConcurrentModificationException,当修改次数,与期望的修改次数(调用iterator方法时候的修改次数)不一致的时候,会发生该异常,详细我们看一下代码实现:
@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}
expectedModCount这个值是在用户调用ArrayList的iterator方法时候确定的,但是在这之后用户add,或者remove了ArrayList的元素,那么modCount就会改变,那么这个值就会不相等,将会引发ConcurrentModificationException异常,这个是在多线程使用情况下,比较常见的一个异常。










