Java 容器

🧐 为什么要用容器？

容器（即持有对象）是Java中的一种基本编程工具，它可以弥补普通数组的两个缺陷：

  1. 大小固定：容器可以自动扩容。
  2. 类型固定：如果不用尖括号指定类型，其实可以在一个容器里边同时存放不同的类型。
@SuppressWarnings("unchecked")	// 添加注解以消除警告⚠️
public static void main(String[] args){
	ArrayList apples=new ArrayList();	// 没有用尖括号指定容器存放什么类型的元素
	for(int i=0;i<3;i++){
		apples.add(new Apple());	// 编译器会警告：使用了未经检查或不安全的操作⚠️
	}
	apples.add(new Orange());
	for (int i=0;i<apples.size();i++){
        // 如果容器没有指定类型，那么get方法返回的对象是Object类型，因此需要强制类型转换
		System.out.println(((Apple)apples.get(i)).id());
        // ❎当执行到orange时，虚拟机会抛出ClassCastException的异常，提示Orange不能强制转换为Apple
	}
}

🤨 有哪些容器？

image-20181126213800872

Java中的主要容器包括Collection和Map两类（Hashtable基本上可以说是弃用了deprecated），Collection用于存放一个个独立的对象，而Map用于存放两个对象组成的键值对(Key-Value)。平时所见的链表、栈、队列都属于Collection，而所谓的散列表就属于Map。

💊 Collection

image-20181126211002965

如上所示为Collection的UML类图，惊奇的发现，与C++不同，我们常见的一些数据结构Set(集合)、List(列表)、Queue(队列)居然不是类，而是接口（Map也是接口）。各种extends和implements关系错综复杂。

可能是为了实现的方便吧，java中Collection并没有按照我们想象的那样分成集合、列表、堆栈、队列，相互独立，Java中集合相对独立，而堆栈和队列则是使用列表来实现的，Stack继承自AbstractList，而Queue则只是一个接口，使用的时候一般用一个Queue引用来引用一个LinkedList（链表）。

1）Set

set是一种没有重复元素的Collection：a. 接口和Collection一样；b. 没有重复元素。

Java中set有三种常见的实现，他们主要的区别是元素的存储方式不同：

  • HashSet：用的最多的一种Set，使用Hash来保存元素以提高访问速度，因此访问时元素顺序是杂乱的。
  • LinkedHashSet：使用hash来提高访问速度，但是将元素保存在了LinkedList里边，所以元素是按照插入顺序存放的。
  • TreeSet：使用红黑树保存数据，元素是有序排列的。

2）List

List是最常用的容器，一般使用自动扩容的数组或者链表实现。Java中常见的List有：

  • LinkedList：使用链表实现的List，插入和删除元素的效率很高，但是随机访问的效率低；
  • ArrayList：使用数组实现，随机访问的效率很高，但是插入和删除元素的效率低；
  • Vector：和ArrayList一样都是使用数组实现的，与其不同的是Vector是线程安全的，同一时间只能有一个线程对其进行写操作。也正因为有线程安全机制，Vector的效率比ArrayList低，所以如果没有线程安全的需求，一般不用Vector；
  • Stack：继承自Vector，是一种“先入后出（LIFO）”的数据结构，但是，可能是历史原因吧，Stack继承自Vector，所以效率不高，Java官方也推荐有LIFO需求时优先使用ArrayDeque，如：Deque<Integer> stack = new ArrayDeque<Integer>();

3）Queue

**Queue**是一种“先入先出(FIFO)”的容器，如上面的类图所示，Java中的LinkedList实现了Queue接口，因此，Java中一般把LinkedList作为Queue使用（用Queue接口调用LinkedList），即Queue<Integer> queue = new LinkedList<Integer>()。

PriorityQueue即优先队列，是实现了Queue接口的另一个类，普通Queue里边的元素会按照插入顺序来进行FIFO，而Priority中的元素会按照某种优先级来进行FIFO，即优先级高的元素会自动放在队列的头部。默认情况下的优先级会按照数据的值从大到小排列，也可以实现一个自己的Comparator传给PriorityQueue的构造器，从而自定义优先级顺序。

Deque即双向队列，它也是一个接口，继承自Queue，所以可以当做Queue使用，但是他又实现了LIFO的接口：push(e)和pop()等，因此也可以当做Stack使用。实现了Deque接口的类主要有LinkedList和ArrayDeque：

  • 使用FIFO队列：Queue<Integer> queue = new LinkedList<Integer>();
  • 使用LIFO堆栈：Deque<Integer> stack = new ArrayDeque<Integer>();

💣 Map

image-20181126211045494

Map是保存“键值对”的一种数据结构，而在Java中Map是一种接口，而Map具体的实现常见的有三种：HashMap、LinkedHashMap和TreeMap，之间的区别也是存储方式的差异，与Set中的情况类似。

除了以上三种外，Java中的Hashtable也实现了Map接口，Hashtable出现的时间在HashMap之前，目前一般认为Hashtable是一种过时了的类，它和HashMap最大的区别就是Hashtable是线程安全的，所以效率会比HashMap低。Java官方文档也指出，如果没有线程安全的需求，推荐使用HashMap，而如果是在有线程安全需求的高并发应用中，则推荐使用 ConcurrentHashMap。