Java基础

集合框架——List接口及其实现类源码解析（JDK8）

2018-07-21  本文已影响23人  黄金矿工00七

不多说，直接上源码

List接口:

JDK文档中是这样描述的

/**
 * An ordered collection (also known as a <i>sequence</i>).  The user of this
 * interface has precise control over where in the list each element is
 * inserted.  The user can access elements by their integer index (position in
 * the list), and search for elements in the list.<p>
 * Unlike sets, lists typically allow duplicate elements.  More formally,
 * lists typically allow pairs of elements <tt>e1</tt> and <tt>e2</tt>
 * such that <tt>e1.equals(e2)</tt>, and they typically allow multiple
 * null elements if they allow null elements at all.  It is not inconceivable
 * that someone might wish to implement a list that prohibits duplicates, by
 * throwing runtime exceptions when the user attempts to insert them, but we
 * expect this usage to be rare.<p>
Note: While it is permissible for lists to contain themselves as elements,
 * extreme caution is advised: the <tt>equals</tt> and <tt>hashCode</tt>
 * methods are no longer well defined on such a list.
 */
ArrayList

吐槽简书，这段注释不识别

  /**
   * Resizable-array implementation of the <tt>List</tt> interface.  Implements
   * all optional list operations, and permits all elements, including
   * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
   * this class provides methods to manipulate the size of the array that is
   * used internally to store the list.  (This class is roughly equivalent to
   * <tt>Vector</tt>, except that it is unsynchronized.)
   */

总结一下，文档中描述的大概就是下面这些东西：

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            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);
        }
    }

    /**默认容量大小
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**用于空实例的共享空数组实例（当设置容量为0时或者使用collection来构造时使用的数组实例）
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**默认使用的数组实例
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**存储ArrayList元素的数组缓冲区。ArrayList的容量等于这个数组缓冲区的长度。
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**数组元素的数量
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

总结一下：数组默认容量为10，有两个空数组的实例，一个数组缓冲区的引用，会指向两个空数组实例之一，缓冲区的大小等于ArrayList的容量，以及数组元素的数量

List <String> list = new ArrayList <> ();
list.add("123");
图片.png

在list 初始化之后，数组缓冲区的长度为0，add一个元素之后，数组缓冲区的长度等于DEFAULT_CAPACITY =10，我们再来看一下，继续添加元素之后的扩容机制。

    private void ensureCapacityInternal(int minCapacity) {
          //如果是默认创建的list，则最小容量等于DEFAULT_CAPACITY, minCapacity之间的最大值
         // 也就是说在数组元素的数量小于10的时候，最小容量=10，大于等于10的时候，最小容量为当前size+1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }


    private void ensureExplicitCapacity(int minCapacity) {
        //修改次数+1，用来实现迭代器是fail-fast机制(是在AbstractList中实现的。)，所有对集合的修改都会增加
        //在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。
        //在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了集合对象
        modCount++;

        // overflow-conscious code 考虑溢出的情况
        //上面代码中minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);实际上
        //minCapacity有可能超过Integer.MAX_VALUE，发生了溢出  那么minCapacity 就会等于DEFAULT_CAPACITY，所以就不会继续增加数组的容量，已经是最大值了
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


  private void grow(int minCapacity) {
        // overflow-conscious code 考虑溢出
        //旧容量为当前数组的长度，第一次添加为0
        int oldCapacity = elementData.length;
        //新的数组容量为原来的1.5倍 >>等于/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
        //如果小于最小容量则新的容量为最小容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        //如果新的数组容量超过Integer.MAX_VALUE - 8
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

  private static int hugeCapacity(int minCapacity) {
        //对溢出进行检测 ，结合下面叙述来看
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

上面的代码 if (newCapacity - minCapacity < 0)以及 if (newCapacity - MAX_ARRAY_SIZE > 0) 这里很关键，为啥不使用newCapacity < minCapacity 和newCapacity >MAX_ARRAY_SIZE来判断 ,我们知道newCapacity 是有可能超过int的正数表示范围的，那么就会溢出，成为一个负数，而minCapacity是一个正数，负数<正数是恒成立true，而newCapacity - minCapacity，负数减正数是有可能是一个正数，下面同理newCapacity 在MAX_VALUE -1到MAX_VALUE 之间或者newCapacity <-10 (如果溢出肯定小于)，这个条件就会成立，如果使用newCapacity >MAX_ARRAY_SIZE，则newCapacity 溢出的时候会恒不成立

　　向数组中添加到第10个元素时，数组容量仍为10.

　　向数组中添加到第11个元素时，数组容量扩为15.

　　向数组中添加到第16个元素时，数组容量扩为22.
这样带来了很大的性能问题，所以有时候我们需要对数组进行手动扩容，避免数组大量的自动扩容
如果参数大于底层数组长度的1.5倍，那么这个数组的容量就会被扩容到这个参数值，
如果参数小于底层数组长度的1.5倍，那么这个容量就会被扩容到底层数组长度的1.5倍。

    /**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *扩展数组容量，尽量使用最小容量
     * @param   minCapacity   the desired minimum capacity
     */
  public void ensureCapacity(int minCapacity) {
          //判断list是否是默认方式创建，如果是则最小扩展量为DEFAULT_CAPACITY，如果不是则等于0
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
        //如果参数大于底层数组长度的1.5倍，那么这个数组的容量就会被扩容到这个参数值，
        //如果参数小于底层数组长度的1.5倍，那么这个容量就会被扩容到底层数组长度的1.5倍。
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

剩下的add（index）、addAll（index）、remove方法都是基于System.arraycopy（）来实现的不在多说。
然后我们发现还有一个subList方法，这个方法是做什么的呢？

 public static void main(String[] args) {

    LinkedList<String> ll = new LinkedList<>();
    ll.add("1");
    ll.add("2");
    ll.add("3");
    ll.add("4");
    ll.add("5");
    List<String> l2 =  ll.subList(2, 4);
    l2.clear();
    System.out.println(ll);

  }
图片.png 
public class Test {

  public static void main(String[] args) {
    //  初始化链表5000个元素
    List<String> list_5000 = new ArrayList<String>(5000);
    List<String> list_10000 = new ArrayList<String>(10000);
    List<String> list_100000 = new ArrayList<String>(100000);
    for (int i = 0; i < 1000; i++) {
      list_5000.add("1");
      list_5000.add("2");
      list_5000.add("3");
      list_5000.add("4");
      list_5000.add("5");
    }
    for (int j = 0; j < 2000; j++) {
      list_10000.add("1");
      list_10000.add("2");
      list_10000.add("3");
      list_10000.add("4");
      list_10000.add("5");
    }
    for (int k = 0; k < 20000; k++) {
      list_100000.add("1");
      list_100000.add("2");
      list_100000.add("3");
      list_100000.add("4");
      list_100000.add("5");
    }
    //avgTime(list_5000);
    //avgTime(list_10000);
    avgTime(list_100000);
    //System.out.println(traverseByFor(list_100000));
  }

  public static void avgTime(List list) {
    long forAvgTime = 0;
    long foreachAbgTime = 0;
    long iteratorAvgTime = 0;
    long listIteratorAvgTime = 0;
    for (int i = 0; i < 20; i++) {
      forAvgTime += traverseByFor(list);
      foreachAbgTime += traverseByForeach(list);
      iteratorAvgTime += traverseByIterator(list);
      listIteratorAvgTime += traverseByListIterator(list);
    }
    System.out.println("使用for遍历时间 ：" + forAvgTime );
    System.out.println("使用迭代器遍历时间 ：" + iteratorAvgTime );
    System.out.println("使用List迭代器遍历时间 ：" + listIteratorAvgTime );
    System.out.println("使用foreach遍历时间 ：" + foreachAbgTime );
  }

  /**
   * 使用for遍历
   */
  public static long traverseByFor(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
      String s = (String) list.get(i);
      //相应的业务逻辑
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

  /**
   * 使用迭代器遍历
   */
  public static long traverseByIterator(List list) {
    long start = System.currentTimeMillis();

    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
      String s = (String) iterator.next();
      //相应的业务逻辑
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

  public static long traverseByListIterator(List list) {
    long start = System.currentTimeMillis();

    Iterator iterator = list.listIterator();
    while (iterator.hasNext()) {
      String s = (String) iterator.next();
      //相应的业务逻辑
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

  /**
   * 使用foreach遍历
   */
  public static long traverseByForeach(List<String> list) {
    long start = System.currentTimeMillis();
    for (String attribute : list) {
      //相应的业务逻辑
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

}

public E get(int 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;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读