Java容器_List源码分析(5)

ArrayList

ArrayList 实现了 List 接口,并继承了 AbstractList 抽象类,List 接口和 AbstractList 抽象类提供了添加、删除、修改、遍历等操作,AbstractList 实现了 List 接口大部分通用的操作

实现了 Cloneable 标记接口,并重写了 Object 类的 clone 方法,所以支持浅拷贝

实现了 Serializable 标记接口,所以支持序列化,并且在类中也定义了序列化和反序列化的方法

实现了 RandmoAccess 标记接口,所以可以通过索引快速访问元素,并且效率要比迭代器高

1
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

ArrayList 底层是数组,所以 size、isEmpty、get、set、iterator、listIterator 方法的时间复杂度为 O(1),而 add、remove 方法的复杂度为 O(n),允许包含 null 元素

提供有 ensureCapacity 方法,在添加元素前调用来对数组进行扩容,避免多次默认的 size+1 的扩容

重要的属性如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
//默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//指定容量为0返回该空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//调用无参构造方法返回该空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存添加的元素,容量就是该数组的长度
//修饰为transient,自定义的序列化和反序列化方法见writeObject和readObject
transient Object[] elementData;
//包含元素的个数
private int size;

三个重载的构造方法创建的都是空的数组,但是在第一次添加元素时,扩容的方式不同

 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
//无参构造方法创建默认空数组,当添加第一个元素时会自动扩容到DEFAULT_CAPACITY的10
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//指定容量创建实例,创建的也是空数组,但是区别于默认空数组
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    //如果指定的容量为负数则抛出异常
    throw new IllegalArgumentException(
      "Illegal Capacity: "+ initialCapacity);
  }
}
//根据传入的同泛型Collection元素创建实例,元素顺序为迭代器返回的顺序
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

add 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
//在数组最后添加元素
public boolean add(E e) {
  //确认数组容量,如果不够则容量+1,会修改modCount
  ensureCapacityInternal(size + 1); // Increments modCount!!
  elementData[size++] = e;
  return true;
}
//在指定索引处添加元素
public void add(int index, E element) {
  //越界检查,超出索引范围抛出异常IndexOutOfBoundsException
  //add方法还要检查index是否位负数,如果不检查要到System.arraycopy才会抛出异常
  //如果为负数则直接抛出异常,不再执行ensureCapacityInternal
  rangeCheckForAdd(index);
  //确认数组容量,如果不够则容量+1,会修改modCount
  ensureCapacityInternal(size + 1); // Increments modCount!!
  //通过复制将index后的元素后移一位,将要插入的index位置空出来
  System.arraycopy(
    elementData, index, elementData, index + 1, size - index);
  elementData[index] = element;
  size++;
}

扩容方法

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//对外提供的,在添加元素前,传入需要容量来对数组进行扩容,减少扩容次数,add方法每次只会+1
public void ensureCapacity(int minCapacity) {
  //创建默认空数组后,添加第一个元素时,扩容到DEFAULT_CAPACITY默认的10
  //如果创建实例时指定了初始容量,则最小扩容量为0
  int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    ? 0 : DEFAULT_CAPACITY;
  if (minCapacity > minExpand) {
    ensureExplicitCapacity(minCapacity);
  }
}
//内部的,在添加元素前,传入需要容量来对数组进行扩容,add方法传入的需要的容量是size+1
private void ensureCapacityInternal(int minCapacity) {
  //只有默认空数组第一次添加元素calculateCapacity返回10,其他都是传入的size+1
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算数组需要的最小容量,主要是针对创建的默认空数组,超过了10则使用传入的需要容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  //在默认空数组添加第一个元素时,扩容到DEFAULT_CAPACITY默认的10
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}
//上面的方法是得出需要的最小容量,传入该方法来判断并执行扩容
private void ensureExplicitCapacity(int minCapacity) {
  modCount++; 
  //如果需要的容量超出了数组长度,则进行扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
//扩容方法
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  //先扩容50%
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  //判断扩容后容量够不够,如果不够则扩容到需要的容量
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  //判断有没超过最大限制,如果超过了就进行大容量分配
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  //复制旧数组到新数组,所以建议通过构造方法指定合适的容量提高效率
  elementData = Arrays.copyOf(elementData, newCapacity);
}
//最大容量方法
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0)
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
//最大容量,减8是防止大于JVM的limit,进而导致OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

remove 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public E remove(int index) {
  //越界检查
  rangeCheck(index);
  modCount++; //会修改modCount
  E oldValue = elementData(index);
	//计算需要移动的元素个数
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //为了让GC起作用,必须显式的为最后一个位置赋为null
  elementData[--size] = null; // clear to let GC do its work
  return oldValue;
}

克隆方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//实现的是浅拷贝
public Object clone() {
  try {
    ArrayList<?> v = (ArrayList<?>) super.clone();
    //最终调用System.arraycopy()方法
    v.elementData = Arrays.copyOf(elementData, size);
    v.modCount = 0;
    return v;
  } catch (CloneNotSupportedException e) {
    // this shouldn't happen, since we are Cloneable
    throw new InternalError(e);
  }
}

序列化方法

 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
27
28
29
30
31
32
//将ArrayList的容量、所有的元素值写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
  throws java.io.IOException{
  int expectedModCount = modCount;
  s.defaultWriteObject();
  //写入size
  s.writeInt(size);
  for (int i=0; i<size; i++) {
    s.writeObject(elementData[i]);
  }
  if (modCount != expectedModCount) {
    throw new ConcurrentModificationException();
  }
}
//elementData的容量比实际的size大,只需要对elementData中有元素的部分进行序列化
//先将ArrayList的容量读出,然后再将所有的元素值读出
private void readObject(java.io.ObjectInputStream s)
  throws java.io.IOException, ClassNotFoundException {
  elementData = EMPTY_ELEMENTDATA;
  s.defaultReadObject();
  //读取size
  s.readInt();
  if (size > 0) {
    int capacity = calculateCapacity(elementData, size);
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
    ensureCapacityInternal(size);
    Object[] a = elementData;
    for (int i=0; i<size; i++) {
      a[i] = s.readObject();
    }
  }
}

Iterator 的 fail-fast

Iterator 的 fail-fast 是 Collection 和 Map 的一种错误机制,在遍历一个集合对象时,如果集合结构被修改,则很有可能会触发 fail-fast,抛出 ConcurrentModificationException 异常,可通过迭代器提供的方法在遍历时进行修改

在 ArrayList 的父类 AbstractList 中查看 Iterator 的源码

 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
27
28
29
30
31
32
33
34
35
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  //记录List修改次数,每执行一次修改(添加、删除等)操作,则modCount+1
  protected transient int modCount = 0;
  //返回Iterator接口的实现类Itr的实例
  public Iterator<E> iterator() {
    return new Itr();
  }
  private class Itr implements Iterator<E> {
    //每次新建Itr对象都会保存新建该对象时对应的modCount
    int expectedModCount = modCount;
    public E next() {
      //获取下一个元素前都会判断expectedModCount和当前modCount是否相等
      //若不相等,则抛出ConcurrentModificationException异常,产生fail-fast事件
      checkForComodification();
      //...
    }
    final void checkForComodification() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
    //迭代器的修改方法在执行完后会重新给expectedModCount赋值,保证与modCount相等
    public void remove() {
      //...
      expectedModCount = modCount;
    }
  }
  private class ListItr extends Itr implements ListIterator<E> {
    //迭代器的修改方法在执行完后会重新给expectedModCount赋值,保证与modCount相等
    public void add(E e) {
      //...
      expectedModCount = modCount;
      //...
    }
  }
}

查看 CopyOnWriteArrayList 的源码

 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
27
28
29
30
31
32
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  //用来保存添加的元素的数组,通过volatile修饰保证数据的一致性
  private transient volatile Object[] array;
  //CopyOnWriteArrayList对于会改变List的方法,都会先复制一份,在copy的数组上进行操作
  public boolean add(E e) {
    //...
    Object[] elements = getArray();
    //...
    //Object[] newElements = Arrays.copyOf(elements...
    //System.arraycopy(...)
    setArray(newElements);
  }
  public E remove(int index) {
    //...
    Object[] elements = getArray();
    //...
    //Object[] newElements = new Object[len - 1];
    //System.arraycopy(...)
    setArray(newElements);
  }
  //操作完成后再将原本数组的引用指向修改后的数组
  final void setArray(Object[] a) {
    array = a;
  }
  //返回COWIterator实例
  public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
  }
  static final class COWIterator<E> implements ListIterator<E> {
    //...
  }
}    

与 ArrayList 不同,CopyOnWriteArrayList 没有继承 AbstractList,仅实现了 List 接口,且 ArrayList 返回的 Iterator 是 AbstractList 实现的,而 CopyOnWriteArrayList 自己实现了 ListIterator 接口

CopyOnWriteArrayList 不会抛出 ConcurrentModificationException 异常是因为在迭代器中没有比较两个 modCount 是否相同,如果在 ArrayList 中不比较同样也不会抛出异常,ArrayList 比较 modCount 的目的是为了保证数据的一致性,而 CopyOnWriteArrayList 通过 getArray 方法返回的array 是被 volatile 修饰的,所以不用再比较 modCount ,具体的将在 CopyOnWriteArrayList 源码分析中进行讨论

LinkedList

LinkedList 实现了 List、Deque 、Cloneable、Serializable 接口,继承了 AbstractSequentialList 抽象类,底层实现是双向链表,实现 Deque 接口,表示可以当作队列使用,允许包含 null 元素

实现 Cloneable 标记接口,并重写了 Object 类的 clone 方法,支持浅拷贝

Serializable 标记接口表示支持序列化,支持序列化,并且在类中也定义了序列化和反序列化的方法

Java 6 LinkedList 的双向链表是循环的,Java 7 优化为直线型不再循环,用 first 和 last 指针的方式来代替 headerEntry (为了方便 header 的空校验),使得双向链表结构更清晰

1
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

重要的属性如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
transient int size = 0;  //节点个数
transient Node<E> first; //头结点指针
transient Node<E> last;  //尾结点指针
//结点内部类
private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;
  Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
  }
}

构造方法

1
2
3
4
5
6
7
//构建空链表
public LinkedList() {}
//先构建空链表,再将传入的集合c的元素添加到链表
public LinkedList(Collection<? extends E> c) {
  this();
  addAll(c);
}

addAll 方法

 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
27
28
29
30
31
32
33
34
35
36
public boolean addAll(int index, Collection<? extends E> c) {
  //检查索引,index >= 0 && index <= size;
  checkPositionIndex(index);
	//将传入的集合转换为Object数组
  Object[] a = c.toArray();
  int numNew = a.length;
  if (numNew == 0)
    return false;
  Node<E> pred, succ;
  if (index == size) {
    //构造方法调用时,index=size=0,进入这个条件
    succ = null;
    pred = last;
  } else {
    succ = node(index);
    pred = succ.prev;
  }
	//遍历Object数组,将元素插入到节点中
  for (Object o : a) {
    Node<E> newNode = new Node<>(pred, e, null);
    if (pred == null)
      first = newNode;
    else
      pred.next = newNode;
    pred = newNode;
  }
  if (succ == null) {
    last = pred;
  } else {
    pred.next = succ;
    succ.prev = pred;
  }
  size += numNew;
  modCount++;
  return true;
}

索引

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public E get(int index) {
  //调用node方法前要先调用checkElementIndex(index)方法检查索引
  checkElementIndex(index);
  return node(index).item;
}
Node<E> node(int index) {
  //如果索引在链表的前半部分,则从头结点开始遍历
  if (index < (size >> 1)) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
    //如果索引在链表的后半部分,则从尾结点开始遍历
  } else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

以上内容是玉山整理的笔记,如有错误还请指出