java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
本文主要介绍了 Java 中 ArrayList 类的源码解析,具有很好的参考价值。下面跟着小编一起来看下吧
前言:在前面我们提到数据结构的 线性表 。那么今天我们详细看下 Java 源码是如何实现线性表的,这一篇主要讲解顺序表 ArrayList 链式表下一篇在提及。
1:ArrayList 结构图
2:关于 Collection 和 List 的区别
最好的比对就是查看他们的源码我们先看 Collection 的所有接口
- public interface Collection < E > extends Iterable < E > {
- int size();
- boolean contains(Object o);
- Iterator < E > iterator();
- Object[] toArray(); < T > T[] toArray(T[] a);
- boolean add(E e);
- boolean remove(Object o);
- boolean containsAll(Collection < ?>c);
- boolean addAll(Collection < ?extends E > c);
- boolean retainAll(Collection < ?>c);
- void clear();
- boolean equals(Object o);
- int hashCode();
- }
在看 List 接口
- public interface List < E > extends Collection < E > {
- int size();
- boolean isEmpty();
- Iterator < E > iterator();
- Object[] toArray(); < T > T[] toArray(T[] a);
- boolean add(E e);
- boolean remove(Object o);
- boolean containsAll(Collection < ?>c);
- boolean addAll(Collection < ?extends E > c);
- boolean addAll(int index, Collection < ?extends E > c);
- boolean removeAll(Collection < ?>c);
- boolean retainAll(Collection < ?>c);
- void clear();
- boolean equals(Object o);
- int hashCode();
- E get(int index);
- E set(int index, E element);
- void add(int index, E element);
- E remove(int index);
- int indexOf(Object o);
- int lastIndexOf(Object o);
- ListIterator < E > listIterator();
- ListIterator < E > listIterator(int index);
- List < E > subList(int fromIndex, int toIndex);
- }
由于 List 是继承 Collection,所有具有 Collection 所有的功能,从 Collection 接口中我们也可以看出,Collection 不具有索引,不可以取元素的值,而 List 取可以,List 是具有索引的,这样一来在获取元素方面远远好于 Collection。
3:Iterable 接口
从 ArrayList 中我们可以看出,最顶端的接口就是 Iterable 这个接口,这个是一个迭代器,接口如下
- public interface Iterable < T > {
- Iterator < T > iterator();
- }
这个接口主要是返回一个对象,这个对象是 Iterator,那么我们在看看 Iterator 接口里面的方法
- public interface Iterator < E > {
- boolean hasNext();
- E next();
- void remove();
- }
那么我们主要看 ArrayList 是如何实现迭代器 Iterator 的。Iterator 的实现在 AbstractList 这个抽象类中的一个私有类 Itr 中。我们看看具体实现
- private class Itr implements Iterator < E > {
- int cursor = 0;
- int lastRet = -1;
- int expectedModCount = modCount;
- public boolean hasNext() {
- return cursor != size();
- }
cursor:记录即将调用索引的位置
lastRet:最后一个元素的索引
int expectedModCount = modCount; 目的是为了验证 modCount 后面会单独说下。
判断这个集合是否存在最后一个元素,通过 cursor != size();size 表示数组的长度,因为数组中元素索引从 0 开始,所以当最后一个索引等于数组长度的时候说明已经到数组的尾部了。
- public E next() {
- checkForComodification();
- try {
- E next = get(cursor);
- lastRet = cursor++;
- return next;
- } catch(IndexOutOfBoundsException e) {
- checkForComodification();
- throw new NoSuchElementException();
- }
- }
- final void checkForComodification() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- }
modCount:记录所有数组数据结构变动的次数,包括添加、删除、更改等,为了避免并发时候,当多个线程同时操作时候,某个线程修改了数组结构,而另一个线程恰恰读取这个数组,这样一来就会产生错误。所以在这段代码中加入了 modCount != expectedModCount,比如 A 线程对数据结构修改一次,那么 modCount 比如 + 1,而 expectedModCount 并没有发生变化,所以这样就会抛出异常。
- public void remove() {
- if (lastRet == -1)
- throw new IllegalStateException();
- checkForComodification();
- try {
- AbstractList.this.remove(lastRet);
- if (lastRet < cursor)
- cursor--;
- lastRet = -1;
- expectedModCount = modCount;
- } catch (IndexOutOfBoundsException e) {
- throw new ConcurrentModificationException();
- }
- }
我们刚刚说了 lastRet 记录的是最后一个元素,所以删除的时候直接按照索引删除即可,因为 modCount 会减一,所以重新对 expectedModCount 进行赋值,避免遍历时候产生错误。而且把 lastRed 在次赋初始值。
4:分析 ArrayList
刚刚目的是为了更加连接 ArrayList 做个铺垫,ArrayList 和我们以前数据结构中提到的顺序表一样,采用 Object[] 数组进行存储元素,用 size 来记录元素的元素的个数。
- /**
- * The array buffer into which the elements of the ArrayList are stored.
- * The capacity of the ArrayList is the length of this array buffer.
- */
- private transient Object[] elementData;
- /**
- * The size of the ArrayList (the number of elements it contains).
- *
- * @serial
- */
- private int size;
关于 transient,一旦变量被 transient 修饰,变量将不再是对象持久化的一部分,那么为啥采用 transient 修饰呢,由于 elementData 本身是一个缓存数组,通常会预留一些容量,当容量不够时然后进行扩充,比如现在 elementData 容量是 10,但是只有 5 个元素,数组中的最后五个元素是没有实际意义的,不需要储存,所以 ArrayList 的设计者将 elementData 设计为 transient,然后在 writeObject 方法中手动将其序列化,并且只序列化了实际存储的那些元素,而不是整个数组。我们看下 writeObject 方法
- private void writeObject(java.io.ObjectOutputStream s)
- throws java.io.IOException{
- // Write out element count, and any hidden stuff
- int expectedModCount = modCount;
- s.defaultWriteObject();
- // Write out array length
- s.writeInt(elementData.length);
- // Write out all elements in the proper order.
- for (int i=0; i<size; i++)
- s.writeObject(elementData[i]);
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
关于 ArrayList 的初始化。ArrayList 的设计者采用 3 种方式初始化。(默认数组容量是 10)
- public ArrayList(int initialCapacity) {
- super();
- if (initialCapacity < 0)
- throw new IllegalArgumentException("Illegal Capacity: "+
- initialCapacity);
- this.elementData = new Object[initialCapacity];
- }
- public ArrayList() {
- this(10);
- }
- 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);
- }
trimToSize 方法,这个方法可能我们好多人用的少,其实意义蛮大的,它主要把没用的容量去除掉,这样一来可以减少内存的开销
- public void trimToSize() {
- modCount++;
- int oldCapacity = elementData.length;
- if (size < oldCapacity) {
- elementData = Arrays.copyOf(elementData, size);
- }
ensureCapacity 方法,我们知道数组如果满了就会进行扩容,这个方法就是扩容的。
- public void ensureCapacity(int minCapacity) {
- modCount++;
- int oldCapacity = elementData.length;
- if (minCapacity > oldCapacity) {
- Object oldData[] = elementData;
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity)
- newCapacity = minCapacity;
- // minCapacity is usually close to size, so this is a win:
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
modCount 就是增加因子,记录操作数组结构的次数,首先和容量进行比对,如果不够了进行扩容。这是 Java1.6 版本的就是在原来的基础上扩容 1.5 倍。1.7 采用 >>1 也就是所有元素像右边移动一位然后加上原来的容量。其中
indexOf 方法,这个方法是获取元素索引。通过索引然后进行查询元素
- 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 是支持 null 的插入的。同样采用的是循环遍历来进行查找,时间复杂的为 n。
contains 方法,验证数组是否包含某元素,直接通过 indexOf 验证返回值即可
- public boolean contains(Object o) {
- return indexOf(o) >= 0;
- }
lastIndexOf 方法,和 indexOf 相对,indexOf 是从前往后,lastIndexOf 是从后面往前查找如下
- public int lastIndexOf(Object o) {
- if (o == null) {
- for (int i = size-1; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = size-1; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
- }
toArray 方法,就是把 List 转换成数组形式
- public Object[] toArray() {
- return Arrays.copyOf(elementData, size);
- }
get 和 set 方法,这个就很简单了大家看下就行
- public E get(int index) {
- RangeCheck(index);
- return (E) elementData[index];
- }
- public E set(int index, E element) {
- RangeCheck(index);
- E oldValue = (E) elementData[index];
- elementData[index] = element;
- return oldValue;
- }
RangeCheck 方法是进行验证的,查询的索引不可以超过数组的长度如下
- private void RangeCheck(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException(
- "Index: "+index+", Size: "+size);
- }
add(E e) 添加一个元素,这个采用尾插入,先验证容量,size+1 是加入 1 个元素后长度,看原来数组容量是否够。
- public boolean add(E e) {
- ensureCapacity(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
add(int index, E element) 按照索引进行插入,第一个还是一样进行扩容,然后把索引 index 后面的元素全部向后面移一位。System.arraycopy(elementData, index, elementData, index + 1,
size - index); 的意思就是将 elementData 的第 index 个元素移到第 index+1 个元素上,长度为 size-index。
- public void add(int index, E element) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException(
- "Index: "+index+", Size: "+size);
- ensureCapacity(size+1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
addAll(Collection<? extends E> c)
- public boolean addAll(Collection < ?extends E > c) {
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacity(size + numNew); // Increments modCount
- System.arraycopy(a, 0, elementData, size, numNew);
- size += numNew;
- return numNew != 0;
- }
首先把集合 c 转换成 a 数组,然后计算要进行添加的数组长度,其它的基本和添加元素一致。arraycopy(Object src, int srcPos,Object dest, int destPos,int length)
参数次数依次 源数组,源数组起始位置,目标数组,目标数组起始位置,复制数组元素数目。
addAll(int index, Collection<? extends E> c) 把数组插入到指定位置
- public boolean addAll(int index, Collection<? extends E> c) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException(
- "Index: " + index + ", Size: " + size);
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacity(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;
- }
首先判断是是否越界,然后和上面的基本一样,就是进行扩容判断,然后 index 后面的值进行后移包括 index,然后留下的空间插入集合 a。所以 2 次进行复制元素。
E remove(int index) 和 add 相对,删除这个元素然后把 index 后面的元素往前面移一位 size - index - 1 其中 - 1 是因为 index 这个元素会被删除,会少一位元素。
- public E remove(int index) {
- RangeCheck(index);
- modCount++;
- E oldValue = (E) elementData[index];
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // Let gc do its work
- return oldValue;
- }
remove(Object o) 这个就需要先进性验证然后找到这个元素的位置最后进行删除
- 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 void fastRemove(int index) {
- modCount++;
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // Let gc do its work
- }
clear 就是把所有的原素置空
- public void clear() {
- modCount++;
- // Let gc do its work
- for (int i = 0; i < size; i++)
- elementData[i] = null;
- size = 0;
- }
subList 方法,我们知道 ArrayList 是有这个方法,在 ArrayList 源码并不存在,因为是继承 AbstractList 而来的
- public List<E> subList(int fromIndex, int toIndex) {
- return (this instanceof RandomAccess ?
- new RandomAccessSubList<E>(this, fromIndex, toIndex) :
- new SubList<E>(this, fromIndex, toIndex));
- }
- class SubList<E> extends AbstractList<E> {
- private AbstractList<E> l;
- private int offset;
- private int size;
- private int expectedModCount;
- SubList(AbstractList<E> list, int fromIndex, int toIndex) {
- if (fromIndex < 0)
- throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
- if (toIndex > list.size())
- throw new IndexOutOfBoundsException("toIndex = " + toIndex);
- if (fromIndex > toIndex)
- throw new IllegalArgumentException("fromIndex(" + fromIndex +
- ") > toIndex(" + toIndex + ")");
- l = list;
- offset = fromIndex;
- size = toIndex - fromIndex;
- expectedModCount = l.modCount;
- }
从代码中我们可以看出这个一个基本内部类的实现,subList 只是去 List 中的一段数据。但是关于 subList 我们要注意几个事项。
第一:如果我们改变了 List 的数值,那么你获取的 subList 中的值也随之改变,原因如下
- public E get(int index) {
- rangeCheck(index);
- checkForComodification();
- return l.get(index + offset);
- }
因为获取的还是以前 List 中的数据。同样如果修改 subList 获取的数值,List 同样改变,
第二:如果改变了 List 结构,可能导致 subList 的不可用,因为这些修改已然基于原来的 list,他们共同用一个 list 数组。
- public void add(int index, E element) {
- if (index<0 || index>size)
- throw new IndexOutOfBoundsException();
- checkForComodification();
- l.add(index+offset, element);
- expectedModCount = l.modCount;
- size++;
- modCount++;
- }
5:关于 list 删除错误分析
list 在采用循环删除的时候会报 ConcurrentModificationException 异常,那么我们来看看具体原因,先看一段代码
- List < String > list = new ArrayList < String > ();
- list.add("a");
- list.add("b");
- list.add("c");
- list.add("d");
- list.add("e");
- for (String str: list) {
- list.remove(str);
- }
由于 foreach 遍历最终会 for (Iterator it=iterator;iterators.hasNext();) 模式那么所以获取元素的时候必然会用到迭代器中的 next 方法,next 方法我们前面说了会有 if(modCount!= expectedModCount)throw new ConcurrentModificationException() 验证。因为调用 remove(T x) 方法时候 modCount 会 + 1, 所以 2 次比较就会出现不一致。
正确写法如下
- Iterator iterator = list.iterator();
- while (iterator.hasNext()) {
- iterator.next();
- iterator.remove();
- }
为啥迭代器中 remove 就可以呢,是由于在 remove 代码中有 expectedModCount = modCount 这句代码。
6:ArrayList 是线程安全吗
线程不安全就是指多个线程同时操作造成脏读,错读情况,很明显 ArrayList 是非线程安全的,比如说 ArrayList 现在只有一个值后,如果 A,B2 个线程同时删除这个值,A 线程判断得到 size=1, 而此时时间片段到,CPU 调用 B 线程执行发现 size 也是 1,开始删除操作,然后 A 继续进行发现 ArrayList 已经空了就会报异常。或者添加等等。但是 Vector 是线程安全的,因为里面所有方法都加入了 synchronized,这样造成的结果就是所有线程执行 ArrayList 方法都必须等待,直到获取同步锁才可以继续进行,这样一来性能大大降低。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持 PHPERZ!
来源: http://www.phperz.com/article/17/1219/358042.html