天天看點
傳回

瘋狂Java講義-Java集合Java集合

Java集合

本章思維導圖

瘋狂Java講義-Java集合Java集合

Java集合概述

為了儲存數量不确定的資料，以及儲存具有映射關系的資料（也被稱為關聯數組），Java提供了集合類。集合類主要負責儲存、盛裝其他資料，是以集合類也被稱為容器類。

集合和數組不一樣，數組元素既可以是基本類型的值，也可以是對象（實際上儲存的是對象的引用變量）；而集合裡隻能儲存對象（實際上隻是儲存對象的引用變量）。

Java的集合類主要由兩個接口派生而出：Collection和Map，Collection和Map是Java集合架構的根接口，這兩個接口又包含了一些子接口或實作類。

Set和List接口是Collection接口派生出的兩個子接口，它們分别代表了無序集合和有序集合；Queue是java提供的隊列實作，類似于List。

Map實作類用于儲存具有映射關系的資料（關聯數組）；Map儲存的每項資料都是

key-value

對；Map裡的key是不可重複的，key用于辨別集合裡的每項資料。

可以把Java所有集合分成三大類

  • Set

     ：把一個對象添加到Set集合時，Set集合無法記住添加這個元素的順序，是以Set裡的元素不能重複。

  • List

     ：非常像一個數組，它可以記住每次添加元素的順序、且List的長度可變。

  • Map

     ：也像一個罐子，隻是它裡面的每項資料都由兩個值組成。

Collection和Iterator接口

Collection體系圖

瘋狂Java講義-Java集合Java集合

Collection接口是List、Set和Queue接口的父接口，該接口裡定義的方法既可以用于操作Set集合，也可用于操作List和Queue集合。

Collection接口裡定義了如下操作集合元素的方法：

  • boolean add(Object o)

     :該方法用于向集合裡添加一個元素。如果集合對象被添加操作改變了，則傳回true。

  • boolean addAll(Collection c)

     :該方法把集合c裡的所有元素添加到指定集合裡。如果集合對象被添加操作改變了，則傳回true。

  • void clear()

     :清除集合裡的所有元素，将集合長度變為0.

  • boolean contains(Object o)

     :傳回集合裡是否包含指定元素。

  • boolean containsAll(Collection c)

     :傳回集合裡是否包含集合c裡的所有元素。

  • boolean isEmpty()

     :傳回集合是否為空。當集合長度為0時傳回true，否則傳回false。

  • Iterator iterator()

     :傳回一個Iterator對象，用于周遊集合裡的元素。

  • boolean remove(Object o)

     :删除集合中指定元素o，當集合中包含了一個或多個元素o時，該方法隻删除第一個符合條件的元素，該方法将傳回true。

  • boolean removeAll(Collection c)

     :從集合中删除集合c裡包含的所有元素（相當于調用該方法的集合減集合c），如果删除了一個或一個以上的元素，則該方法傳回true。

  • boolean retainAll(Collection c)

     :從集合中删除集合c裡不包含的元素（相當于把調用該方法的集合變成該集合和集合c的交集），如果該操作改變了調用該方法的集合，則該方法傳回true。

  • int size()

     :該方法傳回集合裡元素的個數。

  • Object[] toArray()

     :該方法把集合轉換成一個數組，所有的集合元素變成對應的數組元素。

使用Lambda表達式周遊集合

Java8為Iterable接口新增了一個

forEach(Consumer action)

預設方法，該方法所需參數的類型是一個函數式接口，而Iterable接口是Collection接口的父接口，是以Collection集合也可直接調用該方法。

當程式調用Iterable的

forEach(Consumer action)

周遊集合時，程式會依次将集合元素傳給Consumer的

accept(T t)

方法（該接口中唯一的抽象方法）。正因為Consumer是函數式接口，是以可以使用Lambda表達式來周遊集合元素。

使用Java8增強的Iterator周遊集合元素

Iterator接口也是Java集合架構的成員，但它與Collection系列、Map系列的集合不一樣：Collection系列集合、Map系列集合主要用于盛裝其他對象，而Iterator則主要用于周遊（即疊代通路）Collection集合中的元素，Iterator對象也被稱為疊代器。

Iterator接口隐藏了各種Collection實作類的底層細節，向應用程式提供了周遊Collection集合元素的統一程式設計接口。

Iterator接口裡定義了如下4個方法：

  • boolean hasNext()

     :如果被疊代的集合元素還沒有被周遊完，則傳回true。

  • Object next()

     :傳回集合裡的下一個元素。

  • void remove()

     :删除集合裡的上一次next方法傳回的元素。

  • void forEachRemainning(Consumer action)

     :這是Java8為Iterator新增的預設方法，該方法可使用Lambda表達式來周遊集合元素。

Iterator必須依附于Collection對象，若有一個Iterator對象，則必然有一個與之關聯的Collection對象。

當使用Iterato疊代通路Collection集合時，Collection集合裡的元素不能被改變，隻能通過Iterator的

remove()

方法删除上一次

next()

方法傳回的集合元素才可以；否則将會引發

java.util.ConcurrentModificationException

異常。

Iterator疊代器采用的是**快速失敗（fail-fast）**機制，一旦在疊代過程中檢測到該集合已經被修改（通常是程式中的其他線程修改），程式立即引發

ConcurrentModificationException

異常，而不是顯示修改後的結果，這樣可以避免共享資源而引發的潛在問題。

使用Lambda表達式周遊Iterator

Java8起為Iterator接口新增了一個

forEachRemaining(Consumer action)

方法，該方法所需的Consumer參數同樣也是函數式接口。當程式調用Iterator的

forEachRemaining(Consumer action)

周遊集合元素時，程式會依次将集合元素傳給Consumer的

accept(T t)

方法（該接口中唯一的抽象方法）。

使用foreach循環周遊集合元素

除可以使用Iterator接口疊代通路Collection集合裡的元素之外，使用Java5提供的foreach循環疊代通路集合元素更加便捷。

與使用Ierator接口疊代通路集合元素類似的是，foreach循環中的疊代變量也不是集合元素本身，系統隻是依次把集合元素的值賦給疊代變量。

同樣，當使用foreach循環疊代通路集合元素時，該集合也不能被改變，否則将引發

ConcurrentModificationException

異常。

使用Java8新增的Predicate操作集合

Java8起為Collection集合新增了一個

removeIf(Predicate filter)

方法，該方法将會批量删除符合filter條件的所有元素。該方法需要一個Predicate謂詞對象作為參數，Predicate也是函數式接口，是以可使用Lambda表達式作為參數。

使用Java8新增的Stream操作集合

Java8還新增了Stream、IntStream、LongStream、DoubleStream等流式API，這些API代表多個支援串行和并行聚集操作的元素。Stream是一個通用的流接口，而IntStream、LongStream、DoubleStream則代表元素為int、long、double的流。

Java8還為上面的每個流式API提供了對應的Builder，例如Stream.Builder、IntStream.Builder、LongStream.Builder、DoubleStream.Builder，開發者可以通過這些Builder來建立對應的流。

獨立使用Stream的步驟如下：

  1. 使用Stream或XxxStream的

    builder()

     類方法建立該Stream對應Builder。
  2. 重複調用Builder的add()方法向該流中添加多個元素。
  3. 調用Builder的build()方法擷取對應的Stream。
  4. 調用Stream的聚集方法。

Stream提供了大量的方法進行聚集操作，這些方法既可以是中間的（intermediate），也可以是末端的（terminal）。

中間方法：中間操作允許流保持打開狀态，并允許直接調用後繼方法。

末端方法：末端方法是對流的最終操作。當某個Stream執行末端方法後，該流将會被消耗且不可再用。

除此之外，關于流的方法好有如下兩個特征：

  • 有狀态的方法：這種方法會給流增加一些新的屬性，比如元素的唯一性、元素的最大數量、保證元素以排序的方式被處理等。有狀态的方法往往需要更大的性能開銷。
  • 短路方法：短路方法可以盡早結束對流的操作，不必檢查所有的元素。

Stream常用的中間方法：

  • filter(Predicate predicate)

     :過濾Stream中所有不符合predicate的元素。

  • mapToXxx(ToXxxFunction mapper)

     :使用ToXxxFunction對流中的元素執行一對一的轉換，該方法傳回新流中包含了ToXxxFunction轉換生成的所有元素。

  • peek(Consumer action)

     :依次對每個元素執行一些操作，該方法傳回的流與原有流包含相同的元素。該方法主要用于調試。

  • distinct()

     :該方法用于排序流中所有重複的元素（判斷元素重複的标準是使用

    equals()

     比較傳回true)。這是一個有狀态的方法。

  • sorted()

     :該方法用于保證流中的元素在後繼的通路中處于有序狀态。這是一個有狀态的方法。

  • limit(long maxSize)

     :該方法用于保證對該流的後繼通路中最大允許通路的元素個數。這是一個有狀态的、短路方法。

Stream常用的末端方法：

  • forEach(Consumer action)

     :周遊流中所有元素，對每個元素執行action。

  • toArray()

     :将流中所有元素轉換為一個數組。

  • reduce()

     :該方法有三個重載的版本，都用于通過某種操作來合并流中的元素。

  • max()

     :傳回流中所有元素的最大值。

  • count()

     :傳回流中所有元素的數量。

  • anyMatch(Predicate predicate)

     :判斷流中是否至少包含一個元素符合Predicate條件。

  • allMatch(Predicate predicate)

     :判斷流中是否每個元素都符合Predicate條件。

  • noneMatch(Predicate predicate)

     :判斷流中是否所有元素都不符合Predicate條件。

  • findFirst()

     :傳回流中的第一個元素。

  • findAny()

     :傳回流中的任意一個元素。

Java8允許使用流式API來操作集合，Collection接口提供了一個

stream()

預設方法，該方法傳回該集合對應的流，接下來就即可通過流式API來操作集合元素。由于Stream可以對集合元素進行整體的聚集操作，是以Stream極大地豐富了集合的功能。

Set集合

Set集合與Collection基本相同，沒有提供任何額外的方法。實際上Set就是Collection，隻是行為略有不同（Set不允許包含重複元素）。

Set集合不允許包含相同的元素，如果試圖把兩個相同的元素加入同一個Set集合中，則添加操作失敗，add()方法傳回false，且新元素不會被加入。

HashSet類

HashSet是Set接口的典型實作，大多數時候使用Set集合時就是使用這個實作類。HashSet按Hash算法來存儲集合中的元素，是以具有很好的存取和查找性能。

HashSet具有以下特點：

  • 不能保證元素的排列順序，順序可能與添加順序不同，順序也有可能發生變化。
  • HashSet是不同步的，如果多個線程同時通路一個HashSet，假設有兩個或兩個以上線程同時修改了HashSet集合時，則必須通過代碼來保證其同步。
  • 集合元素值可以是null。

當向HashSet集合中存入一個元素時，HashSet會調用該對象的

hashCode()

方法來得到該對象的hashCode值，然後根據該hashCode值決定該對象在HashSet中的存儲位置。

如果兩個元素通過

equals()

方法比較傳回true，但它們的

hashCode()

方法傳回值不相等，HashSet将會把它們存儲到不同的位置，依然可以添加成功。

也就是說，HashSet集合判斷兩個元素相等的标準是兩個對象通過

equals()

方法比較相等，并且兩個對象的

hashCode()

方法傳回值也相等。

當把一個對象放入HashSet中時，如果需要重寫該對象對應類的

equals()

方法，則也應該重寫其

hashCode()

方法。規則是：如果兩個對象通過

equals()

方法比較傳回true，這兩個對象的hashCode值也應該相同。

如果兩個對象通過

equals()

方法比較傳回true，但這兩個對象的

hashCode()

方法傳回不同的hashCode值時，這将導緻HashSet會把這兩個對象儲存在Hash表的不同位置，進而使兩個對象都可以添加成功，這就與Set集合規則沖突了。

如果兩個對象的

hashCode()

方法傳回相同的hashCode值，但它們通過

equals()

方法比較傳回false時将更麻煩：因為兩個對象的hashCode值相同，HashSet将試圖把他們儲存到同一個位置，但又不行（否則将隻剩下一個對象），所及實際上會在這個位置用鍊式結構來儲存多個對象；而HashSet通路集合元素時也是根據元素的hashCode來快速定位的，如果HashSet中兩個以上的元素具有相同的hashCode值，将會導緻性能下降。

HashSet中每個能存儲元素的槽位（slot）通常稱為桶（bucket），如果有多個元素的hashCode值相同，但它們通過

equals()

方法比較傳回false，就需要在一個“桶”裡放多個元素，這樣會導緻性能下降。

重寫hashCode()方法的基本規則：

  • 在程式運作過程中，同一個對象多次調用

    hashCode()

     方法應該傳回相同的值。
  • 當兩個對象通過

    equals()

     方法比較傳回true時，這兩個對象的

    hashCode()

     方法應該傳回相等的值。
  • 對象中用作

    equals()

     方法比較标準的執行個體變量，都應該用于計算hashCode值。

重寫hashCode()方法的一般步驟：

  1. 把對象内每個有意義的執行個體變量（即每個參與

    equals()

     方法比較标準的執行個體變量）計算出一個int類型的hashCode值。
  • hashCode值的計算方式：
    • boolean:

      hashCode = (f ? 0 : 1);
    • (byte、short、char、int):

      hashCode = (int)f;
    • long:

      hashCode = (int)(f >>> 32));
    • float:

      hashCode = Float.floatToIntBits(f);
    • double:

      long l = Double.doubleToLongBits(f); hashCode = (int)(l ^ (l >>> 32));
    • 引用類型:

      hashCode = f.hashCode();
  1. 用第1步計算出的多個hashCode值組合計算除一個hashCode值傳回。

為了避免直接相加産生偶然相等（兩個對象的f1、f2執行個體變量并不相等，但它們的hashCode的和恰好相等），可以通過為各執行個體變量的hashCode值乘以任意一個質數後再相加。

如果向HashSet中添加一個可變對象後，後面程式修改了該可變對象的執行個體變量，則可能導緻它與集合中的其他元素相同，這就有可能導緻HashSet中包含兩個相同的對象。

當程式把可變對象添加到HashSet中之後，盡量不要去修改該集合元素中參與計算的

hashCode()

、

equals()

的執行個體變量，否則将會導緻HashSet無法正确操作這些集合元素。

當向HashSet中添加可變對象時，必須十分小心。如果修改HashSet集合中的對象，有可能導緻該對象與集合中的其他對象相等，進而導緻HashSet無法精确通路該對象。

LinkedHashSet類

HashSet類還有一個子類LibkedHashSet，LinkedHashSet集合也是根據元素的hashCode值來決定元素的存儲位置，但它同時使用連結清單維護元素的次序，當周遊LinkedHashSet集合裡的元素時，LinkedHashSet将會按元素的添加順序來通路集合裡的元素。

LinkedHashSet需要維護元素的插入順序，是以性能略低于HashSet性能，但在疊代通路Set裡的全部元素時将有很好的性能，是以它以連結清單來維護内部順序。

TreeSet類

TreeSet是SortedSet接口的實作類，TreeSet可以確定集合元素處于排序狀态。與HashSet集合相比，TreeSet還提供了如下幾個額外的方法：

  • Comparator comparator()

     :如果TreeSet采用了定制排序，則該方法傳回定制排序所使用的Comparator；如果TreeSet采用了自然排序，則傳回null。

  • Object first()

     :傳回集合中的第一個元素。

  • Object last()

     :傳回集合中的最後一個元素。

  • Object lower(Object e)

     :傳回集合中位于指定元素之前的元素（即小于指定元素的最大元素，參考元素不需要是TreeSet集合裡的元素）。

  • Object higher(Object e)

     :傳回集合中位于指定元素之後的元素（即大于指定元素的最大元素，參考元素不需要是TreeSet集合裡的元素）。

  • SortedSet subSet(Object fromElement, Object toElement)

     :傳回此Set的子集合，範圍從fromElement（包含）到toElement（不包含）。

  • SortedSet headSet(Object toElement)

     :傳回此Set集合的子集，由小于toElement的元素組成。

  • SortedSet tailSet(Object fromElement)

     :傳回此Set的子集，由大于或等于fromElement的元素組成。

TreeSet并不是根據元素的插入順序進行排序，而是根據元素實際值的大小進行排序的。

HashSet集合采用hash算法來決定元素的存儲位置不同，TreeSet采用紅黑樹的資料結構來存儲集合的元素。

TreeSet支援兩種排序方式：自然排序和定制排序。預設情況下，TreeSet采用自然排序。

自然排序

TreeSet會調用集合元素的

compareTo(Object obj)

方法來比較元素之間的大小關系，然後将集合元素升序排序。

Java提供了一個Comparable接口，該接口裡定義了一個

compareTo(Object obj)

方法，該方法傳回一個整數值，實作該接口的類必須實作該方法，實作了該接口的類的對象就可以比較大小。當一個對象obj1調用該方法與另一個對象obj2進行比較時，如果該方法傳回0，則表明這兩個對象相等；如果該方法傳回一個正整數，則表明ob1大于obj2；如果該方法傳回一個負整數，則表明ob1小于obj2。

Java的一些常用類已經實作的Comparable接口，并提供了比較大小的标準。下面是實作了Comparable接口的常用類：

  • BigDecimal、BigInteger以及所有的數值型對應的包裝類：按它們對應的數值大小進行比較。
  • Character:按字元的UNICODE值進行比較。
  • Boolean:true對應包裝類執行個體大于false對應的包裝類執行個體。
  • String:按字元串中字元的UNICODE值進行比較。
  • Date、Time：後面的時間、日期比前面的時間、日期大。

如果試圖把一個對象添加到TreeSet時，該對象的類必須實作Comparable接口，否則程式将會抛出異常。

大部分類在實作

compareTo(Object obj)

方法時，都需要将被比較對象obj強制類型轉換成相同類型，因為隻有相同類的兩個執行個體才會比較大小。

如果希望TreeSet能正常運作，TreeSet隻能添加同一種類型的對象。

當把一個對象加入TreeSet集合中時，TreeSet調用該對象的

compareTo(Object obj)

方法與容器中的其他對象比較大小，然後根據紅黑樹結構找到它的存儲位置。如果兩個對象通過

compareTo(Object obj)

方法比較相等，新對象将無法添加到TreeSet集合中。

TreeSet集合判斷兩個對象唯一标準就是

compareTo(Object obj)

方法。

當需要把一個對象放入TreeSet中，重寫該對象對應類的

equals()

方法時，應保證該方法與

compareTo(Object obj)

方法有一緻的結果，其規則是：如果兩個對象通過

equals()

方法比較傳回true時，這兩個對象通過

compareTo(Object obj)

方法比較應傳回0。

當執行了删除元素代碼成功後，TreeSet會對集合中的元素重新索引（不是重新排序），接下來就可以删除TreeSet中的所有元素了，包括那些被修改過執行個體變量的值。與HashSet類似的是，如果TreeSet中包含了可變對象，當可變對象的執行個體變量被修改時，TreeSet在處理這些對象時将會非常複雜，而且容易出錯。

定制排序

TreeSet的自然排序是根據集合元素的大小，TreeSet将它們以升序排序。

如果需要實作定制排序，例如以降序排序，則可以通過Comparable接口的幫助。該接口裡包含了一個

int compare(T o1, T o2)

方法，該方法用于比較o1和o2的大小：如果該方法傳回正整數，則表明o1大于o2；如果該方法傳回0，則表明o1等于o2；如果該方法傳回負整數，則表明o1小于o2。

如果需要實作定制排序，則需要在建立TreeSet集合對象時，提供一個Comparator對象與該TreeSet集合關聯，由該Comparator對象負責集合元素的排序邏輯。由于Comparator是一個函數式接口，是以可使用Lambda表達式來代替Comparator對象。

當通過Comparator對象（或Lambda表達式）來實作TreeSet的定制排序時，依然不可以向TreeSet中添加類型不同的對象，否則還會引發

ClassCastException

異常。使用定制排序時，TreeSet對集合元素排序不管集合元素本身的大小，而是由Comparator對象（或Lambda表達式）負責集合元素的排序規則。

TreeSet判斷兩個集合元素的相等的标準是：通過Comparator（或Lambda表達式）比較兩個元素傳回了0，這樣TreeSet不會把第二個元素添加到集合中。

EnumSet類

EnumSet是一個轉為枚舉類設計的集合類，EnumSet中的所有元素都必須是指定枚舉類型的枚舉值，該枚舉類型在建立EnumSet時顯示或隐式地指定。EnumSet的集合元素也是有序的，EnumSet以枚舉值在Enum類内定義順序來決定集合元素的順序。

EnumSet在内部以位向量的形式存儲，這種存儲形式非常緊湊、高效，是以EnumSet對象占用記憶體很小，而且運作效率很好。尤其是進行批量操作（如調用

containsAll()

和

retainAll()

方法）時，如果其參數也是EnumSet集合，則該批量操作的執行速度也非常快。

EnumSet集合不允許加入null元素，如果試圖插入null元素，EnumSet将抛出

NullPointerException

異常。如果隻是想判斷EnumSet是否包含null元素或試圖删除null元素都不會抛出異常，隻是删除操作将傳回false，因為沒有任何null元素被删除。

EnumSet類沒有暴露任何構造器來建立該類的執行個體，程式應該通過它提供的類方法來建立EnumSet對象。EnumSet類它提供了如下常用的類方法來建立EnumSet對象:

  • EnumSet allOf(Class elementType)

     ：建立一個包含指定枚舉類裡所有枚舉值的EnumSet集合。

  • EnumSet complementOf(EnumSet s)

     ：建立一個其元素類型與指定EnumSet裡元素類型相同的EnumSet集合，新EnumSet集合包含原EnumSet集合所不包含的、此枚舉類剩下的枚舉值（即新EnumSet集合和原EnumSet集合的集合元素加起來就是該枚舉類的所有枚舉值）。

  • EnumSet copyOf(Collection c)

     ：使用一個普通集合來建立EnumSet集合。

  • EnumSet copyOf(EnumSet s)

     ：建立一個與指定EnumSet具有相同元素類型、相同集合元素的EnumSet集合。

  • EnumSet noneOf(Class elementType)

     ：建立一個元素類型為指定枚舉類型的空EnumSet。

  • EnumSet Of(E first, E... rest)

     ：建立一個包含一個或多個枚舉值的EnumSet集合，傳入的多個枚舉值必須屬于同一個枚舉類。

  • EnumSet range(E from, E to)

     ：建立一個包含從from枚舉值到to枚舉值範圍内所有枚舉值的EnumSet集合。

當試圖複制Collection集合裡的元素來建立EnumSet集合時，必須保證Collection集合裡的所有元素都是同一個枚舉類的枚舉值。

各Set實作類的性能分析

HashSet和TreeSet是Set的兩個典型實作，到底如何選擇HashSet和TreeSet？HashSet的性能總是比TreeSet好（特别是最常用的添加、查詢元素等操作），因為TreeSet需要額外的紅黑樹算法來維護集合元素的次序。隻有當需要一個保持排序的Set時，才應該使用TreeSet，否則都應該使用HashSet。

HashSet還有一個子類：LinkedHashSet，對于普通的插入、删除操作，LinkedHashSet比HashSet要略微慢一點，這是由維護連結清單所帶來的額外開銷造成的，但由于有了連結清單，周遊LinkedHashSet會更快。

EnumSet是所有Set實作類中性能最好的，但它隻能儲存同一個枚舉類的枚舉值作為集合元素。

Set的三個實作類HashSet、TreeSet和EnumSet都是線程不安全的。如果有多個線程同時通路一個Set集合，并且有超過一個線程修改了該Set集合，則必須手動保證該Set集合的同步性。通常可以通過Collection工具類的synchronizedSortedSet方法來“包裝”該Set集合。此操作最好再建立時進行，以防止對Set集合的意外非同步通路。例如：

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

List集合

List集合代表一個元素有序、可重複的集合，集合中每個元素都有其對應的順序索引。List集合允許使用重複元素，可以通過索引來通路指定位置的集合元素。List集合預設按元素的添加順序設定元素的索引。

Java8改進的List接口和ListIterator接口

List作為Collection接口的子接口，當然可以使用Collection接口裡的全部方法。而且由于List是有序集合，是以List集合裡增加了一些根據索引來操作集合元素的方法。

  • void add(int index, Object element)

     ：将元素element插入到List集合的index處。

  • boolean addAll(int index, Collection c)

     ：将集合c所包含的所有元素都插入到List集合的index處。

  • Object get(int index)

     ：傳回集合index索引處的元素。

  • int indexOf(Object o)

     ：傳回對象o在List集合中第一次出現的位置索引。

  • int lastIndexOf(Object o)

     ：傳回對象o在List集合中最後一次出現的位置索引。

  • Object remove(int index)

     ：删除并傳回index索引處的元素。

  • Object set(int index, Object element)

     ：将index索引處的元素替換成element對象，傳回被替換的舊元素。

  • List subList(int fromIndex, int toIndex)

     ：傳回從索引fromIndex（包含）到索引toIndex（不包含）處所有集合元素組成的子集合。

所有的List實作類都可以調用這些方法來操作集合元素。與Set集合相比，List增加了根據索引來插入、替換和删除集合元素的方法。除此之外，Java8還為List接口添加了如下兩個預設方法。

  • void replaceAll(UnaryOperator operator)

     ：根據operator指定的計算規則重新設定List集合的所有元素。

  • void sort(Comparator c)

     ：根據Comparator參數對List集合的元素排序。

Lisi判斷兩個對象相等隻要通過

equals()

方法比較傳回true即可。

remove(new A());

程式試圖删除一個A對象，Lit将會調用該A對象的

equals()

方法依次與集合元素進行比較，如果該

equals()

方法以某個集合元素作為參數時傳回true。

當調用List的

set(int index, Object element)

方法來改變List集合指定索引處的元素時，指定的索引必須是List集合的有效索引。

set(int index, Object element)

方法不會改變List集合的長度。

Java8為List集合增加了

sort()

和

replaceAll()

兩個常用的預設方法，其中

sort()

方法需要一個Comparator對象來控制元素排序，程式可使用Lambda表達式來作為參數；而

replaceAll()

方法則需要一個UnaryOperator來替換所有集合元素，UnaryOperator也是一個函數式接口，是以也可使用Lambda表示作為參數。

與Set隻提供了一個

iterator()

方法不同，List還額外提供了一個

listIterator()

方法，該方法傳回一個ListIterator對象，ListIterator接口繼承了Iterator接口，提供了專門操作List的方法。ListIterator接口在Iterator接口基礎上增加了如下方法。

  • boolean hasPrevious()

     ：傳回該疊代器關聯的集合是否還有上一個元素。

  • Object previous()

     ：傳回該疊代器的上一個元素。

  • void add(Object o)

     ：在指定位置插入一個元素。

拿ListIterator與普通的Iterator進行對比，不難發現ListIterator增加了向前疊代的功能（Iterator隻能向後疊代），而且ListIterator還可通過

add()

方法向List集合中添加元素（Iterator隻能删除元素）。

ArrayList和Vector實作類

ArrayList和Vector類都是基于數組實作的List類，是以ArrayList和Vector類封裝了一個動态的、允許再配置設定的Object[]數組。ArrayList和Vector對象使用

initialCapacity

參數來設定該數組的長度，當向ArrayList或Vector中添加元素超出了該數組的長度時，它們的initialCapacity會自動增加。

當向ArrayList或Vector集合中添加大量元素時，可使用

ensureCapacity(int minCapacity)

方法一次性地增加initialCapacity。這可以減少重配置設定的次數，進而提高性能。

除此之外，ArrayList和Vector還提供了如下兩個方法來重新配置設定Object[]數組。

  • void ensureCapacity(int minCapasity)

     ：将ArrayList或Vector集合的Object[]數組長度增加大于或等于minCapacity。

  • void trimToSize()

     ：調整ArrayList或Vector集合的Object[]數組長度為目前元素的個數。調用該方法可減少ArrayList或Vector集合對象占用的存儲空間。

ArrayList和Vector的顯著差別是：ArrayList是線程不安全的，當多個線程通路同一個ArrayList集合時，如果有超過一個線程修改了ArrayList集合，則程式必須手動保證該集合的同步性；但Vector集合則是線程安全的，無須程式保證該集合的同步性。因為Vector是線程安全的，是以Vector的性能比ArrayList的性能要低。實際上，即使需要保證List集合線程安全的，也同樣不推薦使用Vector實作類。會有一個Collections工具類，它可以将一個ArrayList變成線程安全的。

Vector還提供了一個Stack子類，它用于模拟棧這種資料結構，“棧”通常是指後進先出（LIFO）的容器。最後“push”進棧的元素，将最先被“pop”出棧。與Java中的其他集合一樣，進棧出棧都是Object，是以從棧中取出元素後必須進行類型轉換，除非是使用Object具有的操作。是以Stack類裡提供了如下幾個方法。

  • Object peek()

     ：傳回“棧”的第一個元素，但并不将該元素“pop”出棧。

  • Object pop()

     ：傳回“棧”的第一個元素，并将該元素“pop”出棧。

  • void push(Object item)

     ：将一個元素“push”進棧，最後一個進“棧”的元素總是位于“棧“頂。

由于Stack繼承了Vector，是以它也是一個非常古老的Java集合類，它同樣是線程安全的、性能較差的，是以應該盡量少用Stack類。如果程式需要使用”棧“這種資料結構，則可以考慮ArrayDeque。

ArrayDeque也是List的實作類，ArrayDeque即實作了List接口，也實作了Deque接口，由于實作了Deque接口，是以可以作為棧來使用；而且ArrayDeque底層也是基于數組的實作，是以性能也很好。

固定長度的List

操作數組的工具類：Arrays，該工具類提供了

asList(Object... a)

方法，該方法可以把一個數組或指定個數的對象轉換成一個List集合，這個List集合既不是ArrayList實作類的執行個體，也不是Vector實作類的執行個體，而是Arrays的内部類ArrayList的執行個體。

Arrays.ArrayList是一個固定長度的List集合，程式隻能周遊通路該集合裡的元素，不可增加、删除該集合裡的元素。

Queue集合

Queue用于模拟隊列這種資料結構，隊列通常是指**先進先出（FIFO）**的容器。隊列的頭部儲存在隊列存放時間最長的元素，隊列的尾部儲存在隊列中存放時間最短的元素。新元素插入（offer）到隊列的尾部，通路元素（poll）操作會傳回隊列頭部的元素。通常，隊列不允許随機通路隊列中的元素。

Queue接口中定義了如下幾個方法。

  • void add(Object e)

     ：将指定元素加入此隊列的尾部。

  • Object element()

     ：擷取隊列頭部的元素，但是不删除該元素。

  • boolean offer(Object e)

     ：将指定元素加入此隊列的尾部。當使用有容量限制的隊列時，此方法通常比

    add(Object e)

     方法更好。

  • Object peek()

     ：擷取隊列頭部的元素，但是不删除該元素。如果此隊列為空，則傳回null。

  • Object poll()

     ：擷取隊列頭部的元素，并删除該元素。如果此隊列為空，則傳回null。

  • Object remove()

     ：擷取隊列頭部的元素，并删除該元素。

Queue接口有一個PriorityQueue實作類。除此之外，Queue還有一個Deque接口，Deque代表一個雙端隊列，雙端隊列可以同時從兩端來添加、删除元素，是以Deque的實作類即可當成隊列使用，也可當成棧使用。Java為Deque提供了ArrayDeque和LinlkedList兩個實作類。

PriorityQueue實作類

PriorityQueue是一個比較标準的隊列實作類。之是以說它是比較标準的隊列實作，而不是絕對标準的隊列實作，是因為PriorityQueue儲存隊列元素的順序并不是按加入隊列的順序，而是按隊列元素的大小進行重新排序。是以當調用

peek()

方法或者

poll()

方法取出隊列中的元素時，并不是取出最先進入隊列的元素，而是去除隊列中最小的元素。

PriorityQueue不允許插入null元素，它還需要對隊列元素進行排序，PriorityQueue的元素有兩種排序方式。

  • 自然排序：采用自然排序的PriorityQueue集合中的元素必須實作了Comparable接口，而且應該是同一個類的多個執行個體，否則可能導緻ClassCastException異常。
  • 定制排序：建立PriorityQueue隊列時，傳入一個Comparable對象，該對象負責對隊列中的所有元素進行排序。采用定制排序時不要求隊列元素實作Comparable接口。

PriorityQueue隊列對元素的要求與TreeSet對元素的要求基本一緻。

Deque接口與ArrayDeque實作類

Deque接口是Queue接口的子接口，它代表一個雙端隊列，Deque接口裡定義了一些雙端隊列的方法，這些方法允許從兩端來操作隊列的元素。

  • void addFirst(Object e)

     ：将指定元素插入該雙端隊列的開頭。

  • void addLast(Object e)

     ：将指定元素插入該隊列的末尾。

  • Iterator descendingIterator()

     ：傳回該雙端隊列對應的疊代器，該疊代器将以逆向順序來疊代隊列中的元素。

  • Object getFirst()

     ：擷取但不删除雙端隊列的第一個元素。

  • Object getLast()

     ：擷取但不删除雙端隊列的最後一個元素。

  • boolean offerFirst(Object e)

     ：将指定元素插入該雙端隊列的開頭。

  • boolean offerLast(Object e)

     ：将指定元素插入該雙端隊列的末尾。

  • Object peekFirst()

     ：擷取但不删除該雙端隊列的第一個元素；如果雙端隊列為空，則傳回null。

  • Object peekLast()

     ：擷取但不删除該雙端隊列的最後一個元素；如果雙端隊列為空，則傳回null。

  • Object pollFirst()

     ：擷取并删除該雙端隊列的第一個元素；如果此雙端隊列為空，則傳回null。

  • Object pollLast()

     ：擷取并删除該雙端隊列的最後一個元素；如果此雙端隊列為空，則傳回null。

  • Object pop()

     ：棧方法，pop出該雙端隊列所表示的棧的棧頂元素。相當于

    removeFirst()

     。

  • void push(Object e)

     ：棧方法，将一個元素push進該雙端隊列所表示的棧的棧頂。相當于

    addFirst(e)

     。

  • Object removeFirst(Object e)

     ：擷取并删除該雙端隊列的第一個元素。

  • Object removeFirstOccurrence(Object o)

     ：删除該雙端隊列的第一次出現的元素o。

  • Object removeLast(Object e)

     ：擷取并删除該雙端隊列的最後一個元素。

  • Object removeLastOccurrence(Object o)

     ：删除該雙端隊列的最後一次出現的元素o。

Deque不僅可以當成雙端隊列使用，而且可以被當成棧來使用，因為該類還包含了pop（出棧）、push（入棧）兩個方法。

Deque的方法與Queue的方法對照表

Queue的方法 Deque的方法
add(e)/offer(e) addLast(e)/offerLast(e)
remove()/poll() removeFirst()/pollFirst()
element()/peek() getFirst()/peekFirst()

Deque的方法與Stack的方法對照表

Stack的方法 Deque的方法
push(e) addFirst(e)/offerFirst(e)
pop() removeFirst()/pollFirst()
peek() getFirst()/peekFirst()

Deque接口提供了一個典型的實作類：ArrayDeque，從該名稱就可以看出，它是一個基于數組實作的雙端隊列，建立Deque時同樣可指定一個numElements參數，該參數用于指定Object[]數組的長度；如果不指定numElements參數，Deque底層的數組長度為16。

ArrayList和ArrayDeque兩個集合類的實作機制基本相似，它們底層都采用一個動态的、可重配置設定的Object[]數組來存儲集合元素，當集合元素超出了該數組的容量時，系統會在底層重新配置設定一個Object[]數組來存儲集合元素。

是以程式中需要使用棧這種資料結構時，推薦使用ArrayDeque，盡量避免使用Stack——因為Stack是古老的集合，性能較差。

LinkedList實作類

LinkedList類是List接口的實作類，可以根據索引來随機通路集合中的元素。除此之外，LinkedList還實作了Deque接口，可以被當成雙端隊列來使用，是以既可以被當成棧來使用，也可以當成隊列使用。

LinkedList與ArrayList、ArrayDeque的實作機制完全不同，ArrayList、ArrayDeque内部以數組的形式來儲存集合中的元素，是以随機通路集合元素時有較好的性能；而LinkedList内部以連結清單的形式來儲存集合中的元素，是以随機通路集合元素時性能較差，但在插入、删除元素時性能比較出色（隻需改變指針所指的位址即可）。雖然Vector也是以數組的形式來存儲集合元素的，但因為它實作了線程的同步功能（而且實作機制也不好），是以各方面性能都比較差。

對于所有的内部基于數組的集合實作，例如ArrayList、ArrayDeque等，使用随機通路的性能比使用Iterator疊代通路的性能要好，因為随機通路會被映射成對數組元素的通路。

各種線性表的性能分析

Java提供的List就是一個線性表接口，而ArrayList、LinkedList又是線性表的兩種典型實作：基于數組的線性表和基于鍊的線性表。Queue代表隊列，Deque代表了雙端隊列（既可作為隊列使用，也可作為棧使用）。

一般來說，由于數組以一塊連續記憶體區來儲存所有的數組元素，是以數組在随機通路時性能最好，所有的内部以數組作為底層實作的集合在随機通路時性能都比較好；而内部以連結清單作為底層實作的集合在執行插入、删除操作時有較好的性能。但總體來說，ArrayList的性能比LinkedList的性能要好，是以大部分時候應該考慮使用ArrayList。

關于使用List集合的建議。

  • 如果需要周遊List集合元素，對于ArrayList、Vector集合，應該使用随機通路方法（get）來周遊集合元素，這樣性能更好；對于LinkedList集合，則應該采用疊代器（Iterator）來周遊集合元素。
  • 如果需要經常執行插入、删除操作來改變包含大量資料的List集合的大小，可考慮使用LinkedList集合。使用ArrayList、Vector集合可能需要經常重新配置設定内部數組的大小，效果可能較差。
  • 如果有多個線程需要同時通路List集合中的元素，可考慮使用Collections将集合包裝成線程安全的集合。

Java8增強的Map集合

Map體系圖

瘋狂Java講義-Java集合Java集合

Map用于儲存具有映射關系的資料，是以Map集合裡儲存着兩組值，一組值用于儲存Map裡的key，另外一組值用于儲存Map裡的value，key和value都可以是任何引用類型的資料。Map裡的key不允許重複，即同一個Map對象的任何兩個key通過

equals()

方法比較總是傳回false。

key和value之間存在單向一對一關系，即通過指定的key，總能找到唯一的、确定的value。

如果把Map裡的所有key放在一起來看，它們就組成了Set集合（所有的key沒有順序，key與key之間不能重複），實際上Map包含了一個

keySet()

方法，用于傳回Map裡的所有key組成的Set集合。

Map裡key集和Set集合裡的元素的存儲形式很像，Map子類和Set子類在名字上也驚人地相似，比如Set接口下有HashSet、LinkedHashSet、SortedSet（接口）、TreeSet、EnumSet等子接口和實作類，而Map接口下則有HashMap、LinkedHashMap、SortedMap（接口）、TreeMap、EnumMap等子接口和實作類。Map的這些實作類和子接口中key集的存儲形式和對應Set集合中元素的存儲形式完全相同。

Set和Map之間的關系非常密切。雖然Map中存放的元素是key-value對，Set集合中放的元素是單個對象，但如果把key-value對中的value當成key的附庸：key在哪裡，value就跟在哪裡。Map提供了一個Entry内部類來封裝key-value對，而計算Entry存儲時則隻考慮Entry封裝的key。從Java源碼來看，Java是先實作了Map，然後通過包裝一個所有value都為null的Mao就實作了Set。

如果把Map裡的所有value放在一起來看，它們有非常類似于一個List：元素與元素之間可以重複，每個元素可以根據索引來查找，隻是Map中的索引不再使用整數值，而是以另一個對象作為索引。Map有時也被稱為字典，或關聯數組。Map接口中定義了如下常用的方法。

  • void clear()

     ：删除該Map對象中的所有key-value對。

  • boolean containsKey(Object key)

     ：查詢Map中是否包含指定的key，如果包含則傳回true。

  • boolean containsValue(Object value)

     ：查詢Map中是否包含一個或多個value，如果包含則傳回true。

  • Set entrySet()

     ：傳回Map中包含的key-value對所組成的Set集合，每個集合元素都是Map.Entry（Entry是Map的内部類）對象。

  • Object get(Object key)

     ：傳回指定key所對應的value；如果此Map中不包含該key，則傳回null。

  • boolean isEmpty()

     ：查詢該Map是否為空（即不包含任何key-value對），如果為空則傳回true。

  • Set keySet()

     ：傳回該Map中所有key組成的Set集合。

  • Object put(Object key, Object value)

     ：添加一個key-value對，如果目前Map中已有一個與該key相等的key-value對，則新的key-value對會覆寫原來的key-value對。

  • void putAll(Map m)

     ：将指定Map中的key-value對複制到本Map中。

  • Object remove(Object key)

     ：删除指定key所對應的key-value對，傳回删除key所關聯的value，如果該key不存在，則傳回null。

  • Object remove(Object key, Object value)

     ：這是Java8新增的方法，删除指定key、value所對應的key-value對。如果該Map中成功地删除該key-value對，該方法傳回true，否則傳回false。

  • int size()

     ：傳回該Map裡的key-value對的個數。

  • Collection values()

     ：傳回該Map裡所有value組成的Collection。

Map接口提供了大量的實作類，典型實作如HashMap和Hashtable等、HashMap的子類LinkedHashMap，還有SortedMap子接口及該接口的實作類TreeMap，以及WeakHashMap、IdentityHashMap等。

Map裡包括了一個内部類Entry，該類封裝了一個key-value對。Entry包含如下三個方法。

  • Object getKey()

     ：傳回該Entry裡包含的key值。

  • Object getValue()

     ：傳回該Entry裡包含的value值。

  • Object setValue(V value)

     ：設定該Entry裡包含的value值，并傳回新設定的value值。

Map集合最典型的用法就是成對地添加、删除key-value對，接下來即可判斷該Map中是否包含指定key，是否包含指定value，也可以通過Map提供的

keySet()

方法擷取所有key組成的集合，進而周遊Map中所有的key-value對。

添加key-value對時，Map允許多個value重複，但如果添加key-value對時Map中已有重複的key，那麼新添加的value會覆寫原來對應的value，該方法會傳回被覆寫的value。

Java8為Map新增的方法

Java8除為Map增加了

remove(Object key, Object value)

預設方法之外，還增加了如下方法。

  • Object compute(Object key, BiFunction remappingFunction)

     ：該方法使用remappingFunction根據原key-value對計算一個新的value。隻要新的value不為null，就是用新的value覆寫原value；如果原value不為null，但新的value為null，則删除原key-value對；如果原value、新value同時為null，那麼該方法不改變任何key-value對，直接傳回null。

  • Object computeIfAbsent(Object key, Function mappingFunction)

     ：如果傳給該方法的key參數在Map中對應的value為null，則使用mappingFunction根據key計算一個新的結果，如果計算結果不為null，則用計算結果覆寫原有的value。如果原Map原來不包括該key，那麼該方法可能會添加一組key-value。

  • Object computeIfPresent(Object key, BiFunction remappingFcuntion)

     ：如果傳給該方法的key參數在Map中對應的value不為null，該方法将使用remappingFunction根據原key-value計算一個新的結果，如果計算結果不為null，則使用該結果覆寫原來的value；如果計算結果為null，則删除原key-value對。

  • void forEach(BiConsumer action)

     ：該方法是Java8為Map新增的一個周遊key-value對的方法，通過該方法可以更簡潔地周遊Map的key-value對。

  • Object getOrDefault(Object key, V defaultValue)

     ：擷取指定key對應的value。如果該key不存在，則傳回defaultValue。

  • Object merge(Object key, Object value, BiFunction remappingFunction)

     ：該方法會根據key參數擷取該Map中對應的value。如果擷取的value為null，則直接用傳入的value覆寫原有的value（在這種情況下，可能要添加一組key-value對）；如果擷取的value不為null，則使用remappingFunction函數根據原value、新value計算一個新的結果，并用得到的結果去覆寫原有的value。

  • Object putIfAbsent(Object key, Object value)

     ：該方法會自動檢測指定key對應的value是否為null，如果該key對應的value為null，該方法會用新的value代替原來的null值。

  • Object replace(Object key, Object value)

     ：将Map中指定key對應的value替換成新value。與傳統

    put()

     方法不同的是，該方法不可能添加新的key-value對。如果嘗試替換的key在原Map中不存在，該方法不會添加key-value，而是傳回null。

  • boolean replace(K key, V oldValue, V newValue)

     ：将Map中指定key-value對原value替換成新value。如果在Map中找到指定的key-value對，則執行替換并傳回true，否則傳回false。

  • replaceAll(BiFunction function)

     ：該方法使用BiFunction對原key-value對執行計算，并将計算結果作為該key-value對的valu值。

Java8改進的HashMap和Hashtable實作類

HashMap和Hashtable都是Map接口的典型實作類，它們之間的關系完全類似于ArrayList和Vector的關系：Hashtable是一個古老的Map實作類，它從JDK1.0起就已經出現了，是以它包含了兩個煩瑣的方法，即

elements()

（類似于Map接口定義的

values()

方法）和

keys()

（類似于Map接口定義的

keySet()

方法），現在很少使用這兩個方法。

Java8改進了HashMap的實作，使用HashMap存在key沖突時依然具有較好的性能。

除此之外，Hashtable和HashMap存在兩點典型差別。

  • Hashtable是一個線程安全的Map實作，但HashMap是線程不安全的實作，是以HashMap比Hashtable的性能高一點；但如果有多個線程通路同一個Map對象時，使用Hashtable實作類會更好。
  • Hashtable不允許使用null作為key和value，如果試圖把null值放進Hashtable中，将會引發NullPointerException異常；但HashMap可以使用null作為key或value。

由于HashMap裡的key不能重複，是以HashMap裡最多隻有一個key-value對key為null，但可以有無數多個key-value對的value為null。

Hashtable是一個古老的類，它的命名甚至沒有遵守Java的命名規範；與Vector類似的是，盡量少用Hashtable實作類，即使需要建立線程安全的Map實作類，也無須使用Hashtable實作類，可以通過Collections集合工具類把HashMap變成線程安全的。

為了成功地在HashMap、Hashtable中存儲、擷取對象，用作key的對象必須實作

hashCode()

方法和

equals()

方法。

與HashSet集合不能保證元素的順序一樣，HashMap、Hashtable也不能保證其中key-value對的順序。類似于HashSet，HashMap、Hashtable判斷兩個key相等的标準也是：兩個key通過

equals()

方法比較傳回true，兩個key的

hashCode()

值也相等。

除此之外，HashMap、Hashtable中還包含一個

containsValue()

方法，用于判斷是否包含指定的value。

Hashtable判斷value相等的标準是：value與另外一個對象通過

equals()

方法比較傳回true即可。

自定義類作為HashMap、Hashtable的key時，如果重寫該類的

equals(Object obj)

和

hashCode()

方法，則應該保證兩個方法判斷标準一緻——當兩個key通過

equals()

方法比較傳回true時，兩個key的

hashCode()

傳回值也應該相同。

與HashSet類似的是，如果使用可變對象作為HashMap、Hashtable的key，并且程式修改了作為key的可變對象，則也可能出現于HashSet類似的情形：程式再無法準确通路到Map中被修改過的key。

LinkedHashMap實作類

HashSet有一個LinkedHashSet子類，HashMap也有一個LinkedHashMap子類；LinkedHashMap也使用雙向連結清單來維護key-value對的次序（其實隻需要考慮key的次序），該連結清單複制維護Map的疊代順序，疊代順序與key-value對的插入順序保持一緻。

LinkedHashMap可以避免對HashMap、Hashtable裡的key-value對進行排序（隻要插入key-value對時保持順序即可），同時又可避免使用TreeMap所增加的成本。

LinkedHashMap需要維護元素的插入順序，是以性能略低于HashMap的性能；但因為它以連結清單來維護内部順序，是以在疊代通路Map裡的全部元素時将有較好的性能。

使用Properties讀寫屬性檔案

Properties類是Hashtable類的子類，該對象在處理屬性檔案時特别友善（Windows操作平台上的ini檔案就是一種屬性檔案）。Properties類可以把Map對象和屬性檔案關聯起來，進而把Map對象中的key-value對寫入屬性檔案中，也可以把屬性檔案中的“屬性名=屬性值”加載到Map對象中。由于屬性檔案裡的屬性名、屬性值都是字元串類型，是以Properties裡的key、value都是字元串類型。該類提供了如下三個方法來修改Properties裡的key、value值。Properties相當于一個key、value都是String類型的Map。

  • String getProperty(String key)

     ：擷取Properties中指定屬性名對應的屬性值，類似于Map的

    get(Object key)

     方法。

  • String getProperty(String key, String defaultValue)

     ：如果Properties中不存在指定的key時，則該方法指定預設值。

  • Object setProperty(String key, String value)

     ：設定屬性值，類似于Hashtable的

    put()

     方法。

除此之外，它還提供了兩個讀寫屬性檔案的方法。

  • void load(InputStream inStream)

     ：從屬性檔案（以輸入流表示）中加載key-value對，把加載到key-value對追加到Properties裡（Properties是Hashtable的子類，它不保證key-value對之間的次序）。

  • void store(OutputStream out, String comments)

     ：将Properties中的key-value對輸出到指定的屬性檔案（以輸出流表示）中。

SortedMap接口和TreeMap實作類

正如Set接口派生出SortedSet子接口，SortedSet接口有一個TreeSet實作類一樣，Map接口也派生出一個SortedMap子接口，SortedMap接口也有一個TreeMap實作類。

TreeMap就是一個紅黑樹資料結構，每個key-value對即作為紅黑樹的一個節點。TreeMap存儲key-value對（節點）時，需要根據key對節點進行排序。TreeMap可以保證所有的key-value對處于有序狀态。TreeMap也有兩種排序方式。

  • 自然排序：TreeMap的所有key必須實作Comparable接口，而且所有的key應該是同一個類的對象，否則将抛出ClassCastException異常。
  • 定制排序：建立TreeMap時，傳入一個Comparator對象，該對象負責對TreeMap中的所有key進行排序。采用定制排序時不要求Map的key實作Comparable接口。

類似于TreeSet中判斷兩個元素相等的标準，TreeMap中判斷兩個key相等的标準是：兩個key通過

compareTo()

方法時應保持一緻的傳回結果：兩個key通過

equals()

方法比較傳回true時，它們通過

compareTo()

方法比較應該傳回0。如果

equals()

方法與

compareTo()

方法的傳回結果不一緻，TreeMap與Map接口的規則就會沖突。

Set和Map的關系十分密切，Java源碼就是先實作了HashMap、TreeMap等集合，然後通過包裝一個所有的value都為null的Map集合實作了Set集合類。

與TreeSet類似的是，TreeMap中也提供了一系列根據key順序通路key-value對的方法。

  • Map.Entry firstEntry()

     ：傳回該Map中最小key所對應的key-value對，如果該Map為空，則傳回null。

  • Object firsrtKey()

     ：傳回該Map中的最小key值，如果該Map為空，則傳回null。

  • Map.Entry lastEntry()

     ：傳回該Map中最大key所對應的key-value對，如果該Map為空或不存在這樣的key-value對，則傳回null。

  • Object lastKey()

     ：傳回該Map中的最大key值，如果該Map為空或不存在這樣的key-value對，則傳回null。

  • Map.Entry higherEntry(Object key)

     ：傳回該Map中位于key後一位的key-value對（即大于指定key的最小key所對應的key-value對）。如果該Map為空，則傳回null。

  • Object higherKey(Object key)

     ：傳回該Map中位于key後一位的key值（即大于指定key的最小key值）。如果該Map為空或不存在這樣的key-value對，則都傳回null。

  • Map.Entry lowerEntry(Object key)

     ：傳回該Map中位于key前一位的key-value對（即小于指定key的最大key所對應的key-value對）。如果該Map為空或不存在這樣的key-value對，則傳回null。

  • Object lowerKey(Object key)

     ：傳回該Map中位于key前一位的key值（即小于指定key的最大key值）。如果該Map為空或不存在這樣的key-value對，則都傳回null。

  • NavigableMap subMap(Object fromKey, boolean fromInclusive, Object toKey, boolean toInclusive)

     ：傳回該Map的子Map，其key的範圍是從fromKey（是否包括取決于第二個參數）到toKey（是否包括取決于第四個參數）。

  • SortedMap subMap(Object key, Object toKey)

     ：傳回該Map的子Map，其key的範圍是從fromKey（包括）到toKey（不包括）。

  • SortedMap tailMap(Object fromKey)

     ：傳回該Map的子Map，其key的範圍是大于fromKey（包括）到所有key。

  • NavigableMap tailMap(Object fromKey, boolean inclusive)

     ：傳回該Map的子Map，其key的範圍是大于fromKey（是否包括取決于第二個參數）的所有key。

  • SortedMap headMap(Object toKey)

     ：傳回該Map的子Map，其key的範圍是小于toKey（不包括）的所有key。

  • NavigableMap headMap(Object toKey, boolean inclusive)

     ：傳回該Map的子Map，其key的範圍是小于toKey（是否包括取決于第二個參數）的所有key。

WeakHashMap實作類

WeakHashMap與HashMap的用法基本相似。與HashMap的差別在于，HashMap的key保留了對實際對象的強引用，這意味着隻要該HashMap對象不被銷毀，該HashMap的所有key所引用的對象就不會被垃圾回收，HashMap也不會自動删除這些key所對應的key-value對；但WeakHashMap的key隻保留了對實際對象的弱引用，這意味着如果WeakHashMap對象的key所引用的對象沒有被其他強引用變量所引用，則這些key所引用的對象可能被垃圾回收，WeakHashMap也可能自動删除這些key所對應的key-value對。

WeakHashMap中的每個key對象隻持有對實際對象的弱引用，是以，當垃圾回收了該key所對應的實際對象之後，WeakHashMap會自動删除該key對應的key-value對。

如果需要使用WeakHashMap的key來保留對象的弱引用，則不要讓該key所引用的對象具有任何強引用，否則将失去WeakHashMap的意義。

IdentityHashMap實作類

這個Map實作類的實作機制與HashMap基本相似，但它在處理兩個key相等時比較特殊：在IndentityHashMap中，當且僅當兩個key嚴格相等（key1==key2)時，IdentityHashMap才認為兩個key相等；對于普通的HashMap而言，隻要key1和key2通過

equals()

方法比較傳回true，且它們的hashCode值相等即可。

IdentityHashMap提供了與HashMap基本相似的方法，也允許使用null作為key和value。與HashMap相似：IdentityHashMap也不保證key-value對之間的順序，更不能保證它們的順序随時間的推移保持不變。

EnumMap實作類

EnumMap是一個與枚舉類一起使用的Map實作，EnumMap中的所有key都必須是單個枚舉類的枚舉值。建立EnumMap時必須顯示或隐式指定它對應的枚舉類。EnumMap具有如下特征。

  • EnumMap在内部以數組形式儲存，是以這種實作形式非常緊湊、高效。
  • EnumMap根據key的自然順序（即枚舉值在枚舉類中的定義順序）來維護key-value對的順序。當程式通過

    keySet()

     、

    entrySet()

     、

    values()

     等方法周遊EnumMap時可以看到這種順序。
  • EnumMap不允許使用null作為key，但允許使用null作為value。如果試圖使用null作為key時将抛出NullPointerException異常。如果隻是查詢是否包含值為null的key，或隻是删除值為null的key，都不會抛出異常。

與建立普通的Map所有差別的是，建立EnumMap時必須指定一個枚舉類，進而将該EnumMap和指定枚舉類關聯起來。

各Map實作類的性能分析

對于Map常用實作類而言，雖然HashMap和Hashtable的實作機制幾乎一樣，但由于Hashtable是一個古老的、線程安全的集合，是以HashMap通常比Hashtable要快。

TreeMap通常比HashMap、Hashtable要慢（尤其在插入、删除key-value對時更慢），因為TreeMap底層采用紅黑樹來管理key-value對（紅黑樹的每個結點就是一個key-value對）。

使用TreeMap有一個好處：TreeMap中的key-value對總是處于有序狀态，無序專門進行排序操作。當TreeMap被填充之後，就可以調用

keySet()

，取得由key組成的Set，然後使用

toArray()

方法生成key的數組，接下來使用Arrays的

binarySearch()

方法在已排序的數組中快速地查詢對象。

對于一般的應用場景，程式應該多考慮使用HashMap，因為HashMap正是為快速查詢設計的（HashMap底層其實也是采用數組來存儲key-value對）。但如果程式需要一個總是排好序的Map時，則可以考慮使用TreeMap。

LinkedHashMap比HashMap慢一點，因為它需要維護連結清單來保持Map中的key-value時的添加順序。IdentityHashMap性能沒有特别出色之處，因為它采用HashMap基本相似的實作，隻是它使用

==

而不是

equals()

方法來判斷元素相等。EnumMap的性能最好，但它隻能使用同一個枚舉類的枚舉值作為key。

HashSet和HashMap的性能選項

對于HashSet及其子類而言，他們采用hash算法來決定集合中元素的存儲位置，并通過hash算法來控制集合的大小；對于HashMap、Hashtable及其子類而言，它們采用hash算法來決定Map中key的存儲，并通過hash算法來增加key集合的大小。

hsh表裡可以存儲元素的位置被稱為桶（bucket），在通常情況，單個“桶”裡存儲一個元素，此時有最好的性能：hash算法可以根據hashCode值計算出“桶”存儲位置，接着從“桶”中取出元素。但hahs表的狀态時open的：在發生hash沖突的情況下，單個桶會存儲多個元素。這些元素以連結清單形式存儲。

因為HashSet和HashMap、Hashtable都是用hash算法來決定其元素（HashMap則隻考慮key）的存儲，是以HashSet、HashMap的hash表包含如下屬性。

  • 容量（capacity）：hash表中桶的數量
  • 初始化容量（initial capacity）：建立hash表時桶的數量。HashMap和HashSet都允許在構造器中指定初始化容量。
  • 尺寸（size）：目前hash表中記錄的數量。
  • 負載因子（load factor）：負載因子等于size/capacity。負載因子為0時，表示空的hash表，0.5表示半滿的hash表，以此類推。輕負載的hash表具有沖突少、适宜插入與查詢的特點（但是使用Iterator疊代元素時比較慢）。

除此之外，hash表裡還有一個負載極限，負載極限是一個0~1的數值，負載極限決定了hash表的最大填滿程度。當hash表中的負載因子達到指定的負載極限時，hash表會自動成倍地增加容量（桶的數量），并将原有的對象重新配置設定，放入新的桶内，這稱為rehashing。

HashSet和HashMap、Hashtable的構造器允許指定一個負載極限，HashSet和HashMap、Hashtable預設的負載極限為0.75。

負載極限的預設值（0.75）是時間和空間成本上的一種折中：較高的負載極限可以降低hash表所占用的記憶體空間，但會增加查詢資料的時間開銷，而查詢是最頻繁的操作（HashMap的

get()

與

put()

方法都要用到查詢）；較低的負載極限會提高查詢資料的性能，但會增加hash表所占用的記憶體開銷。

如果開始就知道HashSet和HashMap、Hashtable會儲存很多記錄，則可以在建立時就是用較大的初始化容量，如果初始化容量始終大于HashSet和HashMap、Hashtable所包含的最大記錄數除以負載極限，就不會發生rehashing，使用足夠大的初始化容量建立HashSet和HashMap、Hashtable時，可以更高效地增加記錄，當将初始化容量設定太高可能會浪費空間。

操作集合的工具類：Collections

Java提供了一個操作Set、List和Map等集合的工具類：Collctions，該工具類裡提供了大量方法對集合元素進行排序、查詢和修改等操作。

排序操作

Collections提供了如下常用的類方法用于對List集合元素進行排序。

  • void reverse(List list)

     ：反轉指定List集合中的元素順序。

  • void shuffle(List list)

     ：對List集合元素進行随機排序（shuffle方法模拟了”洗牌“動作）。
  • void sort(List list)`：根根據元素的自然順序對指定List集合的元素按升序進行排序。

  • void sort(List list, Comparator c)

     ：根據指定Comparator産生的順序對List集合元素進行排序。

  • void swap(List list, int i, int j)

     ：将指定List集合中的i處元素和j處元素進行交換。

  • void rotate(List list, int distance)

     ：當distance為正數時，将list集合的後distance個元素”整體“移到前面；當distance為負數時，将list集合的前distance個元素”整體“移到後面。

查找、替換操作

Collections還提供了如下常用的用于查找、替換集合元素的類方法。

  • int binarySearch(List list, Object key)

     ：使用二分搜尋法搜尋指定的List集合，以獲得指定對象在List集合中的索引。如果要使用該方法可以正常工作，則必須保證List中的元素已經處于有序狀态。

  • Object max(Collection coll)

     ：根據元素的自然排序，傳回給定集合中的最大元素。

  • Object max(Collection coll, Comparator comp)

     ：根據Comparator指定的順序，傳回給定集合中的最大元素。

  • Object min(Collection coll)

     ：根據元素的自然排序，傳回給定集合中的最小元素。

  • Object min(Collection coll, Comparator comp)

     ：根據Comparator指定的順序，傳回給定集合中的最小元素。

  • void fill(List list, Object obj)

     ：使用指定元素obj替換指定List集合中的所有元素。

  • int frequency(Collection c, Object o)

     ：傳回指定集合中指定元素的出現次數。

  • int indexOfSubList(List source, List target)

     ：傳回子List對象在父List對象中第一次出現的位置索引；如果父List中沒有出現這樣的子List，則傳回-1。

  • int lastIndexOfSubList(List source, List target)

     ：傳回子List對象在父List對象中最後一次出現的位置索引；如果父List中沒有出現這樣的子List，則傳回-1。

  • bollean replaceAll(List list, Object oldVal, Object newVal)

     ：使用一個新值newVal替換List對象的所有舊值oldVal。

同步控制

Collections類中提供了多個

synchronizedXxx()

方法，該方法将指定集合包裝成線程同步的集合，進而可以解決多線程并發通路集合時的線程安全問題。

Java中常用的集合架構中的實作類HashSet、TreeSet、ArrayList、ArrayDeque、LinkedList、HashMap和TreeMap都是線程不安全的。如果有多個線程通路它們，而且有超過一個的線程試圖修改它們，則存線上程安全的問題。Collections提供了多個類方法可以把它們包裝成線程同步的集合。

設定不可變集合

COllections提供了如下三類方法來傳回一個不可變的集合。

  • emptyXxx()

     ：傳回一個空的、不可變的集合對象，此處的集合既可以是List，也可以是SortedSet、Set，還可以是Map、SortedMap等。

  • singletonXxx()

     ：傳回一個隻包含指定對象（隻有一個或一項元素）的、不可變的集合對象，此處的集合既可以是List，還可以是Map。

  • unmodifiableXxx()

     ：傳回指定集合對象的不可變試圖，此處的集合既可以是List，也可以是Set、SortedSet，還可以是Map、SortedMap等。

上面三類方法的參數是原有的集合對象，傳回值是該集合的隻讀版本。

Java9新增的不可變集合

Java9以前要建立一個包含6個元素的Set集合，程式需要先建立Set集合，然後6次調用

add()

方法向Set集合中添加元素。Java9對此進行了簡化，程式直接調用Set、List、Map的

of()

方法即可建立包含N個元素的不可變的集合。

不可變意味着程式不能向集合中添加元素，也不能從集合中删除元素。

建立不可變的Map集合有兩個方法：使用

of()

類方法時隻要依次傳入多個key-value對即可；還可使用

ofEntries()

類方法，該方法可接受多個Entry對象，是以程式顯示使用

Map.entry()

方法來建立Map.Entry對象。

煩瑣的接口：Enumeration

Enumeration接口是Iterator疊代器的古老版本，從JDK1.0開始，Enumeration接口就已經存在了（Iterator從JDK1.2出現）。Enumeration接口隻有兩個名字很長的方法。

  • boolean hasMoreElements()

     ：如果次疊代器還有剩下的元素，則傳回true。

  • Object nextElement()

     ：傳回該疊代器的下一個元素，如果還有的話（否則将抛出異常）。

Enumeration接口中的方法名稱冗長，難以記憶，而且沒有提供Iterator的

remove()

方法。如果現在編寫Java程式，應該盡量采用Iterator疊代器。

Java之是以保留Enumeration接口，主要是為了照顧以前那些“古老”的程式，那些程式裡大量使用了Enumeration接口，如果新版本的Java裡直接删除Enumeration接口，将會導緻那些程式全部出錯。在計算機行業有一條規則：加入任何規則都必須謹慎，因為以後無法删除規則。

實際上，Vector（包括其子類Stack）、Hashtable兩個集合類，以及另一個極少使用的BitSet，都是從JDK1.0遺留下來的集合類，而Enumeration接口可用于周遊這些“古老”的集合類。對于ArrayList、HashMap等集合類，不再支援使用Enumeration。

瘋狂Java講義 java
上一篇: java瘋狂講義 筆記_《瘋狂Java講義》閱讀筆記1
下一篇: discuz論壇(discuz論壇官網)

繼續閱讀