JDK容器类List，Set，Queue源码解读

list，set，queue都是继承collection接口的单列集合接口。list常用的实现主要有arraylist，linkedlist，list中的数据是有序可重复的。set常用的实现主要是hashset，set中的数据是无序不可重复的。queue常用的实现主要有arrayblockingqueue，linkedblockingqueue，queue是一个保持先进先出的顺序队列，不允许随机访问队列中的元素。

arraylist核心源码解读

arraylist是一个底层用数组实现的集合，数组元素类型为object类型，支持随机访问，元素有序且可以重复，它继承于abstractlist，实现了list, randomaccess, cloneable, java.io.serializable这些接口。

当通过 arraylist() 构造一个是集合，它是构造了一个空数组，初始长度为0。当第1次添加元素时，会创建一个长度为10的数组，并将该元素赋值到数组的第一个位置，当添加的元素大于10的时候，数组会进行第一次扩容。扩容1.5倍，长度变为15。

arraylist在遍历的时候时不能修改的，即遍历的时候不能增加或者删除元素，否则会抛concurrentmodificationexception

arraylist是线程不安全的。

arraylist源码中的主要字段

// 默认数组的大小
private static final int default_capacity = 10;

// 默认空数组
private static final object[] empty_elementdata = {};

// 实际存放数据的数组
private transient object[] elementdata;

arraylist源码中的构造器

    /**
     * constructs an empty list with an initial capacity of ten.
     */
    public arraylist() {
        this.elementdata = defaultcapacity_empty_elementdata;
    }

    /**
     * constructs an empty list with the specified initial capacity.
     *
     * @param  initialcapacity  the initial capacity of the list
     * @throws illegalargumentexception if the specified initial capacity
     *         is negative
     */
    public arraylist(int initialcapacity) {
        if (initialcapacity > 0) {
            this.elementdata = new object[initialcapacity]; //将自定义的容量大小当成初始化elementdata的大小
        } else if (initialcapacity == 0) {
            this.elementdata = empty_elementdata;
        } else {
            throw new illegalargumentexception("illegal capacity: "+
                                               initialcapacity);
        }
    }

arraylist源码中的add方法

    /**
     * appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link collection#add})
     */
    public boolean add(e e) {
        ensurecapacityinternal(size + 1); //添加元素之前，首先要确定集合的大小
        elementdata[size++] = e; //在数据中正确的位置上放上元素e，并且size++
        return true;
    }

    private void ensurecapacityinternal(int mincapacity) {
        ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
    }

    private static int calculatecapacity(object[] elementdata, int mincapacity) {
        if (elementdata == defaultcapacity_empty_elementdata) { // 如果为空数组
            return math.max(default_capacity, mincapacity); // 返回默认的我数组长度
        }
        return mincapacity;
    }

    private void ensureexplicitcapacity(int mincapacity) {
        modcount++; // 修改次数+1，相当于版本号

        // overflow-conscious code
        if (mincapacity - elementdata.length > 0) // 如果实际容量小于需要容量
            grow(mincapacity);                    // 扩容 
    }

    /**
     * increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param mincapacity the desired minimum capacity
     */
    private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length; // 拿到数组的当前长度
        int newcapacity = oldcapacity + (oldcapacity >> 1); //新数组的长度等于原数组长度的1.5倍
        if (newcapacity - mincapacity < 0) //当新数组长度仍然比mincapacity小，则为保证最小长度，新数组等于mincapacity
            newcapacity = mincapacity;
        if (newcapacity - max_array_size > 0) //当得到的新数组长度比 max_array_size大时，调用 hugecapacity 处理大数组
            newcapacity = hugecapacity(mincapacity);
        // mincapacity is usually close to size, so this is a win:
        elementdata = arrays.copyof(elementdata, newcapacity); //调用 arrays.copyof将原数组拷贝到一个大小为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; // 数组的最大长度为integer.max_value
    }

arraylist源码中的get方法

    /**
     * returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws indexoutofboundsexception {@inheritdoc}
     */
    public e get(int index) {
        rangecheck(index); //判断索引合法性

        return elementdata(index);
    }

线程安全的arraylist—copyonwritearraylist

copyonwritearraylist是基于写时复制（copy-on-write）思想来实现的一个线程安全的arraylist集合类。它实现了list接口，内部持有一个reentrantlock来给写上锁，底层是用volatile transient声明的数组array，它是读写分离的，写入数据时会复制出一个新的数组并加上reentrantlock锁，完成写入后将新数组赋值给当前array，而读操作不需要获得锁，支持并发。

copyonwritearraylist的写时复制导致了数据并不是实时的，有一定的延迟性，同时由于数据的复制，当数据量非常大的时候会占用很大的内存。

copyonwritearraylist是适合读多写少的场景。

copyonwritearraylist核心源码解读

// 存放数据的数组
private transient volatile object[] array;

    /**
     * 添加数据方法
     * appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link collection#add})
     */
    public boolean add(e e) {
        final reentrantlock lock = this.lock;
        lock.lock(); // 加锁，保证数据安全
        try {
            object[] elements = getarray(); // 拿到数组
            int len = elements.length; // 获取数组长度
            object[] newelements = arrays.copyof(elements, len + 1); // 拷贝数组到新数组
            newelements[len] = e; // 将元素赋值到新数组的末尾
            setarray(newelements); //设置新数组为当前数组
            return true;
        } finally {
            lock.unlock(); // 解锁
        }
    }

hashset源码解读

hashset是最常用的set实现，它继承了abstractset抽象类，实现了set，cloneable和java.io.serializable接口。
hashset中存储的是无序不可重复的数据，他的底层的数据存储是通过hashmap实现的，hashset将数据存储在hashmap的key中，将hashmap的value设为一个object引用。

hashset核心源码解读

// 实际存储数据的hashmap
private transient hashmap<e,object> map;

// hashmap的value引用
private static final object present = new object();

    /**
     * constructs a new, empty set; the backing <tt>hashmap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public hashset() {
        map = new hashmap<>(); //new一个 hashmap 对象出来，采用无参的 hashmap 构造函数，具有默认初始容量（16）和加载因子（0.75）。
    }

    /**
     * adds the specified element to this set if it is not already present.
     * more formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * if this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(e e) {
        return map.put(e, present)==null;
    }

线程安全的hashset—copyonwritearrayset

copyonwritearrayset是一个线程安全的hashset，它底层是通过copyonwritearraylist实现的，它是通过在添加数据的时候如果数据不存在才进行添加来实现了数据的不可重复

copyonwritearrayset 核心源码解读

// 实际存放数据
private final copyonwritearraylist<e> al;

    /**
     * adds the specified element to this set if it is not already present.
     * more formally, adds the specified element {@code e} to this set if
     * the set contains no element {@code e2} such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * if this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     */
    public boolean add(e e) {
        return al.addifabsent(e); // 如果不存在则添加
    }

queue详细分析

queue是先入先出（fifo）的一个队列数据结构，可以分为阻塞队列和非阻塞队列，queue接口与list、set同一级别，都是继承了collection接口。

queue api

arrayblockingqueue源码解读

arrayblockingqueue是数组实现的线程安全的有界的阻塞队列。

// 存放数据的数组
final object[] items;

// 取数据索引
int takeindex;

// 放数据索引
int putindex;

// 数据量
int count;

// 锁
final reentrantlock lock;

 /** condition for waiting takes */
private final condition notempty;

/** condition for waiting puts */
private final condition notfull;

    /** items index for next put, offer, or add */
    int putindex;

    /**
     * inserts the specified element at the tail of this queue if it is
     * possible to do so immediately without exceeding the queue's capacity,
     * returning {@code true} upon success and {@code false} if this queue
     * is full.  this method is generally preferable to method {@link #add},
     * which can fail to insert an element only by throwing an exception.
     *
     * @throws nullpointerexception if the specified element is null
     */
    public boolean offer(e e) {  // offer方法是非阻塞
        checknotnull(e);
        final reentrantlock lock = this.lock; // offer的时候加锁
        lock.lock();
        try {
            if (count == items.length) // 如果没有空间， 返回false
                return false;
            else {
                enqueue(e);  // 如果有空间，入队列
                return true;
            }
        } finally {
            lock.unlock();
        }
    }

    /**
     * inserts the specified element at the tail of this queue, waiting
     * for space to become available if the queue is full.
     *
     * @throws interruptedexception {@inheritdoc}
     * @throws nullpointerexception {@inheritdoc}
     */
    public void put(e e) throws interruptedexception {
        checknotnull(e);
        final reentrantlock lock = this.lock; // 加锁
        lock.lockinterruptibly();
        try {
            while (count == items.length)  // queue的容量已满
                notfull.await();           // 阻塞
            enqueue(e);
        } finally {
            lock.unlock();
        }
    }

    public e take() throws interruptedexception {
        final reentrantlock lock = this.lock;
        lock.lockinterruptibly();
        try {
            while (count == 0)
                notempty.await(); //队列为空时，将使这个线程进入阻塞状态,直到被其他线程唤醒时取出元素
            return dequeue(); //消费对头中的元素
        } finally {
            lock.unlock();
        }
    }

linkedblockingqueue源码解读

linkedblockingqueue底层是采用链表实现的一个阻塞的线程安全的队列。
linkedblockingqueue构造的时候若没有指定大小，则默认大小为integer.max_value，当然也可以在构造函数的参数中指定大小。
linkedblockingqueue中采用两把锁，取数据的时候加takelock，放数据的时候加putlock。

// 容量
private final int capacity;

// 元素数量
private final atomicinteger count = new atomicinteger();

// 链表头
transient node<e> head;

// 链表尾
private transient node<e> last;

// take锁
private final reentrantlock takelock = new reentrantlock();

// 当队列无元素时，take锁会阻塞在notempty条件上，等待其它线程唤醒
private final condition notempty = takelock.newcondition();

// 放锁
private final reentrantlock putlock = new reentrantlock();

// 当队列满了时，put锁会会阻塞在notfull上，等待其它线程唤醒
private final condition notfull = putlock.newcondition();

    /**
     * creates a {@code linkedblockingqueue} with a capacity of
     * {@link integer#max_value}.
     */
    public linkedblockingqueue() {
        this(integer.max_value); // 如果没传容量，就使用最大int值初始化其容量
    }

    /**
     * inserts the specified element at the tail of this queue, waiting if
     * necessary for space to become available.
     *
     * @throws interruptedexception {@inheritdoc}
     * @throws nullpointerexception {@inheritdoc}
     */
    public void put(e e) throws interruptedexception {
        if (e == null) throw new nullpointerexception();
        // note: convention in all put/take/etc is to preset local var
        // holding count negative to indicate failure unless set.
        int c = -1;
        node<e> node = new node<e>(e);
        final reentrantlock putlock = this.putlock;   // 使用putlock锁加锁
        final atomicinteger count = this.count;
        putlock.lockinterruptibly();
        try {
            /*
             * note that count is used in wait guard even though it is
             * not protected by lock. this works because count can
             * only decrease at this point (all other puts are shut
             * out by lock), and we (or some other waiting put) are
             * signalled if it ever changes from capacity. similarly
             * for all other uses of count in other wait guards.
             */
            while (count.get() == capacity) {  // 如果队列满了，就阻塞在notfull条件上
                notfull.await(); // 等待被其它线程唤醒
            }
            enqueue(node);     // 队列不满了，就入队
            c = count.getandincrement();
            if (c + 1 < capacity)
                notfull.signal();
        } finally {
            putlock.unlock();
        }
        if (c == 0) 
            signalnotempty();
    }

    public e take() throws interruptedexception {
        e x;
        int c = -1;
        final atomicinteger count = this.count;
        final reentrantlock takelock = this.takelock; // 使用takelock加锁
        takelock.lockinterruptibly();
        try {
            while (count.get() == 0) { // 如果队列无元素，则阻塞在notempty条件上
                notempty.await();
            }
            x = dequeue();
            c = count.getanddecrement();
            if (c > 1)
                notempty.signal();
        } finally {
            takelock.unlock();
        }
        if (c == capacity)
            signalnotfull();
        return x;
    }

concurrentlinkedqueue源码解读

concurrentlinkedqueue是线程安全的无界非阻塞队列，其底层数据结构是使用单向链表实现，入队和出队操作是使用我们经常提到的cas来保证线程安全的。
concurrentlinkedqueue不允许插入的元素为null。

private transient volatile node<e> head;

private transient volatile node<e> tail;

private static final sun.misc.unsafe unsafe;

private static final long headoffset;

private static final long tailoffset;

   /**
     * inserts the specified element at the tail of this queue.
     * as the queue is unbounded, this method will never return {@code false}.
     *
     * @return {@code true} (as specified by {@link queue#offer})
     * @throws nullpointerexception if the specified element is null
     */
    public boolean offer(e e) {
        checknotnull(e); // 为null则抛出空指针异常
        final node<e> newnode = new node<e>(e);

        for (node<e> t = tail, p = t;;) { // 自旋
            node<e> q = p.next;
            if (q == null) { // 如果q==null说明p是尾节点，则执行插入
                // p is last node
                if (p.casnext(null, newnode)) { // 使用cas设置p节点的next节点
                    // successful cas is the linearization point
                    // for e to become an element of this queue,
                    // and for newnode to become "live".
                    if (p != t) // hop two nodes at a time
                        castail(t, newnode);  // failure is ok.
                    return true;
                }
                // lost cas race to another thread; re-read next
            }
            else if (p == q)
                // we have fallen off list.  if tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  else the new tail is a better bet.
                p = (t != (t = tail)) ? t : head;
            else
                // check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }