java 之容器Java容器的基本概念疊代器ListStackSetMap

在java中，我們想要儲存對象可以使用很多種手段。我們之前了解過的數組就是其中之一。但是數組具有固定的尺寸，而通常來說，程式總是在運作時根據條件來建立對象，我們無法預知将要建立對象的個數以及類型，是以java推出了容器類來解決這一問題。

java的容器類分為<code>list</code>,<code>set</code>,<code>queue</code>和<code>map</code>。我們也稱它們為集合類(collection)。

java使用泛型來實作容器類，例如我們要使用順序表這一資料結構，java提供了arraylist和linkedlist兩種實作類，arraylist的實作就是基于數組的。比如我們要存儲一組使用者，在<code>java8</code>之前的版本，我們就可以這樣聲明對象：<code>list&lt;user&gt; users = new arraylist&lt;user&gt;();</code>。然後通過<code>add</code>方法來添加變量。

如果你是一個喜歡新事物，也不妨嘗試下<code>java7</code>,它可以對泛型的目标類型進行推斷。我們就可以這樣聲明這個對象<code>list&lt;user&gt; users = new arraylist&lt;&gt;();</code>。

在<code>java7</code>中，編譯器會根據變量聲明時的泛型類型自動推斷出執行個體化所用的泛型類型。但是它在建立泛型執行個體時的類型推斷是有限制的：隻有構造器的參數化類型在上下文中被顯著的聲明了，才可以使用類型推斷，否則不行。比如：

而在<code>java8</code>中，它支援兩種泛型的目标類型推斷：

1.支援通過方法上下文推斷泛型目标類型

2.支援在方法調用鍊路當中，泛型類型推斷傳遞到最後一個方法

上述程式可以更改如下：

java容器類庫是用來儲存對象的，他有兩種不同的概念：

<code>collection</code>。獨立元素的序列，這些元素都服從一條或多條規則。<code>list</code>、<code>set</code>以及<code>queue</code>都是<code>collection</code>的一種，<code>list</code>必須按照順序儲存元素，而<code>set</code>不能有重複元素，<code>queue</code>需要按照排隊規則來确定對象的順序。

<code>map</code>。<code>map</code>是鍵值對類型，允許使用者通過鍵來查找對象。<code>arraylist</code>允許使用數字來查找值，<code>hash表</code>允許我們使用另一個對象來查找某個對象。

盡管存在這兩種概念，我們在工程中，大部分代碼還是和接口打交道。<code>collection</code>接口概括了序列的概念，即存放一組對象的方式。<code>arraylist</code>,<code>hashset</code>等具體類均實作了collection接口或collection接口的子接口（list接口和set接口等）。

collection接口的定義如下：

我們可以看出collection接口實際上繼承了<code>iterable</code>接口，實作這個接口的類可以使用疊代器以及<code>foreach</code>文法進行周遊。

size, isempty, contains, iterator, toarray, add, remove, containall, addall, removeall, clear方法分别表示擷取這個collection類型的對象的元素個數，是否為空，是否包含某個元素，擷取疊代器，轉換為數組，增加元素，删除元素，某個collection對象是否為它的子集以及進行取差集和清空操作。

除了上述成員方法，<code>java.utils</code>包中的<code>arrays</code>和<code>collections</code>類中還提供了很多實用的方法，如：

arrays.aslist()方法可以接受數組或逗号分隔的元素清單，并将其轉化為一個<code>list</code>對象。

collections.addall()方法接受一個<code>collection</code>對象和一個數組或以逗号分隔的清單将其加入到集合當中。

等等

我們可以這樣使用：

使用aslist()方法輸出産生的對象需要注意一些問題，因為在這種情況下，它的底層表示仍然是數組，是以我們是不能夠該表它的尺寸的。這時使用<code>add</code>和<code>delete</code>方法可能會引發改變數組尺寸的嘗試，會在運作時得到<code>unsupported operation</code>錯誤。

如果要使用可以改變尺寸的list,我推薦大家在擷取到aslist()方法的輸出後，再構造一個arraylist。

從之前的collection接口中可以看出，任何容器類，都可以以某種方式插入、擷取和删除元素。add()作為最基本的插入元素方法而get()則是基本取元素的方法。

但是如果我們僅僅使用get和add方法來進行元素操作，如果将一個類的方法實作了，如果想要将相同的代碼用在其他容器類中就會遇到問題，那麼我們如何解決這一問題呢？

在這裡我們就引入了面向對象的設計模式<code>疊代器</code>模式。疊代器是一個對象，它的工作是周遊并選擇序列中的對象。用戶端不需要知道序列的底層架構。

java的iterator的定義如下：

我們可以使用：

next()方法來擷取序列的下一個元素。

hasnext()檢查序列中是否還有元素。

使用remove()将疊代器新近傳回的元素删除。比如我們要周遊一個容器：

iterator還有一些功能更為強大的子類型，我會在下文予以介紹。在接下來的幾節我會依次和大家介紹java容器類中的幾種接口。

list可以将元素維護在特定的序列中。list接口繼承于collection接口，并在此基礎上添加了大量的方法，使得我們可以在list中間進行元素的插入和移動。

list有兩種類型分别為：

arraylist，擅長随機通路元素，但是插入、删除元素較慢

linkedlist,擅長插入、删除和移動元素，但是随機通路元素性能較低。

提示

學過資料結構的朋友們應該都知道，arraylist是我們平時所使用的數組，而linkedlist就是連結清單。

數組的存儲在記憶體空間中是連續的。是以在底層，我們可以通過每個元素所占的記憶體大小以及偏移量計算出每個元素所在的起始位址。但是在删除、插入元素時，由于需要保證資料存儲位置的連續性，我們需要對它周圍的元素進行搬移，而周圍元素的搬移又會引起後續其他元素的搬移需求，是以最終所導緻的移動操作很多。

而連結清單在記憶體中并不是連續存儲的。它是一種邏輯順序結構，每個連結清單存儲的對象，都會存儲下一個元素以及上一個元素的引用，通過引用來進行疊代。在删除、移動和插入時，我們不需要對元素的實際位置進行搬移，僅僅需要改變引用就可以了。但是由于它是邏輯上的順序表，我們不能夠靜态的計算它的位置，隻能一個一個的尋找，是以它的随機存取性能較低。

list接口的執行個體化對象可以使用collection的所有方法：

在使用時，我們會發現arraylist類型的對象和linkedlist類型對象性能的不同。其中需要注意的是倒數第二行我們使用的sublist函數是list接口獨有的，它可以擷取順序表的一部分生成一個新的list。

listiterator是更為強大的iterator的子類型，但是它僅僅針對list的類進行通路。listiterator可以進行雙向移動、擷取疊代器所處元素的前後元素的索引，還可以使用set()方法替換它通路過的最後一個元素。如：

<code>stack</code>實作了棧資料結構，它是一種lifo(後進先出)的容器。也就是我們先放進棧的元素，在使用時會先擷取到最後放入的元素。

set是一種不儲存重複元素的資料結構。如果我們将多個相同元素放入set中，它僅僅會儲存一個。使用set很适合進行查找操作，java中提供了一個hashset類，它的查找速度很快，适合用作快速查找。

在使用時與其他collection的使用類似：

我們在set中加入了一系列的詞彙，其中有一些重複詞彙，但是在實際輸出時我們會發現，并不存在那麼多的元素，而僅僅列印不重複元素。

set有多種實作：

hashset，使用了散列方式進行存儲。

treeset，将元素存儲在紅黑數當中。它會對集合元素進行排序。

linkedhashset，使用連結清單和哈希表來實作set。

具體的實作我們可以在資料結構的教程中深入了解，在這裡我隻與大家分享該如何在工程中選取資料結構。比如我們需要擷取一個排好序的數列集合。我們就可以使用treeset，插入元素後，元素就會按照順序存儲。我們可以很友善的插入或删除元素同時保證排序品質。如果我們不需要排序，隻需要保證插入和查找效率，那我們就可以僅僅使用hashset來進行工作，我們可以很友善的通過它來測試元素的歸屬性，以及進行一系列的集合操作。

map可以将一個對象映射到另一個對象。在工程上，它是十分重要的資料結構。比如我們有一系列使用者分組對象它儲存了使用者分組的資訊，我們經常需要通過使用者分組對象擷取這個分組的所有使用者。如果我們僅僅通過list進行存儲，在查找時的工作量是很大的。因為我們需要從頭開始周遊list，判斷每個元素是否屬于這一分組，但是引入map後就簡單許多了，我們可以将一個對象映射到另一個對象上，是以可以這樣實作：

這次我們第一次用到了多元的實作，map中嵌套list，事實上容器的嵌套層次是可以很深的。我們甚至将在map中的list再嵌套一個set。但是我們使用何種資料結構，要取決于我們程式的需求，我們資料結構的組合選擇需要最大程度的滿足我們的需求并盡可能地提高程式的效率。

map資料結構除了上述映射擷取功能以外，還可以擷取鍵、值或鍵值對的集合，分别使用keyset, value以及entryset。比如我們要周遊map：