本章将简单介绍一下常用的集合类的特点，同时并不会深入源码分析原理，本文目的仅仅在于对 Java 集合类有一个整体认识

关于 API，本文不涉及过多，建议直接查看 Java 官方文档

https://docs.oracle.com/javase/9/docs/api/overview-summary.html

---

1. 容器概述

1.1 引入原因

Java 中，数组用来保存一组对象，但是数组具有固定的尺寸。于是为了解决数组长度固定，无法应对对象数量未知的情况，引入容器/集合类。

容器用途就是保存对象。

1.2 容器层级

容器有两大山脉：Collection 和 Map，其层次关系大致如下。

先来个基础的：

img

https://www.cnblogs.com/LipeiNet/p/5888513.html

再来个复杂一点的：

img

图摘自 http://www.cnblogs.com/leeplogs/p/5891861.html

其中：

• Collection 接口是集合类的根接口，本身没有实现类。
• Map 是容器的另一个根接口，与 Collection 相互独立
• Iterator 是所有容器都实现的接口，用于遍历容器中元素。
• 另外 Collections 和 Arrays 是 Object 的直接子类，其中包含了一系列关于 容器 和 数组 的静态方法

1.3 类型安全

通过 泛型 指定参数类型，即指定这个容器实例可以保存的类型。通过使用泛型，可以在编译期防止将错误类型的对象放置到容器中。

保证 类型安全 仅仅是 Java 泛型的其中一个作用。后续我们会学习更多关于 泛型的知识（剧透一下，很复杂）

举个例子：

List<String> list = new ArrayList<String>();

//先不用管 List 和 ArrayList 是啥，就先当作是一个集合就好
//通过指定泛型为 String，那么这个集合就是用来存放 String 类型的，放入其他类型的东西都会出错。

2. Collection

Collection 是一个接口，它下面的 List，Set，Queue 同样也都是接口。

一个独立元素的序列，这些元素都服从一条或多条规则。其中 List 必须按照插入的顺序保存元素；Set 不能有重复元素；Queue 按照排队规则来确定对象的产生顺序（通常与插入顺序相同）

2.1 List

List 是一个接口，它承诺可以将元素维护在特定的序列中。List 接口在 Collection 的基础上添加大量的方法，使得可以在 List 中间插入和移除元素。

• 有序
• 元素可重复

下面主要介绍 两种 List ：ArrayList 和 LinkedList。

2.1.1 ArrayList

优点在于随机访问元素快，但是在中间插入和移除比较慢

原因是 ArrayList 底层是用数组实现的，这也是为什么读取时和数组效率相同，时间复杂度都是1.

2.1.2 LinkedList

优点是善于在中间插入和移除元素，提供了优化的顺序访问，相反缺点是随机访问较慢

原因是底层是使用链式存储

同时，LinkedList 可以实现比 ArrayList 更多的功能特性：LinkedList 支持栈、队列和双端队列。

2.1.3 Stack

Stack（栈）通常指 “后进先出”（LIFO）的容器，最后一个压入栈的元素，第一个弹出栈。

可以想象为弹簧，最先放上弹簧的被放在最下面，后放上去的在上面，每次弹出来一个时，上面的（后放的）先被弹出。

Stack 是通过 LinkedList 实现的。

Stack 继承自 Vector，而 Vector 已被弃用。

2.2 Set

Set 也是一个集合，但是它不保存重复的元素。

Set 具有和 Collection 完全一样的接口，因此没有任何额外的功能，实际上 Set 就是 Collection，只不过行为不同。

继承与多态思想的应用：表现不同的行为

下面简单介绍两个实现类：HashSet 和 TreeSet

2.2.1 HashSet

• 查询速度块。HashSet 使用了散列，散列的价值在于速度 -- 散列使得查询更加快速

• 存储无序

  HashSet 底层使用散列函数

2.2.2 TreeSet

• 存储有序

  TreeSet 将元素存储在红黑树中，因此存储结果有序。

2.2.3 LinkedHashSet

• 存储有序

  通过链表保存添加的顺序

2.3 Queue

Queue （队列）是典型的 先进先出 的容器，即从一端放入事物，从另一端取出，且元素放入容器的顺序和取出的顺序是相同的。

可以想象一个传送带，先放上传送带的物品会首先到达。

同时 Queue 中允许重复元素。

LinkedList 实现了 Queue 接口，因此 LinkedList 可以用作 Queue 的一种实现（将LinkedList 可以向上转型为 Queue）。

相关方法介绍：

方法	作用	说明
add、offer	将元素插入队尾	队列容量已满时<br />add 会抛出异常<br />offer会返回 false
element、peek	返回对头元素（不删除）	队列为空时<br />emelent 会抛出异常<br />peek会返回 null
remove、poll	返回对头元素，并将该元素从队列移除	队列为空时<br />remove 会抛出异常<br />poll 会返回 null

2.3.1 PriorityQueue

• 先入先出描述的是下一个元素应该是等待时间最长的元素

• PriorityQueue（优先级队列）描述的是下一个元素应该是优先级最高的元素。

当我们在 PriorityQueue 上调用 offer() 插入元素的时候，这个元素会在队列中自动被排序，默认情况是自然排序。当然我们可以通过自定义 Comparator 来修改这个顺序。

PriorityQueue 保证我们调用 peek、poll 等方法时，返回的是队列中优先级最高的元素。

---

3. Map

Map 就是一组成对的 “键值对” 对象，允许使用键来查找值。Map 可以将对象映射到其他对象上，在实际开发中使用非常广。

主要方法介绍：

方法	用途
put	添加键值对元素
get	返回与键对应的值
containsKey	查询是否包含某个键
containsValue	查询是否包含某个值
keySet	返回键的 set
entrySet	返回键值对的 set
values	返回值的 collection

3.1 HashMap

• 查询速度很快

• 存储无序

  原因在于，底层使用了 散列函数

• 键可以是 null，键值不可重复（重复会覆盖旧的）

3.2 TreeMap

• 按照比较结果的升序保存键

  红黑树存储

3.3 LinkedHashMap

• 按照插入顺序保存键

• 保留了 HashMap 的查询速度

  底层使用了散列函数 ，同时用一个链表保存插入顺序。

---

4. 迭代器

4.1 概念

Java 中的迭代器（Iterator）：

• 是一个轻量级对象：创建代价小
• 工作是遍历并选择序列中的对象，不关注容器中元素的数量
• 只能单向移动

4.2 用处：

• 使用方法 iterator() 要求容器返回一个 Iterator，此时 Iterator 将准备好返回第一个元素
• 使用 next() 获得序列下一个元素
• 使用 hasNext() 检查序列中是否还有元素
• 使用 remove() 将迭代器最近返回的元素删除

4.3 ListIterator

ListIterator 是 Iterator 的子类型，只能用于各种 List 类的访问。

ListIterator 可以双向移动，它可以产生相对于迭代器在列表中指向的当前位置的前一个（previous()方法）和后一个元素的索引（next() 方法）。

4.4 Iterator 与 foreach

foreach 除了可以作用于数组，还可以应用于所有的 Collection 对象。这是因为 Collection 继承了 Iterable 的接口。该接口包含一个能够产生 iterator 的 iterator() 对象，并且 Iterable 接口被 foreach 用来在序列中移动。

public class IterableClass implements Iterable<String> {
    protected String[] words=("Hello Java").split(" ");
    
    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() {
            }
        };
    }
    public static void main(String[] args){
        for(String s : new iterableClass())
            System.out.println(s + "");
    }
}

//输出：
//Hello Java

---

5. Collections 和 Arrays

Collections 和 Arrays 都是 Object 的直接子类，里面封装了一系列关于集合和数组的静态方法。

部分方法如下：

• Collections.addAll()：用于将一些列元素加入到 Collection

  public static <T> boolean addAll(Collection<? super T> c, T... elements)

• Arrays.asList()：将数组（可变参数列表）写入到一个列表，并将该列表返回

  public static <T> List<T> asList(T... a)

  底层表示为数组，因此不能修改尺寸。如果调用add() 或 delete()，有可能改变数组尺寸，因此会报错。

• Arrays.toString()：产生数组的可打印表示。

---

总结

Java 提供大量持有对象的方式：

1. 数组是将数字和对象联系起来，它保存明确的对象，查询对象时候不需要对查询结果进行转换，它可以是多维的，可以保存基本类型的数据，但是数组一旦生成，其容量不能改变。所以数组是不可以直接删除和添加元素。
2. Collection 保存单一的元素，而 Map 保存相关联的值键对，有了 Java 泛型，可以指定容器存放对象类型，不会将错误类型的对象放在容器中，取元素时候也不需要转型。而且 Collection 和 Map 都可以自动调整其尺寸。容器不可以持有基本类型。
3. 像数组一样，List 也建立数字索引和对象的关联，因此，数组和 List 都是排好序的容器，List 可以自动扩容
4. 如果需要大量的随机访问就要使用 ArrayList，如果要经常从中间插入和删除就要使用 LinkedList。
5. 各种 Queue 和 Stack 由 LinkedList 支持
6. Map 是一种将对象（而非数字）与对象相关联的设计。HashMap 用于快速访问，TreeMap 保持键始终处于排序状态，所以不如 HashMap 快，而 LinkedHashMap 保持元素插入的顺序，但是也通过散列提供了快速访问的能力
7. Set 不接受重复的元素，HashSet 提供最快的访问能力，TreeSet 保持元素排序状态，LinkedHashSet 以插入顺序保存元素。
8. 不应使用过时的 Vector、HashTable

回顾一下开篇的简图：

不包含抽象类和遗留构件

可以发现其实只有四种容器 -- List、Set、Queue、Map。常用的用红色标出，绿色标识接口，其他标识普通的类。

使用时需要注意容器类之间方法的独立性：有些相同，而有些相差很远。

上述即为本章的全部，共勉。