在平時我們的工作中常用到的集合是ArrayList這個類，用來存儲元素。那除了ArrayList還有哪些集合類可以使用呢，ArrayList它的底層又是如何實現的？我們常說到的ArrayList查詢快、LinkedList增刪快到底怎么回事呢？

集合的體系結構

我這里用一張圖來表示常用的集合類體系

Vector和ArrayList、LinkedList聯系和區別,分別的使?用場景?

聯系和區別

• ArrayList: 底層是數組實現，所以查詢快、增刪慢，線程不安全的。
• LinkedList：底層是鏈表，所以增刪快、查詢慢，線程不安全的。
• Vector：底層是數組實現，是線程安全的，使用了synchronized

使用場景

• ArrayList：查詢居多
• LinkedList：增刪居多
• Vector：很少使用

如果需要保證線程安全，ArrayList應該怎么做，有?種?式？

• Collections.synchronizedList(List list); 使用了synchronized 關鍵字
• new CopeOnWriteArrayList(List list); 該類在concurrent包下 使用了 ReentrantLock 鎖

Collections.synchronizedList(List list);和new CopeOnWriteArrayList(List list);這倆種方案實現上有什么區別，使用場景是怎樣的？

• Collections.synchronizedList(List list); 線程中的每個方法加了synchronized 同步鎖，增刪性能好
• new CopeOnWriteArrayList(List list); 執行修改操作的時候（add、update、remove）會拷貝一份新的數組進行操作，等操作完畢之后新的數組會指向原來的數組，其中使用了ReentrantLock 保證了只有一個線程操作。 因為涉及到數組的拷貝，所以增刪慢讀的性能好

CopyOnWriteArrayList的設計思想是怎樣的,有什什么缺點？

• 讀寫分離+最終一致
• 內存占用問題，因為復制機制，會存在倆個對象的的內存，如果對象比較大會導致GC情況

public E set(int index, E element) {
        final ReentrantLock lock = this.lock;  //使用了ReentrantLock鎖
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len); //數組的拷貝
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

ArrayList的擴容機制

• 1.7之后初始化集合的時候，未指定的情況下0，在指定的情況下按照指定的
• 在未指定集合容量的情況下，初次擴容為10
• 當容量小于集合的個數需要再次擴容的時候按照 擴容大小=原始大小+原始大小/2

手寫簡單版ArrayList【需要包含 構造函數(有參和?無參)、add(obj)、 擴容機制】

public class MyArrayList implements Serializable {


    //使用這個字段，來判斷當前集合類是否被并發修改，即迭代器并發修改的fail-fast機制
    private transient int modCount = 0;

    //第一次擴容的容量
    private static final int DEFAULT_CAPACITY = 10;


    //用于初始化空的list
    private static final Object[] EMPTY_ELEMENT_DATA = {};


    //實際存儲的元素
    transient Object[] elementData;


    //實際list集合大小，從0開始
    private int size;


    public MyArrayList(){

        this.elementData = EMPTY_ELEMENT_DATA;
    }



    public MyArrayList(int initialCapcity){

        if(initialCapcity>0){
            this.elementData = new Object[initialCapcity];

        }else if(initialCapcity == 0){
            this.elementData = EMPTY_ELEMENT_DATA;

        }else {
            throw new IllegalArgumentException("參數異常");
        }

    }


    public boolean add(Object e){

        //判斷容量
        ensureCapacityInternal(size+1);

        //使用下標賦值，尾部插入
        elementData[size++] = e;

        return true;
    }


    //計算容量+確保容量
    private void ensureCapacityInternal(int minCapacity){

        //用于并發判斷
        modCount++;

        //如果是初次擴容，則使用默認的容量
        if(elementData == EMPTY_ELEMENT_DATA){
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        //是否需要擴容，需要的最少容量大于現在數組的長度則要擴容
        if(minCapacity - elementData.length > 0){
            int oldCapacity = elementData.length;

            int newCapacity = oldCapacity + (oldCapacity>>1);

            //如果新容量 < 最小容量， 則講最新的容量賦值給新的容量
            if(newCapacity - minCapacity < 0){
                newCapacity = minCapacity;
            }

            //創建新數組
            Object[] objects = new Object[newCapacity];

            //將舊的數組復制到新的數組里面
            System.arraycopy(elementData,0, objects,0,elementData.length);

            //修改引用
            elementData = objects;

        }

    }


    /**
     * 通過下標獲取對象
     * @param index
     * @return
     */
    public Object get(int index){
        rangeCheck(index);
        return elementData[index];

    }

    private void rangeCheck(int index){
        if(index > size || size < 0){
            throw  new IndexOutOfBoundsException("數組越界");
        }
    }


    /**
     * 判斷對象所在的位置
     * @param o
     * @return
     */
    public int indexOf(Object o){

        if(o == null){
            for(int i=0; i < size; i++){
                if(elementData[i] == null){
                    return i;
                }
            }
        }else {
            for(int i=0; i<size; i++){
                if(o.equals(elementData[i])){
                    return i;
                }
            }
        }

    return -1;
    }



    public Object set(int index, Object obj){
        rangeCheck(index);
        Object oldValue = elementData[index];
        elementData[index] = obj;
        return oldValue;
    }


    /**
     * 根據索引刪除元素
     * @param index
     * @return
     */
    public Object remove(int index){

        rangeCheck(index);

        //用于并發判斷
        modCount++;

        Object oldValue = elementData[index];

        //計算要刪除的位置后面有幾個元素
        int numMoved = size - index -1;

        if(numMoved>0){
            System.arraycopy(elementData,index+1,elementData,index,numMoved);
        }

        //將多出的位置為空，沒有引用對象，垃圾收集器可以回收，如果不為空，將會保存一個引用，可能會造成內存泄露
        elementData[--size] = null;

        return oldValue;
    }


    //獲取數組實際大小
    public int size(){
        return this.size;
    }


}

Set集合

核心就是不保存重復的元素，存儲一組唯一的對象set的每一種實現都是對應Map里面的一種封裝，HashSet對應的就是HashMap，treeSet對應的就是treeMap

public HashSet() {
        map = new HashMap<>();
    }

public TreeSet() {
        this(new TreeMap<E,Object>());
    }

關注我的技術公眾號alistarfeng，每周都有優質技術文章推送。

微信掃一掃下方二維碼即可關注：