路的開始
今天我想談談「
Java集合框架」這樣一個有趣的話題，或者簡單地說，關於集合。程式碼的大部分工作是以一種或另一種形式處理資料。取得使用者清單、取得地址清單等。以某種方式對它們進行排序、執行搜尋、比較它們。這就是為什麼收藏知識被認為是核心技能的原因。這就是為什麼我想談談它。此外，Java 開發人員面試中最常見的問題之一是集合。例如，「繪製集合的層次結構」。線上編譯器將幫助我們。例如，您可以使用「Tutorialspoint
Online Java Compiler」或
Repl.it。了解任何資料結構的路徑都是從普通變數（變數）開始的。在 Oracle 網站上，各種主題都表示為「路徑」或「蹤跡」。因此，了解 Java 的路徑稱為「
Trail：學習 Java 語言：目錄」。語言的基礎知識（即語言基礎）從變數開始。因此，讓我們來寫一段簡單的程式碼：
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
它在所有方面都很好，只是我們知道這段程式碼只對一個變數來說是好的和漂亮的。如果有多個怎麼辦？數組的發明是為了儲存一種類型的資料。在 Oracle 的同一 Trail 中，有一個單獨的部分專門介紹陣列。本節稱為：「
數組」。使用陣列也非常簡單：
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
數組解決了在一個地方儲存多個值的問題。但它有一個限制：數組大小是恆定的。如範例所示，如果我們說 size = 2，則它等於 2。就這樣。如果我們想要更大的數組，我們需要建立一個新實例。另外，對於數組來說，查找元素也是一件棘手的事情。有一個方法
Arrays.binarySearch，但此搜尋僅適用於已排序的數組（對於未排序的數組，結果是未定義的或根本不可預測）。也就是說，搜尋將迫使我們每次都進行排序。刪除也只會清除該值。因此，我們仍然不知道數組中實際有多少數據，我們只知道數組中有多少個單元格。刷新您有關數組的知識：
作為 Java 語言發展的結果，Java Collections Framework 出現在 JDK 1.2 中，我們今天將討論它。
收藏
從一開始就開始計算成本。為什麼要收藏？這個術語本身來自“類型理論”和“抽象資料類型”等內容。但如果你不看什麼高大上的東西，那麼當我們有幾個東西的時候，我們就可以稱它為「東西的集合」。收集物品的人。一般來說，「收集」一詞本身來自拉丁語。collectio 「收集，收集」。也就是說，集合是某物的集合，也是某些元素的容器。所以我們有一個元素的集合。我們可能想用它做什麼：
正如你所看到的，我們可能想要非常合乎邏輯的東西。我們也了解我們可能想要對多個集合執行某些操作：
因此，Java 開發人員編寫了java.util.Collection介面來描述所有集合的一般行為。Collection 介面是所有集合的起源處。集合是一種思想，它是所有集合應該如何表現的思想。因此，術語“集合”被表達為介面。當然，介面需要實作。介面
java.util.Collection有一個抽象類別
AbstractCollection，即一些“抽象集合”，它代表其他實作的骨架（如類別上方的 JavaDoc 中所寫
java.util.AbstractCollection）。說到集合，讓我們回過頭來記住我們想要迭代它們。這意味著我們要逐一迭代元素。這是一個非常重要的概念。因此，此介面
Collection繼承自
Iterable. 這非常重要，因為... 首先，所有 Iterable 都必須能夠根據其內容傳回一個 Iterator。其次，所有 Iterable 都可以在循環中使用
for-each-loop。正是在迭代器的幫助下實現了、、
AbstractCollection等方法。理解集合的路徑始於最常見的資料結構之一 - 列表，即 。
containstoArrayremoveList
清單
因此，列表在集合的層次結構中佔據著重要的位置：
正如我們所看到的，列表實作了
java.util.List介面。列表表示我們有一個按某種順序依次排列的元素的集合。每個元素都有一個索引（就像在陣列中一樣）。通常，清單允許您擁有具有相同值的元素。正如我們上面所說，
List它知道元素的索引。這允許您透過索引取得 (
get) 元素或為特定索引 ( ) 設定值
set。集合方法
add、
addAll、
remove允許您指定執行它們的索引。此外，y
List有自己的迭代器版本，稱為
ListIterator。此迭代器知道元素的索引，因此它不僅可以向前迭代，還可以向後迭代。它甚至可以從集合中的特定位置創建。在所有的實作中，最常用的有兩種：
ArrayList和
LinkedList。首先，它是一個基於數組（）的
ArrayList列表（）。這允許您實現
對元素的“隨機存取”。隨機存取是指立即透過索引檢索元素的能力，而不是迭代所有元素，直到找到具有所需索引的元素。正是以數組為基礎才能實現這一點。相反，它是一個鍊錶。鍊錶中的每個條目都以 形式表示，該形式儲存資料本身，以及指向下一個 (next) 和上一個 (previous) 的連結。從而實現「順序存取
」。很明顯，要找到第 5 個元素，我們必須從第一個元素到最後一個元素，因為 我們無法直接存取第五個元素。我們只能從第四個元素存取它。它們概念上的差異如下：
ListArrayLinkedListEntryEntryLinkedList
正如你所理解的，在工作上也存在差異。例如，新增元素。這些
LinkedList元素就像鏈條中的連結一樣簡單地連接起來。但
ArrayList它將元素儲存在數組中。正如我們所知，數組不能改變它的大小。那麼它是如何運作的呢
ArrayList？而且它的工作原理非常簡單。當陣列空間用完時，它會增加1.5倍。這是縮放代碼：
int newCapacity = oldCapacity + (oldCapacity >> 1); 操作上的另一個區別是元素的任何位移。例如，在中間新增或刪除元素時。若要從
LinkedList元素中刪除，只需刪除對此元素的參考即可。在 的情況下，
ArrayList我們每次都被迫使用 來移動元素
System.arraycopy。因此，元素越多，必須執行的操作就越多。更詳細的描述可以在這些文章中找到：
研究過 ArrayList 後，我們不禁會想起它的“前身”，即
java.util.Vector類別。它的不同之處
Vector在於
ArrayList使用集合的方法（新增、刪除等）是同步的。也就是說，如果一個線程（
Thread）添加元素，那麼其他線程將等待，直到第一個線程完成其工作。由於通常不需要線程安全，因此建議在這種情況下使用該類
ArrayList，如該類的 JavaDoc 中明確指出的那樣
Vector。另外，
Vector它的尺寸增加的不是1.5倍，
ArrayList而是2倍。否則，行為是相同的 -
Vector隱藏數組形式的元素存儲，並且添加/刪除元素具有與 中相同的結果
ArrayList。事實上，
Vector我們記住這一點是有原因的。如果我們查看 Javadoc，我們將在「直接已知子類別」中看到諸如
java.util.Stack之類的結構。堆疊是一個有趣的結構，它是一種 LIFO
last-in-first-out（後進先出）結構。Stack從英文翻譯過來就是堆疊（例如一疊書）。堆疊實作了附加方法：
peek(look,look)、
pop(push)、
push(push)。此方法
peek翻譯為look（例如，
peek inside the bag翻譯為“
look inside the bag ”，
peek through the keyhole翻譯為“
peek through the keyhole ”）。此方法可讓您查看堆疊的“頂部”，即 取得最後一個元素而不將其從堆疊中刪除（即不刪除）。該方法
push將一個新元素壓入（新增）到堆疊中並返回它，而元素方法將
pop壓入（刪除）並返回被刪除的元素。在所有三種情況（即檢視、彈出和推送）中，我們僅處理最後一個元素（即「堆疊頂部」）。這是棧結構的主要特徵。順便說一句，在《程式設計師的職業生涯》（破解編碼面試）一書中描述了一個有趣的任務來理解堆疊。有一個有趣的任務，使用「堆疊」結構（LIFO），您需要實現「隊列” ” 結構（先進先出）。它應該看起來像這樣：
這個任務的分析可以在這裡找到：《
Implement A Queue using Stacks - The Queue ADT》（LeetCode 上的「Implement A Queue Using Stacks」）。所以我們順利地轉向一種新的資料結構—佇列。
佇列
隊列是我們生活中熟悉的結構。去商店、去看醫生都要排隊。誰先到（First In），誰就先離開隊列（First Out）。在 Java 中，佇列由
java.util.Queue介面表示。根據佇列的Javadoc，佇列新增了以下方法：
正如您所看到的，有訂單方法（無法執行它們會出現異常）和請求方法（無法執行它們不會導致錯誤）。也可以獲得元素而不刪除它（檢視或元素）。隊列介面還有一個有用的後繼者 -
Deque。這就是所謂的「雙向隊列」。也就是說，這樣的佇列允許您從頭到尾都使用這個結構。文件中說“Deques也可以用作LIFO（後進先出）堆疊。這個介面應該優先於遺留的Stack類別使用。”，也就是說，建議使用Deque實作而不是使用堆疊。Javadoc 顯示了 Deque 介面描述的方法：
讓我們看看有哪些實作。我們會看到一個有趣的事實——LinkedList已經進入了隊列陣營）也就是說，LinkedList同時實現了
List, 和
Deque。但也有「僅限隊列」的情況，例如
PriorityQueue。她不常被人們記住，但卻是徒勞無功的。首先，您不能在此隊列中使用“不可比較的物件”，即 要么必須指定比較器，要么所有物件都必須具有可比較性。其次，「此實作為入隊和出隊方法提供了 O(log(n)) 時間」。對數複雜度的存在是有原因的。基於堆實現的PriorityQueue。Javadoc 說：“優先權佇列表示為平衡的二進位堆。” 其儲存本身是一個常規數組。必要時就會增長。當堆小時，增加2倍。然後是 50%。程式碼註解：「如果小則加倍；否則成長 50%」。優先權佇列和二元堆是一個單獨的主題。因此，欲了解更多資訊：
一個實作
java.util.Deque可以是
java.util.ArrayDeque類別。即列表可以使用鍊錶和數組來實現，隊列也可以使用數組或鍊錶來實現。
Queue和介面
Deque具有代表“阻塞隊列”的後代：
BlockingQueue和
BlockingDeque。以下是與常規佇列相比的介面變化：
讓我們來看一些阻塞隊列的範例。但它們很有趣。例如，BlockingQueue 的實作方式有：
PriorityBlockingQueue、
SynchronousQueue、 ArrayBlockingQueue 、
DelayQueue、
LinkedBlockingQueue。但
BlockingDeque他們實現了標準集合框架中的所有內容
LinkedBlockingDeque。每個隊列都是單獨審查的主題。在本次審查的框架內，我們不僅將使用 來描述類別層次結構
List，而且還將使用 來描述類別層次結構
Queue：
從圖中我們可以看出，Java Collections Framework 的介面和類別是高度交織的。讓我們加入層次結構的另一個分支 -
Set。
放
Set——翻譯為「設定」。它與佇列和列表的不同之處
Set在於它對元素儲存的更大抽象。
Set- 就像一袋物體，我們不知道這些物體是如何定位的以及它們放置的順序。
在 Java 中，這樣的集合由java.util.Set介面表示。正如文件所說，
Set這是一個「不包含重複元素的集合」。有趣的是，介面本身並
Set沒有為介面添加新的方法
Collection，而只是澄清了要求（關於哪些內容不應包含重複項）。此外，從前面的描述可以看出，您不能簡單地
Set從中獲取元素。迭代器用於取得元素。
Set還有幾個與之相關的介面。第一個是
SortedSet。顧名思義，
SortedSet它表示這樣的集合是有序的，因此元素實作介面
Comparable或被指定
Comparator。此外，
SortedSet它還提供了幾種有趣的方法：
此外，還有方法
first（按值最小元素）和
last（按值最大元素）。有
SortedSet一個繼承人——
NavigableSet。此介面的目的是描述更準確地識別適當元素所需的導航方法。有趣的是
NavigableSet，它為通常的迭代器（從最小到最大）添加了一個相反順序的迭代器 -
descendingIterator。此外，
NavigableSet它還允許您使用該方法
descendingSet來獲取您自己的視圖（View），其中的元素順序相反。之所以這樣稱呼它，是
View因為透過結果元素，您可以更改原始元素的元素
Set。也就是說，本質上，它是原始資料以不同方式的表示，而不是它的副本。有趣的是
NavigableSet， 和 一樣
Queue，可以處理
pollFirst（最小）和
pollLast（最大）元素。也就是說，它會取得該元素並將其從集合中刪除。有哪些具體的實現方式？首先，最著名的實作是基於雜湊碼 -
HashSet。另一個同樣著名的實作是基於紅黑樹 -
TreeSet。讓我們完成我們的圖表：
在藏品中，仍需要理清隱士的等級制度。乍一看，這是站在一邊的 -
java.util.Map。
地圖
映射是一種按鍵儲存資料的資料結構。例如，密鑰可以是 ID 或城市代碼。正是透過這個鍵來搜尋數據。有趣的是，這些卡片是分開展示的。根據開發人員的說法（請參閱「
Java Collections API Design FAQ」），鍵值映射不是集合。映射可以更快被認為是鍵的集合、值的集合、鍵值對的集合。這是一種非常有趣的動物。卡片提供哪些方法？讓我們來看看 Java API 介面
java.util.Map。因為 由於映射不是集合（它們不繼承自集合），因此它們不包含
contains. 這是合乎邏輯的。映射由鍵和值組成。該方法應該檢查其中哪些
contains以及如何避免混淆？因此，此介面
Map有兩個不同的版本：（
containsKey包含鍵）和
containsValue（包含值）。使用它
keySet可以讓您獲得一組密鑰（相同的
Set）。並且使用該方法
values我們可以取得map中的值的集合。映射中的鍵是唯一的，這是資料結構所強調的
Set。值可以重複，這是Collection資料結構所強調的。另外，使用該方法
entrySet我們可以得到一組鍵值對。您可以在最詳細的分析中閱讀有關卡實現的更多資訊：
我還想看看與和
HashMap非常相似的內容。它們甚至具有相似的介面：、和。所以我們的最終地圖將如下所示：
HashSetTreeMapTreeSetNavigableSetNavigableMapSortedSetSortedMap
我們可以結束一個有趣的事實，集合
Set內部使用
Map，其中添加的值是鍵，並且值在各處都是相同的。這很有趣，因為它
Map不是一個集合並返回
Set，它是一個集合但實際上是作為 實現的
Map。有點超現實，但結果就是這樣）
結論
好消息是這篇評論到這裡就結束了。壞消息是這是一篇評論性很強的文章。每個集合的每個實作都值得一篇單獨的文章，對於我們看不見的每個演算法也是如此。但本次審查的目的是記住它們是什麼以及介面之間的連接是什麼。我希望經過深思熟慮的閱讀後，你能夠憑記憶畫出集合的圖表。
好吧，像往常一樣，一些鏈接：
#維亞切斯拉夫
GO TO FULL VERSION