Java集合框架
Java集合框架（Java collections framework）是一個包含一系列實作可重複使用集合的資料結構的類別和介面集合。雖然稱為「框架」，其使用方式卻像個函式庫。集合框架提供了定義各式各樣集合的介面和實作上述集合的類別。
與陣列的不同處
[編輯]集合和陣列在兩者保持物件參考核可被視作為一個團體上有著功能上的相似處。集合和陣列其中一點不同的是，集合在宣告時不需要指定固定的容量。集合可以在新增或移除內容時自動地增加或縮減其容量。 另外，集合無法收納基本資料型態，像是整數（int）、長整數（long）或者雙精度浮點數（double）。取而代之的是，集合可以收納上述基本資料型態的包裹類別（Integer、Long、Double）。[註 1][1]
歷史
[編輯]集合介面在JDK 1.2先行版版本時納入，並包含少數簡單的資料結構類別，但當時並未包含完整的集合框架。[2] 原本在Java典型集中物件的方法是使用陣列（array）、向量（Vector）或者雜湊表（Hashtable）類別來處理。但上述的類別並不容易擴展，而且並沒有一個標準的介面。[3] 當時若想使用可重用集合資料結構，也是有數種第三方框架可供選擇。最廣為使用的例如道格·利亞的集合包（Collections package）[4]的集合包[5]
集合框架主要由約書亞·布洛克設計且開發，並於JDK 1.2中導入。它重新使用了不少來自道格·利亞的集合包的概念和類別，並在最後使後者過時。[5] [6] 道格·利亞後來投入發展並發性Java包，並在其使用了和集合框架有關的類別。[7]而後來並發性工具在JDK 5.0以JSR 166導入。
架構
[編輯]在Java，幾乎全部的集合都衍生自java.util.Collection。集合介面定義了所有集合的基本部件。介面中定義了加入（add）和移除（remove）兩種方法來增加或移除該集合內的元素。另一個必要的方法例如轉成陣列（toArray），用於把該集合的所有轉換成基本陣列。最後，一個名為含有（contains）的方法用來檢查某元素是否在該集合內。集合這個介面是java.lang.Iterable的子介面，故此集合可被用於For-each函式的查詢目標。（Iterable介面包含方法疊代器（iterator）來讓For-each函式使用）。所有的集合都具有一個疊代器來遍詢集合內的所有元素。另外，集合也是一個Java的泛型。任何集合皆須要寫成能接受任何類別。例如：集合<字串>可以用來存放字串，而且在其中的所有元素提出來都被視作字串，而不需要另外轉型。[8]使用時，角括號裡面填入該集合應該存放哪種類別。
三種集合
[編輯]集合可分為三種：有序列表（ordered lists）、映射表（maps）和集（sets）。有序列表容許程式設計師依序地加入元素，並以同樣的順序取回元素，例如等候列表。在有序列表介面底下有兩個子介面，分別為列表（Lists）和佇列（Queue）。映射表使用索引來參考物件並取回其值。在映射表介面底下有一個子介面映射表（Map）。集是一種可供遍巡的無序集合，但當中不允許重複的物件存在。在其中有個子介面集（Set）。[1]
列表介面
[編輯]列表在集合框架下藉由java.util.List介面實作，其將列表定義為一種更靈活的陣列。元素有特定的順序，而且容許相同的元素存在。元素可被放置在特定的位置，也可以在列表中被搜尋。以下兩種舉例為實作了列表介面的具體物件:
- java.util.ArrayList:其將列表實作為一種陣列。當操作其方法並填入類別時，該種類別會把元素存在某個所屬陣列當中。
- java.util.LinkedList:這個類別將元素包裝成節點，而每個節點包含前一節點和後一節點的指標。這種列表藉由讀取上述的指標來在節點中巡查並操作元素。元素可以藉由操作指標來掛上和脫離節點，來簡單地實現新增或刪除。[9]
堆疊類別
[編輯]堆疊可由java.util.Stack建立。其提供方法來推入（push）或彈出（pop）當中的元素。堆疊會依循後進先出的原則來回傳元素。意即，最後推入的元素會最先彈出。java.util.Stack是Java所提供的堆疊標準實作。其延伸了java.util.Vector並加入了5種新操作來讓向量可被看成堆疊。除提供了推入和彈出方法外，還提供了窺（Seek）方法來檢查最上方的元素、檢查堆疊是否空白的方法、還有尋找並檢查某元素離最上方有多遠的方法。當堆疊被建立時，當中不含任何元素。
佇列類別
[編輯]java.util.Queue定義了佇列資料結構，也就是將元素以其加入的順序來排序的集合。新加入的元素會放在對列的最末端，而提出物件時會先從最頂端開始提出。這實現了先進先出的模式。在這介面下有java.util.LinkedList, java.util.ArrayDeque,和java.util.PriorityQueue。[10]
集介面
[編輯]Java的java.util.Set定義了集。集不能包含任何重複的元素，另外集也沒有順序。也因為如此，在集內的元素無法以索引存取。在集底下實作了雜湊集（java.util.HashSet）、連結雜湊集（java.util.LinkedHashSet）和樹狀集（java.util.TreeSet）。雜湊集使用雜湊映射表（java.util.HashMap）來儲存元素和其雜湊值來防止重複。連結雜湊集藉由建立雙向連結列表來按照各個元素的加入順序進行聯繫，如此可以保持這個集的順序。樹狀集使用紅黑樹來確保沒有重複的元素。另外，如此的實作容許樹狀集能實作已排序集（java.util.SortedSet）。[11] 跟一般的集所不同的是，已排序集會藉由元素的與之比較（compareTo）方法、或於已排序集建構式當中提供的函數，來對其中元素進行排序。如此可以輕鬆取得已排序集當中的第一和第末元素，或者由某最大和最小值為區間來取得子集。[12]
已排序集還可藉由可導航集（java.util.NavigableSet）介面擴充。可導航集和已排序集很像，不過有著額外的新方法，像是地板（floor）、天花板（ceiling）、更低（lower）和更高（higher）。這些方法可以按照某參數來在可導航集尋找符合條件的元素。另外，可導航集也提供了一個疊代器，可用於遍詢其中的元素。[13]
映射表介面
[編輯]Java的java.util.Map定義了映射表。映射表是一種以索引和元素掛鉤的簡單資料結構。如果在映射表內以雜湊值代表某元素的索引，則這個映射表實質上是一個集。如果以一個遞增號碼來做索引，則實質上為一個列表。在映射表底下實作了雜湊表（java.util.HashMap）、連結雜湊表（java.util.LinkedHashMap）、和樹狀表（java.util.TreeMap）。雜湊表會儲存索引值的雜湊值來做為比對並提出該索引連接的元素之用。連結雜湊表進一步拓展了上述架構，它增加了一個雙向連結串列來連結當中的元素，使其能保存元素加入時的順序。樹狀表使用紅黑樹來比對索引值。[14]
映射表介面藉由他的子介面，已排序映射表（java.util.SortedMap），得到進一步的拓展。已排序映射表會藉由索引的與之比較（compareTo）方法、或於已排序映射表建構式當中提供的函數，來對其中索引進行排序。如此可以輕鬆取得已排序映射表當中的第一和第末索引，或者由某最大和最小值為區間來取得索引與值來建立子映射表。[15]
參見
[編輯]注釋
[編輯]- ^ 注意基本型態宣告時用小寫開頭，包裹類別宣告時用大寫開頭
參考資料
[編輯]- ^ 1.0 1.1 Horstmann, Cay. Big Java Early Objects. 2014.
- ^ Java Collections Framework (PDF). IBM. [2011-01-01]. （原始內容 (PDF)存檔於2011-08-07）.
- ^ Dan Becker. Get started with the Java Collections Framework. JavaWorld. 1998-01-11 [2011-01-01]. （原始內容存檔於2010-03-30）.
Before Collections made its most welcome debut, the standard methods for grouping Java objects were via the array, the Vector, and the Hashtable. All three of these collections have different methods and syntax for accessing members: arrays use the square bracket ([]) symbols, Vector uses the elementAt method, and Hashtable uses
getandputmethods. - ^ Recursion Software. Need a good set of abstract data structures? ObjectSpace's JGL packs a punch!. Generic Collection Library. JavaWorld. 1997-01-06 [2011-01-01]. （原始內容存檔於2012-03-02）.
As with Java itself, the Java Generic Library borrows heavily from the C++ camp: It takes the best from C++'s STL, while leaving the C++ warts behind. Most C++ programmers today will know of their STL, but few are managing to exploit its potential.
- ^ 5.0 5.1 Doug Lea. Overview of the collections Package. [2011-01-01]. （原始內容存檔於2019-12-30）.
The Sun Java Development Kit JDK1.2 finally includes a standard set of collection classes. While there are some design and implementation differences, the JDK1.2 package contains most of the same basic abstractions, structure, and functionality as this package. For this reason, this collections package will NOT be further updated
- ^ The battle of the container frameworks: which should you use?. JavaWorld. 1999-01-01 [2011-01-01]. （原始內容存檔於2010-04-12）.
Comparing ObjectSpace Inc.'s JGL and Sun's Collections Framework turns out to be like comparing apples and kiwi fruits. At first sight, the two frameworks seem to be competing for the same developers, but after a closer inspection it is clear that the two cannot be compared fairly without acknowledging first that the two frameworks have different goals. If, like Sun's documentation states, Collections is going to homogenize Sun's own APIs (core API, extensions, etc.), then clearly Collections has to be great news, and a good thing, even to the most fanatic JGL addict. Provided Sun doesn't break its promise in this area, I'll be happy to invest my resources in adopting Collections in earnest.
- ^ Doug Lea. Overview of package util.concurrent Release 1.3.4. [2011-01-01]. （原始內容存檔於2020-12-18）.
Note: Upon release of J2SE 5.0, this package enters maintenance mode: Only essential corrections will be released. J2SE5 package java.util.concurrent includes improved, more efficient, standardized versions of the main components in this package.
- ^ Iterable (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2020-12-17）.
- ^ List (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2020-11-12）.
- ^ Queue (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2018-03-09）.
- ^ Set (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2020-11-12）.
- ^ SortedSet (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2020-07-30）.
- ^ NavigableSet (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2019-04-03]. （原始內容存檔於2020-11-12）.
- ^ Map (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2020-11-11）.
- ^ SortedMap (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. （原始內容存檔於2020-11-08）.
外部連結
[編輯]
_waving.svg)