JDK源码阅读_集合框架(1)_ArrayList和LinkedList源码分析

集合框架jdk源码java并发编程

集合框架源码解读（一）

1.整体概述

1.1

首先，我总结了西下面这幅简单的结构图，先对java集合框架中的Collection接口有个大致的认识

其实类似这样的树形图总结在网上可以找到很多，并且比我这个全多了，其中总结的也很全面，很多朋友就是面试的时候拿来看看，当时记得挺清楚的，但是之后可能就忘记了，下面几篇文章，我们就从源码仔细解读下jdk的集合框架。文章后面我会给出一些比较全的总结图。

1.2

下面来看下几个重要接口的大致情况，包括接口签名和方法

public interface Iterator<E> {

public interface Collection<E> extends Iterable<E> {

public interface Set<E> extends Collection<E> {

public interface List<E> extends Collection<E> {

ps:

• 对于queue接口我们先不介绍，因为在实际的开发过程中不是最常用的。
• 从上面的接口方法列表图中，我们需要对整个集合框架有一个大致的了解，知道每一种集合框架都需要具备的功能大致是什么。
• 这里的每一个集合框架都需要具备迭代器的功能

2. List

首先，我们来介绍List，list接口的实现类很多，在jdk中主要使用的就是ArrayList和LinkedList ，下面我们一个个来分析。
首先，我们来看一下ArrayList的类和LinkedList类的签名：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
        
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

这里我们主要说一下AbstractList抽象类和AbstractSequentialList抽象类和RandomAcess接口

2.1 AbstractList和AbstractSequentialList

下面是AbstractList的类签名

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {

该类的注释中主要来看下下面这段:

 * This class provides a skeletal implementation of the {@link List}
 * interface to minimize the effort required to implement this interface
 * backed by a "random access" data store (such as an array).  For sequential
 * access data (such as a linked list), {@link AbstractSequentialList} should
 * be used in preference to this class.

大致就是说,AbstractList是一个简单实现了list接口的抽象类,其中对list接口中的规范做了部分实现，这样如果想要实现一个可以支持随机访问的list集合就可以直接继承这个抽象类，这样可以尽量减少你的工作。这里需要注意的是，随机访问，为什么集成AbstractList的类就表示支持随机访问呢？首先随机访问是指,获取元素的时候,我们可以直接通过元素的下标获取到元素,也就是获取是O(1),注释中又说了一个 AbstractSequentialList ，意思是说如果需要实现一个连续顺序存储的list，那么可以继承AbstractSequentialList抽象类来减少工作

public abstract class AbstractSequentialList<E> extends AbstractList<E> {

可以看到AbstractSequentialList继承了AbstractList，但是其中的AbstractSequentialList中的迭代器是自己实现的

    public abstract ListIterator<E> listIterator(int index);\
    
    public Iterator<E> iterator() {
    return listIterator();
    }

可以看到,无论是普通迭代器,还是双向迭代器,内部其实都是直接调用的双向迭代器,也就是listIterator,但是这是一个抽象方法,继承AbstractSequentialList的实现类需要重新实现迭代器,那为什么不直接使用继承的AbstractList中已经实现好的迭代器呢?
先来看下AbstractList中实现好的迭代器的代码:

    public Iterator<E> iterator() {
        return new Itr();
    }
    
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

    public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);
        return new ListItr(index);
    }

可以看到,AbstractList中有普通迭代器的实现Itr,也有双向迭代器的实现ListItr
以Itr的next为例

        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

可以看到,这里是通过下表直接获取元素的,所以这是支持随机访问的集合的规范操作,但是前面jdk的源码注释中说明了,AbstractSequentialList是让支持数据连续存储的集合实现的,所以不能使用这个迭代器(其实本质可以理解为数组和链表的差异)

2.2 RandomAccess

上面,我们看到AbstractList实现了RandomAcess接口但是AbstractSequentialList没有实现,RandomAccess接口有什么作用呢?
想来看下这个接口:

public interface RandomAccess {
}

可以看到这个接口是没有方法的,凭借十几年的crud经验,大致可以判断出来,这是一个jdk中的标记接口,其实也就是类似于
Serializable,Cloneable这类接口,不卖关子,这个接口做的标记就是: 如果一个实现类实现了这个接口,就代表这个实现类支持快速随机访问.通俗点理解就是可以支持快速下标访问,这样的话,在某些场景下可以根据是否为这个接口的实现类来判断是否支持快速随机访问,进而选择不同的遍历方法.

Q1: 说到这里,不得不说一下,支持随机访问的集合实现类和支持连续存储的集合实现类在遍历过程中到底有什么需要注意的,为什么需要判断这个来决定用什么方法遍历?
这个答案,等介绍完LinedList和ArrayList再说吧,其实就是数组和链表直接的遍历效率问题.

2.3 ArrayList

2.3.1 先来看下ArrayList中的几个成员变量属性;

• 默认ArrayList的容量是10

private static final int DEFAULT_CAPACITY = 10;

• 初始化一个空集合对象

private static final Object[] EMPTY_ELEMENTDATA = {};

• 又初始化了一个空集合对象

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• ArrayList集合中存储数据的容器

transient Object[] elementData;

• 当前ArrayList中的实际元素个数,每次删除或者添加的时候都会顺便改变了size的值，这样的好处是，在需要获取当前实际的长度的时候可以直接后去size的值即可，不需要遍历整个ArrayList计算实际元素的个数（长度）

private int size;

Q2:为什么要初始化两个空集合属性
在ArrayList中有下面两种构造方法:

    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);
        }
    }
    
    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

第一种是指定初始化的容器数组的大小,第二种是使用默认的容器数组的大小(DEFAULT_CAPACITY = 10),首先需要搞清楚两点.

1. 之所以声明空的集合对象,是为了在后面判断集合是否为空,或者初始化一个空的集合可以直接使用.
2. ArrayList中初始化容量是在添加第一个元素的时候(自定义容量大于0的情况除外)
   基于上面两点,考虑这样一个问题,如果在第一次调用add的时候,判断当前的ArrayList是不是走默认的容量呢?还是走指定的自定义容量呢?
   所以在构造方法,初始化空数组的时候,我们选择两种情况下使用不同的数组,进而在第一次add的时候可以根据之前构造方法中初始化使用的 是哪一个空数组来判断是否是默认的初始化容量.

如果还不明白,可以仔细看下下面的源码,代码很简单,主要是要搞清楚调用顺序,其实就是我前面说的两点

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        //如果是自定义初始化容量并且初始化容量是0,那么赋值的是EMPTY_ELEMENTDATA                                          
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    
    public ArrayList() {
        //如果是使用默认的构造方法则是赋值的DEFAULTCAPACITY_EMPTY_ELEMENTDATA,这样在后面的add的时候就会判断到时DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        //然后就可以赋值为默认初始容量0
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

现在我们来看下add方法

    public boolean add(E e) {
        //重点就是这个方法，该方法执行来判断当前容量是否够用，不够则扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }  
    
    private void ensureCapacityInternal(int minCapacity) {
        //和之前说的一样，如果之前赋值的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则直接扩容到默认容量10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //如果赋值的是EMPTY_ELEMENTDATA，则为自定义容量的构造方法初始化的
        ensureExplicitCapacity(minCapacity);
    }
    
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        /**判断是否需要扩容，从这里可以看出
         *1.扩容时机是在插入的元素个数大于容量的时候才会扩容
         *2.从下面的grow方法可以看出需要扩容的时候，将容量扩大为原来的3/2,也就是增大原来的1/2，扩大为原来的1.5倍
         **/
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //2. 需要扩容的时候，将容量扩大为原来的3/2,也就是增大原来的1/2，扩大为原来的1.5倍（右移一位）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

ps: 可以看出，如果是默认容量，那么整个ArrayList的扩容历程是：10，15，22，33 ...
如果是自定义的，如果初始容量赋值为0，那么则为1，2， 3，4，6，9，13，19

2.3.2 ArrayList中的插入操作

从源码入手，ArrayList中支持下面的插入方法

    //插入尾部
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    //插入指定位置
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

ps:数组工具类Arrays的copy的方法

Arrays.copyOf(elementData, newCapacity);

    //original是原数组
    //newLength是复制的数组的长度，即新数组的长度  
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
    
    
    /**
    source_arr : 源数组
    sourcePos : 源数组拷贝元素的起始位置
    dest_arr : 目标数组
    destPos : 目标数组接收拷贝元素的起始位置
    len : 拷贝的元素的数目
    可以看出这里复制后是返回一个新的数组
    **/
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
    

从前面我们可以看到,如果需要扩容,那么调用的是grow方法,再grow方法中调用的是Arrays的copy方法,所以返回的是一个新的扩容后的数组对象,但是再插入的时候如果不需要扩容,那么返回的就是原来数组移动元素后的数组,数组对象引用地址并没有变化,只是元素移动了位置. 因为再add的时候

        //这里的原数组和目的数组都是elementData变量
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
                         

总结:ArrayList在发生扩容的时候,调用的是Arrays.copyOf方法,会生成一个容量扩大的新数组对象并返回;在add操作的时候,如果没有发生扩容,如果是插入尾部,那么就是直接使用数组的下标赋值即可,如果是插入指定位置则调用System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);方法,其中国的源数组和目的数组都是当前ArrayList的容器数组,所以只会发生数组的元素位置迁移,不会生成新的数组.其实很简单,需要扩容的时候,我们知道,数组的大小是固定的,声明了就无法改变,想要改变大小就需要重新创建新的,但是如果不需要扩容,那么直接移动数组元素位置就好了,不需要创建新的.

ArrayList中其他的操作,比如remove等源码也都是比较容易理解的,这里不做解读了,其实也都是涉及了数组中元素的位置移动

    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;
    }
    
    
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

2.3 LinedList

2.3.1 LinkedList中的几个重要属性

    transient int size = 0;
    
    transient Node<E> first;

    transient Node<E> last;

可以看出来，LinkedList内部使用的是双向链表作为容器来保存元素数据的

LinkedList中几个重要的内部类

    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;
        }
    }

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

可以看到，在LinkedList中重新实现了一个迭代器，并且重写了AbstractSequalList中的listIterator（）方法

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

但是你可能会说，我在new LinkedList的时候，使迭代器是直接调用的iterator()方法，但是在LinedList中没有找到，是的，前面我们介绍了其实AbstractSequalList中是这样的：

    public Iterator<E> iterator() {
        return listIterator();
    }
    
    public abstract ListIterator<E> listIterator(int index);

所以，你调用的iterator()方法其实是父类AbstractSequentialList的，只是父类中的iterator()调用的是子类中实现的listIterator方法，所以最终LinkedList中使用的迭代器是自己实现的，也就是上面的代码，内部类ListItr

ps:如果你对迭代器还不熟悉，还是建议你看下迭代器接口的源码，可以去这篇文章java中的迭代器

2.3.2

同样的先来看LinkedList的构造方法

    //无参构造
    public LinkedList() {
    }
    
    //
    public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
    }

    public boolean addAll(Collection<? extends E> c) {
                    
        return addAll(size, c);
    }

最后调用的是这个addAll方法,将指定的集合c从指定的index位置开始插入,这里放在构造方法中,也就是从链表的开始节点开始插入(因为开始的时候链表的size=0),插入整个集合到这个新的链表

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); //检测待指定的开始插入的位置是否合法(index >= 0 && index <= size)

        Object[] a = c.toArray();  //待插入的集合转为数组
        int numNew = a.length; //转为数组的长度
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) { //如果是插入链表尾部
            succ = null; //待插入的节点就是null
            pred = last; //最后一个节点就是待插入节点的上个节点
        } else {
            succ = node(index); //获取当前待插入的节点
            pred = succ.prev; //获取当前待插入的节点的上个节点  如果是要插入头部那么此时pred=null
        }

        for (Object o : a) { //一个个放入待插入元素
            @SuppressWarnings("unchecked") E e = (E) o;
            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;
    }

---

下面来看下元素的插入

• 插入到链表的尾部

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    //节点插入尾部
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

ps: 其实linkedList中的操作都是双向链表的常规操作，主要就是下面的源码

    /**
     * Links e as first element.插入元素到头部
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.插入元素到尾部
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ. 插入元素到指定位置
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Unlinks non-null first node f.//删除头元素
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null last node l.删除尾元素
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null node x.  删除任意元素
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

所以关于LinkedList的一些操作源码我们不做过多分析了，大家可以去看下我之前的实现双向链表的文章，里面有简单而实现LinkedList的基础操作

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/05/17 00:12