使用集合的技巧

一、藏品清單

您可能還記得，Java 有集合——一種用於存儲相同類型對象的便捷工具。

讓我們試著回憶一下與集合相關的主要接口：

列表、集合、映射和隊列。

像往常一樣，工具不一定好或壞——重要的是您是否將它們用於預期目的。為此，我們必須徹底了解它們的具體功能，以便知道何時使用哪個集合。

1.清單

讓我們從最常用的集合開始。

列出盡可能接近普通的舊數組。

這個集合讓我們可以方便地存儲相同類型的對象列表，而不用擔心集合本身的大小，如果我們使用數組就必須擔心。集合的元素通過索引訪問。如果我們確切地知道一個對像在哪裡並且需要經常訪問它而不需要經常添加或刪除元素，那麼 List是理想的選擇。

2.設置

Set具有完全不同的結構。

當我們需要存儲唯一的對象時， Set是最合適的。例如，圖書館中的一組作者，其中每個作者都是唯一的。但是我們不能只是去從中獲取任何特定的作者。Set讓我們可以快速檢查特定作者是否存在於我們的圖書館中，即我們可以檢查Set中是否存在唯一對象。我們還可以遍歷整個集合，訪問每個元素，但這樣做並不是最優的。

換句話說，對於我們的圖書館，一個Set可以代表所有唯一作者的集合，以快速檢查是否存在任何特定作者。

3. 地圖

地圖更像是一個文件櫃，每個文件都經過簽名，可以存儲單個對像或整個結構。在我們需要維護從一個值到另一個值的映射的情況下，應該使用Map 。

對於Map，這些關係稱為鍵值對。

我們可以在我們的圖書館中使用這種結構，方法是將作者對像用作鍵，將書籍的列表（List對象）用作值。因此，在檢查Set以查看圖書館中是否存在作者對象之後，我們可以使用相同的作者對像從Map中獲取他或她的書籍的列表。

4.隊列

Queue是一個集合——驚喜！— 實現隊列的行為。隊列可以是LIFO（後進先出）或FIFO（先進先出）。更重要的是，隊列可以是雙向的，或“雙端”。

當添加到類中的對象需要按接收順序使用時，此結構很有用。以我們的圖書館為例。

我們可以將新來的訪客添加到隊列中，並依次為他們服務，發放他們來找的書。

正如我們所看到的，如果用於其預期目的，這些結構中的每一個都是好的。我們在一個庫示例中發現了所有四種類型的集合的良好用途。

2. 複雜性

如前所述，我們上面考慮的集合是接口，這意味著它們必須有實現才能讓我們使用它們。

就像用顯微鏡敲釘子不是最好的主意一樣，並非每個集合的實施都適合所有情況。

在為一項工作選擇合適的工具時，我們通常會考慮兩個特徵：

• 該工具與工作的匹配程度如何？
• 它完成工作的速度有多快？

我們花了一些時間弄清楚如何為工作選擇合適的工具，但它的速度是新事物。

在計算中，工具的速度通常用時間複雜度表示，並用大寫字母 O 表示。

時間複雜度到底是什麼？

簡單來說，時間複雜度表示集合中的算法執行特定操作（添加/刪除元素、搜索元素）所需的時間。

ArrayList 與 LinkedList

讓我們使用List接口的兩個實現 - ArrayList和LinkedList來看一下。

對於外觀，使用這些集合是相似的：

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

如您所見，對於這兩種集合類型，添加、獲取和刪除元素看起來是一樣的。這是因為它們是同一接口上的實現。但這就是相似之處結束的地方。

由於它們對List接口的不同實現，這兩個結構比其他結構更有效地執行不同的操作。

考慮刪除和添加一個元素。

如果我們需要從ArrayList的中間刪除一個元素，我們必須覆蓋列表中我們刪除的元素後面的任何部分。

假設我們有一個包含 5 個元素的列表，我們想要刪除第 3 個元素。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

在這種情況下，移除釋放了一個單元格，因此我們需要將第 4 個元素寫入第 3 個元素，將第 5 個元素寫入第 4 個元素。

這是非常低效的。

將元素添加到列表中間時也會發生同樣的情況。

LinkedList 的結構不同。添加或刪除元素很快，因為我​​們只需要更改前一個和下一個元素中的引用，從而從元素鏈中排除我們要刪除的對象。

回到同樣包含 5 個元素的列表示例，在刪除第 3 個元素之後，我們需要做的只是將第 2 個元素的引用更改為下一個元素，將第 4 個元素的引用更改為前一個元素。

當一個元素被添加到列表中時，同樣的過程發生，但相反。

請注意，與ArrayList相比，我們在LinkedList中需要做的工作要少得多。這只是 5 個元素。如果我們的列表有 100 個或更多元素， LinkedList的優越性將變得更加明顯。

但是如果我們通過索引訪問一個元素，情況會發生什麼變化呢？

這裡的一切都恰恰相反。

由於 ArrayList 的結構與普通數組相同，因此通過索引獲取任何元素對我們來說都非常容易。我們只需將指針移動到某個地方，然後從相應的單元格中獲取元素。

但是LinkedList根本不能那樣工作。我們必須遍歷列表的所有元素才能找到具有特定索引的元素。

我們是否應該嘗試用大 O 來表達所有這些？

讓我們從按索引訪問元素開始。

在ArrayList中，無論元素在列表中的位置如何，這一步都會發生。無論是在結尾還是開頭。

在這種情況下，時間複雜度將為O(1)。

在LinkedList中，我們必須遍歷等於所需索引值的多個元素。

這種操作的時間複雜度為O(n)，其中 n 是我們需要的元素的索引。

在這裡，您會看到我們放在大 O 括號中的數字對應於執行的操作數。

我們返回刪除和添加的外殼？

讓我們從鍊錶開始。

因為我們不需要做大量的操作來添加或刪除一個元素，而且這個操作的速度不以任何方式依賴於元素所在的位置，所以它的複雜度表示為 O(1)並表示保持不變。

ArrayList的這個操作的時間複雜度也是O(n)，我們稱之為線性複雜度。

在具有線性複雜度的算法中，運行時間直接取決於要處理的元素數量。它還可能取決於元素的位置，是在列表的開頭還是接近結尾。

時間複雜度也可以是對數的。這表示為O(log n)。

例如，考慮一個由 10 個數字組成的排序TreeSet。我們想找到數字 2。

由於列表已排序並且不包含重複項，我們可以將其分成兩半並檢查哪一半包含所需的數字，丟棄不相關的部分然後重複此過程直到我們到達所需的元素。最終，我們將找到（或找不到）處理 log(n) 個元素後的數字。

下表總結了其餘集合的時間複雜度。

現在我們有了一張顯示流行集合的時間複雜度的表格，我們可以回答為什麼在這麼多集合中我們最常使用ArrayList、HashSet和HashMap的問題。

只是它們對於大多數任務來說是最有效的 :)