Java容器框架（一）--概述篇

1. 概述

在Java开发中，我们经常使用到一些容器类例如ArrayList、HashMap等，很少去了解其他一些容器类或者说对Java容器有一个整体的了解。于是趁此闲暇之际，对Java容器进行一个整体的描述，一方面是为了对Java容器能有一个整体的思维，另一方面也是为了在平常工作中能够通过不同的场景对容器类的使用做到游刃有余。

我们知道Java容器类基本上都是在java.util包下，有一个Collection接口，它是Java容器的顶级接口（除了Map），在编辑器中打开Collection接口，然后快捷键（IDEA默认是Ctrl+h）查看该接口的实现类，可以看到在util包下有List、Set和Queue三大接口，Java容器中大部分类都实现了这三大接口中的一个或多个，容器中除了这三大接口，当然还有另一个重要的接口了即Map。因此Java容器的最顶层结构如下图：

下面我会对这四大接口及下面的子类做一个详细的介绍，在介绍之前，允许我借用网上一张图片，能够对容器类有一个大致的轮廓（图中暂时缺少map系列，在介绍map的时候会给对应的类图）。

2. List集合

List集合，通过名字大概能够猜测到它是一个线性结构的列表，学过数据结构都知道线性表有两种存储方式即顺序存储（数组）和链式存储（链表），其实List集合正式这种线性结构集合的实现，List集合它是一个存放可重复、无序（不会对存放的数据进行排序）的线性结构数据集合。

通过同样的方法在编辑器中打开List接口，查看其实现类，可以看到大致有如下实现类：AbstractList、ArrayList、Vector、LinkedList、CopyOnWriteArrayList（多线程中）。List容器类结构图大致如下：

那么问题来了，List容器这些子类都有些什么作用呢？

此处只是简单介绍List子类的一些作用或实现原理，并不从源码角度进行分析，在之后的文章中会对部分子类进行源码分析。

• AbstractList

看类名就能过猜测到该类为一个抽象类，它继承自AbstractCollection类实现了List接口，是 ArrayList 和 AbstractSequentiaList 的父类。内部实现了List的部分方法，同时也提供了Iterator, ListIterator 迭代器的实现类，分别为 Itr, ListItr。ListItr继承自Itr，从某种角度可以视为Itr的扩展。详情可以参见Java 集合深入理解（6）：AbstractList

• ArrayList

该类相信大家再熟悉不过，继承自AbstractList抽象类，实现List、RandomAccess等接口，内部是由数组实现，容量大小不固定，元素的顺序和存放的顺序一致，遍历元素可以通过随机读写（RandomAccess）和迭代器（Iterator）两种方式，由于数组的特性，当然RandomAccess方式要由于Iterator。

• LinkedList

在List家族，除了对ArrayList非常熟悉之外，估计就到LinkedList了。LinkedList基于双向链表实现，非常适用于数据插入和删除，对数据遍历较慢，和ArrayList恰好相反。

• Vector

Vector 和 ArrayList 一样，也是基于数组来实现，区别是Vector是线程安全的，通过源码可以看到Vector很多方法都是使用synchronized来修饰。

• Stack

通过类名可以知道该类实现了栈的功能，Stack继承自Vector，因此也是由数组来实现，并且线程安全。

• CopyOnWriteArrayList

该类是并发容器（java.util.concurrent）中的类，它的原理是当我们向容器中添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样的意义主要在于当并发读取容器内容时不需要加锁，但是写内容的时候需要保证同步并且需要开辟新的内存空间，因此比较适合读多写少的并发场景。

3. Set集合

什么是Set集合，它有什么特性？

先来看看代码中的英文说明：

A collection that contains no duplicate elements. More formally, sets contain no pair of elements <code>e1</code> and e2 such that  e1.equals(e2), and at most one null element.

大概意思就是：该集合中存放一些不能重复的元素。正式一点来说，就是不能存在这样一对元素（例如：e1.equals(e2)返回为true），并且容器中最对可以有一个为null的元素。

Set集合下的类大致有：SortedSet（接口）、AbstractSet（抽象类）、HashSet、LinkedHashSet、NavigableSet（接口）、TreeSet等等，如下图所示：

我们一起来了解了解这些接口或类所具有的作用。

• AbstractSet

AbstractSet之余Set很类似于AbstractList之余List，主要起着一个骨架的作用，它继承AbstractCollection，实现Set接口，它其实仅仅只实现了equals、hasCode、removeAll三个方法。

• HashSet

我们首先看看类结构：

public class HashSet<E>  extends  AbstractSet<E>  implements  Set<E>, Cloneable, java.io.Serializable

继承自AbstractSet，实现了Set接口，它内部代码并不多，使用HashMap来存储数据。当对HashSet添加一个元素E时，其实就是向HashMap中添加一个键值对，键就是E，值为一个通用的Object对象，这也就很能理解HashSet不能存放相同元素的原因了吧，同时也可以 知道访问的顺序和插入的顺序有可能是不一样的。

• LinkedHashSet

类结构如下：

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet继承自HashSet，调用的构造器其实就是HashSet的构造器，只不过它是用LinkedHashMap来存储数据，因此它的特性和LinkedHashMap很相似，可以保证遍历顺序序和插入顺序序一致。

• SortedSet&NavigableSet

Set容器本身没有排序能力，当类实现了SortedSet或NavigableSet接口，则提供了排序方案。

• TreeSet

TreeSet类结构如下：

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable

实现了NavigableSet，由于NavigableSet继承自SortedSet，因此TreeSet具有排序的功能。TreeSet内部使用NavigableMap来存放数据，默认情况下，是使用TreeMap来保存数据，因此它的特性和TreeMap的特性是很类似的。

通过对Set集合的了解，我们发现Set的子类与Map的子类有这千丝万缕的关系，要知道Set子类的实现原理必当先了解Map子类的实现原理，下面我们来大概了解下Map家族。

4. Map集合

先一言不合来张Map类图：

看看函数的命名，有没有发现与Set里面很相似（当然我更加相信是Set是参考Map），下面对Map家族稍作了解。

• Map：键值对映射的接口，该映射不包括重复的键，一个键对应一个值。
• SortedMap：有序的键值对接口，继承Map接口。
• NavigableMap：继承SortedMap，具有针对给定搜索目标返回最接近匹配项的导航方法的接口。
• AbstractMap：实现了Map中的绝大部分函数接口，它减少了Map的实现类的重复编码。
• TreeMap： 有序散列表，实现SortedMap 接口，底层通过红黑树实现。
• Dictionary：任何可将键映射到相应值的类的抽象父类。
• HashTable： 基于“拉链法”实现的散列表，多线程安全，大部分方法都是使用synchronized修饰的。
• HashMap： 是基于“拉链法”实现的散列表，底层采用“数组+链表”实现。
• LinkedHashMap： HashMap无法保证数据的存与取顺序一致，LinkedHashMap正式弥补了这样的缺点，内部通过维护一条双向循环链表来保证数据的插入和访问顺序。
• WeakHashMap：基于“拉链法”实现的散列表，和HashMap不同的是它保存的键都是弱键，也就是说映射的存在并不阻止对键进行垃圾回收，键没有值自然也丢弃。
• ConcurrentHashMap：该类是在java.util.concurrent包中，主要是考虑多线程安全的情况，我们都知道HashMap多线程是不安全的，而HashTable虽然多线程安全但是效率太低，于是就出现了ConcurrentHashMap。它是采用锁分段技术保证线程安全。

到这里，Map家族基本上介绍完了，回头一看，发现还有一个家族没有分析，那就是Queue家族，常规操作，仍然来看看Queue家族的成员。

5. Queue集合

Queue即队列，所谓队列就是一个先入先出（FIFO）的数据结构，它也是一个线性表，只不过在队列的尾部插入数据，头部删除数据，Queue家族体系如下图所示：

• Deque

Deque是Queue的子接口，Queue是队列，Deque它是一个双向队列，也就是说它支持从两端删除或插入元素。它下面的实现类主要有ArrayDeque和LinkedList以及concurrent包下的ConcurrentLinkedDeque，ArrayDeque看类名想必大家就能知道一个基于数组实现，LinkedList前面有介绍基于链表实现。ConcurrentLinkedDeque是Java7中引入的，实现了非阻塞式并发列表，它内部的链表节点都声明为volatile类型来保证数据一致性。

• BlockingQueue

它类结构如下：public interface BlockingQueue<E> extends Queue<E>，类图中没有将其包含，可以视为阻塞队列，用户可以为该队列设置一个初始容量（即该队列中最多能够放入多少个数据）。当BlockingQueue为空时，获取元素线程被阻塞直到BlockingQueue变为非空；当BlockingQueue满时，添加元素线程被阻塞直到Queue不满。它下面的主要实现类有ArrayBlockingQueue、LinkedBlockingQueue等。

总结

至此，Java容器内容大致介绍完成，Java容器大致可以分为四大家族，有些家族之间紧密相连。List家族即线性表，它的子类有通过数组来实现的顺序表及通过链式结构来实现的链表两种类型；Queue家族即队列，也属于一种操作受限的线性表，支持先进先出原则，当然也有子类实现了两端都支持删除和插入元素的功能；Map家族即键值对，支持key-value的形式存放数据；Set家族它子类中大部分都是通过Map家族中的类来完成，Set中存放的值作为Map中的key，实例化一个全局的Object对象作为所有key的值，无非就是能够通过Map来存放单个数据的能力。以上仅为个人见解，如有理解错误的地方，欢迎指正。

参考文献

https://blog.csdn.net/u011240877/article/details/52834074

https://blog.csdn.net/qq_33642117/article/details/52040345

https://blog.csdn.net/jeffleo/article/details/55000077

https://www.cnblogs.com/zaizhoumo/p/7786793.html