数据结构与集合(二) --- 集合框架图

java中的集合时用于存储对象的工具类容器,它实现了常用的数据结构,提供了一系列公开的方法用于增加, 删除, 修改, 查找和遍历数据, 降低了日常开发成本.

集合的种类非常多, 形成了一个比较经典的继承关系树, 称为Java 集合框架图, 如图所示:

框架图中主要分为两类: 第一类是按照单个元素存储的Collection,在继承树中Set 和List 都实现了 Collection 接口; 第二类就是按照Key-Value 存储的Map .

在集合框架中, 红色代表接口, 蓝色代表抽象类,绿色代表并发包中的类, 灰色代表早期线程安全的类(基本已经弃用). 可以看到, 与Collection 相关的4条线分别是List , Queue, Set, Map, 他们的子类会映射到数据结构中的表, 树, 哈希等.

List集合

List集合时线性数据结构的主要实现, 集合元素通常存在明确的上一个和下一个元素, 也存在明确的第一个元素和最后一个元素. List集合的遍历结果是稳定的. 该体系最常用的是 ArrayList 和LinkedList 两个集合类.

ArrayList 是容量可以改变的非线程安全集合, 内部实现使用数组进行存储, 集合扩容时会创建更大的数组空间, 把原有数据复制到新数组中, ArrayList 支持对元素的快速随机访问, 但是插入与删除时速度通常很慢, 因为这个过程很有可能需要移动其他元素.

LinkedList 的本质是双向链表. 与ArrayList 相比, LinkedList的插入和删除速度更快, 但是随机访问速度则很慢. 除继承 AbstractList 抽象类外, LinkedList 还实现了另一个接口 Deque, 即 double-ended queue。 这个接口同时具有队列和栈的性质。 LinkedList 包含3 个重要的成员： size、 first、last。size是双向链表中节点的个数。 first和last 分别指向第一个和最后一个节点的引用。 LinkedList 的优点在于可以将零散的内存单元通过附加引用的方式关联起来， 形成按链路顺序查找的线性结构 ， 内存利用率较高。

Queue 集合

Queue （队列）是一种先进先出的数据结构， 队列是一种特殊的线性表， 它只允许在表的一端进行获取操作，在表的另一端进行插入操作。 当队列中没有元素时， 称为空队列。 自从BlockingQueue （阻塞队列）问世以来，队列的地位得到了极大的提升，在各种高并发编程场景中， 由于其本身FIFO 的特性和阻塞操作的特点， 经常被作为Buffer（数据缓冲区）使用。

Map 集合

Map 集合是以Key-Value 键值对作为存储实现的哈希结构， Key 按某种哈希函数计算后是唯一的，Value 则是可以重复的，Map类提供三种 Collection 视图，在集合框架图中，Map 指向Collection 的箭头仅表示两个类之间的依赖关系。 可以使用keySet（）查看所有的Key， 使用value（）查看所有的Value， 使用entrySet（）查看所有的键值对。 HashMap ，线程是不安全的，ConcurrentHashMap 是线程安全的, 优先推荐使用 ConcurrentHashMap, 而不是HashMap。 TreeMap是 Key 有序的Map 类集合。

Set 集合

Set 是不允许出现重复元素的集合类型。 Set 体系最常用的是 HashSet、TreeSet 和 LinkedHashSet 三个集合类。hashSet 从源码分析是使用 HashMap 来实现的，只是Value 固定为一个静态对象，使用 Key 保证集合元素的唯一性，但它不保证集合元素的顺序。TreeSet 也是如此，从源码分析是使用TreeMap 来实现的， 底层为树结构，在添加新元素到集合中时，按照某种比较规则将其插入合适的位置，保证插入后的集合仍然是有序的。LinkedHashSet 继承自HashSet，具有HashSet 的优点，内部使用链表维护了元素插入顺序。