Java集合框架概述
前言
Java集合框架概述; 主要总述Java集合框架的设计理念, 组成和基本接口(及其区别等)
Java
集合框架系列博客:
正文
一. 设计理念
在Java 2之前,Java是没有完整的集合框架的。它只有一些简单的可以自扩展的容器类,比如Vector,Stack,Hashtable等)
Java集合其实就是一组对象的集合
独立于实现细节, 方便重用, 保证向下兼容(即保留了
Vector
等旧的API)加强了API之间的互通信, 减少了新API的学习: 提供尽量统一的接口
二. 基本组成
2.1 总述
Java集合框架主要分为三个部分: 接口, 实现和算法
2.1-1 接口
接口指的是以Collection
和Map
为起始的一系列公用接口
实际上从Map
出发的并不是真正的集合, 只是其包含集合视图操作, 所以也将其归入集合框架中
从Collection
出发的公用接口主要有以下几个, 也是这次会着重讲解和比较的; 当然, 下面的接口并不全面, 在后面会逐渐扩展和补充
从Map
出发的公用接口如下
当然, 上述列举出来的子接口都是直接继承自Collection
或者Map
, 对于其子接口的子接口, 这里并没有列出在这里(比如NavigableMap
接口是SortedMap
接口的子接口, 而不是直接继承Map
的, 所以这里并没有直接列出来)
2.1-2 实现
实现指的是接口的实现类, 这里笔者在官网找到一张表, 如下, 很好的列出了平时重点所用的实现类
Interface | Hash Table | Resizable Array | Balanced Tree | Linked List | Hash Table + Linked List |
---|---|---|---|---|---|
Set | HashSet | TreeSet | LinkedHashSet | ||
List | ArrayList | LinkedList | |||
Deque | ArrayDeque | LinkedList | |||
Map | HashMap | TreeMap | LinkedHashMap |
当然, 还应该包含Java 2以前几个旧API, 即: Vector
, Stack
, Hashtable
2.1-3 算法
(1). 算法
算法指的是以Collections
为主的提供的一系列对集合的操作, 参见下图, 列出了其提供的常用算法
下面对上述方法进行一些简单解释
sort(List)
: 使用归并排序, 保证NlogN
的时间复杂度和稳定性binarySearch(List, Object)
: 在一个有序的List
中使用二分查找reverse(List)
: 逆转List
shuffle(List)
: 将List
中的元素随机重排fill(List, Object)
: 使用指定值(Object
)覆盖List
中所有元素copy(List dest, List src)
: 拷贝min(Collection)
: 返回最小值max(Collection)
: 返回最大值rotate(List list, int distance)
: 将List
中元素旋转指定distance
replaceAll(List list, Object oldVal, Object newVal)
: 将List
中出现的所有oldVal
替换为newVal
indexOfSubList(List source, List target)
: 返回source
中与target
匹配的第一个子项的首元素索引lastIndexOfSubList(List source, List target)
: 返回最后一个匹配子项的首元素索引swap(List, int, int)
: 交换指定位置的两个元素frequency(Collection, Object)
: 找出指定元素出现次数disjoint(Collection, Collection)
: 判断两个集合是否包含相同元素(即集合是否相交)addAll(Collection<? super T>, T...)
: 将指定元素添加到指定集合中
(2). 包装类
当然, 实际上Collections
提供的不仅仅是针对集合的算法, 其还提供了一系列对集合的包装类(即Wrapper
), 主要包括以下三大类:
Collections.unmodifiableInterface()
: 返回一个不可修改的集合, 包括UnmodifiableCollection
,UnmodifiableSet
,UnmodifiableList
; 实现原理是在修改集合的操作上(如add()
,remove()
等)抛出异常Collections.synchronizedInterface()
: 返回一个线程安全的集合, 包括SynchronizedCollection
,SynchronizedSet
,SynchronizedList
; 实现原理是在需要同步的方法上添加synchronized
限制Collections.checkedInterface()
: 返回一个类型检查的集合, 包括CheckedCollection
,CheckedQueue
,CheckedSet
,CheckedList
; 实现原理是在add()
的时候进行类型检查, 如果是非法类型, 就抛出异常ClassCastException
; 这里的类型检查实际上是使用Class.isInstance()
来检查的, 关于该方法和instanceof
运算符的区别, 参见博客; (大致上, 二者是等价的, 只是isInstance()
是在运行时才进行类型检查, 故可用于反射, 泛型;
但是instanceof
需要在编译时知道类的具体类型(重点理解在动态等价))
这些包装类的作用主要是满足平时一些特殊的需求, 比如同步, 不可修改等
三. 基本接口
在这一节, 主要讲解上面提到的几个基本接口, 这里不会涉及到其实现类
3.1 Collection
Collection
是集合框架中一个最顶层的基本接口, 提供了一个数据集的基本描述, 在官方API中并没有提供其直接实现类, 而是在其基础上提供了进一步的限制接口, 即List
, Set
, Queue
; 这样做的好处有:
代码复用: 从面向对象的角度讲, 抽取出一个*接口, 有助于用户代码复用, 即编写一个接口, 实现不同传参(
Collection
的各种实现类), 实际上也是利用了多态(官方文档的解释是: 实现最大通用性)易于扩展: 符合面向对象的思想, 即将数据集抽象, 通过不同的需求对其实现不同方便的限制, 易于扩展; 同时减少新API学习成本
Collection
提供了数据操作的基本方法, 如add()
, remove()
, size()
, clear()
等; 同时, 其还继承了Iterable
接口, 这个接口是用于使用迭代器遍历集合用的, 使用迭代器遍历集合的优点是我们不必知道集合的内部结果,集合的内部结构、状态由Iterator
来维持, 通过统一的方法hasNext()
, next()
来判断和获取下一个元素
3.2 List
List
在Collection
上做的限制是, 元素有序(但并不是排序), 允许重复元素; 同时还将迭代器换成了ListIterator
; 关于ListIterator
, 其允许双向的迭代, 以及元素插入(ListIterator.add()
), 删除(ListIterator.remove()
)和替换ListIterator.set()
在JDK9
中, 还提供了一个List.of()
的静态方法, 用于返回一个不可变List
(Immutable List
)
3.3 Set
Set
在Collection
上做的限制是, 元素不重复, 至多一个null元素
在JDK9
中, 还提供了一个Set.of()
的静态方法, 用于返回一个不可变的Set
3.4 Queue
Queue
在Collection
上做的限制是, 除了Collection
提供的基本操作外, 还提供了一些额外的操作, 分为两类, 一个返回特定值, 另一个抛出异常, 见下表
Throw Exception | Return Special Value |
---|---|
Insert | add(e) |
Remove | remove() |
Examine | element() |
3.5 Map
Map
本质上是一组键值对, Map
允许单独访问key
(通过keySet()
返回key
的Set
), 也可以单独访问value
(通过values()
方法返回value
的Collection
), 也可以通过entrySet()
获取key-value
的对应关系