Java中ArrayList、Vector與Stack怎么用

這篇文章主要為大家展示了“Java中ArrayList、Vector與Stack怎么用”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“Java中ArrayList、Vector與Stack怎么用”這篇文章吧。

ArrayList

ArrayList概述

ArrayList是實現List接口的動態數組，所謂動態就是它的大小是可變的。實現了所有可選列表操作，并允許包括 null 在內的所有元素。除了實現 List 接口外，此類還提供一些方法來操作內部用來存儲列表的數組的大小。

每個ArrayList實例都有一個容量，該容量是指用來存儲列表元素的數組的大小。默認初始容量為10。隨著ArrayList中元素的增加，它的容量也會不斷的自動增長。

在每次添加新的元素時，ArrayList都會檢查是否需要進行擴容操作，擴容操作帶來數據向新數組的重新拷貝，所以如果我們知道具體業務數據量，在構造ArrayList時可以給ArrayList指定一個初始容量，這樣就會減少擴容時數據的拷貝問題。當然在添加大量元素前，應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減少遞增式再分配的數量。

注意，ArrayList實現不是同步的。如果多個線程同時訪問一個ArrayList實例，而其中至少一個線程從結構上修改了列表，那么它必須保持外部同步。所以為了保證同步，最好的辦法是在創建時完成，以防止意外對列表進行不同步的訪問：

    List list = Collections.synchronizedList(new ArrayList(...));

ArrayList的繼承關系

ArrayList繼承AbstractList抽象父類，實現了List接口（規定了List的操作規范）、RandomAccess（可隨機訪問）、Cloneable（可拷貝）、Serializable（可序列化）。

底層數據結構

ArrayList的底層是一個object數組，并且由trasient修飾。

//transient Object[] elementData; //

non-private to simplify nested class access
//ArrayList底層數組不會參與序列化，而是使用另外的序列化方式。

//使用writeobject方法進行序列化,具體為什么這么做歡迎查看我之前的關于序列化的文章

//總結一下就是只復制數組中有值的位置，其他未賦值的位置不進行序列化，可以節省空間。

//        private void writeObject(java.io.ObjectOutputStream s)
//        throws java.io.IOException{
//            // Write out element count, and any hidden stuff
//            int expectedModCount = modCount;
//            s.defaultWriteObject();
//
//            // Write out size as capacity for behavioural compatibility with clone()
//            s.writeInt(size);
//
//            // Write out all elements in the proper order.
//            for (int i=0; i<size; i++) {
//                s.writeObject(elementData[i]);
//            }
//
//            if (modCount != expectedModCount) {
//                throw new ConcurrentModificationException();
//            }
//        }

增刪改查

//增刪改查

添加元素時，首先判斷索引是否合法，然后檢測是否需要擴容，最后使用System.arraycopy方法來完成數組的復制。

這個方法無非就是使用System.arraycopy()方法將C集合(先準換為數組)里面的數據復制到elementData數組中。這里就稍微介紹下System.arraycopy()，因為下面還將大量用到該方法

。該方法的原型為：

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)。

它的根本目的就是進行數組元素的復制。即從指定源數組中復制一個數組，復制從指定的位置開始，到目標數組的指定位置結束。

將源數組src從srcPos位置開始復制到dest數組中，復制長度為length，數據從dest的destPos位置開始粘貼。

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

刪除元素時，同樣判斷索引是否和法，刪除的方式是把被刪除元素右邊的元素左移，方法同樣是使用System.arraycopy進行拷貝。

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

ArrayList提供一個清空數組的辦法，方法是將所有元素置為null，這樣就可以讓GC自動回收掉沒有被引用的元素了。

//
//        /**
//         * Removes all of the elements from this list.  The list will
//         * be empty after this call returns.
//         */
//        public void clear() {
//            modCount++;
//
//            // clear to let GC do its work
//            for (int i = 0; i < size; i++)
//                elementData[i] = null;
//
//            size = 0;
//        }

修改元素時，只需要檢查下標即可進行修改操作。

//        public E set(int index, E element) {
//            rangeCheck(index);
//
//            E oldValue = elementData(index);
//            elementData[index] = element;
//            return oldValue;
//        }
//
//        public E get(int index) {
//            rangeCheck(index);
//
//            return elementData(index);
//        }
//

上述方法都使用了rangeCheck方法，其實就是簡單地檢查下標而已。

//        private void rangeCheck(int index) {
//            if (index >= size)
//                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//        }

modCount

//        protected transient int modCount = 0;

由以上代碼可以看出，在一個迭代器初始的時候會賦予它調用這個迭代器的對象的mCount，如何在迭代器遍歷的過程中，一旦發現這個對象的mcount和迭代器中存儲的mcount不一樣那就拋異常

好的，下面是這個的完整解釋
Fail-Fast 機制
我們知道 java.util.ArrayList 不是線程安全的，ArrayList，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。

這一策略在源碼中的實現是通過 modCount 域，modCount 顧名思義就是修改次數，對ArrayList 內容的修改都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount。

在迭代過程中，判斷 modCount 跟 expectedModCount 是否相等，如果不相等就表示已經有其他線程修改了 ArrayList。

所以在這里和大家建議，當大家遍歷那些非線程安全的數據結構時，盡量使用迭代器

初始容量和擴容方式

初始容量是10，下面是擴容方法。
首先先取

//        private static final int DEFAULT_CAPACITY = 10;
擴容發生在add元素時，傳入當前元素容量加一
   public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
這里給出初始化時的數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
這說明：如果數組還是初始數組，那么最小的擴容大小就是size+1和初始容量中較大的一個，初始容量為10。
因為addall方法也會調用該函數，所以此時需要做判斷。
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
//開始精確地擴容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
        如果此時擴容容量大于數組長度嗎，執行grow，否則不執行。
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

真正執行擴容的方法grow

擴容方式是讓新容量等于舊容量的1.5被。

當新容量大于最大數組容量時，執行大數擴容

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

當新容量大于最大數組長度，有兩種情況，一種是溢出，拋異常，一種是沒溢出，返回整數的最大值。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

在這里有一個疑問，為什么每次擴容處理會是1.5倍，而不是2.5、3、4倍呢？通過google查找，發現1.5倍的擴容是最好的倍數。因為一次性擴容太大(例如2.5倍)可能會浪費更多的內存(1.5倍最多浪費33%，而2.5被最多會浪費60%，3.5倍則會浪費71%……)。但是一次性擴容太小，需要多次對數組重新分配內存，對性能消耗比較嚴重。所以1.5倍剛剛好，既能滿足性能需求，也不會造成很大的內存消耗。

處理這個ensureCapacity()這個擴容數組外，ArrayList還給我們提供了將底層數組的容量調整為當前列表保存的實際元素的大小的功能。它可以通過trimToSize()方法來實現。該方法可以最小化ArrayList實例的存儲量。

public void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (size < oldCapacity) {
        elementData = Arrays.copyOf(elementData, size);
    }
}

線程安全

ArrayList是線程不安全的。在其迭代器iteator中，如果有多線程操作導致modcount改變，會執行fastfail。拋出異常。

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

Vector

Vector簡介

Vector可以實現可增長的對象數組。與數組一樣，它包含可以使用整數索引進行訪問的組件。不過，Vector的大小是可以增加或者減小的，以便適應創建Vector后進行添加或者刪除操作。

Vector實現List接口，繼承AbstractList類，所以我們可以將其看做隊列，支持相關的添加、刪除、修改、遍歷等功能。

Vector實現RandmoAccess接口，即提供了隨機訪問功能，提供提供快速訪問功能。在Vector我們可以直接訪問元素。

Vector 實現了Cloneable接口，支持clone()方法，可以被克隆。

vector底層數組不加transient，序列化時會全部復制

 protected Object[] elementData;
//        private void writeObject(java.io.ObjectOutputStream s)
//            throws java.io.IOException {
//            final java.io.ObjectOutputStream.PutField fields = s.putFields();
//            final Object[] data;
//            synchronized (this) {
//                fields.put("capacityIncrement", capacityIncrement);
//                fields.put("elementCount", elementCount);
//                data = elementData.clone();
//            }
//            fields.put("elementData", data);
//            s.writeFields();
//        }

Vector除了iterator外還提供Enumeration枚舉方法，不過現在比較過時。

//        public Enumeration<E> elements() {
//            return new Enumeration<E>() {
//                int count = 0;
//
//                public boolean hasMoreElements() {
//                    return count < elementCount;
//                }
//
//                public E nextElement() {
//                    synchronized (Vector.this) {
//                        if (count < elementCount) {
//                            return elementData(count++);
//                        }
//                    }
//                    throw new NoSuchElementException("Vector Enumeration");
//                }
//            };
//        }
//

增刪改查

vector的增刪改查既提供了自己的實現，也繼承了abstractList抽象類的部分方法。
下面的方法是vector自己實現的。

//
//    public synchronized E elementAt(int index) {
//        if (index >= elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
//        }
//
//        return elementData(index);
//    }
//
//
//    public synchronized void setElementAt(E obj, int index) {
//        if (index >= elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index + " >= " +
//                    elementCount);
//        }
//        elementData[index] = obj;
//    }
//
//    public synchronized void removeElementAt(int index) {
//        modCount++;
//        if (index >= elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index + " >= " +
//                    elementCount);
//        }
//        else if (index < 0) {
//            throw new ArrayIndexOutOfBoundsException(index);
//        }
//        int j = elementCount - index - 1;
//        if (j > 0) {
//            System.arraycopy(elementData, index + 1, elementData, index, j);
//        }
//        elementCount--;
//        elementData[elementCount] = null; /* to let gc do its work */
//    }
//    public synchronized void insertElementAt(E obj, int index) {
//        modCount++;
//        if (index > elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index
//                    + " > " + elementCount);
//        }
//        ensureCapacityHelper(elementCount + 1);
//        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
//        elementData[index] = obj;
//        elementCount++;
//    }
//
//    public synchronized void addElement(E obj) {
//        modCount++;
//        ensureCapacityHelper(elementCount + 1);
//        elementData[elementCount++] = obj;
//    }

初始容量和擴容

擴容方式與ArrayList基本一樣，但是擴容時不是1.5倍擴容，而是有一個擴容增量。

//    protected int elementCount;
//    protected int capacityIncrement;
//
//
//    }
//    public Vector() {
//        this(10);
//    }

capacityIncrement：向量的大小大于其容量時，容量自動增加的量。如果在創建Vector時，指定了capacityIncrement的大小；則，每次當Vector中動態數組容量增加時>，增加的大小都是capacityIncrement。如果容量的增量小于等于零，則每次需要增大容量時，向量的容量將增大一倍。

//        public synchronized void ensureCapacity(int minCapacity) {
//            if (minCapacity > 0) {
//                modCount++;
//                ensureCapacityHelper(minCapacity);
//            }
//        }
//        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);
//        }

下面是擴容過程示意圖

線程安全

vector大部分方法都使用了synchronized修飾符，所以他是線層安全的集合類。

Stack

我們最常用的數據結構之一大概就是stack了。在實際的程序執行，方法調用的過程中都離不開stack。那么，在一個成熟的類庫里面，它的實現是怎么樣的呢？也許平時我們實踐的時候也會嘗試著去寫一個stack的實現玩玩。這里，我們就仔細的分析一下jdk里的詳細實現。

Stack

如果我們去查jdk的文檔，我們會發現stack是在java.util這個包里。它對應的一個大致的類關系圖如下：

通過繼承Vector類，Stack類可以很容易的實現他本身的功能。因為大部分的功能在Vector里面已經提供支持了。

在Java中Stack類表示后進先出（LIFO）的對象堆棧。棧是一種非常常見的數據結構，它采用典型的先進后出的操作方式完成的。

Stack通過五個操作對Vector進行擴展，允許將向量視為堆棧。這個五個操作如下：

empty()

測試堆棧是否為空。

peek()

查看堆棧頂部的對象，但不從堆棧中移除它。

pop()

移除堆棧頂部的對象，并作為此函數的值返回該對象。

push(E item)

把項壓入堆棧頂部。

search(Object o)

返回對象在堆棧中的位置，以 1 為基數。

Stack繼承Vector，他對Vector進行了簡單的擴展：

public class Stackextends Vector
 Stack的實現非常簡單，僅有一個構造方法，五個實現方法（從Vector繼承而來的方法不算與其中），同時其實現的源碼非常簡單

/**
 * 構造函數
 */
public Stack() {
}
/**
 *  push函數：將元素存入棧頂
 */
public E push(E item) {
    // 將元素存入棧頂。
    // addElement()的實現在Vector.java中
    addElement(item);
    return item;
}
/**
 * pop函數：返回棧頂元素，并將其從棧中刪除
 */
public synchronized E pop() {
    E    obj;
    int    len = size();
    obj = peek();
    // 刪除棧頂元素，removeElementAt()的實現在Vector.java中
    removeElementAt(len - 1);
    return obj;
}
/**
 * peek函數：返回棧頂元素，不執行刪除操作
 */
public synchronized E peek() {
    int    len = size();
    if (len == 0)
        throw new EmptyStackException();
    // 返回棧頂元素，elementAt()具體實現在Vector.java中
    return elementAt(len - 1);
}
/**
 * 棧是否為空
 */
public boolean empty() {
    return size() == 0;
}
/**
 *  查找“元素o”在棧中的位置：由棧底向棧頂方向數
 */
public synchronized int search(Object o) {
    // 獲取元素索引，elementAt()具體實現在Vector.java中
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

Stack的源碼很多都是基于Vector，所以這里不再累述

三個集合類之間的區別

ArrayList的優缺點

從上面的幾個過程總結一下ArrayList的優缺點。ArrayList的優點如下：
>

1、ArrayList底層以數組實現，是一種隨機訪問模式，再加上它實現了RandomAccess接口，因此查找也就是get的時候非常快

2、ArrayList在順序添加一個元素的時候非常方便，只是往數組里面添加了一個元素而已

不過ArrayList的缺點也十分明顯：
>

1、刪除元素的時候，涉及到一次元素復制，如果要復制的元素很多，那么就會比較耗費性能

2、插入元素的時候，涉及到一次元素復制，如果要復制的元素很多，那么就會比較耗費性能

因此，ArrayList比較適合順序添加、隨機訪問的場景。

ArrayList和Vector的區別

ArrayList是線程非安全的，這很明顯，因為ArrayList中所有的方法都不是同步的，在并發下一定會出現線程安全問題。那么我們想要使用ArrayList并且讓它線程安全怎么辦？一個方法是用Collections.synchronizedList方法把你的ArrayList變成一個線程安全的List，比如：

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
    System.out.println(synchronizedList.get(i));
}

另一個方法就是Vector，它是ArrayList的線程安全版本，其實現90%和ArrayList都完全一樣，區別在于：

1、Vector是線程安全的，ArrayList是線程非安全的

2、Vector可以指定增長因子，如果該增長因子指定了，那么擴容的時候會每次新的數組大小會在原數組的大小基礎上加上增長因子；如果不指定增長因子，那么就給原數組大小*2，源代碼是這樣的：

int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                 capacityIncrement : oldCapacity);

以上是“Java中ArrayList、Vector與Stack怎么用”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！