JDK容器類List和Set及Queue源碼怎么編寫

JDK容器類List和Set及Queue源碼怎么編寫，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

List，Set，Queue都是繼承Collection接口的單列集合接口。List常用的實現(xiàn)主要有ArrayList，LinkedList，List中的數(shù)據(jù)是有序可重復的。Set常用的實現(xiàn)主要是HashSet，Set中的數(shù)據(jù)是無序不可重復的。Queue常用的實現(xiàn)主要有ArrayBlockingQueue，LinkedBlockingQueue，Queue是一個保持先進先出的順序隊列，不允許隨機訪問隊列中的元素。

ArrayList核心源碼解讀

ArrayList是一個底層用數(shù)組實現(xiàn)的集合，數(shù)組元素類型為Object類型，支持隨機訪問，元素有序且可以重復，它繼承于AbstractList，實現(xiàn)了List, RandomAccess, Cloneable, java.io.Serializable這些接口。

當通過 ArrayList() 構造一個是集合，它是構造了一個空數(shù)組，初始長度為0。當?shù)?次添加元素時，會創(chuàng)建一個長度為10的數(shù)組，并將該元素賦值到數(shù)組的第一個位置，當添加的元素大于10的時候，數(shù)組會進行第一次擴容。擴容1.5倍，長度變?yōu)?5。

ArrayList在遍歷的時候時不能修改的，即遍歷的時候不能增加或者刪除元素，否則會拋ConcurrentModificationException

ArrayList是線程不安全的。

ArrayList源碼中的主要字段

// 默認數(shù)組的大小
private static final int DEFAULT_CAPACITY = 10;

// 默認空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};

// 實際存放數(shù)據(jù)的數(shù)組
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; //在數(shù)據(jù)中正確的位置上放上元素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) { // 如果為空數(shù)組
            return Math.max(DEFAULT_CAPACITY, minCapacity); // 返回默認的我數(shù)組長度
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 修改次數(shù)+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; // 拿到數(shù)組的當前長度
        int newCapacity = oldCapacity + (oldCapacity >> 1); //新數(shù)組的長度等于原數(shù)組長度的1.5倍
        if (newCapacity - minCapacity < 0) //當新數(shù)組長度仍然比minCapacity小，則為保證最小長度，新數(shù)組等于minCapacity
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) //當?shù)玫降男聰?shù)組長度比 MAX_ARRAY_SIZE大時，調(diào)用 hugeCapacity 處理大數(shù)組
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity); //調(diào)用 Arrays.copyOf將原數(shù)組拷貝到一個大小為newCapacity的新數(shù)組（拷貝引用）
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE : 
            MAX_ARRAY_SIZE; // 數(shù)組的最大長度為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）思想來實現(xiàn)的一個線程安全的ArrayList集合類。它實現(xiàn)了List接口，內(nèi)部持有一個ReentrantLock來給寫上鎖，底層是用volatile transient聲明的數(shù)組array，它是讀寫分離的，寫入數(shù)據(jù)時會復制出一個新的數(shù)組并加上ReentrantLock鎖，完成寫入后將新數(shù)組賦值給當前array，而讀操作不需要獲得鎖，支持并發(fā)。

CopyOnWriteArrayList的寫時復制導致了數(shù)據(jù)并不是實時的，有一定的延遲性，同時由于數(shù)據(jù)的復制，當數(shù)據(jù)量非常大的時候會占用很大的內(nèi)存。

CopyOnWriteArrayList是適合讀多寫少的場景。

CopyOnWriteArrayList核心源碼解讀

// 存放數(shù)據(jù)的數(shù)組
private transient volatile Object[] array;


    /**
     * 添加數(shù)據(jù)方法
     * 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(); // 加鎖，保證數(shù)據(jù)安全
        try {
            Object[] elements = getArray(); // 拿到數(shù)組
            int len = elements.length; // 獲取數(shù)組長度
            Object[] newElements = Arrays.copyOf(elements, len + 1); // 拷貝數(shù)組到新數(shù)組
            newElements[len] = e; // 將元素賦值到新數(shù)組的末尾
            setArray(newElements); //設置新數(shù)組為當前數(shù)組
            return true;
        } finally {
            lock.unlock(); // 解鎖
        }
    }

HashSet源碼解讀

HashSet是最常用的Set實現(xiàn)，它繼承了AbstractSet抽象類，實現(xiàn)了Set，Cloneable和java.io.Serializable接口。 HashSet中存儲的是無序不可重復的數(shù)據(jù)，他的底層的數(shù)據(jù)存儲是通過HashMap實現(xiàn)的，HashSet將數(shù)據(jù)存儲在HashMap的key中，將HashMap的value設為一個Object引用。

HashSet核心源碼解讀

// 實際存儲數(shù)據(jù)的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 構造函數(shù)，具有默認初始容量（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實現(xiàn)的，它是通過在添加數(shù)據(jù)的時候如果數(shù)據(jù)不存在才進行添加來實現(xiàn)了數(shù)據(jù)的不可重復

CopyOnWriteArraySet 核心源碼解讀

// 實際存放數(shù)據(jù)
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）的一個隊列數(shù)據(jù)結構，可以分為阻塞隊列和非阻塞隊列，Queue接口與List、Set同一級別，都是繼承了Collection接口。

Queue API

ArrayBlockingQueue源碼解讀

ArrayBlockingQueue是數(shù)組實現(xiàn)的線程安全的有界的阻塞隊列。

// 存放數(shù)據(jù)的數(shù)組
final Object[] items;

// 取數(shù)據(jù)索引
int takeIndex;

// 放數(shù)據(jù)索引
int putIndex;

// 數(shù)據(jù)量
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(); //隊列為空時，將使這個線程進入阻塞狀態(tài),直到被其他線程喚醒時取出元素
            return dequeue(); //消費對頭中的元素
        } finally {
            lock.unlock();
        }
    }

LinkedBlockingQueue源碼解讀

LinkedBlockingQueue底層是采用鏈表實現(xiàn)的一個阻塞的線程安全的隊列。 LinkedBlockingQueue構造的時候若沒有指定大小，則默認大小為Integer.MAX_VALUE，當然也可以在構造函數(shù)的參數(shù)中指定大小。 LinkedBlockingQueue中采用兩把鎖，取數(shù)據(jù)的時候加takeLock，放數(shù)據(jù)的時候加putLock。

// 容量
private final int capacity;

// 元素數(shù)量
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是線程安全的無界非阻塞隊列，其底層數(shù)據(jù)結構是使用單向鏈表實現(xiàn)，入隊和出隊操作是使用我們經(jīng)常提到的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是尾節(jié)點，則執(zhí)行插入
                // p is last node
                if (p.casNext(null, newNode)) { // 使用CAS設置p節(jié)點的next節(jié)點
                    // 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;
        }
    }

關于JDK容器類List和Set及Queue源碼怎么編寫問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業(yè)資訊頻道了解更多相關知識。