Java集合(容器)框架 00 - 概括

前言

关于Java集合框架(Java Collections Framework, JCF)的资料较于C++的STL少之甚少，JCF的设计参考了STL，但其定位不是Java版的STL，而是要实现一个精简紧凑的集合框架，STL的教程/资料不能替代对JCK。

以下笔者阅读《Java编程思想》第11章和第17章，以及网上的参考资料(见参考资料)，梳理、深入理解Java集合框架。

容器，就是可以容纳其他Java对象的对象。Java Collections Framework（JCF）为Java开发者提供了通用的容器，其始于JDK 1.2，优点是:

• 降低编程难度
• 提高程序性能
• 提高API间的互操作性
• 降低学习难度
• 降低设计和实现相关API的难度
• 增加程序的重用性

在Java 2之前，Java是没有完整的集合框架的。它只有一些简单的可以自扩展的容器类，比如Vector，Stack，Hashtable等。这些容器类在使用的过程中由于效率问题饱受诟病，因此在Java 2中，Java设计者们进行了大刀阔斧的整改，重新设计，于是就有了现在的集合框架。需要注意的是，之前的那些容器类库并没有被弃用而是进行了保留，主要是为了向下兼容的目的，但我们在平时使用中还是应该尽量少用。

正文

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

集合接口

集合接口

Map接口没有继承自Collection接口，因为Map表示的是关联式容器而不是集合。但Java为我们提供了从Map转换到Collection的方法，可以方便的将Map切换到集合视图。 上图中提供了Queue接口，却没有Stack，这是因为Stack的功能已被JDK 1.6引入的Deque取代。

集合实现

上述接口的通用实现见下表：

集合实现

Collection

1. List: 存储一组不唯一(可以有多个元素引用相同的对象)，有序的对象。

• ArrayList: Object数组，基于动态数组实现，支持随机访问。
• Vector: Object数组，它是线程安全的。
• LinkedList: 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环) ，只能顺序访问，但是可以快速地在链表中间插入和删除元素。

2. Set: 不允许重复的集合。不会有多个元素引用相同的对象。

• HashSet(无序，唯一): 基于HashMap实现的，底层采用HashMap来保存元素，支持快速查找，但不支持有序性操作。
• LinkedHashSet: LinkedHashSet继承与HashSet，并且其内部是通过LinkedHashMap来实现的，具有HashSet的查找效率，且内部使用双向链表维护元素的插入顺序。
• TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如HashSet，HashSet查找的时间复杂度为O(1)，TreeSet则为 O(logN)。

3. Queue: 先进先出(FIFO)的容器

• LinkedList: 实现了Queue接口，提供了方法以支持队列的行为。
• PriorityQueue: 基于堆结构实现，可以用它来实现优先队列。

Map

使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

• HashMap: JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap: LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• HashTable: 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
• TreeMap: 红黑树（自平衡的排序二叉树）

集合的选用方式: 主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用Map接口下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时，就选择实现Collection接口的集合，需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet，不需要就选择实现List接口的比如ArrayList或LinkedList，然后再根据实现这些接口的集合的特点来选用。

课后作业

• List, Set, Map三者的区别?

参考文献:

• Eckel B. Java 编程思想 [M]. 机械工业出版社, 2002.
• Collections Framework Overview
• 【Java学习+面试指南】 一份涵盖大部分Java程序员所需要掌握的核心知识
• 深入理解Java集合框架