服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - Java中ArrayList类的源码解析

Java中ArrayList类的源码解析

2020-08-27 14:33朝向远方 Java教程

本文主要介绍了Java中ArrayList类的源码解析,具有很好的参考价值。下面跟着小编一起来看下吧

前言:在前面我们提到数据结构的线性表。那么今天我们详细看下Java源码是如何实现线性表的,这一篇主要讲解顺序表ArrayList链式表下一篇在提及。

1:ArrayList结构图

Java中ArrayList类的源码解析

2:关于Collection和List的区别

最好的比对就是查看他们的源码我们先看Collection的所有接口

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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接口

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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这个接口,这个是一个迭代器,接口如下

?
1
2
3
public interface Iterable<T> {
 Iterator<T> iterator();
}

这个接口主要是返回一个对象,这个对象是Iterator,那么我们在看看Iterator接口里面的方法

?
1
2
3
4
5
public interface Iterator<E> {
 boolean hasNext();
 E next();
 void remove();
}

那么我们主要看ArrayList是如何实现迭代器Iterator的。Iterator的实现在AbstractList这个抽象中的一个私有类Itr中。我们看看具体实现

?
1
2
3
4
5
6
7
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开始,所以当最后一个索引等于数组长度的时候说明已经到数组的尾部了。

?
1
2
3
4
5
6
7
8
9
10
11
public E next() {
  checkForComodification();
 try {
 E next = get(cursor);
 lastRet = cursor++;
 return next;
 } catch (IndexOutOfBoundsException e) {
 checkForComodification();
 throw new NoSuchElementException();
 }
 }
?
1
2
3
4
final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }

modCount:记录所有数组数据结构变动的次数,包括添加、删除、更改等,为了避免并发时候,当多个线程同时操作时候,某个线程修改了数组结构,而另一个线程恰恰读取这个数组,这样一来就会产生错误。所以在这段代码中加入了modCount != expectedModCount,比如A线程对数据结构修改一次,那么modCount比如+1,而expectedModCount并没有发生变化,所以这样就会抛出异常。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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来记录元素的元素的个数。

?
1
2
3
4
5
6
7
8
9
10
11
/**
 * 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方法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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方法,这个方法可能我们好多人用的少,其实意义蛮大的,它主要把没用的容量去除掉,这样一来可以减少内存的开销

?
1
2
3
4
5
6
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
 elementData = Arrays.copyOf(elementData, size);
}

ensureCapacity方法,我们知道数组如果满了就会进行扩容,这个方法就是扩容的。

?
1
2
3
4
5
6
7
8
9
10
11
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方法,这个方法是获取元素索引。通过索引然后进行查询元素

?
1
2
3
4
5
6
7
8
9
10
11
12
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验证返回值即可

?
1
2
3
public boolean contains(Object o) {
 return indexOf(o) >= 0;
 }

lastIndexOf方法,和indexOf相对,indexOf是从前往后,lastIndexOf是从后面往前查找如下

?
1
2
3
4
5
6
7
8
9
10
11
12
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转换成数组形式

?
1
2
3
public Object[] toArray() {
 return Arrays.copyOf(elementData, size);
 }

get和set方法,这个就很简单了大家看下就行

?
1
2
3
4
5
6
7
8
9
10
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方法是进行验证的,查询的索引不可以超过数组的长度如下

?
1
2
3
4
5
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}

add(E e)添加一个元素,这个采用尾插入,先验证容量,size+1是加入1个元素后长度,看原来数组容量是否够。

?
1
2
3
4
5
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。

?
1
2
3
4
5
6
7
8
9
10
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)

?
1
2
3
4
5
6
7
8
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)把数组插入到指定位置

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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这个元素会被删除,会少一位元素。

?
1
2
3
4
5
6
7
8
9
10
11
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)这个就需要先进性验证然后找到这个元素的位置最后进行删除

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
 }
?
1
2
3
4
5
6
7
8
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就是把所有的原素置空

?
1
2
3
4
5
6
7
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而来的

?
1
2
3
4
5
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
 new RandomAccessSubList<E>(this, fromIndex, toIndex) :
 new SubList<E>(this, fromIndex, toIndex));
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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中的值也随之改变,原因如下

?
1
2
3
4
5
public E get(int index) {
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}

因为获取的还是以前List中的数据。同样如果修改subList获取的数值,List同样改变,

第二:如果改变了List结构,可能导致subList的不可用,因为这些修改已然基于原来的list,他们共同用一个list数组。

?
1
2
3
4
5
6
7
8
9
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异常,那么我们来看看具体原因,先看一段代码

?
1
2
3
4
5
6
7
8
9
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次比较就会出现不一致。

正确写法如下

?
1
2
3
4
5
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方法都必须等待,直到获取同步锁才可以继续进行,这样一来性能大大降低。

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持服务器之家!

原文链接:http://www.cnblogs.com/LipeiNet/p/6523350.html

延伸 · 阅读

精彩推荐