1.2　List集合實現——Vector

java.util.Vector集合是從Java早期版本（從JDK 1.0開始）就開始提供的一種List集合，其主要的繼承體系如圖1-8所示。

根據圖1-8可知，Vector集合是支持隨機訪問的，該特性在1.1節中已經進行了講解，這里不再贅述。Vector集合的工作特性除了支持數據對象的隨機訪問，還有集合的大小可變、保證線程安全的運行環境等。

下面對Vector集合中的典型操作進行詳細介紹（注意源碼版本為JDK 9+，直到JDK 14官方都未對該源碼進行調整）。首先介紹存在于Vector集合（及其上級AbstractList類）中的重要變量信息，源碼如下。

根據對以上3個重要變量的描述可知，Vector集合的基本結構包括一個數組、一個指向當前數組的可驗證邊界、一個數組擴容的參考值，如圖1-9所示。

在Vector集合中，elementCount變量非常重要，它在Vector集合進行寫性質操作時會發生變化。elementCount變量的值可以小于elementData數組的容量值（使用capacity()方法可獲取當前數組的容量值），也可以和elementData數組的容量值相等。當elementData數組中的每個索引位上都添加了數據對象時，可以將這些數據對象設置為null。

1.2.1　Vector集合的擴容操作

1. 什么時候擴容

Vector集合需要進行擴容操作的情況有多種。Vector集合在初始化時會進行擴容操作，它的elementData數組會進行初始化；在Vector集合中，當數據對象數量elementCount的值大于elementData數組的最大容量capacity的值時，也會進行擴容操作，這時，elementData數組中的數據對象會被復制到另一個更大的數組中，并且elementData數組變量的引用會重新指向后者；當Vector集合的調用者明確要求重新確認集合容量時，也可能會進行擴容操作。

1）在初始化Vector集合時，擴容過程的詳細源碼如下。

上述3個構造方法的執行過程和關聯關系一目了然，不需要再做過多說明。根據上述源碼片段可知，如果沒有在Vector集合初始化時指定集合的初始化容量（initialCapacity），則會將初始化容量值設置為10；如果沒有在Vector集合初始化時指定擴容增量（capacityIncrement），則會將擴容增量值設置為0。如果擴容增量值被設置成了0，那么在隨后進行的每次擴容操作中，elementData數組擴容后的容量都會變為擴容前容量的2倍，即10->20->40->80……以此類推。

2）在當前Vector集合中的數據對象總量超出數組容量上限時，會進行擴容操作。

以Vector集合中的add(E)方法為例，源碼片段如下。

add()方法的操作過程分為以下兩種情況。

? 當集合中對象數據數量elementCount的值小于當前elementData數組容量的值時，不必對elementData數組進行擴容操作，直接在elementData數組中的elementCount號索引位上添加新的數據對象即可。

? 當集合中數據對象數量elementCount的值大于或等于elementData數組容量的值時，需要先對elementData數組進行擴容操作，再在elementCount號索引位上添加新的數據對象。

3）當調用者明確要求重新確認Vector集合容量時，也可能會進行擴容操作。例如，Vector集合中的setSize(int)方法允許調用者重新為Vector集合設置一個容量值，如果這個容量值大于當前Vector集合的容量值，則會進行擴容操作；如果新的容量值小于當前容量值，則會將多余的數據對象丟棄，源碼片段如下。

注意：在特定的場景中，可以減小Vector集合的數組容量（縮容）。可查看Vector集合中的trimToSize() 方法。

2. 詳細的擴容過程

根據前面的源碼可知，Vector集合進行擴容操作的主要方法是grow(int)方法，所以我們主要對這個方法進行分析（在JDK 14中，該方法已經簡化，更容易理解），源碼如下。

根據上述源碼可知，如果當前Vector集合沒有在實例化時指定增量capacityIncrement的值，那么在一般情況下，每次擴容增加的容量都是當前容量的1倍；如果當前Vector集合在實例化時指定了增量capacityIncrement的值，那么在一般情況下，會按照指定的增量capacityIncrement的值進行擴容操作。

下面重點講解一下Arrays.copyOf()方法和ArraysSupport.newLength()方法。

1）Arrays.copyOf(T[] original, int newLength)方法。

該方法是一個工具性質的方法，主要用于將原始數組（original）復制為一個新的數組，后者的長度為指定的新長度（newLength）。

按照這樣的描述，對于指定的新長度（newLength），會出現以下兩種情況。

? 指定的新長度（newLength）小于原始數組（original）的長度，那么原始數組（original）無法復制的部分會被拋棄。

? 指定的新長度（newLength）大于或等于原始數組（original）的長度，那么原始數組（original）中的所有數據對象（的引用）會按照原來的索引位被依次復制到新的數組中，新數組中多出來的空余部分會被填充為null，如圖1-10所示。

圖1-10中不包括新長度（newLength）無效的情況。例如，當newLength的值為負數時，Arrays.copyOf(T[] original, int newLength)方法會拋出java.lang.NegativeArraySizeException異常。有的讀者會問，當newLength的值為0時，會出現什么情況？這種情況滿足以上描述的第一種情況——沒有任何數據對象可以填充，所以會輸出一個空數組。

此外，圖1-10中也不包括對Java基礎類型數組（int[]、long[]、float[]等）進行復制的場景。在這些基礎類型數組的復制過程中，新數組中多余的位置上會填充這個基礎類型的默認值。例如，在int[]數組的復制過程中，新數組中多余的位置上會被填充“0”。

2）ArraysSupport.newLength(int oldLength, int minGrowth, int prefGrowth)方法。

該方法同樣是一個工具性質的方法，主要用于幫助數組在擴容前在不同的場景中找到新的數組容量，并且防止新的數組容量超過系統規定的數組容量上限。該方法的參數如下。

? oldLength：擴容前的數組容量。

? minGrowth：最小的容量增量（必須為正數）。

? prefGrowth：常規的容量增量，該值需要大于minGrowth的值，否則會被忽略。

在計算擴容后數組容量的過程中，如果prefGrowth的值大于minGrowth的值，則以prefGrowth的值計算擴容后的新容量，否則以minGrowth的值計算擴容后的新容量。

如果計算得到的新容量大于系統規定的數組容量上限（使用MAX_ARRAY_LENGTH常量表示，在64位Windows操作系統中該值為2 147 483 639），則需要進行容量限制處理（在實際工作中很少出現這樣的情況，但必須考慮到）。

在進行容量限制處理時，如果通過minGrowth（最小容量增加值）計算得到的新容量值小于常量MAX_ARRAY_LENGTH的值，則返回常量MAX_ARRAY_LENGTH的值，否則返回Integer.MAX_VALUE的值。

1.2.2　Vector集合的修改方法——set(int, E)

set(int, E)方法主要用于在指定索引位上設置新的數據對象，設置的數據對象可以為null。該方法有兩個參數，第一個參數為int型數據，表示索引位；第二個參數為需要在這個索引位上設置的新的數據對象。

set(int, E)方法有以下幾個關鍵點。

? 可以指定索引位的有效范圍上限。不是依據當前Vector集合中elementData數組大小的值，而是依據當前Vector集合中存在的數據量elementCount的值（elementCount的值在Vector集合中的另一個含義就是Vector集合的大小）。

? 該方法有一個返回值，這個返回值會向調用者返回指定索引位上變更之前的值。

1.2.3　Vector集合的刪除方法——removeElementAt(int)

removeElementAt(int)方法主要用于移除Vector集合中elementData數組指定索引位上的數據對象，并且改變其索引位的指向。在操作者看來，這個操作可以成功移除X號索引位上的數據對象（X<elementCount），并且在操作成功后，操作者雖然依舊可以通過X號索引位取得數據對象（X<elementCount），但此時取得的是與原數據對象緊鄰的數據對象，如圖1-11所示。

圖1-11展示了removeElementAt(int)方法的運行實質：以當前指定的索引位為起點，將后續數據對象的索引位依次向前移動。該方法的源碼如下。

首先講解上述源碼中的System.arraycopy(Object src, int srcPos, Object dest, int destPos,int length)方法。該方法是一種JNI native方法，是JDK提供的用于進行兩個數組中數據對象復制的性能最好的方法之一。該方法的參數如下。

? src：該參數只能傳入數組，表示當前進行數組復制的源數組。

? srcPos：表示在源數組中進行復制操作的起始位置。

? dest：該參數同樣只能傳入數組，表示當前進行數組復制的目標數組。

? destPos：表示在目標數組中進行復制操作的起始位置。

? length：用于指定進行復制操作的長度。

上述源碼使用System.arraycopy()方法的意圖如圖1-12所示。

在圖1-12中，雖然完成了數組自身的數據移動，但這時數組中最后一個索引位上的數據對象并沒有改變，所以需要手動減小數組中的數據值，并且手動設置最后一個索引位上的數據對象為null。所以上述源碼中會出現如下內容。

讀者應該已經注意到了，源碼片段中多次出現對elementCount變量的操作，這個變量實際上對CAS思想進行了借鑒，本書將在后續相關章節進行介紹。