Java中ArrayList、Vector與Stack怎么用

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

ArrayList

ArrayList概述

ArrayList是實(shí)現(xiàn)List接口的動(dòng)態(tài)數(shù)組，所謂動(dòng)態(tài)就是它的大小是可變的。實(shí)現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實(shí)現(xiàn) List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲(chǔ)列表的數(shù)組的大小。

每個(gè)ArrayList實(shí)例都有一個(gè)容量，該容量是指用來存儲(chǔ)列表元素的數(shù)組的大小。默認(rèn)初始容量為10。隨著ArrayList中元素的增加，它的容量也會(huì)不斷的自動(dòng)增長。

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

注意，ArrayList實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè)ArrayList實(shí)例，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步。所以為了保證同步，最好的辦法是在創(chuàng)建時(shí)完成，以防止意外對(duì)列表進(jìn)行不同步的訪問：

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

ArrayList的繼承關(guān)系

ArrayList繼承AbstractList抽象父類，實(shí)現(xiàn)了List接口（規(guī)定了List的操作規(guī)范）、RandomAccess（可隨機(jī)訪問）、Cloneable（可拷貝）、Serializable（可序列化）。

底層數(shù)據(jù)結(jié)構(gòu)

ArrayList的底層是一個(gè)object數(shù)組，并且由trasient修飾。

//transient Object[] elementData; //

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

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

//總結(jié)一下就是只復(fù)制數(shù)組中有值的位置，其他未賦值的位置不進(jìn)行序列化，可以節(jié)省空間。

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

增刪改查

//增刪改查

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

這個(gè)方法無非就是使用System.arraycopy()方法將C集合(先準(zhǔn)換為數(shù)組)里面的數(shù)據(jù)復(fù)制到elementData數(shù)組中。這里就稍微介紹下System.arraycopy()，因?yàn)橄旅孢€將大量用到該方法

。該方法的原型為：

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

它的根本目的就是進(jìn)行數(shù)組元素的復(fù)制。即從指定源數(shù)組中復(fù)制一個(gè)數(shù)組，復(fù)制從指定的位置開始，到目標(biāo)數(shù)組的指定位置結(jié)束。

將源數(shù)組src從srcPos位置開始復(fù)制到dest數(shù)組中，復(fù)制長度為length，數(shù)據(jù)從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++;
//        }
//

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

//        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提供一個(gè)清空數(shù)組的辦法，方法是將所有元素置為null，這樣就可以讓GC自動(dòng)回收掉沒有被引用的元素了。

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

修改元素時(shí)，只需要檢查下標(biāo)即可進(jìn)行修改操作。

//        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方法，其實(shí)就是簡單地檢查下標(biāo)而已。

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

modCount

//        protected transient int modCount = 0;

由以上代碼可以看出，在一個(gè)迭代器初始的時(shí)候會(huì)賦予它調(diào)用這個(gè)迭代器的對(duì)象的mCount，如何在迭代器遍歷的過程中，一旦發(fā)現(xiàn)這個(gè)對(duì)象的mcount和迭代器中存儲(chǔ)的mcount不一樣那就拋異常

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

這一策略在源碼中的實(shí)現(xiàn)是通過 modCount 域，modCount 顧名思義就是修改次數(shù)，對(duì)ArrayList 內(nèi)容的修改都將增加這個(gè)值，那么在迭代器初始化過程中會(huì)將這個(gè)值賦給迭代器的 expectedModCount。

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

所以在這里和大家建議，當(dāng)大家遍歷那些非線程安全的數(shù)據(jù)結(jié)構(gòu)時(shí)，盡量使用迭代器

初始容量和擴(kuò)容方式

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

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

真正執(zhí)行擴(kuò)容的方法grow

擴(kuò)容方式是讓新容量等于舊容量的1.5被。

當(dāng)新容量大于最大數(shù)組容量時(shí)，執(zhí)行大數(shù)擴(kuò)容

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

當(dāng)新容量大于最大數(shù)組長度，有兩種情況，一種是溢出，拋異常，一種是沒溢出，返回整數(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;
}

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

處理這個(gè)ensureCapacity()這個(gè)擴(kuò)容數(shù)組外，ArrayList還給我們提供了將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小的功能。它可以通過trimToSize()方法來實(shí)現(xiàn)。該方法可以最小化ArrayList實(shí)例的存儲(chǔ)量。

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

線程安全

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

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

Vector

Vector簡介

Vector可以實(shí)現(xiàn)可增長的對(duì)象數(shù)組。與數(shù)組一樣，它包含可以使用整數(shù)索引進(jìn)行訪問的組件。不過，Vector的大小是可以增加或者減小的，以便適應(yīng)創(chuàng)建Vector后進(jìn)行添加或者刪除操作。

Vector實(shí)現(xiàn)List接口，繼承AbstractList類，所以我們可以將其看做隊(duì)列，支持相關(guān)的添加、刪除、修改、遍歷等功能。

Vector實(shí)現(xiàn)RandmoAccess接口，即提供了隨機(jī)訪問功能，提供提供快速訪問功能。在Vector我們可以直接訪問元素。

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

vector底層數(shù)組不加transient，序列化時(shí)會(huì)全部復(fù)制

 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枚舉方法，不過現(xiàn)在比較過時(shí)。

//        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的增刪改查既提供了自己的實(shí)現(xiàn)，也繼承了abstractList抽象類的部分方法。
下面的方法是vector自己實(shí)現(xiàn)的。

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

初始容量和擴(kuò)容

擴(kuò)容方式與ArrayList基本一樣，但是擴(kuò)容時(shí)不是1.5倍擴(kuò)容，而是有一個(gè)擴(kuò)容增量。

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

capacityIncrement：向量的大小大于其容量時(shí)，容量自動(dòng)增加的量。如果在創(chuàng)建Vector時(shí)，指定了capacityIncrement的大??；則，每次當(dāng)Vector中動(dòng)態(tài)數(shù)組容量增加時(shí)>，增加的大小都是capacityIncrement。如果容量的增量小于等于零，則每次需要增大容量時(shí)，向量的容量將增大一倍。

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

下面是擴(kuò)容過程示意圖

線程安全

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

Stack

我們最常用的數(shù)據(jù)結(jié)構(gòu)之一大概就是stack了。在實(shí)際的程序執(zhí)行，方法調(diào)用的過程中都離不開stack。那么，在一個(gè)成熟的類庫里面，它的實(shí)現(xiàn)是怎么樣的呢？也許平時(shí)我們實(shí)踐的時(shí)候也會(huì)嘗試著去寫一個(gè)stack的實(shí)現(xiàn)玩玩。這里，我們就仔細(xì)的分析一下jdk里的詳細(xì)實(shí)現(xiàn)。

Stack

如果我們?nèi)ゲ閖dk的文檔，我們會(huì)發(fā)現(xiàn)stack是在java.util這個(gè)包里。它對(duì)應(yīng)的一個(gè)大致的類關(guān)系圖如下：

通過繼承Vector類，Stack類可以很容易的實(shí)現(xiàn)他本身的功能。因?yàn)榇蟛糠值墓δ茉赩ector里面已經(jīng)提供支持了。

在Java中Stack類表示后進(jìn)先出（LIFO）的對(duì)象堆棧。棧是一種非常常見的數(shù)據(jù)結(jié)構(gòu)，它采用典型的先進(jìn)后出的操作方式完成的。

Stack通過五個(gè)操作對(duì)Vector進(jìn)行擴(kuò)展，允許將向量視為堆棧。這個(gè)五個(gè)操作如下：

empty()

測(cè)試堆棧是否為空。

peek()

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

pop()

移除堆棧頂部的對(duì)象，并作為此函數(shù)的值返回該對(duì)象。

push(E item)

把項(xiàng)壓入堆棧頂部。

search(Object o)

返回對(duì)象在堆棧中的位置，以 1 為基數(shù)。

Stack繼承Vector，他對(duì)Vector進(jìn)行了簡單的擴(kuò)展：

public class Stackextends Vector
 Stack的實(shí)現(xiàn)非常簡單，僅有一個(gè)構(gòu)造方法，五個(gè)實(shí)現(xiàn)方法（從Vector繼承而來的方法不算與其中），同時(shí)其實(shí)現(xiàn)的源碼非常簡單

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

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

三個(gè)集合類之間的區(qū)別

ArrayList的優(yōu)缺點(diǎn)

從上面的幾個(gè)過程總結(jié)一下ArrayList的優(yōu)缺點(diǎn)。ArrayList的優(yōu)點(diǎn)如下：
>

1、ArrayList底層以數(shù)組實(shí)現(xiàn)，是一種隨機(jī)訪問模式，再加上它實(shí)現(xiàn)了RandomAccess接口，因此查找也就是get的時(shí)候非?？?/p>

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

不過ArrayList的缺點(diǎn)也十分明顯：
>

1、刪除元素的時(shí)候，涉及到一次元素復(fù)制，如果要復(fù)制的元素很多，那么就會(huì)比較耗費(fèi)性能

2、插入元素的時(shí)候，涉及到一次元素復(fù)制，如果要復(fù)制的元素很多，那么就會(huì)比較耗費(fèi)性能

因此，ArrayList比較適合順序添加、隨機(jī)訪問的場(chǎng)景。

ArrayList和Vector的區(qū)別

ArrayList是線程非安全的，這很明顯，因?yàn)锳rrayList中所有的方法都不是同步的，在并發(fā)下一定會(huì)出現(xiàn)線程安全問題。那么我們想要使用ArrayList并且讓它線程安全怎么辦？一個(gè)方法是用Collections.synchronizedList方法把你的ArrayList變成一個(gè)線程安全的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));
}

另一個(gè)方法就是Vector，它是ArrayList的線程安全版本，其實(shí)現(xiàn)90%和ArrayList都完全一樣，區(qū)別在于：

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

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

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

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