Java 容器

一、概览

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

Collection单列集合


1. Set

  • TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

  • HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

  • LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

2. List

  • ArrayList：基于动态数组实现，支持随机访问。

  • Vector：和 ArrayList 类似，但它是线程安全的。

  • LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

3. Queue & Deque

  • ArrayDeque：基于数组实现，和 ArrayList 类似，但是 ArrayDeque 不支持随机访问。

  • LinkedList：可以用它来实现双向队列。

  • PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

Map双列映射


  • TreeMap：基于红黑树实现。

  • HashMap：基于哈希表实现。

  • HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。

  • LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

二、容器中的设计模式

迭代器模式


Collection 继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

1
2
3
4
5
6
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

适配器模式

java.util.Arrays#asList() 可以把数组类型转换为 List 类型。

1
2
@SafeVarargs
public static <T> List<T> asList(T... a)

应该注意的是 asList() 的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组。

1
2
Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);

也可以使用以下方式调用 asList()：

1
List list = Arrays.asList(1, 2, 3);

集合框架总览

数据结构分为

  • 线性数据结构
  • 树型数据结构
  • 图型数据结构

C++中的容器分为（都是线性的）

  • 顺序容器
    • array 数组
    • vector向量
    • list 链表
  • 关联容器
    • map 映射
    • set 集合
  • 容器适配器
    • stack 栈
    • queue 队列

Java中的集合容器分为单列集合collection和双列映射Map。除了一下基本集合类型，还有多个特殊的类型，后续补充

  • List
    • Arraylist，有序，插入序
    • vector
    • stack
  • Queue
    • linkedlist，双端队列有序，插入序
    • arrayqueue，有序，插入序
    • priorityQueue，有序，自然序
  • Set
    • hashset，无序
    • linkedhashset，有序，插入序
    • treeSet，有序，自然序
  • Map
    • hashmap，无序
    • linkedhashmap，有序，插入序
    • treemap 有序，自然序

  1. 集合框架提供了两个遍历接口：Iterator和ListIterator，其中后者是前者的优化版，支持在任意一个位置进行前后双向遍历。注意图中的Collection应当继承的是Iterable而不是Iterator，后面会解释Iterable和Iterator的区别
  2. 整个集合框架分为两个门派（类型）：Collection和Map，前者是一个容器，存储一系列的对象；后者是键值对<key, value>，存储一系列的键值对
  3. 在集合框架体系下，衍生出四种具体的集合类型：Map、Set、List、Queue
  4. Map存储<key,value>键值对，查找元素时通过key查找value
  5. Set内部存储一系列不可重复的对象，且是一个无序集合，对象排列顺序不一
  6. List内部存储一系列可重复的对象，是一个有序集合，对象按插入顺序排列
  7. Queue是一个队列容器，其特性与List相同，但只能从队头和队尾操作元素
  8. JDK 为集合的各种操作提供了两个工具类Collections和Arrays，之后会讲解工具类的常用方法
  9. 四种抽象集合类型内部也会衍生出许多具有不同特性的集合类，不同场景下择优使用，没有最佳的集合

集合概要对比

章节结束各集合总结：（以 JDK1.8 为例）

数据类型 插入、删除时间复杂度 查询时间复杂度 底层数据结构 是否线程安全
Vector O(N) O(1) 数组 是（已淘汰）
ArrayList O(N) O(1) 数组 否
LinkedList O(1) O(N) 双向链表 否（已淘汰）
HashSet O(1) O(1) 数组+链表+红黑树 否
TreeSet O(logN) O(logN) 红黑树 否
LinkedHashSet O(1) O(1)~O(N) 数组 + 链表 + 红黑树 否
ArrayDeque O(N) O(1) 数组 否
PriorityQueue O(logN) O(logN) 堆（数组实现） 否
HashMap O(1) ~ O(N) O(1) ~ O(N) 数组+链表+红黑树 否
TreeMap O(logN) O(logN) 数组+红黑树 否
HashTable O(1) / O(N) O(1) / O(N) 数组+链表 是（已淘汰）

参考资料