第十七章、容器的深入研究

前言

1、兩個對象值相同(x.equals(y) == true)，但卻可有不同的hash code，這句話對不對？

2、用最有效率的方法計算2乘以8?

3、如何實現對象克隆？

1. 完整的容器分類法

​

​​Java SE5新添加了：

• Queue接口：LinkedList已經為實現該接口做了修改；及其實現PriorityQueue和各種風格的BlockingQueue（用於生產者-消費者模型，多線程機制）；
• ConcurrentMap接口及其實現ConcurrentHashMap，用於多線程機制；
• CopyOnWriteArrayList和CopyOnWriteArraySet，用於多線程機制；
• EnumSet和EnumMap，為使用enum而設計的set和map的特殊實現；
• 在Collections類中的多個便利方法。

2. 填充容器

Collections類也有一些實用的static方法，其中包括fill()，同Arrays一樣只複製同一對象引用來填充整個容器的，並且只對List對象有用，但是所產生的列表可以傳遞給構造器或addAll方法。

• Collections.addAll() 將一些元素添加到一個Collection中
• Collections.nCopies() 複製一些元素到Collections中，返回一個List集合
• Collections.fill() 複製元素填充到集合當中

3. 使用Abstract類

每個java.util容器都有其自己的Abstract類，它們提供了該容器的部分實現，因此必須做的只是去實現那些產生想要的容器所必需的方法。

• AbstractList 實現了List接口；
• AbstractMap 實現了Map接口；
• AbstractSet 實現了Set接口；

享元模式（GoF23）：可在普通解決方案需要過多對象，或者產生普通對象太佔用空間時使用享元。享元模式使得對象的一部分可以被具體化，因此，與對象中的所有事物都包含在對象內部不同，可以在更加高效的外部表中查找對象的一部分或整體。

4.Collection的功能方法(Collection是一個接口)

下面表格列出了可以通過Collection執行的所有操作。它們也可以是通過Set或者List執行的所有操作。

Iterator迭代器接口方法：

• hasNext(); 判斷是否存在下一個對象元素；
• next(); 獲取下一個元素；
• remove(); 移除元素。

4. 可選操作

• 概念：執行各種不同的添加和移除的方法在Collection接口中都是可選操作。這意味著實現類並不需要為這些方法提供功能定義。
• 聲明調用某些方法將不會執行有意義的行為，相反，它們會拋出異常。如果一個操作是可選的，編譯器仍舊會嚴格要求你只能調用該接口中的方法。
• 設計原因：可以防止在設計中出現接口爆炸的情況。

4.1 未獲支持的操作

• 未獲支持操作異常：UnsupportedOperationException：必須是一種罕見的事件。即，對於大多數類來說，所有的操作都應該是可以工作的，只有在特例中才會有未獲得支持的操作。在Java容器類庫中確實如此，因為只有99%的時間裡面使用的所有的容器類，如ArrayList、LinkedList、HashSet和HashMap，以及其他具體的實現，都支持所有的操作。
• 如果一個操作是未獲支持的，那麼在實現接口的時候就可能會導致UnsupportedOperationException異常（表明此為編程錯誤）。

異常案例1（Arrays.asList()）：

• Arrays.asList()：將數組轉換為List時，產生固定尺寸的List，僅支持那些不會改變數組大小的操作。
• 最常見的未獲支持的操作，源於背後由固定尺寸的數據結構支持的容器。
• 任何會引起對底層數據結構的尺寸進行修改的方法都會產生一個UnsupportedOperationException異常，以表示對未獲支持操作的調用。
• 支持對容器的元素進行修改。

異常案例2（Collections.unmodifiableList()）：

• Collections.unmodifiableList()：產生不可修改的列表。
• 不支持對容器的元素進行修改。

5. List的功能方法

List接口：

• get(int); 獲取指定索引位置的列表元素
• set(int,E); 設置指定索引位置的列表元素
• add(int,E); 將指定的元素添加到此列表的索引位置。
• remove(int); 移除指定索引位置的元素;
• indexOf(Object); 從列表頭部查找Object對象元素
• lastIndexOf(Objcet); 從列表尾部查找Object對象元素
• listIterator(); 返回列表迭代器
• listIterator(int); 返回指定索引位置的列表迭代器
• subList(int,int); 該方法返回的是父list一個視圖，從fromIndex（包含），到toIndex（不包含）

ListIterator迭代器接口方法:

• hasPrevious(); 如果以逆向遍歷列表，列表迭代器前面還有元素，則返回 true，否則返回false
• previous(); 返回列表中ListIterator指向位置前面的元素
• set(E); 從列表中將next()或previous()返回的最後一個元素返回的最後一個元素更改為指定元素e
• add(E); 將指定的元素插入列表，插入位置為迭代器當前位置之前
• nextIndex(); 返回列表中ListIterator所需位置後面元素的索引
• previousIndex(); 返回列表中ListIterator所需位置前面元素的索引

6. Set和存儲順序

• Set接口：繼承來自Collection接口的行為。
• 存儲順序：不同的set實現不僅具有不同的行為，而且它們對於可以在特定的set中放置元素的類型也有不同的要求。
• default：如果沒有其他限制，應該默認選擇HashSet（加*），因為它對速度進行了優化。
• equals()：必須為散列存儲（Hash）和樹形（Tree）儲存都創建equals方法；
• hashCode()：只有在類被置於HashSet和LinkedHashSet時才必須（即TreeSet在語法上非強制要求）。但是良好的編程風格（Effective Java）要求：覆蓋equals方法時，總是同時覆蓋hashCode方法。

6.1 SortedSet

SortedSet中的元素可以保證處於排序狀態，SortedSet接口中的下列方法提供附加的功能：

• Comparator comparator()返回當前Set使用的Comparator；或者返回null，表示以自然方式排序。
• Object first()返回容器中的第一個元素。
• Object last()返回容器中的最末一個元素。
• SortedSet subSet(fromElement, toElement)生成此Set的子集，範圍從fromElement（包含）到toElement（不包含）。
• SortedSet headSet(toElement)生成此Set的子集，由小於toElement的元素組成
• SortedSet tailSet(fromElement)生成此Set的子集，由大於或等於fromElement的元素組成

7. Queue

Queue接口包含：

• boolean add(E e); 添加一個元素，添加失敗時會拋出異常
• boolean offer(E e); 添加一個元素，通過返回值判斷是否添加成功
• E remove(); 移除一個元素，刪除失敗時會拋出異常
• E poll(); 移除一個元素，返回移除的元素
• E element(); 在隊列的頭部查詢元素，如果隊列為空，拋出異常
• E peek(); 在隊列的頭部查詢元素，如果隊列為空，返回null
• Queue在Java SE5中僅有的兩個實現是LinkedList和PriorityQueue，它們的差異在於排序行為而不是性能

7.1 優先級隊列

PriorityQueue：

• 設計：列表中的每個對象都包含一個字符串和一個主要的以及次要的優先級值。
• 優先級排序：該列表的排序順序也是通過實現Comparable而進行控制的：Queue<string> queue=new PriorityQueue<>();/<string>

7.2 雙向隊列

• 概念：雙向隊列就像一個隊列，但是可以在任意一段添加或移除元素。
• 實現：在LinkedList中包含支持雙向隊列的方法，但在Java標準類庫中沒有任何顯式的用於雙向隊列的接口。因此，LinkedList無法去實現這樣的接口，無法像前面轉型到Queue那樣向上轉型為Deque。但是可以使用組合創建一個Deque類，並直接從LinkedList中暴露相關方法。

LinkedList中支持雙向隊列操作的相關方法：

• queue.addFirst(); 向隊列首部添加元素
• queue.addList(); 向隊列尾部添加元素
• queue.getLast(); 獲取隊列尾部元素
• queue.getFirst(); 獲取隊列首部元素
• queue.removeFirst(); 移除隊列首部元素
• queue.removeLast(); 移除隊列尾元素
• queue.size(); 返回隊列大小

8. 理解Map

Map接口：

• size(); 返回Map大小
• isEmpty(); 判斷Map集合是否為空
• containsKey(); 判斷Mpa集合是否包括Key鍵
• containsVaule(); 判斷Map集合是否包括Vaule
• get(Object); 獲得Map集合鍵為Object的Vaule
• put(K,V); 添加一個K,V鍵值對
• remove(Object); 移除K鍵值對
• putAll(Map); 添加所有元素Map集合
• clear(); 清空Map中所有集合元素
• keySet(); 返回鍵Key的Set集合
• values(); 返回值Vaule的Set集合
• entrySet(); 返回Map.entrySet集合
• remove(Objcet,Object); 移除K,V集合
• replace(K,V,V); 替換鍵值對

8.1 性能

• 性能是Map容器（K-V映射表）的一個重要問題。
• get進行線性搜索時，執行速度會相當慢，這正是HashMap提高速度的地方。
• 散列碼（hash code）：是相對唯一的，用以代表對象的int值，它是通過將該對象的某些信息進行轉換而生成的。
• 散列函數：hashCode()是類Object中的方法，因此所有Java對象都能產生散列碼。

8.1.1 HashMap

• 默認選擇（*）
• 使用散列碼（對象的hashCode()）來取代對鍵的緩慢搜索，此方法能夠顯著提高性能。

8.2 SortedMap接口

使用SortedMap（TreeMap的唯一實現），可確保鍵處於排序狀態。使得它具有額外的功能，這些功能由SortedMap接口中的下列方法提供：

• Comparator comparator()：返回當前Map使用的Comparator；或者返回null，表示以自然方式排序
• T firstKey返回Map中的第一個鍵
• T lastKey返回Map中的最末一個鍵
• SortedMap subMap(fromKey,toKey)生成此Map的子集，範圍由fromKey（包括）到toKey（不包含）的鍵確定
• SortedMap headMap(toKey)生成此Map的子集，由鍵小於toKey的所有鍵值對組成
• SortedMap tailMap(fromkey)生成此Map的子集，由鍵大於或等於fromKey的所有鍵值對組成

8.3 LinkedHashMap

• 特性1：LinkedHashMap在迭代遍歷鍵值對時，為了提高速度，以元素的插入或者LRU順序來返回鍵值對（不同於HashMap）。
• 特性2：LinkedHashMap使用鏈表維護內部次序（不同於HashMap）。
• 最近最少使用（LRU）算法：沒有被訪問過的元素就會出現在隊列的前面；LinkedHashMap可以在構造器中設定，使之使用此算法。

9. 散列與散列碼

對於一個放入Map集合的對象，它的類必須同時實現hashCode()和equals()方法。

正確的equals必須滿足5個條件：

• 自反性，對任意x，x.equals(x)一定返回true；
• 對稱性，對任意x和y，如果x.equals(y)為true，則y.equals(x)也為true；
• 傳遞性，對任意x,y,z，如果有x.equals(y)返回true，y.equals(z)返回true，則x.equals(z)一定返回true；
• 一致性，對任意x和y，如果對象中用於等價比較的信息沒有改變，那麼無論調用x.equals(y)多少次，返回結果應該保持一致；
• 對任何不是null的x，x.equals(null)一定返回false。

9.1 理解hashCode()

• 散列的數據結構：（HashSet、HashMap、LinkedHashMap和LinkedHashSet），要正確處理鍵必須覆蓋hashCode和equals方法。要很好的解決問題，必須瞭解數據結構的內部構造。
• 散列：目的在於想要使用一個對象來查找另一個對象。不過可以使用TreeMap或者自己實現的Map也可以達到這個目的。

9.2 為速度而散列

散列的價值在於速度，針對k-v查詢（由於瓶頸位於鍵的查詢速度）：

• 方式1（普通方式）：線性查詢，最慢的查詢方式；
• 方式2（次優方式）：保持鍵的排序狀態，然後使用Collections.binarySearch進行快速查詢。
• 方式3（更優方式）：散列則更進一步，使用數組（存儲一組元素最快的數據結構）來表示鍵的信息（不是鍵本身）。但數組不能調整容量，所以數組並不保存鍵本身，而是通過鍵對象生成一個數字，將其作為數組的下標（這個數字就是散列碼）。

關於散列碼&k值查詢：

• 不同的鍵可以產生相同的下標（散列碼）：也就是說，可能會有衝突，因此數組多大（可以固定size）就不重要了，任何鍵總能在數組中找到它的位置。
• k值散列方式的查詢過程：

step1：首先是計算散列碼；

step2：然後使用散列碼查詢數組（保持了k值信息，非k值對象本身）。如果沒有衝突，那就有了一個完美的散列函數。通常，如散列衝突由外部鏈接處理：

step3：但是如果散列函數好的話，數組的每個位置就只有較少的值。因此，不是查詢整個list，而是快速地跳到數組的某個位置，只對很少的元素進行比較。這就是HashMap如此快的原因。

9.3 覆蓋hashCode()

設計hashCode()時重要原則：

• 原則1：無論何時，對同一個對象調用hashCode()都應該生成同樣的值
  。
• 原則2：此外，也不應該是hashCode()依賴於具有唯一性的對象信息，尤其是使用this的值。因為這樣做無法生成一個新的鍵，使之與put中元素的鍵值對中的鍵相同。
• 舉例：以String為例：程序中有多個String對象，都包含相同的字符串序列，那麼這些String對象都映射到同一塊內存區域。所以new String(“hello”)生成的兩個實例，雖然相互獨立的，但是對它們使用hashCode()應該產生相同的結果。

如何設計一個好的hashCode方法？

10.選擇接口的不同實現（容器選型）

• 容器選型原則：容器之間的區別通常歸結為由什麼在背後支持它們。也就是說，所使用的接口是有什麼樣的數據結構實現的。
• 舉例1： ArrayList底層由數組支持；而LinkedList是由雙向鏈表實現，其中每個對象包含數據的同時還包含執行鏈表的前一個與後一個元素引用。因此，如果經常在表中插入或刪除元素，LinkedList就比較合適；否則，應該使用速度更快的ArrayList。
• 舉例2：Set中，HashSet是最常用的，查詢速度最快；LinkedHashSet保持元素插入的次序；TreeSet基於Treemap ，生成一個總是處於排序狀態的Set。

10.1對List的選擇

• get和set測試：使用了隨機數生成器來執行List的隨機訪問。在輸出中，對於背後有數組支持的List和ArrayList，無論列表的大小如何變化，這些訪問速度都很快。而對於LinkedList來說，訪問時間對於較大的列表來說明顯增加。很顯然，如果你需要執行大量的隨機訪問，鏈表不是一個很好的選擇。
• interadd測試：使用迭代器在列表中間插入元素。對於ArrayList來說，當列表變大的時候，其開銷會變得十分巨大，但是對於LinkedList來說，相對比較低廉，並且不會受著列表尺寸的變大而變大。
• insert和remove測試：都使用了索引作為插入和刪除點，而沒有選擇List兩端的元素，LinkedList對於插入和刪除操作來說十分低廉，並且不會隨著列表尺寸的變大而變大。但是對於ArrayList來說，插入操作的代價特別高昂，並且隨著列表尺寸的變大而變大。

List容器選型總結：

• 最佳的做法可能是將ArrayList做為默認首選
• 只要需要使用額外的功能，或者當程序的性能因為經常從表中間進行插入和刪除而變差的時候，才會選擇LinkedList。
• 如果使用的是固定數量的元素，那麼既可以選擇使用背後有數組支撐的List，也可以選擇真正的數組。
• CopyOnWriteArrayList是List的一個特殊實現，專門用於併發編程。

10.2 對Set的選擇

• HashSet的性能基本上總是比TreeSet好，特別是在添加和查詢元素時。
• TreeSet存在的唯一原因是它可以維持元素的排序狀態；所以，只有當需要一個排好序的Set時，才應該使用TreeSet。因為其內部結構支持排序，並且因為迭代是更有可能執行的操作，所以，用TreeSet迭代通常比用HashSet更快。
• 對於插入操作，LinkedHashSet比HashSet的代價更高，這是由維護鏈表所帶來額外開銷造成的。

10.3 對Map的選擇

• 所有Map實現的插入操作都會隨著Map的尺寸的變大而明顯變慢。但是，查找的代價通常比插入小得多。
• HashMap：Hashtable的性能大體上與HashMap相當，因為HashMap是用來替換Hashtable的（Hashtable已廢棄），因此它們使用了相同的底層存儲和查找機制。
• TreeMap通常比HashMap要慢，並且不必進行特殊排序。一旦填充了一個TreeMap，就可以調用keySet()方法來獲取鍵的Set視圖，然後調用toArray()來產生由這些鍵構成的數組。之後可以使用Arrays.binarySearch()在排序數組中查找對象。當然，這隻有HashMap的行為不可接受的情況下才有意義。因為hashMap本身就被設計為可以快速查找鍵。
• LinkedHashMap在插入時比HashMap慢一點，因為它維護散列數據結構的同時還要維護鏈表（以保持插入順序）。正是因為這給列表，使得其迭代速度更快。
• IdentityHashMap則具有完全不同的性能，因為它使用==而不是equals來比較元素。

HashMap的性能因子

• 容量：表中的桶位數
• 初始容量：表在創建時所擁有的桶位數，HashMap和HashSet都具有允許指定初始化容量的構造器
• 尺寸：表中當前存儲的項數
• 負載因子：尺寸/容量。空表的負載因子是0，而半滿表的負載因子是0.5。以此類推。負載輕的表產生衝突的可能性小，因此對於插入和查找都是最理想的。HashMap和HashSet都具有允許指定負載因子的構造器，表示當負載情況達到該負載因子的水平時，容器將自動增加其容量，實現方式是是容量大致加倍，並重新將現有對象分佈到新的桶位集中（成為再散列）。

HashMap使用默認的負載因子0.75，這個因子在時間和空間代價之間到達了平衡：

• 更高的負載因子：可以降低表所需的空間，但是會增加查找代價。因為查找是我們在大多數時間裡所做的操作。
• 如果知道將要在HashMap中存儲多少項，那麼創建一個具有恰當大小的初始容量將可以避免自動再散列的開銷。

11. Collections實用方法(Collections類中的靜態方法)

11.1 List的排序和查詢

List排序和查詢使用的方法與對象數組所使用的相應方法有相同的名字與語法，只是用Collections的static方法代替Arrays的方法：

• Collections.sort(list) 是哪個list中的自然排序
• Collections.binarySearch(list,key) 在list集合中查找所需要的key

11.2 設定Collection或者Map為不可修改的元素：

• Collections.unmodifiableCollection()
• Collections.unmodifiableList()
• Collections.unmodifiableSet()
• Collections.unmodifiableSortedSet()
• Collections.unmodifiableMap()
• Collections.unmodifiableSortedMap()

11.3 Collection或Map的同步控制

• Collections.synchronizedCollection()
• Collections.synchronizedList()
• Collections.synchronizedSet()
• Collections.synchronizedSortedSet()
• Collections.synchronizedMap()
• Collections.synchronizedSortedMap()

直接將新生成的容器傳遞給了適當的“同步方法”；這樣做就不會有任何機會暴露出不同步的版本。

11.4 快速報錯（ConcurrentModificationException）

• 快速報錯(fail-fast)機制：Java容器有一種保護機制，能夠防止多個進程同時修改同一容器的內容。如果在迭代遍歷某個容器的過程中，另一個進程介入其中，並且插入、刪除或修改此容器內的某個對象，那就會出問題。Java容器類類庫採用快速報錯(fail-fast)機制。
• ConcurrentModificationException異常：Java會探查容器上的任何除了進程所進行的操作以外的所有變化，一旦它發現其他進程修改了容器，就會立刻拋出ConcurrentModificationException異常。
• 內置規避併發報錯的容器：ConcurrentHashMap、CopyOnWriteArrayList和CopyOnWriteArraySet都使用了可以避免ConcurrentModificationException的技術。

舉例：

<code>public class FailFast {    public static void main(String[] args) {        Collection<string> c = new ArrayList<string>();        Iterator<string> it = c.iterator();        c.add("An object");        try {            String s = it.next(); //程序運行時發生了異常：因為在容器取得迭代器之後，新增元素被放入該容器中。        } catch (ConcurrentModificationException e) {            System.out.println(e);        }    }}/<string>/<string>/<string>/<code>

12. 持有引用

• java.lang.ref類庫：包含了一組類，這些類為垃圾回收提供了更大的靈活性。當存在可能會耗盡內存的大對象時，這些類顯得特別有用。
• 有三個繼承自抽象類Reference的類：SoftReference、WeakReference和PhantomReference。
• 當垃圾回收器正在考察的對象只能通過某個Reference對象才可獲得時，上訴這些不同的派生類為垃圾回收器提供了不同級別的間接性指示。
• 對象是可獲得的（reachable）：是指此對象可在程序中的某處找到，這意味著在棧中有一個普通引用，它指向此對象。如果一個對象是可獲得的，垃圾回收器就不能釋放它，因為它仍然為程序所用。如果一個對象不是可獲得的，那程序將無法使用它，所以將其回收是安全的。

對象引用四種類型（由強到弱排列，對應不同級別“可獲得性”）：

• 強引用：StrongReference：默認項。
• 軟引用：SoftReference：用以實現內存敏感的高速緩存。
• 弱引用：WeakReference：是為實現規範映射而設計，它不妨礙垃圾回收器回收映射的鍵或值。規範映射中對象的實例可以在程序的多出被同時使用，以節省存儲空間。--常用於避免內存洩露場景。
• 虛引用：PhantomReference：用以調度回收前的清理工作，它比Java終止機制更靈活。

12.1 WeakHashMap

• WeakHashMap用來保存WeakReference。它使得規範映射更易於使用，在這種映射中，每個值只保存一份實例以節省存儲空間。當程序需要那個值的時候，便在映射中查詢現有的對象，然後使用它。映射可將值做為其初始化的一部分，不過通常在需要的時候才生成值。
• 這是一種節約存儲空間的技術，因為WeakHashMap允許垃圾回收器自動清理鍵和值，所以十分便。對於WeakHashMap添加鍵和值的操作，則沒有什麼特殊要求，映射會自動使用WeakReference包裝他們。

13 Java 1.0/1.1 的容器（已廢棄，不建議再使用！）

• Vector（->Collection和List）：在Java 1.0/1.1 中，Vector是唯一可以自我擴展的序列，它實現類List接口。基本可以看做ArrayList，但是具有又長又難的方法名。在訂正過Java容器類類庫中，Vector被改造過，可將其歸類為Collection和List。
• Enumeration（->Iterator）：
• HashTable（->HashMap）：Hashtable實現Map接口，HashTable是線程安全的，在實現線程安全的方式是在修改整個數據之前鎖住整個HashTable。
• Stack（->LinkedList）：Java1.0/1.1的Stack是繼承Vector。所以他擁有Vector的所有特點和行為，再加上一些額外的Stack行為。
• BitSet（->EnumSet）：高效率存儲大量“開/關”信息，BitSet是最好的選擇。不過它的效率僅是對空間而言；如果需要高效的訪問時間，BitSet比本地數組稍慢一點。此外，BitSet的最小容量是long：64位。如果存儲的內容比較小，例如8位，那麼BitSet就浪費了一些空間。

閱讀更多 編程家園 的文章

關鍵字: 數據結構 容器 設計