ArrayList源碼分析

自定義List集合接口

package com.mayikt.ext;

/**
 * @Description: 自定義List集合
 * @Author: ChenYi
 * @Date: 2020/06/09 20:43
 **/

public interface MayiktList<E> {
    /**
     * 集合的大小
     *
     * @return
     */
    int size();

    /**
     * 往集合中添加元素
     *
     * @param e
     * @return
     */
    boolean add(E e);

    /**
     * 通過索引擷取集合的元素
     *
     * @param index
     * @return
     */
    E get(int index);
}

自定義ArrayList類

package com.mayikt.ext.impl;

import com.mayikt.ext.MayiktList;

import java.util.Arrays;

/**
 * @Description: 自定義ArrayList
 * @Author: ChenYi
 * @Date: 2020/06/09 20:46
 **/

public class MayiktArrayList<E> implements MayiktList<E> {
    /**
     * 初始化空的數組
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * 數組的容量，transient代表該變量不能被序列化
     */
    transient Object[] elementData;
    /**
     * 集合的大小
     */
    private int size;
    /**
     * ArrayList預設的初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;


    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    protected transient int modCount = 0;

    public MayiktArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean add(E e) {
        //初始化集合的大小
        ensureCapacityInternal(size + 1);
        //指派
        elementData[size++] = e;
        return true;
    }

    @Override
    public E get(int index) {
        return (E) elementData[index];
    }

    @Override
    public E remove(int index) {
        //檢測數組是否越界
        rangeCheck(index);
        //保證線程安全性
        modCount++;
        E oldValue = get(index);
        int numMoved = size - index - 1;
        //檢測如果是删除最後一位的話直接把最後一位置空
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        }
        //最後索引位置置空
        elementData[--size] = null;

        return oldValue;
    }

    private void ensureCapacityInternal(int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //沒有指定集合容量的大小并且是第一次添加元素的時候進來
            //minCapacity=0+1   DEFAULT_CAPACITY=10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //第一次初始化的集合的大小為10
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //保證線程的安全性，如果同時寫入的話就可能報錯
        modCount++;
        //判斷數組是否需要擴容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }

    /**
     * 判斷數組是否越界
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    private void grow(int minCapacity) {
        // 第一次elementData為空數組 0
        int oldCapacity = elementData.length;
        /**
         *  >>位運算  向右移動相當于/2  左移相當于*2
         *   0+0/2=0
         */
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 0-10
        if (newCapacity - minCapacity < 0) {
            //第一次擴容的時候才進來 10
            newCapacity = minCapacity;
        }
        //集合的最大容量是2 的21次方
        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;
    }
}

總結：

使用無參建構函數new出ArrayList集合的時候，數組的容量是0，elementData是一個空的數組
第一次添加的時候才會初始化數組的大小，會調用grow方法進行擴容，初始化的大小為10
每次擴容的時候，數組的長度增加0.5倍
數組最大的長度是Interger的最大值
集合删除元素之後，數組是不會縮容的，對應的位置置為null
由于ArrayList是線程不安全的，在高并發的情況下會出現Fail-Fast，是以裡面用了一個modCount來保證線程的安全。

CopyOnWriteArrayList源碼分析

自定義的CopyOnWriteArrayList類

package com.mayikt.ext.impl;

import com.mayikt.ext.MayiktList;

import java.util.Arrays;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @Description: 自定義CopyOnWriteArrayList
 * @Author: ChenYi
 * @Date: 2020/06/11 07:46
 **/

public class MayiktCopyOnWriteArrayList<E> implements MayiktList<E> {
    final transient ReentrantLock lock = new ReentrantLock();
    private transient volatile Object[] array;

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        //加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();
        }
    }

    final Object[] getArray() {
        return array;
    }


    public MayiktCopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

    final void setArray(Object[] a) {
        array = a;
    }

    @Override
    public E get(int index) {
        return get(getArray(), index);
    }

    private E get(Object[] a, int index) {
        return (E) a[index];
    }

    @Override
    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0) {
                setArray(Arrays.copyOf(elements, len - 1));
            } else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                        numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
}

總結:

使用無參建構對象的時候，預設的數組也是空的
每次添加元素的時候都會加Lock鎖，原來的數組長度加1，建立出新的數組，然後把之前的值放進去，沒有存在擴容的操作。
讀的時候是沒有加Lock鎖的，是以讀取的時候效率比較快。

Vector源碼解析

自定義的Vector類

package com.mayikt.ext.impl;

import com.mayikt.ext.MayiktList;

import java.util.Arrays;

/**
 * @Description: 自定義Vector集合
 * @Author: ChenYi
 * @Date: 2020/06/11 08:19
 **/

public class MayiktVector<E> implements MayiktList<E> {
    protected int capacityIncrement;
    protected Object[] elementData;

    protected transient int modCount = 0;

    protected int elementCount;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public MayiktVector() {
        this(10);
    }

    public MayiktVector(int initialCapacity) {
        this(initialCapacity, 0);
    }

    public MayiktVector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                capacityIncrement : oldCapacity);
        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;
    }

    @Override
    public synchronized E get(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        return elementData(index);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

    @Override
    public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        E oldValue = elementData(index);

        int numMoved = elementCount - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        }
        elementData[--elementCount] = null;
        return oldValue;
    }
}

總結：

使用無參建構建立對象的時候預設建立容量為10的數組
存在擴容的原理，跟ArrayList一樣，隻是線程是安全的，在修改或者讀取資料的時候都加了synchronized關鍵字，效率很低，capacityIncrement沒有指定的時候，擴容預設是擴大一倍的

LinkeList源碼分析

自定義的LinkList類

package com.mayikt.ext.impl;

import com.mayikt.ext.MayiktList;

import java.util.Objects;

/**
 * @Description:自定義LinkList集合
 * @Author: ChenYi
 * @Date: 2020/06/20 09:11
 **/

public class MayiktLinkList<E> implements MayiktList<E> {
    transient int size = 0;
    transient MayiktLinkList.Node<E> first;
    transient MayiktLinkList.Node<E> last;
    protected transient int modCount = 0;

    public MayiktLinkList() {
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    private void linkLast(E e) {
        final MayiktLinkList.Node<E> l = last;
        final MayiktLinkList.Node<E> newNode = new MayiktLinkList.Node<>(l, e, null);
        last = newNode;
        if (l == null) {
            //連結清單的第一個元素
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
        modCount++;
    }

    @Override
    public E get(int index) throws Exception {
        checkElementIndex(index);
        return (E) node(index).item;
    }

    private MayiktLinkList.Node node(int index) {
        //采用折半查找
        MayiktLinkList.Node x;
        if (index <= size >> 1) {
            x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        } else {
            x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
        }
        return x;
    }

    private void checkElementIndex(int index) throws Exception {
        if (isElementIndex(index)) {
            return;
        }
        throw new Exception("數組越界!!!");
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    @Override
    public E remove(int index) throws Exception {
        checkElementIndex(index);
        return unlink(node(index));
    }

    private E unlink(Node current) {
        //要删除節點的上節點
        Object item = current.item;
        Node prev = current.prev;
        //要删除節點的下節點
        Node next = current.next;
        //說明删除的是第一個元素
        if (Objects.isNull(prev)) {
            first = next;
        } else {
            prev.next = next;
            //設定為空給垃圾回收
            current.prev = null;
        }
        //說明删除最後一個元素
        if (Objects.isNull(next)) {
            last = prev;
        } else {
            next.prev = prev;
            //設定為空給gc回收
            current.next = null;
        }
        //設定為空
        current.item = null;
        size--;
        modCount++;
        return (E) item;
    }

    private static class Node<E> {
        E item;
        MayiktLinkList.Node<E> next;
        MayiktLinkList.Node<E> prev;

        Node(MayiktLinkList.Node<E> prev, E element, MayiktLinkList.Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

總結：

底層是采用雙連結清單的資料結構來存儲資料的，底層采用了靜态内部類Node節點存放節點元素，包含指向上個節點的指針prev，目前的資料item,下個節點的指針next,連結清單是不需要擴容的，因為長度是可以不斷變化的，數組的資料結構才需要擴容
add原理是一直在連結清單之後添加
get的原理是采用折半查詢，查詢效率比較低，時間複雜度是O(n/2)
remove的原理是改變上下節點的指針

參考：來自螞蟻課堂

List集合源碼深度解析ArrayList源碼分析CopyOnWriteArrayList源碼分析Vector源碼解析LinkeList源碼分析

ArrayList源碼分析

CopyOnWriteArrayList源碼分析

Vector源碼解析

LinkeList源碼分析

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method