Java集合框架Java collections framework)是一个包含一系列实现可重复使用集合的数据结构类别接口集合。虽然称为“框架”,其使用方式却像个函数库。集合框架提供了定义各式各样集合的接口和实现上述集合的类别。

java.util.Collection底下的类别和接口继承树
Java的java.util.Map底下的类别和接口继承树

与数组的不同处

编辑

集合和数组在两者保持物件参考核可被视作为一个团体上有着功能上的相似处。集合和数组其中一点不同的是,集合在声明时不需要指定固定的容量。集合可以在新增或移除内容时自动地增加或缩减其容量。 另外,集合无法收纳基本数据类型,像是整数(int)、长整数(long)或者双精度浮点数(double)。取而代之的是,集合可以收纳上述基本数据类型的封装类型(Integer、Long、Double)。[注 1][1]

历史

编辑

集合接口在JDK 1.2先行版版本时纳入,并包含少数简单的数据结构类别,但当时并未包含完整的集合框架。[2] 原本在Java典型集中物件的方法是使用数组(array)、向量(Vector)或者散列表(Hashtable)类别来处理。但上述的类别并不容易扩展,而且并没有一个标准的接口。[3] 当时若想使用可重用集合数据结构,也是有数种第三方框架可供选择。最广为使用的例如道格·利亚英语Doug Lea集合包(Collections package)[4]集合包[5]

集合框架主要由约书亚·布洛克设计且开发,并于JDK 1.2中导入。它重新使用了不少来自道格·利亚的集合包的概念和类别,并在最后使后者过时。[5] [6] 道格·利亚后来投入发展并发性Java包英语Java package,并在其使用了和集合框架有关的类别。[7]而后来并发性工具在JDK 5.0英语Java_version_history#J2SE 5.0JSR 166英语Java concurrency导入。

架构

编辑

在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. ^ 注意基本类型声明时用小写开头,封装类型声明时用大写开头

参考资料

编辑
  1. ^ 1.0 1.1 Horstmann, Cay. Big Java Early Objects. 2014. 
  2. ^ Java Collections Framework (PDF). IBM. [2011-01-01]. (原始内容 (PDF)存档于2011-08-07). 
  3. ^ 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 get and put methods. 
  4. ^ 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. ^ 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 
  6. ^ 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.  
  7. ^ 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. 
  8. ^ Iterable (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2020-12-17). 
  9. ^ List (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2020-11-12). 
  10. ^ Queue (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2018-03-09). 
  11. ^ Set (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2020-11-12). 
  12. ^ SortedSet (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2020-07-30). 
  13. ^ NavigableSet (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2019-04-03]. (原始内容存档于2020-11-12). 
  14. ^ Map (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2020-11-11). 
  15. ^ SortedMap (Java Platform SE 7 ). Docs.oracle.com. 2013-06-06 [2013-08-16]. (原始内容存档于2020-11-08). 

外部链接

编辑