前言
通常, 我们总是在程序运行过程中才获得一些条件去创建对象, 这些动态创建的对象就需要使用一些方式去保存. 我们可以使用数组去存储, 但是需要注意数组的尺寸一旦定义便不可修改, 而我们并不知道程序在运行过程中会产生多少对象, 于是数组的尺寸便成了限制. Java 实用类库还提供了一套的容器类来解决这个问题, 基本类型为: List ,Set,Queue 和 Map. 这些对象类型也称为集合类, 但是由于 Java 类库使用了 Collection 这个名字来指代该类库中的一个特殊子集, 所以使用术语 "容器" 来称呼它们. 下面将简单介绍 Java 容器类库的基本概念和功能, 每个容器的不同版本实现和和从整体分析容器之间的联系.
Java 容器类库概览
Java 容器类的框架图
Java 容器类库的主要作用是 "保存对象", 我们将其划分成以下两个不同的概念:
Collection
一个独立的元素序列(一种存放一组对象的方式), 这些元素都服从一条或多条规则. List 必须按照插入的顺序保存元素; Set 中不能有重复的元素; Queue 按排队规则来确定对象产生的顺序.
Collection 是一个高度抽象的容器接口, 其中包含了容器的基本操作和属性.
Map
一组成对的 "键值对" 对象, 允许你使用键来查找值.
框架类图中还包含了许多 Abstract 类, 主要方便于我们创建容器的实例, Abstract 类中已基本实现了接口中的方法, 我们只需要选择我们需要的方法进行覆盖即可.
Iterator
我们再来看 Iterator, 我们通常是使用 Iterator 迭代器来遍历容器. 上图存在的 Collection 依赖于 Iterator 是指: 实现 Collection 需要实现 iterator()函数, 可以返回一个 Iterator 对象. ListIterator 是专门用于遍历 List 的迭代器.
工具类 Arrays 和 Collections 为容器添加元素
java.util 包中的 Arrays 和 Collections 类中包含了很多的实用方法. Arrays 类中包含操作数组的各种方法, 还包含一个静态的 Arrays.asList()方法接受一个数组或是用逗号分隔的元素列表, 将其转换成一个列表对象. Collection 类包含对集合操作的各种方法. 我们也可以使用 Collections.addAll()想容器中添加一组元素. Collections.addAll()接受一个 Collection 对象以及一个数组或者用逗号分隔的元素列表, 将元素添加到 Collection 对象中.
Arrays.asList()的底层实现是一个数组, 即使用 Arrays.asList()生成的 List 的尺寸是不可以修改的(添加或删除元素), 否则将会抛出 UnsupportedOperationException 异常.
List
List 接口继承自 Collection 接口, 用于 Collection 中的所有方法, 在 Collection 的基础上也添加了许多方法, 使得可以在 List 中插入和删除元素. List 有两种基本的实现: ArrayList 和 LinkedList
基本的 ArrayList, 它适合于随机访问元素, 但是在插入和删除元素时就比较慢
LinkedList 适合于在元素插入和删除较频繁时使用, 随机访问的速度比较慢
Set
Set 中不保存重复的元素, 含义同数学概念上的集合. Set 常用于测试归属性, 即查询某个元素是否在某个 Set 中. 正因为如此查找也就成了 Set 中重要的操作. 通常会选择 HashSet 的实现, 它对快速查找进行了优化. Set 也有多种不同的实现, 不同的 Set 实现不仅具有不同的行为, 而且它们对于可以在特定的 Set 中防止元素的类型也有不同的要求.
Set(interface)
存入 Set 的每个元素必须是唯一对的. 加入 Set 的元素必须定义 equals()方法以确保对象的唯一性. Set 接口不保证维护元素的次序.
HashSet
为快速查找而设计的 Set. 存入 HashSet 的元素必须定义 hashCode(). 使用 HashMap 实现.
TreeSet
保持次序的 Set, 底层为树结构. 使用它可以从 Set 中提取有序的序列. 元素必须实现 Comparable 接口. 使用 TreeSet 实现.
LinkedHashSet
具有 HashSet 的查询速度, 且内部使用链表维护元素的顺序 (插入的次序). 在使用迭代器遍历该 Set 时, 结果会按照元素插入的次序显示. 元素也必须定义 hashCode() 方法
Map
Map 有以下特点:
Map 是将键映射到值的键值对 (key-value) 接口
映射中不能包含重复的键, 每个键最多可以映射到一个值, 但是一个值可以被多个键映射
Map 提供了三个 Set 视图供我们访问: 键的 Set, 值的 Set 和键值对的 Set
映射的顺序定义为访问的映射 Set 上的迭代器返回元素的顺序. TreeMa 类, 可以对映射的顺序做出特定保证; 其他的, 则不能保证
可变对象作为映射键需要非常小心
Map 的实现类应该提供两个 "标准" 构造函数
第一个, void(无参数)构造方法, 用于创建空映射
第二个, 带有单个 Map 类型参数的构造方法, 用于创建一个与其参数具有相同键 - 值映射关系的新映射. 带有单个 Map 类型参数的构造方法, 用于创建一个与其参数具有相同键 - 值映射关系的新映射
Map 的几种基本实现:
HashMap
Map 是基于散列表的实现 (取代了 HashTable).HashMap 使用散列码(对象 hashCode() 生成的值)来进行快速搜索.
LinkedHashMap
类似于 HashMap, 但是迭代的时候, 取得键值对的顺序是起插入的顺序, 或者是最近最少使用 (LRU) 的次序. 只比 HashMap 慢一点, 而迭代访问的时候更快, 因为使用链表维护了内部次序.
TreeMap
基于红黑树的实现. 查看 "键" 或者 "键值对" 时, 它们会被排序 (次序由 Comparable 或 Comparator 决定).TreeMap 的特点在于所得到的结果是经过排序的. TreeMap 是唯一的带有 subMap() 的 Map, 可以返回一个子树.
WeakHashMap
弱键 (weak key) 映射, 允许释放映射所指向的对象, 这是为了解决某类特殊问题而设计的. 如果映射之外没有引用指向某个 "键", 则此 "键" 可以被垃圾回收.
ConcurrentHashMap
一种线程安全的 Map, 不涉及同步加锁. 在并发中还会介绍.
Stack 和 Queue
Stack 是一个先进后出 (LIFO) 的容器. 往盒子中放书, 先放进去的最后才拿得出来, 最后放进去的第一个就可以取出, 这种模型就是栈 (Stack) 可以描述的. LinkedList 中有可以实现栈所有功能的方法, 有时也可以直接将 LinkedList 作为栈使用.
队列是一个典型的先进先出 (FIFO) 的容器. 事物放进容器的顺序和取出的顺序是相同的(优先级队列根据事物优先级出队事物). 队列常被当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径. 队列在并发编程中特别重要. 同样, LinkedList 也提供了方法支持队列的行为, 并且它实现了 Queue 接口.
优先级队列 PriorityQueue
先进先出描述了典型的队列规则. 队列规则是指在给定一组队列的元素情况下, 确定下一个弹出队列的元素的规则. 优先级队列声明的下一个弹出的元素是最需要的元素(具有最高优先级的元素).
我们可以在 PriorityQueue 上调用 offer()方法来插入一个对象, 这个对象就会在队列中被排序, 默认排序为自然排序, 即按插入的先后进行排序, 但是我们可以通过提供自己的 Comparator 来修改这个排序. 当调用 peek(),poll()和 remove()方法时, 将获取队列优先级最高的元素.
优先级队列算法实现的数据结构通常是一个堆.
迭代器
对于访问容器而言, 有没有一种方式使得同一份遍历的代码可以适用于不同类型的容器? 要实现这样的目的就可以使用迭代器. 使用迭代器对象, 遍历并选择序列中的对象, 而客户端不必知道或关心该序列底层的结构. Java 中对迭代器有一些限制, 比如 Java 的 Iterator 只能单向移动, 这个 Iterator 只能用来:
使用 next()方法获得序列的下一个元素
使用 hasNext()方法检查序列中是否还有元素
使用 remove()方法将迭代器新近返回的元素删除, 意味着在调用 remove()之前必须先调用 next()
API 中的 Iterator 接口中方法如上, 实现 Iterator 对象需要实现 hashNext()方法和 next()方法, remove 方法是一个可选操作. forEachRemaining 是 Java 1.8(Java SE8)中加入的方法, 用于 Lambda 表达式.
举一个简单的使用迭代器访问容器的例子:
- class Cat{
- private static int counter = 0;
- private int id = counter++;
- @Override
- public String toString() {
- return "Cat:" + id;
- }
- }
- public class IteratorAccessContainer {
- // 不包含任何容器类型信息的遍历容器方法
- public static void showElement(Iterator<Cat> it) {
- while (it.hasNext()) { //hasNext()检查序列中是否还有元素
- Cat cat = it.next(); //next()返回序列中的元素
- System.out.print(cat + "\t");
- }
- System.out.println();
- }
- public static void main(String[] args) {
- ArrayList<Cat> cats1 = new ArrayList<Cat>();
- LinkedList<Cat> cats2 = new LinkedList<>(); // 可以省略类型参数 编译器可自动推断出
- HashSet<Cat> cats3 = new HashSet<>();
- for(int i=0;i<3; i++) {
- cats1.add(new Cat());
- cats2.add(new Cat());
- cats3.add(new Cat());
- }
- showElement(cats1.iterator());
- showElement(cats2.iterator());
- showElement(cats3.iterator());
- }
- }
- /*
- output:
- Cat: 0 Cat: 3 Cat: 6
- Cat: 1 Cat: 4 Cat: 7
- Cat: 2 Cat: 8 Cat: 5
- */
showElement()方法不包含任何有关它遍历的序列类型信息, 这就展示了 Iterator 的好处: 能够将遍历序列的操作与序列底层结构分离. 也可以说, 迭代器统一了对容器的访问方式.
从容器框架图中我们可以看出, Collection 是描述所有序列容器的共性的根接口. 但是在 C++ 中, 标准的 C++ 类库中没有其他容器的任何公共基类, 容器之间的共性都是通过迭代器达成的. 在 Java 中, 则将两种方法绑定到了一起, 实现 Collection 的同时也要实现 iterator()方法(返回该容器的迭代器).
ListIterator
ListIterator 是一个更加强大的 Iterator 子类型, 但是它只能用于各种 List 的访问. Iterator 只能前向移动, 但 ListIterator 允许我们可以前后移动. 它还可以产生相对于迭代器在列表中指向当前位置的前一个和后一个索引, 并且可以使用 set()方法替换它访问过的最后一个元素. remove()方法可以删除它访问过的最后一个元素. 需要注意, 这两处的最后一个元素只的都是调用 next()或者 previous 返回的元素, 也就意味着调用 set(),remove()这两个方法之前, 要先调用 next()或者 previous().
需要注意 ListIterator 在序列中的游标位置与 Iterator 不同, Iterator 的游标位置始终位于调用 previous()将返回的元素和调用 next()将返回的元素之间. 长度为 n 的列表的迭代器的游标位置有 n+1 个.
使用 ListIterator 对列表进行正向和返回迭代, 以及使用 set()替换列表元素的例子:
- public class ListIteration {
- public static void main(String[] args) {
- List<Cat> catList = new ArrayList<>();
- for(int i=0; i<5; i++) {
- catList.add(new Cat());
- }
- ListIterator<Cat> it = catList.listIterator();
- System.out.println("CatNo.\t nextIndex\t previousIndex");
- // 正向遍历
- System.out.println("正向遍历:");
- while (it.hasNext()) {
- Cat cat = it.next();
- System.out.println(cat+"\t\t"+it.nextIndex()+"\t\t"+it.previousIndex());
- }
- System.out.println();
- System.out.println("当迭代器游标处于最后一个元素末尾时:");
- ListIterator<Cat> it2 = catList.listIterator();
- while (it2.hasNext()) {
- Cat cat = it2.next();
- System.out.println(cat+"\t\t"+it.nextIndex()+"\t\t"+it.previousIndex());
- }
- System.out.println();
- // 反向遍历
- System.out.println("反向遍历");
- while(it.hasPrevious()) {
- Cat cat = it.previous();
- System.out.println(cat+"\t\t"+it.nextIndex()+"\t\t"+it.previousIndex());
- }
- System.out.println();
- // 产生指定游标位置的迭代器 从第二个位置开始向前替换列表中的 Cat 对象
- System.out.println("从第二个位置开始向前替换列表中的 Cat 对象");
- it = catList.listIterator(2);
- while(it.hasNext()) {
- it.next();
- it.set(new Cat());
- }
- System.out.println(catList);
- }
- }
- /*
- CatNo. nextIndex previousIndex
- 正向遍历:
- Cat: 0 1 0
- Cat: 1 2 1
- Cat: 2 3 2
- Cat: 3 4 3
- Cat: 4 5 4
- 当迭代器游标处于最后一个元素末尾时:
- Cat: 0 5 4
- Cat: 1 5 4
- Cat: 2 5 4
- Cat: 3 5 4
- Cat: 4 5 4
- 反向遍历
- Cat: 4 4 3
- Cat: 3 3 2
- Cat: 2 2 1
- Cat: 1 1 0
- Cat: 0 0 -1
- 从第二个位置开始向前替换列表中的 Cat 对象
- [Cat: 0, Cat: 1, Cat: 5, Cat: 6, Cat: 7]
- */
foreach 与迭代器
foreach 语法不仅可以用在数组, 也可以用在任何 Collection 对象. 之所以可以用在 Collection 对象, 是因为 Java SE5 引入了 Iterable 接口, 该接口包含一个能够产生 Iterator 的 iterator()方法, 并且 Iterable 接口被 foreach 用来在序列中移动. 因此, 如果创建了任何实现 Iterable 的类, 都可以将它用于 foreach 当中. 需要注意, 数组虽然可以使用 foreach 语法遍历, 但不意味着数组是 Iterable 的.
实现一个可迭代的类, 使用 foreach 方法遍历
- public class IterableClass implements Iterable<String>{
- private String[] words = ("This is happy day.").split(" ");
- @Override
- public Iterator<String> iterator() {
- return new Iterator<String>() {
- private int index = 0;
- // 判断是否存在下一个元素
- public boolean hasNext() {
- return index < words.length;
- }
- // 返回下一个元素
- public String next() {
- return words[index++];
- }
- public void remove() { //remove 可以不用实现
- throw new UnsupportedOperationException();
- }
- };
- }
- public static void main(String[] args) {
- //foreach 语法遍历实现了 Iterable 接口的类
- for(String s : new IterableClass()) {
- System.out.println(s);
- }
- }
- }
- /*
- This
- is
- happy
- day.
- */
小结
对 Java 容器类库做了大致的介绍, 具体的容器使用方法以及实现会在后面的博客中继续介绍. 本文重点介绍了 Iterator, 它统一了对容器的访问方式, 但是仍有一点心存疑惑: foreach 语法可以遍历容器是因为容器实现了 Iterable 的原因, 但是也可以遍历数组, 数组并不是 Iterable 的. 那么 foreach 可以遍历数组的依据是什么呢? 这个问题暂时还没有看到合适的解答, 各位看官若有想法可留言告知, 感激不尽!
参考:
Java 集合系列目录(Catedory): https://www.cnblogs.com/skywang12345/p/3323085.html
《Java 编程思想》第四版
来源: https://www.cnblogs.com/myworld7/p/10456821.html